DEV Community

AoC Day 3: No Matter How You Slice It

Ryan Palo on December 03, 2018

Day three! Our DEV leaderboard is up to 44 people, which is awesome! Also, check out the much classier cover images for these posts that @aspitte...

Read full post

Ali Spittel • Dec 3 '18 • Edited

Solved last night, refactored this morning! Actually pretty proud of this. Python solution:

import re

with open('input.txt', 'r') as f:
    data = []
    for line in f:
        nums = [int(n) for n in re.findall(r'\d+', line)]
        data.append({'id': nums[0], 'coordinates': [nums[1], nums[2]], 'dimensions': [nums[3], nums[4]]})


def get_coordinates(coordinates, dimensions):
    for x in range(dimensions[0]):
        for y in range(dimensions[1]):
            yield str(x + coordinates[0]) + "," + str(y + coordinates[1])


def get_overlaps(data):
    overlaps = set()
    filled = set()
    for line in data:
        for coord in get_coordinates(line['coordinates'], line['dimensions']):
            if coord in filled:
                overlaps.add(coord)
            else:
                filled.add(coord)
    return overlaps


def no_overlaps(coordinates, dimensions, overlaps):
    for coord in get_coordinates(coordinates, dimensions):
        if coord in overlaps: 
            return False
    return True


def find_no_overlaps(data, overlaps):
    for line in data:
        if no_overlaps(line['coordinates'], line['dimensions'], overlaps):
            return line['id']


overlaps = get_overlaps(data)
# Q1
print(len(overlaps))

# Q2
print(find_no_overlaps(data, overlaps))

jess unrein • Dec 3 '18

I love how clean this solution is!

Ali Spittel • Dec 3 '18

Thank you so much -- that means a lot (I've been super sad this morning because somebody was mean about my solution on Twitter).

jess unrein • Dec 3 '18

🙄People can be the worst sometimes. Sorry you had to deal with that.

Tarush Nagpal • Dec 3 '18

If someone still doesn't get how to do it, I put up a pretty simple explaination with the code on my repo And here's the matrix that I got!

Ryan Palo • Dec 3 '18

Cool visual!

Tarush Nagpal • Dec 4 '18

Thanks! Love using p5.js

Jon Bristow • Dec 3 '18 • Edited

Kotlin Solution

UGH! This one seemed like a reversal, the first part was much harder than the second part.

I started out as I always do when pretending to be a video game developer: swearing loudly because my rectangles were overlapping and I forgot that it's way easier to find out if they're not overlapping.

Then I kept trying to optimize, but that wasn't getting me anywhere. I ended up brute-forcing my way through. This is ugly... maybe 25 seconds to chunk through.

Part 1


typealias Point = Pair<Int, Int>

val Point.x get() = first
val Point.y get() = second

private fun String.parseRect(): Rectangle {
    val result = Regex("""#(\d+) @ (\d+),(\d+): (\d+)x(\d+)""").find(this)
    val groups = result!!.groups
    return Rectangle(
        groups[1]!!.value,
        groups[2]!!.value.toInt(),
        groups[3]!!.value.toInt(),
        groups[4]!!.value.toInt(),
        groups[5]!!.value.toInt()
    )
}

class Rectangle(val id: String, val tl: Point, val br: Point) {
    constructor(id: String, x: Int, y: Int, width: Int, height: Int) :
            this(id, x to y, x + width to y + height)
}

private fun Rectangle.overlaps(b: Rectangle) = when {
    this.id == b.id -> false
    b.br.x <= tl.x || b.tl.x >= br.x -> false
    b.br.y <= tl.y || b.tl.y >= br.y -> false
    else -> true
}

fun Rectangle.intersection(b: Rectangle): Set<Point> =
    (max(tl.x, b.tl.x) until min(br.x, b.br.x)).flatMap { x ->
        (max(tl.y, b.tl.y) until min(br.y, b.br.y)).map { y -> x to y }
    }.toSet()

fun answer1(input: List<String>) =
    input
        .cartesian { a, b -> a.parseRect() to b.parseRect() }
        .filter { (a, b) -> a.overlaps(b) }
        .map { (a, b) -> a.intersection(b) }
        .reduce { set, other -> set.union(other) }
        .count()

Part 2

After calming down a little (rectangles are dumb), I set in to work on the second part. This turned out much simpler. It was just another n² with an early escape function. Almost identical to yesterday. The key is making sure our find eliminates candidates as fast as possible. Enter none, which returns false as soon as we see an overlap with our current. Yes, I was lazy and just added a quick "same id == no overlap" check instead of making sure I was checking unique pairs. I'm getting sleepy, and the first one frustrated me more than I would have liked.

fun answer2(input: List<String>) =
    input.asSequence()
        .map(String::parseRect)
        .let { rects ->
            rects.find { a -> rects.none(a::overlaps) }?.id
        }

Ryan Palo • Dec 3 '18

#rectanglesaredumb

Jon Bristow • Dec 3 '18

From my pain, your gain! An image of the overlapping areas plotted.

jess unrein • Dec 3 '18

I totally agree that the second part seemed so much easier that the first. It really threw me off.

Paula Gearon • Dec 4 '18

I initially thought that I should use my data structure from part one to solve part 2, but while figuring it out I realized that a different structure was much more effective. I like to make my functions for the first and second parts independent anyway, so it didn’t bother me to do it again. And it came out much smaller!

jess unrein • Dec 3 '18 • Edited

My messy af Python solutions. If I’m feeling energetic later today I’ll clean these up and write a Golang solution and benchmark the 2 :)

Part 1:

import re

def claims(input):
    c = input.read().splitlines()
    side = 1000
    matrix = [["O" for x in range(side)] for y in range (side)]
    idx = r'\d*(,)\d*'
    dim = r'\d*(x)\d*'
    cl = r'(#)\d*'
    for claim in c:
        claimant = int(re.search(cl, claim).group(0)[1:])
        inidicies = [int(i) for i in re.search(idx, claim).group(0).split(',')]
        dimensions = [int(i) for i in re.search(dim, claim).group(0).split('x')]
        x = inidicies[0]
        y = inidicies[1]
        width = dimensions[0]
        height = dimensions[1]
        for _ in range(height):
            for _ in range(width):
                space = matrix[y][x]
                if space == "O":
                    matrix[y][x] = claimant
                else:
                    matrix[y][x] = "X"
                x += 1
            x = inidicies[0]
            y += 1
        check_overlap = 0
    for x in matrix:
        check_overlap += x.count("X")

    return check_overlap

print(claims(open('input.txt', 'r')))

Part 2

import re

def claims(input):
    c = input.read().splitlines()
    side = 1000
    matrix = [["O" for x in range(side)] for y in range (side)]
    idx = r'\d*(,)\d*'
    dim = r'\d*(x)\d*'
    cl = r'(#)\d*'
    all_ids = set()
    overlap_ids = set()
    for claim in c:
        claimant = int(re.search(cl, claim).group(0)[1:])
        all_ids.add(claimant)
        inidicies = [int(i) for i in re.search(idx, claim).group(0).split(',')]
        dimensions = [int(i) for i in re.search(dim, claim).group(0).split('x')]
        x = inidicies[0]
        y = inidicies[1]
        width = dimensions[0]
        height = dimensions[1]
        for _ in range(height):
            for _ in range(width):
                space = matrix[y][x]
                if space == "O":
                    # first claim to this space
                    matrix[y][x] = claimant
                elif space == 'X':
                    # claim overlaps with existing overlapped claim
                    overlap_ids.add(claimant)
                else:
                    # claim overlaps with exactly one preexisting claim
                    overlap_ids.add(claimant)
                    overlap_ids.add(space)
                    matrix[y][x] = "X"
                x += 1
            x = inidicies[0]
            y += 1
    return all_ids.difference(overlap_ids)

print(claims(open('input.txt', 'r')))

github.com/thejessleigh/aoc18/tree...

Paula Gearon • Dec 3 '18

I saw someone on the Clojurian's Slack talking about AoC day 3, and made the statement "mutable arrays FTW!" This made me think to try using the core.matrix library. I'm always looking for excuses to get better at using that library, since it can give direct GPU access when doing linear algebra.

Part the First

(ns day3
  (:require [clojure.string :refer [split]]
            [clojure.core.matrix :refer :all]))
(set-current-implementation :ndarray)

(defn lines [input-file]
  (split (slurp input-file) #"\n"))

(defn as-long [s] (Long/parseLong s))

(defn destruct [s]
  (let [[all & params] (re-find #"#(\S+) @ (\d+),(\d+): (\d+)x(\d+)" s)]
    (when all (map as-long params))))

(defn star
  [input-file]
  (let [ll (lines input-file)
        field (new-matrix 1000 1000)]
    (loop [[[id col row w h] & xlines] (map destruct ll)]
      (if-not id
        field
        (let [sm (submatrix field row h col w)]
          (emap! #(if (zero? %) id -1) sm)
          (recur xlines))))
    (ereduce + (eq field -1))))

This uses the same lines function as the last 2 days, and as-long is a trivial wrapping of Java interop so I can map it over the numbers found in each line. I could have just mapped an anonymous function, but I just wish Clojure would include as-long/as-double by default, which is why I named it.

My parsing is far more effort than is needed. Someone else pointed out that the regular nature of the input meant that I could just have split the line with: (re-seq #"\d+" s)

I decided to leave mine alone, partly because it's what I came up with, and partly because it's defensive programming. This puzzle is fine, but in the real world my code will one day see a file containing data that breaks simplistic parsing. That's not saying that my code is solid: for instance, I never check if the rectangles are within the 1000x1000 boundaries, but I like to practice at least a little bit of defensive coding.

The loop is destructuring the parse results then iterating until it's done. Then comes the nice part of core.matrix: pulling out a submatrix (the current rectangle) and updating it. The final line uses the nice trick of using eq to represent booleans as 0/1 and adding them. I learnt to count up booleans that way via APL.

Part the Second

(defn star2
  [input-file]
  (let [ll (lines input-file)
        field (new-matrix 1000 1000)]
    (loop [[[id col row w h] & xlines] (map destruct ll) ids #{}]
      (if-not id
        (first ids)
        (let [sm (submatrix field row h col w)
              ids' (ereduce #(if (zero? %2) %1 (disj %1 %2 id)) (conj ids id) sm)]
          (assign! sm id)
          (recur xlines ids'))))))

This part was actually easier, and ran significantly faster!

In an imperative language I would update the elements of the submatrix as I checked for overlaps. I could do that here too, but the code above is just much cleaner.

As it is, it keeps a set of the ids that currently don't overlap. The ereduce step first assumes that the current id won't overlap and adds it to the set. Then it checks if each cell has been written to, and if so it removes from the set the id of that cell, and the id that is being processed right now. Then the assign! updates the whole rectangle with the current id.

I liked using core.matrix here. It forced me to go through the docs to look for useful functions (like eq), and I also learnt some interesting gotchas with the library, which will be valuable to know.

Ryan Palo • Dec 3 '18

Part 1

I really struggled with part 1. Not because I couldn't figure out the problem, or get my code to compile. I had my tests running pretty quickly! But I kept getting the wrong answer! I was on the very precipice of giving up and checking the subreddit when I realized that str.matches(|c| c.is_digit(10)) only finds single digit at a time -- it doesn't build consecutive digits into a single "find." So with input string #1 @ 55,22: 10x10, it was reading this as id: 1, left: 5, top: 5, width: 2, height: 2 and throwing away the rest. 💩

After scratching my head and then bringing in my first external dependency ever in Rust (pretty painless, all things considered) things worked out just fine.

Since the dependency I brought in was just a regex crate, which would be built-in in some languages, I figured that was OK. I wasn't bringing in the find-overlapping-squares crate.

Anyhow, here's part 1:

use regex::Regex;
use std::collections::HashMap;

/// An X, Y grid of Santa's fabric that elves can lay claim to
struct Fabric {
    squares: HashMap<(usize, usize), usize>,
}

/// The data for a rectangular claim an elf makes on a section of fabric
struct Claim {
    id: usize,
    left: usize,
    top: usize,
    width: usize,
    height: usize,
}

impl Fabric {
    fn new() -> Self {
        Self { squares: HashMap::new() }
    }

    /// Increments the amount of claims covering each of the cells inside
    /// the rectangle.
    fn claim(&mut self, claim: &Claim) {
        for x in claim.left..(claim.left + claim.width) {
            for y in claim.top..(claim.top + claim.height) {
                if x > 999 || y > 999 {
                    continue;
                }
                *self.squares.entry((x, y)).or_insert(0) += 1;
            }
        }
    }

    /// Counts how many cells have more than one claim on them
    fn count_conflicts(&self) -> usize {
        self.squares.values().filter(|count| **count >= 2).count()
    }

    /// Counts the total squares claimed
    /// 
    /// A helper function I wrote to help with debugging... #didnthelp
    fn total_squares(&self) -> usize {
        self.squares.iter().count()
    }
}



/// Processes a claim string into an actual Claim
/// 
/// claim string pattern is #<id> @ <left>,<top>: <width>x<height>
/// Since all the numbers are disjoint, we can just match all the 
/// separated numbers in order.
fn process_claim(claim_text: &str) -> Claim {
    // This makes it so we only compile the regex once
    lazy_static! {
        static ref claim_re: Regex = Regex::new(r"#(?P<id>\d+) @ (?P<left>\d+),(?P<top>\d+): (?P<width>\d+)x(?P<height>\d+)").unwrap();
    }

    let claim_parts = claim_re.captures(claim_text).unwrap();
    Claim {
        id: claim_parts["id"].parse().unwrap(),
        left: claim_parts["left"].parse().unwrap(),
        top: claim_parts["top"].parse().unwrap(),
        width: claim_parts["width"].parse().unwrap(),
        height: claim_parts["height"].parse().unwrap(),
    }
}

/// Counts the number of squares with more than one claim on them
pub fn count_conflicting_squares(text: &str) -> usize {
    let mut fabric = Fabric::new();

    for line in text.lines() {
        let claim = process_claim(line);
        fabric.claim(&claim);
    }

    fabric.count_conflicts()
}

Part 2

Actually, for part 1, I didn't even keep track of the ID of the claims -- I just threw that data away! And then I read part two and sat there in sadness for a few minutes.

But!

Then I realized that I wouldn't have to come up with an entirely new approach. I could process the claims like normal, and then re-run through the claims and recheck all of their squares, to see if any have all cells with only one claim on them. Yeah, it doubles the run-time, but O(n) is O(n), even if you double it (sort of). Anyways, I'm pretty happy with today's challenge. Especially my top level functions count_conflicting_squares and find_unconflicting_id: I was able to make them abstract enough that they're pretty easy to read and figure out.

impl Fabric {
    /// Checks whether or not a given claim has any overlapping cells
    fn check_overlap(&self, claim: &Claim) -> bool {
        for x in claim.left..(claim.left + claim.width) {
            for y in claim.top..(claim.top + claim.height) {
                if self.squares.get(&(x, y)) != Some(&1) {
                    return true;
                }
            }
        }
        false
    }
}

/// Finds out if a claim in a group of claims doesn't overlap.  Returns
/// the first one that doesn't.
pub fn find_unconflicting_id(text: &str) -> usize {
    let mut fabric = Fabric::new();
    let mut claims: Vec<Claim> = Vec::new();

    // Load all the claims in
    for line in text.lines() {
        let claim = process_claim(line);
        fabric.claim(&claim);
        claims.push(claim);
    }

    // Check them all for overlaps
    for claim in claims {
        if !fabric.check_overlap(&claim) {
            return claim.id;
        }
    }
    return 0;
}

jess unrein • Dec 3 '18

I made the exact same mistake with my initial attempt, where I was only grabbing the first digit with my regex. I'm glad it wasn't just me 😅I was so frustrated because the test input worked, since each number in the test input was only one digit! Sometimes I wish that AoC gave just a little more test data to work with before grabbing your final input.

Ryan Palo • Dec 3 '18

Yes! The first test input kept passing, and then I wrote like 4 or 5 more tests to check different things, and they all passed! But I never checked double-digit numbers. :|

Shahor • Dec 3 '18

Here goes my Typescript solution:

import Fs from "fs"
import Path from "path"

const input = Fs.readFileSync(Path.join(__dirname, "input.txt"))
    .toString()
    .split("\n")

interface Range {
    start: number
    end: number
}

interface LineProperties {
    id: string
    rows: Range
    columns: Range
}

type ID = string
interface Pixel {
    ids: ID[]
    hasOverlap: boolean
}

type Coordinates = string

let overlaps = 0
const canvas = new Map<Coordinates, Pixel>()
const idsWithOverlappingStatus: Map<string, boolean> = new Map()

function parseLine(line: string): LineProperties {
    const [
        _ = "",
        id = "",
        columnStart = "",
        rowStart = "",
        width = "",
        height = "",
    ] = line.match(/#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/) || []

    return {
        id,
        columns: {
            start: parseInt(columnStart, 10),
            end: parseInt(columnStart, 10) + parseInt(width, 10),
        },
        rows: {
            start: parseInt(rowStart, 10),
            end: parseInt(rowStart, 10) + parseInt(height, 10),
        },
    }
}

input.forEach(line => {
    const lineProperties: LineProperties = parseLine(line)

    idsWithOverlappingStatus.set(lineProperties.id, false)

    for (
        let row = lineProperties.rows.start;
        row < lineProperties.rows.end;
        row++
    ) {
        for (
            let column = lineProperties.columns.start;
            column < lineProperties.columns.end;
            column++
        ) {
            const coordinnates = `${row}x${column}`
            let pixel: Pixel = { ids: [lineProperties.id], hasOverlap: false }

            // not overlapping yet
            if (canvas.has(coordinnates) === false) {
                canvas.set(coordinnates, pixel)
                continue
            }

            pixel = canvas.get(coordinnates) || pixel
            pixel.ids = [...pixel.ids, lineProperties.id]

            canvas.set(coordinnates, pixel)
            // drop it, it has already been counted
            if (pixel.hasOverlap) {
                continue
            }

            overlaps++
            pixel.ids.forEach(id => idsWithOverlappingStatus.set(id, true))
            canvas.set(coordinnates, {
                ...pixel,
                hasOverlap: true,
            })
        }
    }
})

// part 1
console.log(overlaps)

// part 2
for (const [id, overlapping] of idsWithOverlappingStatus) {
    if (overlapping === false) {
        console.log(id)
        break
    }
}

Ian Kirker • Dec 4 '18 • Edited

This seemed like a natural job for Fortran!

Part 1

No, really, it has nice array operation and slicing syntax! I've just stretched out a big array, added 1 everywhere there's a claim, and then counted the number of elements where there's an element greater than 1.

program aoc31
      use ISO_FORTRAN_ENV
      implicit none
      integer, dimension(0:1023,0:1023) :: cloth
      logical, dimension(0:1023,0:1023) :: cloth_mask
      integer :: id, cut_x, cut_y, cut_width, cut_height
      integer :: overlaps
      integer :: io_status

      cloth = 0

      io_status = 0

      do
        read (*,*,iostat=io_status) id, cut_x, cut_y, cut_width, cut_height
        if (io_status /= 0) then
          exit
        end if
        cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1) = &
         cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1) + 1
      end do

      cloth_mask = (cloth > 1)
      overlaps = count(cloth_mask)

      write(*,*) "Overlaps: ", overlaps
end program aoc31

Part 2

Part 2 was trickier, and I had to use a similar solution to @rpalo , going over each claim again; but then I checked whether the sum of the cut elements was the same as its area to determine whether it was a unique claim. I could have done a similar count-based method to part 1, but I thought of this way first.

program aoc32
      use ISO_FORTRAN_ENV
      implicit none
      integer, dimension(0:1023,0:1023) :: cloth
      logical, dimension(0:1023,0:1023) :: cloth_mask
      integer :: id, cut_x, cut_y, cut_width, cut_height
      integer :: overlaps
      integer :: io_status

      cloth = 0

      io_status = 0

      open (unit=5, file="input.simplified")
      do
        read (5,*,iostat=io_status) id, cut_x, cut_y, cut_width, cut_height
        if (io_status /= 0) then
          exit
        end if
        cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1) = &
         cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1) + 1
      end do
      close(5)

      open (unit=5, file="input.simplified")
      do
        read (5,*,iostat=io_status) id, cut_x, cut_y, cut_width, cut_height
        if (io_status /= 0) exit
        if (sum(cloth(cut_x:cut_x+cut_width-1, cut_y:cut_y+cut_height-1)) == &
         cut_width * cut_height) then
         write(*,*) "Unique ID: ", id
         exit
        end if
      end do
      close(5)

end program aoc32

I don't write a lot of Fortran, and peering at about 7 descriptions of how advanced IO worked didn't get me very far, so I used sed to strip out everything that wasn't a number or a space and that made it much more amenable to Fortran's read input preferences.

Ryan Palo • Dec 4 '18

Woah, this is super cool! The right tool for the right job, huh? 😎 thanks for sharing!

Carly Ho 🌈 • Dec 3 '18

PHP

One of those days when there's a big hint in the name, seems like. The slice/splice functions did the heavy lifting on this one.

Part 1:

<?php
$input = file_get_contents($argv[1]);
$claims = explode("\n", trim($input));
$fabric = array_fill(0, 1000, array_fill(0, 1000, 0));
foreach($claims as $claim) {
  preg_match('/\#[0-9]+ \@ ([0-9]+),([0-9]+): ([0-9]+)x([0-9]+)/', $claim, $data);
  $x = intval($data[1]);
  $y = intval($data[2]);
  $w = intval($data[3]);
  $h = intval($data[4]);

  for ($i = $y; $i < $y+$h; $i++) {
    $slice = array_slice($fabric[$i], $x, $w);
    $slice = array_map(function($x) {
      return $x+1;
    }, $slice);
    array_splice($fabric[$i], $x, $w, $slice);
  }
}

$twoplus = 0;

foreach ($fabric as $row) {
  $claimcounts = array_count_values($row);
  foreach ($claimcounts as $val=>$count) {
    if ($val >= 2) {
      $twoplus += $count;
    }
  }
}
echo $twoplus;
die(1);

Part 2:

<?php
$input = file_get_contents($argv[1]);
$claims = explode("\n", trim($input));
$fabric = array_fill(0, 1000, array_fill(0, 1000, 0));
foreach($claims as $j=>$claim) {
  preg_match('/\#([0-9]+) \@ ([0-9]+),([0-9]+): ([0-9]+)x([0-9]+)/', $claim, $data);
  $claims[$j] = $data;
  $c = $data[1];
  $x = intval($data[2]);
  $y = intval($data[3]);
  $w = intval($data[4]);
  $h = intval($data[5]);

  for ($i = $y; $i < $y+$h; $i++) {
    $slice = array_slice($fabric[$i], $x, $w);
    $slice = array_map(function($x) {
      return $x+1;
    }, $slice);
    array_splice($fabric[$i], $x, $w, $slice);
  }
}

foreach ($claims as $claim) {
  $c = $claim[1];
  $x = $claim[2];
  $y = $claim[3];
  $w = $claim[4];
  $h = $claim[5];

  $arr = array();

  for ($i = $y; $i < $y+$h; $i++) {
    $slice = array_slice($fabric[$i], $x, $w);
    array_push($arr, array_product($slice));
  }

  if (array_product($arr) == 1) {
    echo $c;
    break;
  }
}
die(1);

Russ Hammett • Dec 3 '18

c# again

public class FabricSlicing
    {
        public int GetOverlap(int width, int height, IEnumerable<string> fabricClaims)
        {
            var fabric = GetFabricLayout(width, height, fabricClaims);
            return fabric.GetOverlapArea();
        }

        public IEnumerable<FabricSegments> GetNoOverlap(int width, int height, IEnumerable<string> fabricClaims)
        {
            var fabric = GetFabricLayout(width, height, fabricClaims);
            return fabric.GetNoOverlap();
        }

        protected Fabric GetFabricLayout(int width, int height, IEnumerable<string> fabricClaims)
        {
            var fabric = new Fabric(width, height, PopulateFabricClaims(fabricClaims));

            return fabric;
        }

        protected IEnumerable<FabricSegments> PopulateFabricClaims(IEnumerable<string> fabricClaims)
        {
            List<FabricSegments> fabricSegments = new List<FabricSegments>();

            // #1 @ 1,3: 4x4
            Regex regex = new Regex(@"^#(?<id>\d*)\s@\s(?<x>\d*),(?<y>\d*):\s(?<width>\d*)x(?<height>\d*)$");

            foreach (var claim in fabricClaims)
            {
                var matches = regex.Match(claim);

                fabricSegments.Add(new FabricSegments()
                {
                    ClaimId = int.Parse(matches.Groups["id"].Value),
                    Height = int.Parse(matches.Groups["height"].Value),
                    Width = int.Parse(matches.Groups["width"].Value),
                    StartCoordinateX = int.Parse(matches.Groups["x"].Value),
                    StartCoordinateY = int.Parse(matches.Groups["y"].Value)
                });
            }

            return fabricSegments;
        }
    }

    public class Fabric
    {
        private readonly Point[,] _points;

        public Fabric(int width, int height, IEnumerable<FabricSegments> fabricClaims)
        {
            Width = width;
            Height = height;
            FabricClaims = fabricClaims;

            _points = new Point[Width,Height];

            // Instantiate all the points (is there a better way to do this?)
            for (var row = 0; row < Width; row++)
            {
                for (var column = 0; column < Height; column++)
                {
                    _points[row, column] = new Point();
                }
            }

            PopulatePoints();
        }

        public int Width { get; }
        public int Height { get; }

        public IEnumerable<FabricSegments> FabricClaims { get; }

        public int GetOverlapArea()
        {
            int count = 0;
            for (var row = 0; row < Width; row++)
            {
                for (var column = 0; column < Height; column++)
                {
                    if (_points[row, column].HasOverlap)
                    {
                        count++;
                    }
                }
            }

            return count;
        }

        public IEnumerable<FabricSegments> GetNoOverlap()
        {
            var overlap = GetOverlap();
            return FabricClaims.ToList().Except(overlap);
        }

        private void PopulatePoints()
        {
            foreach (var fabricClaim in FabricClaims)
            {
                for (var width = 0; width < fabricClaim.Width; width++)
                {
                    for (var height = 0; height < fabricClaim.Height; height++)
                    {
                        var point = _points[
                            fabricClaim.StartCoordinateX + width,
                            fabricClaim.StartCoordinateY + height
                        ];

                        point.Occupied.Add(fabricClaim);
                    }
                }
            }
        }

        private IEnumerable<FabricSegments> GetOverlap()
        {
            List<FabricSegments> list = new List<FabricSegments>();

            for (var row = 0; row < Width; row++)
            {
                for (var column = 0; column < Height; column++)
                {
                    var point = _points[row, column];
                    if (point.HasOverlap)
                    {
                        list.AddRange(point.Occupied);
                    }
                }
            }

            return list;
        }
    }

    public class FabricSegments
    {
        public int ClaimId { get; set; }

        public int Width { get; set; }
        public int Height { get; set; }

        public int StartCoordinateX { get; set; }
        public int StartCoordinateY { get; set; }
    }

    public class Point
    {
        public bool IsOccupied => Occupied.Count > 0;
        public bool HasOverlap => Occupied.Count > 1;
        public List<FabricSegments> Occupied { get; set; } = new List<FabricSegments>();
    }

Tests:

public class FabricSlicingTests
    {
        private readonly FabricSlicing _subject = new FabricSlicing();

        private class PopulateFabricClaims_FabricSlicing : FabricSlicing
        {
            public IEnumerable<FabricSegments> GetFabricClaims(
                IEnumerable<string> fabricClaims)
            {
                return PopulateFabricClaims(fabricClaims);
            }
        }

        public static IEnumerable<object[]> SampleData =>
            new List<object[]>()
            {
                new object[]
                {
                    new[]
                    {
                        "#1 @ 1,3: 4x4",
                        "#2 @ 3,1: 4x4",
                        "#3 @ 5,5: 2x2"
                    },
                    8,
                    8,
                    4
                }
            };

        [Theory]
        [MemberData(nameof(SampleData))]
        public void ShouldValidateSample(string[] fabricClaims, int width, int height, int expectedOverlap)
        {
            var result = _subject.GetOverlap(width, height, fabricClaims);

            Assert.Equal(expectedOverlap, result);
        }

        [Theory]
        [MemberData(nameof(SampleData))]
        public void ShouldValidateSampleNoOverlap(string[] fabricClaims, int width, int height, int expectedOverlap)
        {
            var result = _subject.GetNoOverlap(width, height, fabricClaims).ToList();

            Assert.Equal(3, result[0].ClaimId);
        }

        [Fact]
        public void ShouldParseClaimsProperly()
        {
            var claim = "#1 @ 2,3: 4x5";

            var subject = new PopulateFabricClaims_FabricSlicing();
            var result = subject.GetFabricClaims(new[] { claim }).ToList();

            Assert.True(result.Count == 1, nameof(result.Count));
            Assert.True(result[0].ClaimId == 1, nameof(FabricSegments.ClaimId));
            Assert.True(result[0].StartCoordinateX == 2, nameof(FabricSegments.StartCoordinateX));
            Assert.True(result[0].StartCoordinateY == 3, nameof(FabricSegments.StartCoordinateY));
            Assert.True(result[0].Width == 4, nameof(FabricSegments.Width));
            Assert.True(result[0].Height == 5, nameof(FabricSegments.Height));
        }

        [Fact]
        public void DoTheThing()
        {
            var file = Utilities.GetFileContents("./Day3/fabricSlicingData.txt");
            var result = _subject.GetOverlap(1000, 1000, file);

            Assert.Equal(110383, result);
        }

        [Fact]
        public void DoTheThingVersion2()
        {
            var file = Utilities.GetFileContents("./Day3/fabricSlicingData.txt");
            var result = _subject.GetNoOverlap(1000, 1000, file).ToList();

            Assert.Equal(129, result[0].ClaimId);
        }
    }

Antonio Radovcic • Dec 4 '18 • Edited

My solution (Elixir) for the first part was:

Make a list of every data-point's coords and size [((x,y), (w,h)), ...]
Transform each entry to a list of coords (all coords of this rect) [(x,y), ...], so now I have a list of lists with w * h coordinate-pairs
Concatenate all lists into one, so now I have a huge list of every occupied field.
Count every coordinate in a map, %{(x,y) => count, (x,y) => count, ...}
Throw out every entry where count < 2
Count entries in resulting list

Takes about a second. The first version used lists and list-diffing to find duplicates, but this took minutes to compute. Maps were much faster at this size (hundeds of thousands of entries).

I should mention I'm just learning Elixir, so this is not to be understood as "good code" or "knows what he's doing".

Here's the code:

defmodule Ac3 do
  def doit do
    filly =
      getFilledList()
      |> Enum.reduce(%{}, &count/2)

    :maps.filter(fn _, v -> v != 0 end, filly)
    |> Enum.reduce(0, fn i, acc -> acc + 1 end)
    |> IO.inspect()
  end

  def count(item, acc) do
    acc
    |> Map.update(item, 0, &(&1 + 1))
  end

  def getFilledList() do
    File.stream!("input.txt")
    |> Enum.to_list()
    |> Enum.map(&String.trim_trailing/1)
    |> Enum.map(&parse/1)
    |> Enum.map(&to_coords/1)
    |> Enum.reduce([], fn i, acc -> i ++ acc end)
  end

  def to_coords(unit) do
    x = elem(elem(unit, 0), 0)
    y = elem(elem(unit, 0), 1)
    x2 = x + elem(elem(unit, 1), 0) - 1
    y2 = y + elem(elem(unit, 1), 1) - 1
    fill(x, y, x, y, x2, y2)
  end

  def fill(x, y, _x1, _y1, x2, y2) when x === x2 and y === y2 do
    [{x, y}]
  end

  def fill(x, y, x1, y1, x2, y2) when x < x2 do
    [{x, y} | fill(x + 1, y, x1, y1, x2, y2)]
  end

  def fill(x, y, x1, y1, x2, y2) when x === x2 do
    [{x, y} | fill(x1, y + 1, x1, y1, x2, y2)]
  end

  def parse(str) do
    {
      unwrap(Enum.at(split(str), 3)),
      unwrap(Enum.at(split(str), 5))
    }
  end

  def split(str) do
    String.split(str, [" ", ":", "#"])
  end

  def unwrap(str) do
    {
      str
      |> String.split([",", "x"])
      |> Enum.at(0)
      |> String.to_integer(),
      str
      |> String.split([",", "x"])
      |> Enum.at(1)
      |> String.to_integer()
    }
  end
end

Ac3.doit()

Ryan Palo • Dec 4 '18

Cool! Thanks for sharing!

Just a heads up, you can put the word “elixir” immediately after the opening triple backtick, and your code will show up with syntax highlighting. 😁

Jason Steinhauser • Dec 4 '18

I've been solving all of these in Elixir thus far, and it's been pretty fun! Day 3 is the first time I dealt with "off by one" errors...

parse_claim = fn line ->
  line
  |> String.split(~r/[#@,:x\n ]/, trim: true)
  |> Enum.map(&Integer.parse/1)
  |> Enum.map(& elem(&1,0))
end  

claims =
  File.stream!("day3.txt")
  |> Enum.map(parse_claim)

grid = 
  claims
  |> Enum.flat_map(fn [claim, left, top, width, height] -> 
        for x <- left..left+width-1, y <- top..top+height-1, do: {claim, x, y} end)
  |> Enum.reduce(%{}, fn {claim, x, y}, acc -> Map.update(acc, {x,y}, [claim], &[claim | &1]) end)

part1 = fn ->
  grid
  |> Enum.count(fn {_k,v} -> Enum.count(v) > 1 end)
end

IO.puts "Part 1: #{part1.()}"

part2 = fn ->
  singles = 
    grid
    |> Enum.filter(fn {_k,v} -> Enum.count(v) == 1 end)
    |> Enum.group_by(fn {_k,[v]} -> v end, fn _ -> true end)
    |> Enum.map(fn {k, v} -> {k, Enum.count(v, & &1)} end)
    |> Map.new()

  claims
  |> Enum.find(fn [claim, _, _, w, h] -> Map.get(singles, claim) == w * h end)
  |> hd()
  |> Integer.to_string()
end

IO.puts "Part 2: #{part2.()}"

Tiago Romero Garcia • Dec 3 '18 • Edited

Javascript solution using regex capture groups (/^#(?<id>\d*)\s@\s(?<left>\d*),(?<top>\d*):\s(?<width>\d*)x(?<height>\d*)$/):

readFile.js

const fs = require('fs');
const readline = require('readline');

const readLines = (file, onLine) => {
    const reader = readline.createInterface({
        input: fs.createReadStream(file),
        crlfDelay: Infinity
    });

    reader.on('line', onLine);

    return new Promise(resolve => reader.on('close', resolve));
};

const readFile = async file => {
    const lines = [];
    await readLines(file, line => lines.push(line));  
    return lines;
}

module.exports = {
    readLines,
    readFile
};

03a.js

const { readFile } = require('./readLines');

const buildClaims = lines => {
    const claims = new Map();
    const regex = /^#(?<id>\d*)\s@\s(?<left>\d*),(?<top>\d*):\s(?<width>\d*)x(?<height>\d*)$/;
    for (let line of lines) {
        const { id, left, top, width, height } = line.match(regex).groups;
        claims.set(id, { 
            left: +left, 
            top: +top, 
            width: +width, 
            height: +height
        });
    }
    return claims;
};

const calculateOverlaps = claims => {
    const fabric = [];

    let overlaps = 0;

    for (let [id, claim] of claims.entries()) {
        const { left, top, width, height } = claim;
        const bottom = top + height;
        const right = left + width;
        for (let row = top; row < bottom; row++) {
            for (let col = left; col < right; col++) {
                if (!fabric[row]) {
                    fabric[row] = [];
                }
                if (!fabric[row][col]) {
                    fabric[row][col] = 0;
                }
                else if (fabric[row][col] === 1) {
                    overlaps++;
                }
                fabric[row][col]++;
            }
        }
    }

    return overlaps;
};

(async () => {
    const lines = await readFile('03-input.txt');

    const claims = buildClaims(lines);
    const overlaps = calculateOverlaps(claims);

    console.log(`Overlaps are ${overlaps} square inches`);
})();

03b.js

const { readFile } = require('./readLines');

const buildClaims = lines => {
    const claims = new Map();
    const regex = /^#(?<id>\d*)\s@\s(?<left>\d*),(?<top>\d*):\s(?<width>\d*)x(?<height>\d*)$/;
    for (let line of lines) {
        const { id, left, top, width, height } = line.match(regex).groups;
        claims.set(id, { 
            left: +left, 
            top: +top, 
            width: +width, 
            height: +height
        });
    }
    return claims;
};

const findNonOverlappingClaimID = claims => {
    const fabric = [];

    // Marking entries
    for (let [id, claim] of claims.entries()) {
        const { left, top, width, height } = claim;
        const bottom = top + height;
        const right = left + width;
        for (let row = top; row < bottom; row++) {
            for (let col = left; col < right; col++) {
                if (!fabric[row]) {
                    fabric[row] = [];
                }
                if (!fabric[row][col]) {
                    fabric[row][col] = 0;
                }
                fabric[row][col]++;
            }
        }
    }

    // Finding ID for the claim that doesnt overlap
    for (let [id, claim] of claims.entries()) {
        const { left, top, width, height } = claim;
        const bottom = top + height;
        const right = left + width;

        let doesClaimOverlap = false;
        for (let row = top; row < bottom; row++) {
            for (let col = left; col < right; col++) {
                if (fabric[row][col] > 1) {
                    doesClaimOverlap = true; 
                }
            }
        }

        if (!doesClaimOverlap) {
            return id;
        }
    }
};

(async () => {
    const lines = await readFile('03-input.txt');

    const claims = buildClaims(lines);
    const id = findNonOverlappingClaimID(claims);

    console.log(`The ID of the only claim that doesn't overlap is ${id}`);
})();

rohmanovich • Dec 13 '18 • Edited


#Part 1

from collections import defaultdict
claims = defaultdict(list)
i = 1
for line in film.split('\n'):
    if line is None or line == '':
        continue
    _, _, offset, size = line.split(' ')

    l, t = map(int, offset[:-1].split(','))
    w, h = map(int, size.split('x'))

    claims.update({(l+x,t+y): claims.get((l+x,t+y),[]) + [i] for x in range(1,w+1) for y in range(1,h+1)})
    i += 1
print(len([claim for claim in claims.values() if len(claim) > 1]))

#Part 2
overlapping_claims = []
for x in claims.values():
    if len(x) > 1:
        overlapping_claims += x
print(set(range(1,1360)).difference(set(overlapping_claims)))

Bjarne Magnussen • Dec 3 '18

Puh, that was a tough one for me today. I started out by counting the number of claims for each square on the "canvas" which gave me a correct aswer. However, I later misunderstand part 2 thinking I should find completely unclaimed squares that could be filled out by one claim...

After cheating a little and getting inspirations for solutions I have implemented a Golang solution for today. At least I am happy that I could implement it in Golang without any prior experience using Golang:

Part 1 and 2 together:

package main

import (
    "bufio"
    "fmt"
    "os"
    "regexp"
    "strconv"
)

type coord struct {
    l int
    t int
}

// readLines reads a whole file into memory
// and returns a slice of its lines.
func readLines(path string) ([]string, error) {
    file, err := os.Open(path)
    if err != nil {
        return nil, err
    }
    defer file.Close()

    var lines []string
    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        lines = append(lines, scanner.Text())
    }
    return lines, scanner.Err()
}

func mapClaims(data []string) (map[coord][]int, map[int][]int) {
    m := make(map[coord][]int)
    claims := make([][]int, len(data))
    overlaps := make(map[int][]int)
    r, _ := regexp.Compile("-?[0-9]+")
    for i, d := range data {
        claimsVal := r.FindAllString(d, -1)
        for _, valStr := range claimsVal {
            val, _ := strconv.Atoi(valStr)
            claims[i] = append(claims[i], val)
        }
        id := claims[i][0]
        startX := claims[i][1]
        startY := claims[i][2]
        width := claims[i][3]
        height := claims[i][4]
        overlaps[id] = []int{}
        for l := startX; l < startX+width; l++ {
            for t := startY; t < startY+height; t++ {
                claimSet := m[coord{l, t}]
                for _, number := range claimSet {
                    overlaps[number] = append(overlaps[number], id)
                    overlaps[id] = append(overlaps[id], number)
                }
                claimSet = append(claimSet, id)
                m[coord{l, t}] = claimSet
            }
        }

    }
    return m, overlaps
}

func main() {
    start := time.Now()
    data, err := readLines("input")
    if err != nil {
        panic(err)
    }

    m, overlaps := mapClaims(data)

    partA := 0
    for _, v := range m {
        if len(v) >= 2 {
            partA++
        }
    }
    fmt.Println(partA)

    partB := []int{}
    for k, v := range overlaps {
        if len(v) == 0 {
            partB = append(partB, k)
        }
    }
    fmt.Println(partB[0])
    elapsed := time.Since(start)
}

JavaScript Room • Dec 4 '18

Hi guys! Here is my solution on #typescript.

Repo: github.com/room-js/adventOfCode201...

E. Choroba • Dec 3 '18

Perl solutions. The first part was easy, just counting how many times each square occurred. The second part was trickier and the naive solution was too slow, so I summoned some regular expressions to help me:

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my %grid;
while (<>) {
    my ($x, $y, $w, $h) = /#\d+ @ (\d+),(\d+): (\d+)x(\d+)/;
    for my $j ($y .. $y + $h - 1) {
        for my $i ($x .. $x + $w - 1) {
            ++$grid{"$i $j"};
        }
    }
}

say scalar grep $grid{$_} > 1, keys %grid;

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my %grid;
while (<>) {
    my ($id, $x, $y, $w, $h) = /(#\d+) @ (\d+),(\d+): (\d+)x(\d+)/;
    for my $j ($y .. $y + $h - 1) {
        for my $i ($x .. $x + $w - 1) {
            $grid{"$i $j"} .= $id;
        }
    }
}

my $all = join ':', values %grid;
my %uniq;
undef @uniq{ $all =~ /(?:^|:)(#\d+)(?:$|:)/g };
for my $id (keys %uniq) {
    say($id), last if $all !~ /\d$id/ && $all !~ /$id#/;
}

Florian Rohrer • Dec 3 '18

Part 1

import numpy as np

with open("input.txt") as f:
    claims = []
    for line in f:
        _, _, coords, dim = line.split()
        x, y = coords.split(",")[0], coords.split(",")[1][:-1]
        a, b = dim.split("x")
        claims.append((int(x), int(y), int(a), int(b)))

max_x = max(t[0]+t[2]+1 for t in claims)
max_y = max(t[1]+t[3]+1 for t in claims)

fabric = np.zeros((max_x, max_y), dtype=int)
for x, y, a, b in claims:
    fabric[x:x+a, y:y+b] += 1

print(len(fabric[fabric > 1]))

Part 2

candidates = set(list(range(len(claims))))

fabric = np.zeros((max_x, max_y), dtype=int)
for i, (x, y, a, b) in enumerate(claims):
    f = fabric[x:x+a, y:y+b]
    uniques = np.unique(f)
    if list(uniques) != [0]:
        for u in uniques:
            candidates.discard(u)
        candidates.discard(i)
    fabric[x:x+a, y:y+b] = i

print(candidates.pop()+1)

Ben Lovy • Dec 3 '18 • Edited

F# again - I think I really like this language.

namespace Day3
open System.Text.RegularExpressions

module util =
  // cell contents are a list of ClaimIds
  let grid size = Array2D.create size size []

  let claimRegex = @"#(?<ClaimNum>[0-9]+) @ (?<xCoord>[0-9]+),(?<yCoord>[0-9]+): (?<rows>[0-9]+)x(?<columns>[0-9]+)"

  let fallsInClaim claimX claimY rows columns gridX gridY =
    (gridX >= claimX && gridX < rows + claimX) && (gridY >= claimY && gridY < columns + claimY)

  // Given a claim string and a grid, return a new grid with the claims added
  let claim s g =
    let matches = Regex.Match(s, claimRegex)
    if matches.Success then
      let claimNum = matches.Groups.["ClaimNum"].Value |> System.Convert.ToInt32
      let claimX = matches.Groups.["xCoord"].Value |> System.Convert.ToInt32
      let claimY = matches.Groups.["yCoord"].Value |> System.Convert.ToInt32
      let rows = matches.Groups.["rows"].Value |> System.Convert.ToInt32
      let columns = matches.Groups.["columns"].Value |> System.Convert.ToInt32
      Array2D.mapi (fun i j cell -> if fallsInClaim claimX claimY rows columns i j then cell @ [claimNum] else cell) g
    else
      g

  let readClaims fileName =
    System.IO.File.ReadLines(fileName) |> List.ofSeq

  let applyClaims fileName =
    let g = grid 1000
    let claims = readClaims fileName
    List.fold (fun accGrid c -> claim c accGrid) g claims
    |> Seq.cast<int list>

module part1 =
  let execute fileName =
    util.applyClaims fileName
    |> Seq.filter (fun el -> List.length el > 1)
    |> Seq.length

module part2 =
  // check if a given claim has any overlaps
  let noOverlaps claim g =
    g |> Seq.filter (fun cell -> List.contains claim cell) |> Seq.forall (fun cell -> List.length cell = 1)

  let execute fileName =
    let claims = util.readClaims fileName
                |> Seq.map (fun el ->
                  let matches = Regex.Match(el, util.claimRegex)
                  matches.Groups.["ClaimNum"].Value |> System.Convert.ToInt32)
                |> List.ofSeq
    let g = util.applyClaims fileName
    List.fold (fun s el -> if noOverlaps el g then s @ [el] else s) [] claims
    |> printfn "%A"
    0

This is very suboptimal - it repeats a ton of work to solve for part two. It applies all the claims and then checks every cell again for every single claim, grabbing cells with no overlaps anywhere in the grid. I'd like to revisit this and see if I can manipulate claims as a whole as opposed to just leaving "claim breadcrumbs" in each cell.

Neil Gall • Dec 3 '18

Ah, regexes and string splitting. The One True Way to parse text is with parser combinators.

import org.jparsec.Parser
import org.jparsec.Parsers.*
import org.jparsec.Scanners.*

data class Origin(val left: Int, val top: Int)
data class Size(val width: Int, val height: Int)
data class Claim(val id: origin: Origin, size: Size)

val integer: Parser<Int> = INTEGER.map(String::toInt)

fun <T> integerPair(sep: Char, c: (Int, Int) -> T): Parser<T> =  
    sequence(integer.followedBy(isChar(sep)), integer, c)

val claimId: Parser<Int> = isChar('#').next(integer)

val origin: Parser<Origin> = WHITESPACES.followedBy(isChar('@')).followedBy(WHITESPACES).next(integerPair(',', ::Origin))

val size: Parser<Size> = isChar(':').followedBy(WHITESPACES).next(integerPair('x', ::Size))

val claim: Parser<Claim> = sequence(claimId, origin, size, ::Claim)

val input: List<Claim> = File("input.txt").readLines().map(claim::parse)

Part 1

I really wanted to do Part 1 geometrically by splitting and merging claims into non-overlapping regions. It would be O(N²) however, and I was short of actual time to build it so went for the big map of positions like many others:

fun part1(claims: List<Claim>): Int {
    val material = mutableMapOf<Pos, Int>()
    claims.forEach { claim ->
        claim.positions().forEach { pos ->
            material[pos] = (material[pos] ?: 0) + 1
        }
    }
    return material.filterValues { it >= 2 }.size
}

That uses a modified Claim class as follows:

data class Claim(val id: Int, val x: IntRange, val y: IntRange) {
    constructor(id: Int, origin: Origin, size: Size):
        this(id, (origin.left .. origin.left + size.width - 1), (origin.top .. origin.top + size.height - 1))

    fun positions(): Sequence<Pos> = x.asSequence().flatMap { x ->
        y.asSequence().map { y -> Pos(x, y) }
    }
}

Part 2

Fairly simple extension. The tricky bit was remembering to remove both overlapping claims from the candidate result set:

fun part2(claims: List<Claim>): Set<Int> {
    val material = mutableMapOf<Pos, Int>()
    val nonOverlapping: MutableSet<Int> = claims.map { c -> c.id }.toMutableSet()

    claims.forEach { claim ->
        claim.positions().forEach { pos ->
            val claimed = material[pos]
            if (claimed == null) {
                // unclaimed position, now claimed
                material[pos] = claim.id
            } else {
                // overlapping position, remove both claims from result set
                nonOverlapping -= setOf(claimed, claim.id)
            }
        }
    }
    return nonOverlapping
}

Yordi Verkroost • Dec 3 '18 • Edited

Solution in Elixir below.

It took me a while to figure out the best way to store the fabric because matrices are not really a thing in Elixir. And it's a bit harder for me (coming from an OOP background), as everything is immutable in a functional language like Elixir. A mindset switch is necessary sometimes.

Part one:


defmodule AoC.DayThree.PartOne do
  alias AoC.DayThree.Common

  def main() do
    "lib/day3/input.txt"
    |> Common.read_input()
    |> Common.parse_into_structs()
    |> Common.get_fabric()
    |> Enum.filter(fn {_key, value} -> value > 1 end)
    |> Enum.count()
  end
end

Part two:

defmodule AoC.DayThree.PartTwo do
  alias AoC.DayThree.Common

  def main() do
    claims =
      "lib/day3/input.txt"
      |> Common.read_input()
      |> Common.parse_into_structs()

    fabric = Common.get_fabric(claims)
    find_non_overlapping_claim(fabric, claims)
  end

  defp find_non_overlapping_claim(fabric, claims) do
    Enum.reduce_while(claims, false, fn claim, _ ->
      result_columns =
        Enum.reduce_while((claim.left + 1)..(claim.left + claim.columns), false, fn x, _ ->
          result_rows =
            Enum.reduce_while((claim.top + 1)..(claim.top + claim.rows), false, fn y, _ ->
              if Map.get(fabric, {x, y}) > 1, do: {:halt, false}, else: {:cont, true}
            end)

          if result_rows, do: {:cont, true}, else: {:halt, false}
        end)

      if result_columns, do: {:halt, claim.id}, else: {:cont, false}
    end)
  end
end

Common:

defmodule AoC.DayThree.Common do
  alias AoC.DayThree.Claim

  def read_input(path) do
    path
    |> File.stream!()
    |> Stream.map(&String.trim_trailing/1)
    |> Enum.to_list()
  end

  def get_fabric(claims) do
    Enum.reduce(claims, %{}, fn claim, map ->
      Enum.reduce((claim.left + 1)..(claim.left + claim.columns), map, fn x, acc_x ->
        Enum.reduce((claim.top + 1)..(claim.top + claim.rows), acc_x, fn y, acc_y ->
          Map.update(acc_y, {x, y}, 1, &(&1 + 1))
        end)
      end)
    end)
  end

  def parse_into_structs(input) do
    input
    |> Enum.map(&parse_struct/1)
  end

  defp parse_struct(input) do
    [id, rest] = String.split(input, "@")
    [location, dimension] = String.split(rest, ":")
    [left, top] = String.split(location, ",")
    [columns, rows] = String.split(dimension, "x")

    id =
      id
      |> String.trim("#")
      |> to_integer()

    left =
      left
      |> to_integer()

    top =
      top
      |> to_integer()

    columns =
      columns
      |> to_integer()

    rows =
      rows
      |> to_integer()

    %Claim{id: id, left: left, top: top, columns: columns, rows: rows}
  end

  defp to_integer(input) do
    input
    |> String.trim()
    |> String.to_integer()
  end
end

Ryan Palo • Dec 3 '18

Wow, nice! Elixir really does seem like a big brain shift.

Matt Morgis • Dec 3 '18 • Edited

Node.js

Reused my work for part 1 in part 2.

I make the 1000 x 1000 array and fill it every slot with a *.
First time a claim is added, it gets a #
If a claim overlaps with another, those cells get marked with an X.

Part 1: Filter matrix for all X values.

Part 2: Check every coordinate for each claim. If every coordinate is a #, then that claim is the answer.

const generateFabricMatrix = () => {
  const fabric = [];

  for (const i of Array(1000).keys()) {
    fabric_columns = [];
    for (const j of Array(1000).keys()) {
      fabric_columns.push("*");
    }
    fabric.push(fabric_columns);
  }
  return fabric;
};

const claimData = input => {
  claimChars = [...input];

  const at = claimChars.indexOf("@");
  const colon = claimChars.indexOf(":");

  const id = Number(input.substr(1, at - 2));
  const xPosition = Number(input.substr(at + 1, colon - at - 1).split(",")[0]);
  const yPosition = Number(input.substr(at + 1, colon - at - 1).split(",")[1]);
  const xLength = Number(input.substr(colon + 1).split("x")[0]);
  const yLength = Number(input.substr(colon + 1).split("x")[1]);

  return {id, xPosition, yPosition, xLength, yLength};
};

const addToFabric = (claimData, fabric) => {
  for (const i of Array(claimData.xLength).keys()) {
    for (const j of Array(claimData.yLength).keys()) {
      if (fabric[claimData.xPosition + i][claimData.yPosition + j] === "*") {
        fabric[claimData.xPosition + i][claimData.yPosition + j] = "#";
      } else if (
        fabric[claimData.xPosition + i][claimData.yPosition + j] === "#"
      ) {
        fabric[claimData.xPosition + i][claimData.yPosition + j] = "X";
      }
    }
  }

  return fabric;
};

const blocked = fabric => {
  let numberBlocked = 0;
  for (let i = 0; i < fabric.length; i++) {
    const arr = fabric[i].filter(val => val === "X");
    numberBlocked += arr.length;
  }
  return numberBlocked;
};

const overlap = async stream => {
  let fabric = generateFabricMatrix();

  for await (const claim of streamToClaim(stream)) {
    fabric = addToFabric(claimData(claim), fabric);
  }

  return blocked(fabric);
};

const unique = async stream => {
  let fabric = generateFabricMatrix();
  const cloned = stream.pipe(new PassThrough({encoding: "utf-8"}));

  for await (const claim of streamToClaim(stream)) {
    fabric = addToFabric(claimData(claim), fabric);
  }

  for await (const claim of streamToClaim(cloned)) {
    const data = claimData(claim);

    const totalLength = data.xLength * data.yLength;
    let checkUnique = 0;

    for (const i of Array(data.xLength).keys()) {
      for (const j of Array(data.yLength).keys()) {
        if (fabric[data.xPosition + i][data.yPosition + j] === "#") {
          checkUnique++;
        }
      }
    }
    if (checkUnique === totalLength) {
      return data.id;
    }
  }
};

Main.js:

const claimStream = () => {
  return fs.createReadStream(__dirname + "/input.txt", {
    encoding: "utf-8",
    highWaterMark: 256
  });
};

const main = async () => {
  try {
    const part1 = await overlap(claimStream());
    console.log({part1});
    const part2 = await unique(claimStream());
    console.log({part2});
  } catch (e) {
    console.log(e.message);
    process.exit(-1);
  }

Paula Gearon • Dec 4 '18

I did my part 1 similarly: I wrote the ID to each cell in it’s rectangle, unless the cell wasn’t zero, in which case I wrote -1. At the end, I counted the -1 values.

The second step was a little different. First of all, I added the ID to a set of IDs that were OK. Then I went through each cell of its rectangle. If the cell is zero, then update it to the current row’s ID. If it had a number in it, then that’s the ID of the most recent rectangle to overlap that cell; so remove the found ID and the current ID from the set of good IDs. Then set all the cells in the entire rectangle to its ID. At the end, the set of good IDs has a single element.

It sounds tricky, but it’s literally just a couple of lines of code

Christopher Kruse • Dec 3 '18

Adding my Clojure solution here - will write another post at some point. I'm oncall this week and got paged at 3am for something out of my control, so I figured "hey, I'm up, might as well." get-overlap solves part 1, while find-no-overlap solves part 2. Second part is a little brute-force, but still worked.

(ns aoc.aoc3
  (:require [clojure.string :as s]
            [clojure.set :as set]))

(defrecord Claim [claim-number squares])

(defn convert-to-grid
  "Converts a claim into a sequence of 'taken' squares."
  [claim grid-width]
  ;; Named groups would be great here, but Clojure doesn't support this natively.
  (let [matcher #"#(?<claim>\d+)\s@\s(?<x>\d+),(?<y>\d+):\s(?<width>\d+)x(?<height>\d+)$"
        matches (re-find matcher claim)
        [_ claim horiz vert width height] matches
        x (Integer. horiz)
        y (Integer. vert)
        w (Integer. width)
        h (Integer. height)
        rows (take h (iterate inc y))]
    (->> (map #(range (+ x (* grid-width %)) (+ (+ x w) (* grid-width %))) rows)
         (flatten)
         (set)
         (Claim. (Integer. claim) ))))

(defn get-overlap
  "returns the amount of overlap based on calculated inputs.
   Answer provided in square units matching the units entered
   (for the case of the problem, square inches)."
  [claims]
  ;; Perform intersection to find any matches, then union to combine; repeat through the list.
  (loop [mapped-area (map #(convert-to-grid % 1000) claims)
         shared-fabric #{}
         intersections #{}]
    (if (empty? mapped-area)
      intersections
      (let [intersect (set/intersection shared-fabric (:squares (first mapped-area)))
            union (set/union shared-fabric (:squares (first mapped-area)))]
        (recur (rest mapped-area) union (set/union intersections intersect))))))

(defn overlapping-claim [c1 c2]
  (cond
    (= (:claim-number c1) (:claim-number c2)) nil
    (not-empty (set/intersection (:squares c1) (:squares c2))) c2))

(defn find-no-overlap
"given a set of input claims, find the claim that has no overlap
  with any other claims."
[claims]
(let [grid-claims (map #(convert-to-grid % 1000) claims)]
  (loop [idx 0 ignores #{}]
    (if-not (contains? (:claim-id (nth grid-claims idx)) ignores)
      (if-let [overlap (some #(overlapping-claim (nth grid-claims idx) %) grid-claims)]
        (recur (inc idx) (conj ignores (:claim-number overlap)))
        (:claim-number (nth grid-claims idx)))
      (recur (inc idx) ignores)))))

Ryan Palo • Dec 3 '18

Wow, this is really clear and nice! Ruby has so. Many. Convenience methods that I really miss when I go to other languages sometimes.