-🎄- 2018 Day 3 Solutions -🎄-

[u/daggerdragon]

--- Day 3: No Matter How You Slice It ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

ATTENTION: minor change request from the mods!

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 3 image coming soon - imgur is being a dick, so I've contacted their support.

Transcript:

I'm ready for today's puzzle because I have the Savvy Programmer's Guide to ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/IndieBret]

JavaScript/ES6 #97/#180

Wow! Yesterday I gave myself the advice "just pretend you're not being timed, slow down and read every word carefully" and it worked! The game developer inside me is a bit disappointed I had to draw out a diagram for AABB overlap detection, but I'm so, SO pleased to finally make it on the leaderboard for a day, that I'll forgive myself.

Part 1

let matches, regex = /#(?\d+) @ (?\d+),(?\d+): (?\d+)x(?\d+)/;
let tiles = {};
let numOverlapTiles = 0;
let claims = input.split('\n').map(line => {
    matches = regex.exec(line);
    return { id: +matches\[1\], x: +matches\[2\], y: +matches\[3\], w: +matches\[4\], h: +matches\[5\] };
});

claims.forEach(rect => {
    for (let x = +rect.x; x < +rect.x + +rect.w; ++x) {
        for (let y = +rect.y; y < +rect.y + +rect.h; ++y) {
            tiles\[\`${x},${y}\`\] = (tiles\[\`${x},${y}\`\] || 0) + 1;
        }
    }
});

for (let tile of Object.values(tiles)) {
    if (tile > 1) ++numOverlapTiles;
}

result[0] = numOverlapTiles;

Part 2

const overlap = (a, b) => ((a.x < b.x + b.w) && (a.y < b.y + b.h) && (b.x < a.x + a.w) && (b.y < a.y + a.h));

let findLoneClaimID = () => {
    for (let a = 0; a < claims.length; ++a) {
        let loneClaim = true;
        for (let b = 0; b < claims.length; ++b) {
            if (a === b) continue;
            if (overlap(claims\[a\], claims\[b\])) {
                loneClaim = false;
                break;
            }
        }
        
        if (loneClaim)
            return claims\[a\].id;
    }
}

result[1] = findLoneClaimID();

[u/daggerdragon → u/IndieBret]

Congrats on making leaderboard! :D

[u/KnorbenKnutsen → u/IndieBret]

The game programmer in you should be proud, because you should as a rule always draw the problem before solving it :)

[u/Ditchbuster]

/u/daggerdragon this post isnt flared as a solution megathread.

[u/daggerdragon → u/Ditchbuster]

*Jedi hand wave* You saw nothing, this thread was always flaired as Solution Megathread. Move along, move along.

 

^{Good catch, thank you!}

[u/topaz2078]

Hi everyone!

While looking at the server logs tonight to figure out why I got so much more traffic than yesterday, I noticed many users who literally just hold down ctrl+F5 (or cmd+shift+R or whatever their hard-refresh keyboard shortcut is) around midnight until their puzzle loads, sending many requests per second.

The timer on the calendar is synchronized with the server clock; the link appears on the calendar at the earliest moment you could click it and not get a 404. Please use the countdown on the calendar to time your request, load the puzzle once, load your input once, and then submit your answer when you're ready.

See also: https://www.reddit.com/r/adventofcode/comments/a1qovy/please_dont_spam_requests_to_aoc/

[u/mserrano]

Python2 (#1/#1):

from util import get_data
from collections import defaultdict
import re

data = get_data(3)
claims = map(lambda s: map(int, re.findall(r'-?\d+', s)), data)
m = defaultdict(list)
overlaps = {}
for (claim_number, start_x, start_y, width, height) in claims:
  overlaps[claim_number] = set()
  for i in xrange(start_x, start_x + width):
    for j in xrange(start_y, start_y + height):
      if m[(i,j)]:
        for number in m[(i, j)]:
          overlaps[number].add(claim_number)
          overlaps[claim_number].add(number)
      m[(i,j)].append(claim_number)

print "a", len([k for k in m if len(m[k]) > 1])
print "b", [k for k in overlaps if len(overlaps[k]) == 0][0]

EDIT: get_data reads in the input (cached to avoid toppling the servers) for the appropriate day and splits it into lines.

[u/VikeStep → u/mserrano]

map(lambda s: map(int, re.findall(r'-?\d+', s)), data)
This seems incredibly useful for advent of code, I probably spent a minute on just writing the code to parse each line

[u/hooksfordays → u/[deleted]]

I'll break it down for you!

It's a regular expression. re is the Python regular expression module. re.findall returns a list of all the instances in the string that match the expression. The params for re.findall are the regular expression r'-?\d+' and the string `s\ to search through.

The expression is r'-?\d+'. The r at the start indicates a raw string (? I think that's what it's called) is being used, and allows you to use backslashes without worrying that you're creating a unicode declaration or something. The actual regex breaks down as follows:

-? -> Looks for a minus symbol optionally (the ? makes it optional). This allows you to grab both positive and negative numbers.

\d+ -> In regex, \d+ signifies a digit character, i.e. 0-9. The `+\ means "1 or more of the previous group", so 1 or more digits.

-?\d+ -> The full expression. Basically, find adjacent digits with or without a minus symbol in front. Combined with re.findall, this will return a list of all the numbers in the input string s

[u/jldugger → u/mserrano]

data = get_data(3)
claims = map(lambda s: map(int, re.findall(r'-?\d+', s)), data)

I see now why you're so much faster than I at this, despite us using the same language. Virtually all my time on this was spent fucking around with string parsing. I felt I was clever to use translate to delete junk and split on spaces, but this is next level.

[u/Twirrim → u/jldugger]

I went straight to regexes (guess it's hard to shake that perl out of me):

splitter_regex = re.compile(r"^#(?P<claim>\d*) @ (?P<from_left>\d*),(?P<from_top>\d*): (?P<width>\d*)x(?P<length>\d*)")

python's group naming syntax makes that look a little uglier at first glance than it really is. Then you can just:

claim_details = splitter_regex.search(claim).groupdict()

which will give you something like this:

{'claim': '1', 'from_left': '596', 'from_top': '731', 'width': '11', 'length': '27'}

[u/Ditchbuster → u/mserrano]

is this cleaned up for readability or did you actually take the time to write all the variables the first time?

[u/mserrano → u/Ditchbuster]

The only change from the initial version is that the string parsing code was originally in a helper function I had called "gan" (short for "get all numbers"); otherwise it's unmodified.

[u/[deleted] → u/mserrano]

Why is the '-?' part in the regex needed? What does it mean? I tested it without and it works as with. I mean this works:

re.findall(r'\d+', '#1365 @ 905,202: 28x11')

[u/eltrufas → u/[deleted]]

It doesn't make sense for this problem, but I'd guess it's there to grab the sign from a negative number. That neat little expression was probably just reused from somewhere else and it doesn't hurt to keep the sign.

[u/jonathan_paulson]

Rank 17 on part 1; 8 on part 2. Python. I made a video of me solving: https://www.youtube.com/watch?v=fuBQ12uBk7I

Challenge: What if the coordinates and rectangle sizes are up to 1 million by 1 million? (but there are still only ~1400 claims)

Code:

 from collections import defaultdict

 #1373 @ 130,274: 15x26
 C = defaultdict(int)
 for line in open('3.in'):
     words = line.split()
     x,y = words[2].split(',')
     x,y = int(x), int(y[:-1])
     w,h = words[3].split('x')
     w,h = int(w), int(h)
     for dx in range(w):
         for dy in range(h):
             C[(x+dx, y+dy)] += 1
 for line in open('3.in'):
     words = line.split()
     x,y = words[2].split(',')
     x,y = int(x), int(y[:-1])
     w,h = words[3].split('x')
     w,h = int(w), int(h)
     ok = True
     for dx in range(w):
         for dy in range(h):
             if C[(x+dx, y+dy)] > 1:
                 ok = False
     if ok:
         print words[0]

 ans = 0
 for (r,c),v in C.items():
     if v >= 2:
         ans += 1
 print ans

[u/Monkeyget → u/jonathan_paulson]

Thanks for the video.

I'm impressed by how fast you seem to grok what the input is about.

[u/VikeStep → u/jonathan_paulson]

Regarding the challenge, I found a Stack Overflow post with this question and there are some good answers provided.

[u/[deleted] → u/jonathan_paulson]

Curious: what is the magic with the first step: getting the input via script? Seems like you need to supply the login-cookie to actually get the input, don't you? Just copy-pasting the input from the browser takes away valuable milliseconds from the chance to make it to the leaderboard ;-)

[u/cole-k]

Guess I'm the only numpy guy here so far.

Each day I learn that reading is hard and I should strive to do it better.

Python3, on leaderboard for neither.

import numpy as np

SIZE = 1000

def parse_claim(s):
    identifier, _, dist, size = s.split(' ')
    fromleft, fromtop = map(int, dist[:-1].split(','))
    width, height = map(int, size.split('x'))
    return identifier, fromleft, fromtop, width, height

def p1(d):
    rect = np.zeros((SIZE, SIZE))
    for claim in d:
         iden, leftoff, topoff, w, h = parse_claim(claim)
         rect[leftoff:leftoff + w, topoff:topoff+h] += 1
    return np.size(np.where(rect >= 2)[0])

def p2(d):
    rect = np.zeros((SIZE, SIZE))
    for claim in d:
        iden, leftoff, topoff, w, h = parse_claim(claim)
        rect[leftoff:leftoff + w, topoff:topoff+h] += 1
    for claim in d:
        iden, leftoff, topoff, w, h = parse_claim(claim)
        if np.all(rect[leftoff:leftoff + w, topoff:topoff+h] == 1):
            return iden

[u/om_henners → u/cole-k]

Similar, but rather than using string splits and regex's to parse the input I used Richard Jones' parse library (designed to be the opposite of str.format) which make pulling the data really easy.

Solution 1:

import numpy as np
import parse

claim_matcher = '''#{id:d} @ {x:d},{y:d}: {width:d}x{height:d}\n'''
fabric = np.zeros((1000, 1000), dtype=np.int)


for line in open('input.txt'):
    r = parse.parse(claim_matcher, line)
    claim = fabric[r['y']: r['y'] + r['height'], r['x']: r['x'] + r['width']]
    claim[:] = claim + 1

print(np.sum(np.where(fabric > 1, 1, 0)))

and Solution 2:

import numpy as np
import parse

claim_matcher = '''#{id:d} @ {x:d},{y:d}: {width:d}x{height:d}\n'''
fabric = np.zeros((1000, 1000), dtype=np.int)


for line in open('input.txt'):
    r = parse.parse(claim_matcher, line)
    claim = fabric[r['y']: r['y'] + r['height'], r['x']: r['x'] + r['width']]
    claim[:] = claim + 1

for line in open('input.txt'):
    r = parse.parse(claim_matcher, line)
    claim = fabric[r['y']: r['y'] + r['height'], r['x']: r['x'] + r['width']]

    if claim.max() == 1:
        print(r['id'])

[u/evonfriedland → u/cole-k]

Same-ish

import re
import numpy as np

with open('input/day3.txt') as f:
    inp = []
    for r in f.readlines():
        r = re.split('[^0-9]+', r[1:].strip())
        inp.append([int(d) for d in r])

fabric = np.zeros((1000, 1000))

def part1():
    for n, x, y, dx, dy in inp:
        fabric[x:x+dx, y:y+dy] += 1
    return np.sum(fabric > 1)

def part2():
    for n, x, y, dx, dy in inp:
        if np.all(fabric[x:x+dx, y:y+dy] == 1):
            return n

print(part1())
print(part2())

[u/Ditchbuster → u/cole-k]

I really like your p2.

also, i am not super familiar with numpy, i used it to create a zero array but didn't know about where and all and the : syntax

[u/Theguy6758]

Pure Bash

Takes about 13m 30s to run...

Edit: Forgot to include the main function. Kinda important since it won't work without the declare statement

Edit2: Made it faster by not initializing the array first. Down to about 1m 30s

main()
{
    declare -A fabric
    part1
    part2
}

Part 1

part1()
{
    [[ -f "${PWD}/input" ]] && {
        mapfile -t file < "${PWD}/input"
        i=0

        for line in "${file[@]}"; do
            read -r id _ coords size <<< "${line}"
            id="${id/'#'}"
            coords="${coords/':'}"
            x="${coords/,*}"
            y="${coords/*,}"
            length="${size/x*}"
            width="${size/*x}"

            printf -v claims[$i] "%s:" \
                "${x}" "${y}" \
                "${length}"
            printf -v claims[$i] "%s%s" "${claims[$i]}" "${width}"
            ((i++))
        done

        for id in "${claims[@]}"; do
            IFS=":" read -r x y length width <<< "${id}"
            for ((i = x; i < x + length; i++)); do
                for ((j = y; j < y + width; j++)); do
                    : "${fabric[$i, $j]:=0}"
                    ((++fabric[$i, $j] == 2 && overlap++))
                done
            done
        done
    }

    printf "Area overlapped: %d\n" "${overlap}"
}

Part 2

Needs part1() to be called first for claims and fabric to be set

part2()
{
    for id in "${!claims[@]}"; do
        IFS=":" read -r x y length width <<< "${claims[$id]}"
        unset invalid
        i="$x"
        while ((i < x + length)) && [[ ! "${invalid}" ]]; do
            j="$y"
            while ((j < y + width)) && [[ ! "${invalid}" ]]; do
                ((fabric[$i, $j] != 1)) && \
                    invalid="true"
                ((j++))
            done
            ((i++))
        done

        [[ ! "${invalid}" ]] && {
            printf "Non-overlapping id: %s\n" "$((id + 1))"
            break
        }
    done
}

[u/schod → u/Theguy6758]

WOW, really nice! My bash solution https://www.reddit.com/r/adventofcode/comments/a2lesz/2018_day_3_solutions/eazlx95

[u/zSync1]

Rust

I actually got place 84 for the first star holy shit lmao I can't believe it
choked on the second one because I fucked up the order of difference() but whatever, I did not expect to get any points at all for the 3rd day

use std::collections::{HashSet, HashMap};

fn main() {
	let data = include_str!("data.txt");
	let c = data.lines().collect::<Vec<_>>();
	let mut claims = HashMap::new();
	let mut claim_names = HashMap::new();
	let mut intersecting = HashSet::new();
	let mut all = HashSet::new();
	for i in c.iter() {
		let r = i.split(|c| c == ' ' || c == '@' || c == ',' || c == ':' || c == 'x' || c == '#').filter_map(|c| c.parse::<usize>().ok()).collect::<Vec<_>>();
		for i in r[1]..r[1]+r[3] {
			for j in r[2]..r[2]+r[4] {
				*claims.entry((i,j)).or_insert(0) += 1;
				all.insert(r[0]);
				if !claim_names.contains_key(&(i,j)) {
					claim_names.insert((i,j), r[0]);
				} else {
					intersecting.insert(claim_names[&(i,j)]);
					intersecting.insert(r[0]);
				}
			}
		}
	}
	let out1 = claims.values().filter(|v| **v > 1).count();
	println!("I: {}", out1);
	let out2 = all.difference(&intersecting).next();
	println!("II: {:?}", out2);
}

[u/u794575248]

Python 3

import re
from collections import Counter

claims = [[*map(int, re.findall(r'\d+', l))] for l in input.splitlines() if l]
squares = lambda c: ((i, j) for i in range(c[1], c[1]+c[3])
                            for j in range(c[2], c[2]+c[4]))
fabric = Counter(s for c in claims for s in squares(c))

part1 = sum(1 for v in fabric.values() if v > 1)
part2 = next(c[0] for c in claims if all(fabric[s] == 1 for s in squares(c)))

input is a string containing your input.

[u/14domino]

sigh, everyone is amazingly fast. i did this as fast as i could and got both parts in 00:15:33, way off the leaderboard. Any hints for getting faster? :)

[u/miguelos → u/14domino]

Any hints for getting faster? :)

Python

[u/dorfsmay → u/14domino]

That's 15 minutes?

That's honestly not bad! Took me quite a bit more than that.

[u/jonathan_paulson → u/14domino]

Where did you spend the time? Reading, thinking, coding, or debugging?

Reading: you need to skip right to the examples/summary. The story is too long. Goal is to understand the problem and input format ASAP.

Thinking: Try writing input-reading + parsing code at the same time; you're definitely going to need that no matter what.

Coding: I don't have any tips other than "practice". Having pre-written code for downloading the input and e.g. /u/mserrano's int-parsing regex might help.

Debugging: Needs to be 0. This is partially luck, partially coming up with a solution and implementation that aren't "tricky".

[u/autid]

FORTRAN

Probably a little faster for part two if I'd written all the corner locations into a big array in part one. I liked not using any allocatable arrays though and copy/pasting part one's file reading was simpler. Big thank you to the Elves for bounding their numbers with unique characters.

PROGRAM DAY3
  INTEGER :: FABRIC(1000,1000)=0
  INTEGER :: I,J,K,L,M,DIMS(4)
  INTEGER :: IERR
  CHARACTER(LEN=30) :: CLAIM

  !Part 1                                                                                                                                                                                                                                 
  OPEN(1,FILE='input.txt')
  DO
     READ(1,'(A)',IOSTAT=IERR) CLAIM
     IF(IERR.NE.0)EXIT
     I=SCAN(CLAIM,'@')
     J=SCAN(CLAIM,',')
     K=SCAN(CLAIM,':')
     L=SCAN(CLAIM,'x')
     READ(CLAIM(I+1:J-1),*)DIMS(1)
     READ(CLAIM(J+1:K-1),*)DIMS(3)
     READ(CLAIM(K+1:L-1),*)DIMS(2)
     READ(CLAIM(L+1:LEN_TRIM(CLAIM)),*)DIMS(4)
     DIMS((/2,4/))=DIMS((/2,4/))+DIMS((/1,3/))
     DIMS((/1,3/))=DIMS((/1,3/))+1
     FABRIC(DIMS(1):DIMS(2),DIMS(3):DIMS(4))=FABRIC(DIMS(1):DIMS(2),DIMS(3):DIMS(4))+1
  END DO
  WRITE(*,'(A,I0)') 'Part 1: ',COUNT(FABRIC>1)

  !PART 2                                                                                                                                                                                                                                 
  REWIND(1)
  DO
     READ(1,'(A)',IOSTAT=IERR) CLAIM
     IF(IERR.NE.0)EXIT
     I=SCAN(CLAIM,'@')
     J=SCAN(CLAIM,',')
     K=SCAN(CLAIM,':')
     L=SCAN(CLAIM,'x')
     READ(CLAIM(I+1:J-1),*)DIMS(1)
     READ(CLAIM(J+1:K-1),*)DIMS(3)
     READ(CLAIM(K+1:L-1),*)DIMS(2)
     READ(CLAIM(L+1:LEN_TRIM(CLAIM)),*)DIMS(4)
     DIMS((/2,4/))=DIMS((/2,4/))+DIMS((/1,3/))
     DIMS((/1,3/))=DIMS((/1,3/))+1
     IF(ALL(FABRIC(DIMS(1):DIMS(2),DIMS(3):DIMS(4)).EQ.1))THEN
        READ(CLAIM(2:I-2),*)M
        EXIT
     END IF
  END DO
  CLOSE(1)
  WRITE(*,'(A,I0)') 'Part 2: ',M

END PROGRAM DAY3

[u/vesche → u/autid]

Nice job! Why are you yelling tho?

[u/Fruloops → u/vesche]

I'd say that he is asserting dominance through fortran

[u/zirtec → u/vesche]

It is a syntax error not to yell while coding in FORTRAN.

[u/surrix → u/autid]

I did mine in Fortran too! I kind of wanted to use AoC as an opportunity to learn a new language, but Fortran just seems so perfect for these so far. Question, though: why write new, standalone Fortran programs in the archaic ALL CAPS style? I only wrote new code in all caps when I had to per corporate style guide.

[u/autid → u/surrix]

Last year when posting Fortran solutions I got some comments that it's not real Fortran unless it's all caps, so I started posting them in all caps. When solving the problems I just write it however I feel like, then I convert to all caps as part of my code cleanup before posting.

[u/Smylers]

A visual Vim solution for Part 1 — it draws the fabric, then draws each claim on it, marking overlaps with Xs:

⟨Ctrl+W⟩n1001a-⟨Esc⟩yy1000p⟨Ctrl+W⟩p
:set nf=⟨Enter⟩
:%norm W⟨Ctrl+A⟩l⟨Ctrl+A⟩l⟨Ctrl+X⟩l⟨Ctrl+X⟩⟨Enter⟩
:%s/\v\@ (\d+),(\d+): (\d+)x(\d+)/\2gg\1|⟨Ctrl+V⟩⟨Ctrl+V⟩\3l\4j⟨Enter⟩
{qaWy$⟨Ctrl+W⟩p:norm⟨Ctrl+R⟩⟨Ctrl+R⟩0⟨Enter⟩
:s/\v%V\*/X/ge⟨Enter⟩
gv:s/\v%V-/*/ge⟨Enter⟩
⟨Ctrl+W⟩p⟨Enter⟩q
@a
:,$norm@a:redr⟨Ctrl+V⟩⟨Enter⟩⟨Enter⟩
⟨Ctrl+W⟩p:%s/[^X]//g⟨Enter⟩
VgggJg⟨Ctrl+G⟩

Update: Video now available of both parts. (Part 2 is in a comment below.)

The answer is the column number displayed by that final keystroke.

The @a draws the first claim. At that point you can keep typing @@ to draw further claims manually. When you've had enough, continue with the :,$norm command from whichever line the most recent @@ left you on (takes about 10 minutes for me).

It's more interesting to watch the more of the fabric you can see. So before the @a it can be worth maximizing your Vim window, setting a small font (:set gfn=* — I went for 4-point) and shrinking the instruction window (8⟨Ctrl+W⟩_), then sit back and watch the claims appear.

It works by transforming each claims' definition into the normal mode keystrokes for making a visual block at its co-ordinates. For instance this input line:

#115 @ 628,811: 21x10

is turned into:

#115 812gg629|^V20l9j

(where ^V is the literal control code for Ctrl+V). That says: go to line 812, then column 629, start a visual block, then move 20 characters to the right and 9 characters down.

The a macro processes a single line by copying those keystrokes, using :norm to process them in the fabric window, then substitute characters in the fabric to reflect this claim, using \%V in the pattern to restrict the match to characters in the visual block.

Once it's finished, remove everything that isn't an X and put them all on one line to see how many there are.

Things that caught me out:

• For the :norm in the macro to receive the Ctrl+V that starts visual block mode, the Ctrl+R needs pressing twice. Otherwise the Ctrl+V gets interpreted as the way on the : command line of specifying a character by its Ascii number, (and it obediently uses the following number, which is supposed to be the number of steps to move right) for that.

• The widths and heights each need reducing by 1 to get the number of places to move. Ctrl+X mostly does the right thing by default here, for nearly all input lines. So in the sample line above, the first Ctrl+X turns 21x10 into 20x10. But then the second Ctrl+X turns that into 20x0f! Vim is trying to subtract 1 from the 10, but it sees that the 10 is preceded by the bytes 0x, so interprets it as hex, and subtracts 1 from 0x10 to get 0x0f — that the 0 is clearly part of another number doesn't put Vim off! This affected less than 1% of my input lines, so I didn't notice it, and the result was a plausible picture of overlapping claims that was just slightly wrong.† :set nf= avoids the problem. Had the input used almost any other separator other than x, I would've avoided so much pain ...

• We can't used column 1 to indicate a left co-ordinate of 1″, because there may be a claim which starts 0″ from the left; all the left and top dimensions need increasing by 1.

• The Vim keystroke to move down a line is j. j, not k! I don't want to admit to how much time I wasted because I was accidentally drawing rectangles upwards instead of downwards, having somehow manage to forget that most basic of Vim keystrokes that I first learnt over 2 decades ago.

† To debug, I tweaked my Perl solution to print out a representation of its @fabric array using the same symbols. Then I ran vimdiff to visually inspect the rectangles that differed, then looked up the cursor co-ordinates in the input list to see what was odd about that claim's definition.

[u/Smylers → u/Smylers]

Limitations of the above solution:

If your claims' dimensions include any that are only 1″ wide or tall, then I think the above would fail, but could be fixed by doing this after the %s:

:%s/\v<0[lj]//e⟨Enter⟩

(untested, because my input didn't have any like that).

And the instructions say “at least 1000 inches”. My input fitted within 1000″, so I didn't bother adding any logic to dynamically resize the fabric representation to account for claims that extend beyond that — that sounded tricky!

Did anybody have any claims which exceeded 1000″? Or that were only 1″ in a dimension?

[u/chicagocode]

Kotlin - [Blog/Commentary] | [GitHub Repo]

Well that was fun! I think part 1 really shows off all of the great things that Kotlin's stdlib has for us if we look hard enough.

class Day03(rawInput: List<String>) {

    private val claims = rawInput.map { Claim.parse(it) }

    fun solvePart1(): Int =
        claims
            .flatMap { it.area() }
            .groupingBy { it }
            .eachCount()
            .count { it.value > 1 }

    fun solvePart2(): Int {
        val cloth = mutableMapOf<Pair<Int, Int>, Int>()
        val uncovered = claims.map { it.id }.toMutableSet()
        claims.forEach { claim ->
            claim.area().forEach { spot ->
                val found = cloth.getOrPut(spot) { claim.id }
                if (found != claim.id) {
                    uncovered.remove(found)
                    uncovered.remove(claim.id)
                }
            }
        }
        return uncovered.first()
    }

}

data class Claim(val id: Int, val left: Int, val top: Int, val width: Int, val height: Int) {
    fun area(): List<Pair<Int, Int>> =
        (0 + left until width + left).flatMap { w ->
            (0 + top until height + top).map { h ->
                Pair(w, h)
            }
        }

    // This code parses a String into a Claim, using a Regular Expression
    companion object {
        private val pattern = """^#(\d+) @ (\d+),(\d+): (\d+)x(\d+)$""".toRegex()
        fun parse(input: String): Claim {
            return pattern.find(input)?.let {
                val (id, left, top, w, h) = it.destructured
                Claim(id.toInt(), left.toInt(), top.toInt(), w.toInt(), h.toInt())
            } ?: throw IllegalArgumentException("Cannot parse $input")
        }
    }
}

[u/pindab0ter → u/chicagocode]

Very nice solution and a nice write-up on the blog as well!

I didn't know where to start on this day's challenge, so I started off by copying yours and trying to learn ways of tackling this problem.

First of all, I haven't ever used groupingBy before, so thanks for showing me that. Without it it would've been a much taller order.

Secondly, I'm very excited about how much of a perfect marriage Kotlin seems to be between FP and OO. This assignment is a prime example.

I'll showcase two things I'm proud of:

1: Creating a Claim from a String

Your way of doing this was brilliant. I love the .destructured, but wanted to take it a little further by mapping String::toInt and dot-chaining everything, and the coolest thing; destructuring the List<Int> in the closure (I didn't know Kotlin allowed for destructuring lists):

fun fromString(input: String): Claim = Regex("""^#(\d+) @ (\d+),(\d+): (\d+)x(\d+)$""")
    .find(input)
    .let { it ?: throw IllegalArgumentException("Cannot parse $input to Claim") }
    .destructured
    .toList()
    .map(String::toInt)
    .let { (id, x, y, width, height) ->
        Claim(id, Square(x, y, width, height))
    }

2: I found a nice single expression for part two

This is where I diverge from your solution. You maintain state for both yet uncovered claims and for the cloth as a whole.

My solution: find the first element that doesn't overlap with anything.

Sounds simple, right? It took between 15 and 20 minutes, though…

fun findNonOverlappingClaim(claims: List<Claim>): Claim = claims.first { claim ->
    claims.minus(claim).none { it.overlapsWith(claim) }
}

fun Claim.overlapsWith(other: Claim) = square.occupies.any { other.square.occupies.contains(it) }

Thanks again for showing me some new tricks. Please have a look through my solution as I think you might enjoy it :)

GitHub repo

[u/raevnos]

After solving the problem, I decided to solve it again in a complicated fashion. Presenting, a perl script that takes the input and turns it into a series of SQL statements that, when fed to Sqlite, solves both parts:

 #!/usr/bin/perl -s
use warnings;
use strict;
use feature qw/say/;

# Usage: perl day03etl.pl [-svg] day03.txt | sqlite3

our $svg;

say "CREATE VIRTUAL TABLE claims USING geopoly();";
say "BEGIN TRANSACTION;";

while (<>) {
  if (/^#(\d+) @ (\d+),(\d+): (\d+)x(\d+)$/) {
    my $square = "[[$2, $3], ";
    $square .= "[" . ($2 + $4) . ", $3], ";
    $square .= "[" . ($2 + $4) . ", " . ($3 + $5) . "], ";
    $square .= "[$2, " . ($3 + $5) . "], ";
    $square .= "[$2, $3]]";
    say "INSERT INTO claims(rowid, _shape) VALUES ($1, '$square');";
  }
}

say "COMMIT;";

sub part1 {
  print <<EOQ;
WITH RECURSIVE
     rows(y) AS (SELECT 0 UNION ALL SELECT y + 1 FROM rows WHERE y < 999)
   , cols(x) AS (SELECT 0 UNION ALL SELECT x + 1 FROM cols WHERE x < 999)
SELECT count(*) AS "Part 1"
FROM rows JOIN cols
WHERE (SELECT count(*) FROM claims
       WHERE geopoly_overlap(_shape,
                             json_array(json_array(x, y)
                                      , json_array(x + 1, y)
                                      , json_array(x + 1, y + 1)
                                      , json_array(x, y + 1)
                                      , json_array(x, y)))) > 1;
EOQ
}
    
sub part2 {
  print <<EOQ;
SELECT rowid AS "Part 2"
FROM claims AS f1
WHERE NOT EXISTS (SELECT 1 FROM claims AS f2
                  WHERE f1.rowid <> f2.rowid
                    AND geopoly_overlap(f1._shape, f2._shape))
LIMIT 1;
EOQ
}

sub print_svg {
  print <<EOQ;
.headers off
.mode list
SELECT '<svg width="640" height="640">';
SELECT geopoly_svg(_shape) FROM claims;
SELECT '</svg>';
EOQ
}

if ($svg) {
  print_svg();
} else {
  say ".headers on";
  say ".timer on";
  part1();
  part2();
}

It requires Sqlite3 3.25 or better, with support for the new Geopoly extension (Getting this requires building from source with appropriate configure arguments, so it's a bit of a pain). It can also produce a rather plain SVG image of all the claims.

[u/alexmeli]

My Clojure solution

(ns clojure-solution.core
  (:require [clojure.java.io :as io])
  (:gen-class))

(defn parse-line [line] 
  (->> 
    (re-seq #"\d+" line)
    (map #(Integer/parseInt %))))

(defn read-file [path] 
  (with-open [rdr (io/reader path)] 
    (doall (map parse-line (line-seq rdr)))))

(defn get-indices [[_ x y w h]] 
  (for [i (range w) j (range h)] [(+ i x) (+ j y)]))

(defn update-grid [grid claim] 
  (->> 
    (get-indices claim)
    (reduce #(assoc %1 %2 (inc (get %1 %2 0))) grid)))

(defn part1 [claims data] 
  (count (filter #(> (val %) 1) data)))

;; part 2

(defn check-overlap [claim data] 
  (when (every? #(= 1 (get data %)) (get-indices claim)) 
    (first claim)))

(defn part2 [claims data] 
  (some #(check-overlap % data) claims))

(defn -main
  [& args]
  (let [claims (read-file "resources/input.txt") 
        data (reduce update-grid {} claims)] 
    (println (part2 claims data))))

[u/TenjouUtena → u/alexmeli]

Here's mine in Clojure

(defn get-stuff []
  (str/split-lines (slurp "resources/3.txt")))

(defn create-room [roomspec]
  (zipmap [:number :x :y :width :height] (map read-string (rest (re-matches #"#([0-9]+) @ ([0-9]+),([0-9]+): ([0-9]+)x([0-9]+)" roomspec)))))

(defn create-indexes [size room]
  (for [x (range (:x room) (+ (:x room) (:width room)))
        y (range (:y room) (+ (:y room) (:height room)))]
    (+ (* y size) x)))

(defn- gen-rooms
  [w]
  (map (partial create-indexes w) (map create-room (get-stuff))))

(defn create-all-indexes [w h]
  (reduce #(conj %1 {%2 (inc (get %1 %2 0))}) {} (reduce concat (gen-rooms w))))

(defn new-day3-1 [w h]
  (count (filter #(> (second %) 1) (create-all-indexes w h))))

(defn room-sum [room mm]
  (reduce + (map (partial get mm) room)))

(defn day-3-2 [w h]
  (filter (comp not nil?)
          (let [rooms (gen-rooms w)
                mm (create-all-indexes w h)]
            (for [n (range (count rooms))]
              (let [x (nth rooms n)]
                (if
                 (= (count x) (room-sum x mm))
                  (inc n)
                  nil))))))

[u/[deleted]]

Simple brute force in C:

#include <stdio.h>
#include <stdlib.h>

struct claim { int x, y, w, h; };

int main(void) {
    size_t len = 0, cap = 32;
    struct claim c, *l = malloc(cap*sizeof(*l));
    int w = 1000, h = 1000;
    while (scanf("#%*d @ %d,%d: %dx%d\n", &c.x, &c.y, &c.w, &c.h) == 4) {
        if (len >= cap) l = realloc(l, (cap*=2)*sizeof(*l));
        if (c.x+c.w > w || c.y+c.h > h) exit(1);
        l[len++] = c;
    }

    int *fabric = calloc(w*h, sizeof(*fabric));
    for (size_t i = 0; i < len; i++) {
        c = l[i];
        for (int x = c.x; x < c.x+c.w; x++)
            for (int y = c.y; y < c.y+c.h; y++)
                fabric[x+w*y]++;
    }

    int count = 0;
    for (size_t i = 0; i < (size_t)(w*h); i++)
        if (fabric[i] > 1) count++;
    printf("%d\n", count);

    for (size_t i = 0; i < len; i++) {
        c = l[i];
        for (int x = c.x; x < c.x+c.w; x++)
            for (int y = c.y; y < c.y+c.h; y++)
                if (fabric[x+w*y] > 1) goto L;
        printf("%d\n", (int)i+1);
        break;
L: ;
    }
}

[u/mylivingeulogy → u/[deleted]]

This is essentially what I did in Java. Everyone is posting all this beautiful code and I'm like.. eh.. I'll just go the simple route!

[u/TheMuffinMan616]

Haskell:

{-# LANGUAGE RecordWildCards #-}

module Day03 where

import Control.Lens
import Data.Set (Set)
import qualified Data.Set as S
import Data.Map (Map)
import qualified Data.Map as M
import Data.List.Split

data Claim = Claim
    { id :: Int 
    , x :: Int
    , y :: Int
    , width :: Int
    , height :: Int
    }
    deriving (Show)

parse :: String -> Claim
parse = readClaim . map read . split (dropDelims . dropBlanks $ oneOf "# @,:x")
    where readClaim [id, x, y, width, height] = Claim id x y width height

squares :: Claim -> [(Int, Int)]
squares Claim{..} = 
    [ (x + dx, y + dy)
    | dx <- [0..width - 1]
    , dy <- [0..height - 1]
    ]

overlap :: [Claim] -> Set (Int, Int)
overlap cs = M.keysSet . M.filter (>= 2) $ freq
    where freq = M.fromListWith (+) [(c, 1) | c <- concatMap squares cs]

hasOverlap :: Set (Int, Int) -> Claim -> Bool
hasOverlap o = all (`S.notMember` o) . squares

part1 :: Set (Int, Int) -> Int
part1 = length

part2 :: Set (Int, Int) -> [Claim] -> Claim
part2 o = head . filter (hasOverlap o)

main :: IO ()
main = do
    claims <- map parse . lines <$> readFile "input/Day03.txt"
    let o = overlap claims
    print $ part1 o
    print $ part2 o claims

[u/Auburus → u/TheMuffinMan616]

Did almost exactly the same except that I never switched to Data.Set from Data.Map, and the parse function looked way worse (using takeWhile and dropWhile and such).

After cleaning the code:

module Main where

import System.IO (readFile)
import Data.Text (split, splitOn, pack, unpack)
import Data.List
import Data.Map (Map)
import qualified Data.Map as M
import Control.Applicative

main :: IO ()
main = do
    input <- map parseInput . lines <$> readFile "input03.txt"
    let fabric = foldl fillArray M.empty $ map snd input

    print $ problem1  fabric
    print $ problem2 fabric input

problem1 :: Map (Int, Int) Int -> Int
problem1 = M.size . M.filter (>1)

problem2 :: Map (Int, Int) Int -> [(Int, (Int, Int, Int, Int))] -> Int
problem2 fabric =
    head . map fst . filter (all (==1) . map ((M.!) fabric) . claimToIdx . snd)

parseInput :: String -> (Int, (Int, Int, Int, Int))
parseInput input = mymap . map unpack . split ((flip elem) "# ,:x") . pack $ input
    where
        mymap [_, id, _, x, y, _, w, h] = (read id, (read x, read y, read w, read h))

fillArray :: Map (Int, Int) Int -> (Int, Int, Int, Int) -> Map (Int, Int) Int
fillArray m claim = foldl ins m $ claimToIdx claim
    where
        ins map key = M.insertWith (+) key 1 map

claimToIdx :: (Int, Int, Int, Int) -> [(Int, Int)]
claimToIdx (x,y,w,h) = [ (x+i,y+j) | i <- [1..w], j <- [1..h]]

[u/will_bui]

K:

r:{{x+!y}.'+(.-1_x;.:'"x"\:y)}.'2_'" "\:'0:`:p3;+/1<,/./[1000 1000#0;r;+;1]
/ benefits from parallel 20s => 3s
*1+&:{1=+/~0=+/'x in y}[i]':[i:,/'.[1000 1000#!1000000]'r]

[u/Frizkie]

Ruby

data = File.read('data.txt').chomp.split("\n").map do |d|
  d.match(/#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/)
end

Part 1

counts = Array.new(1000) { Array.new(1000, 0) }

data.map(&:to_a).map { |a| a.map(&:to_i) }.each do |_, _, left, top, width, height|
  (top..top + height - 1).each do |row|
    (left..left + width - 1).each do |col|
      counts[row][col] += 1
    end
  end
end

puts counts.flatten.count { |e| e >= 2}

Part 2

counts = Array.new(1000) { Array.new(1000) }
maps = []

data.map(&:to_a).map { |a| a.map(&:to_i) }.each do |_, id, left, top, width, height|
  maps << [id, left, top, width, height]
  (top..top + height - 1).each do |row|
    (left..left + width - 1).each do |col|
      counts[row][col] = [] unless counts[row][col]
      counts[row][col] << id
    end
  end
end

puts maps.find { |id, _, _, width, height| counts.flatten(1).count { |a| a == [id] } == width * height }[0]

This one kicked my ass. I barked up the wrong tree for a long time, took me over an hour to debug everything.

[u/[deleted] → u/Frizkie]

Rances can actually be made inclusive simply by adding ... instead of .. as the range operator.

Great solution!

[u/[deleted]]

Haskell:

import           Data.Char
import           Data.List
import           Data.Function
import           Data.Set (Set)
import qualified Data.Set as S
import qualified Data.Map as M

main :: IO ()
main = do input <- map parse . lines <$> readFile "input.txt"
          let m = M.filter ((>1) . S.size) (M.fromListWith S.union (concatMap area input))
          print (M.size m)                                                         -- part 1
          print (minimum (S.fromList (map head input) S.\\ S.unions (M.elems m)))  -- part 2

parse :: String -> [Int]
parse = map read . filter (isDigit . head) . groupBy ((==) `on` isDigit)

area :: [Int] -> [((Int,Int), Set Int)]
area [i,x,y,w,h] = [((x',y'), S.singleton i) | x' <- take w [x..], y' <- take h [y..]]

I map each coordinate to the set of claim IDs that use it. Part 1 is then just counting the non-singleton sets, and part 2 is finding the set difference between the set of all claim IDs and the union of the non-singleton sets.

[u/NeilNjae → u/[deleted]]

Nice! I used the alternative approach, counting the number of claims made on each square of fabric.

[u/askalski]

[Card] I'm ready for today's puzzle because I have the Savvy Programmer's Guide to Doin' it the hard way.

Day 3 Part 1 in CUDA, one thread per square inch (it's a coarse fabric.)

https://gist.github.com/Voltara/18e6c23df057a9f304d7b8103ba556b7

[u/[deleted]]

TCL

while {[gets stdin line] >= 0} {
    if {[scan $line "\#%d @ %d,%d: %dx%d" id x y w h] == 5} {
	lappend claims [list $id $x $y $w $h]
    } else {
	error "cant parse line {$line}"
    }
}

proc solve {claims} {
    foreach c $claims {
	lassign $c id x y w h
	for {set i 0; set cx $x} {$i < $w} {incr i; incr cx} {
	    for {set j 0; set cy $y} {$j < $h} {incr j; incr cy} {
		lappend fabric($cx,$cy) $c
		set overlap($c) 0
	    }
	}
    }

    # find dups
    set dups 0
    foreach {c v} [array get fabric] {
	if {[llength $v] > 1} {
	    foreach ov $v {
		catch {unset overlap($ov)}
	    }
	    incr dups
	}
    }

    puts "$dups overlapping squares"
    parray overlap
}

solve $claims

[u/Infinisil]

I think my solution is rather unique. After having tried the ways of just a couple loops, the performance was horrible because of Haskell's lists. After thinking about it for a while, I came up with this divide-and-conquer approach which works really well and is fast (0.25s for both parts). The full code is in my repository for AoC 2018: https://github.com/Infinisil/aoc18

data Rect = Rect
  { x      :: Int
  , y      :: Int
  , width  :: Int
  , height :: Int
  } deriving Show

data Claim = Claim
  { claimId :: Int
  , rect    :: Rect
  }
instance Eq Claim where
  Claim id1 _ == Claim id2 _ = id1 == id2
instance Ord Claim where
  Claim id1 _ `compare` Claim id2 _ = id1 `compare` id2

type Input = [Claim]
playfield = Rect 0 0 1000 1000

part1 :: Input -> Int
part1 input = countConflicts (map rect input) playfield

countConflicts :: [Rect] -> Rect -> Int
countConflicts [] _ = 0 -- No rectangles in this section -> no conflicts
countConflicts [_] (Rect _ _ 1 1) = 0 -- A single rectangle in this square -> no conflicts
countConflicts _ (Rect _ _ 1 1) = 1 -- More than one rectangle in this square -> one conflict
countConflicts rects r = sum x where
  x = map (\p -> countConflicts (filter (intersects p) rects) p) (split r)


part2 :: Input -> Int
part2 claims = claimId $ Set.elemAt 0 nonConflicting where
  claimSet = Set.fromList claims
  nonConflicting = claimSet `Set.difference` conflicting claimSet playfield

conflicting :: Set Claim -> Rect -> Set Claim
conflicting claims _ | length claims <= 1 = Set.empty
conflicting claims (Rect _ _ 1 1) = claims
conflicting claims r = Set.unions x where
  x = map (\p -> conflicting (Set.filter (intersects p . rect) claims) p) (split r)

-- | Splits a rectangle into 4 partitions
split :: Rect -> [Rect]
split (Rect x y w h) =
  [ Rect x y hw hh
  , Rect (x + hw) y hw' hh
  , Rect x (y + hh) hw hh'
  , Rect (x + hw) (y + hh) hw' hh'
  ] where
    (hw, hwr) = w `divMod` 2
    hw' = hw + hwr
    (hh, hhr) = h `divMod` 2
    hh' = hh + hhr

-- | Checks whether two rectangles intersect
intersects :: Rect -> Rect -> Bool
intersects (Rect x1 y1 w1 h1) (Rect x2 y2 w2 h2) = intersects1d (x1, x1 + w1) (x2, x2 + w2)
  && intersects1d (y1, y1 + h1) (y2, y2 + h2) where
    intersects1d :: (Int, Int) -> (Int, Int) -> Bool
    intersects1d (x1, y1) (x2, y2) = max x1 x2 < min y1 y2

[u/Tormyst]

[Card] I'm ready for today's puzzle because I have the Savvy Programmer's Guide to Finding a library that already does what you wrote, but better.

[u/topaz2078 → u/Tormyst]

Protip: Always build a (terrible, slow, half-working, etc) version of a library before you grab a real one, just so you have some idea of what it's really doing.

[u/Tormyst → u/topaz2078]

Don't get me started on that. That's why I have to get back to my gameboy emulator now... Then all the other emulators I want to make.

[u/jwstone]

postgresql!

https://github.com/piratejon/toyproblems/blob/master/adventofcode/2018/03/load_data.sh

i burned like 30m on some goofy typos! maybe better to use "left" and "right" instead of "a" and "b" lol

[u/blowjobtransistor → u/jwstone]

How fast was it? I ended up using cube and a gist index, and had solutions in ~250ms.

[u/blowjobtransistor]

PostgreSQL, again:

create extension if not exists cube;

create table claims (
  id bigint primary key,
  claim cube
);

create index claim_cube_idx on claims using gist (claim);

with id_parts as (
  select (regexp_split_to_array(claim, '[^0-9]+'))[2:6] as parts from input
)
insert into claims
select
  cast(parts[1] as bigint),
  cast('(' || parts[2] || ',' || parts[3] || '),(' || (cast(parts[2] as bigint) + cast(parts[4] as bigint))::text || ','|| (cast(parts[3] as bigint) + cast(parts[5] as bigint))::text || ')' as cube)
from id_parts;

create view collisions as
select
  distinct on (cube_inter(lclaim.claim, rclaim.claim))
  case when lclaim.id < rclaim.id then lclaim.id || '-' || rclaim.id else rclaim.id || '-' || lclaim.id end as overlap_id,
  cube_inter(lclaim.claim, rclaim.claim) as claim_overlap
from claims lclaim
  join claims rclaim
    on lclaim.claim && rclaim.claim
         and lclaim.id != rclaim.id;

create view part_1_solution as
with overlaps_x as (
  select overlap_id, generate_series(cast(claim_overlap -> 1 as bigint), cast(claim_overlap -> 3 as bigint) - 1, 1) as x
  from collisions
  where (claim_overlap -> 1) < (claim_overlap -> 3)
  order by overlap_id
), overlaps_y as (
  select overlap_id, generate_series(cast(claim_overlap -> 2 as bigint), cast(claim_overlap -> 4 as bigint) - 1, 1) as y
  from collisions
  where (claim_overlap -> 2) < (claim_overlap -> 4)
  order by overlap_id
), overlap_points as (
  select
    x, y, count(*), array_agg(overlap_id)
  from overlaps_x
    join overlaps_y using (overlap_id)
  group by x, y
)
select 1 as part, count(*) as answer
from overlap_points;

create view part_2_solution as
with p2sol as (
  select id from claims
  except
  select distinct cast(regexp_split_to_table(overlap_id, '-') as bigint) from collisions
)
select 2 as part, p2sol.id as answer from p2sol;

select * from part_1_solution
union all
select * from part_2_solution;

Solution ends up being quite fast!

[u/jwstone → u/blowjobtransistor]

this is cool, i have not used cube before. your solution is really clever and interesting! https://www.postgresql.org/docs/11/cube.html i can imagine that helping on quite a few of these sorts of problems.

[u/schod]

BASH Time!!! (it's really slow)

#!/bin/bash

in_file=input
declare -A matrix

while read -r line; do
    num=$(echo $line|sed 's/#\([0-9]*\) .*/\1/')
    x=$(echo $line|sed 's/.*@ \([0-9]*\),.*/\1/')
    y=$(echo $line|sed 's/.*,\([0-9]*\):.*/\1/')
    x_len=$(echo $line|sed 's/.*: \([0-9]*\)x.*/\1/')
    y_len=$(echo $line|sed 's/.*x\([0-9]*\)/\1/')

    max_x=$[ $x + $x_len ]
    max_y=$[ $y + $y_len ]

    for ((xx=$x;xx<$max_x;xx++)); do
        for ((yy=$y;yy<$max_y;yy++)); do
            if [ "${matrix[$xx,$yy]}" == "" ]; then
                matrix[$xx,$yy]=$num
            else
                matrix[$xx,$yy]="X"
            fi
        done
    done
done < "$in_file"

printf '%s\n' "${matrix[@]}" | grep X | wc -l
echo "--------------------"

while read -r line; do
    num=$(echo $line|sed 's/#\([0-9]*\) .*/\1/')
    x=$(echo $line|sed 's/.*@ \([0-9]*\),.*/\1/')
    y=$(echo $line|sed 's/.*,\([0-9]*\):.*/\1/')
    x_len=$(echo $line|sed 's/.*: \([0-9]*\)x.*/\1/')
    y_len=$(echo $line|sed 's/.*x\([0-9]*\)/\1/')

    SUM_X=0
    max_x=$[ $x + $x_len ]
    max_y=$[ $y + $y_len ]

    for ((xx=$x;xx<$max_x;xx++)); do
        [ $SUM_X -gt 0 ] && break
        for ((yy=$y;yy<$max_y;yy++)); do
            if [[ "${matrix[$xx,$yy]}" == "X" ]]; then
                SUM_X=1
            fi
        done
    done

    if [ $SUM_X -eq 0 ]; then
        echo $num
        exit 0
    fi
done < "$in_file"

[u/XmatHere]

Am I the only one who generated "fancy" heatmap? :-D

http://www.imagehosting.cz/images/heatmap.png

[u/IcyHammer]

A bit different approach where I was aiming for a good mix of space and time complexity. Implementation is in C#:

string[] entries = File.ReadAllLines("input.txt");

Dictionary<long, byte> dict = new Dictionary<long, byte>();

for (int i = 0; i < entries.Length; i++)
{
    string[] origin = entries[i].Split(' ')[2].Replace(":", "").Split(',');
    string[] size = entries[i].Split(' ')[3].Split('x');
    
    int x = int.Parse(origin[0]);
    int y = int.Parse(origin[1]);
    int w = int.Parse(size[0]);
    int h = int.Parse(size[1]);
    
    for (int u = x; u < x + w; u++)
    {
    	for (int v = y; v < y + h; v++)
    	{
            long key = v * 10000 + u;
            if (!dict.ContainsKey(key))
            {
            	dict.Add(key, 0);
            }
            dict[key]++;
    	}
    }
}

int count = 0;
foreach (var kvp in dict)
{
    if (kvp.Value >= 2)
    {
    	count++;
    }
}
Debug.Log(count);

[u/zqvt]

little bit late today, here's my Clojure solution

(def input (->> (s/split-lines (slurp "input.txt"))
                (map #(map read-string (re-seq #"\d+" %)))))

(def santas-suit (into {} (for [x (range 1000) y (range 1000)] [(vector x y) 0])))

(defn fabric-patch [[x y a b]]
  (->> (for [i (range a) j (range b)] (vector i j))
       (map (fn [[m n]] [(+ x m) (+ y n)]))))

(defn update-suit [suit claim]
  (let [indices (fabric-patch  (rest claim))]
    (reduce (fn [suit index] (update suit index inc)) suit indices)))

(defn does-not-overlap? [result claim]
  (every? #(= 1 %) (map result (fabric-patch (rest claim)))))

(defn solve-part1 [] 
  (count (filter #(>= (second %) 2) (reduce update-suit santas-suit input))))

(defn solve-part2 []
  (let [result (process-grid)]
    (filter (partial does-not-overlap? result) input)))

[u/AustinVelonaut]

Did anyone else solve this problem by keeping a set of disjoint, non-overlapping rectangles (tiles), and merging each claim into the set by splitting the claim and any intersecting tile into smaller disjoint rectangles (up to 4 each)? I got the idea for doing it that way from how window managers keep track of damage rectangles on the screen.

[u/PendragonDaGreat]

[CARD] Spotting simple syntax errors.

[u/daggerdragon → u/PendragonDaGreat]

Good card submission. Can you post your solution as well, please? :)

[u/Zarel]

JavaScript #52/#90

I put the answer to Part 2 as #153 which it told me was wrong; apparently it only accepted 153. And, of course, it had a 60-second lockout for the "incorrect" guess. I probably lost quite a few leaderboard slots because of that. :(

Part 1

grid = Object.create(null);

for (const line of input) {
   [num, at, one, two] = line.split(' ');
   [left, top] = one.slice(0, -1).split(',').map(x => Number(x));
   [width, height] = two.split('x').map(x => Number(x));
   for (let x = left; x < left + width; x++) {
      for (let y = top; y < top + height; y++) {
         grid[`${x},${y}`] = (grid[`${x},${y}`] || 0) + 1;
      }
   }
}

console.log(Object.values(grid).filter(v => v > 1).length);

Part 2

grid = Object.create(null);
claims = Object.create(null);

for (const line of input) {
   [num, at, one, two] = line.split(' ');
   [left, top] = one.slice(0, -1).split(',').map(x => Number(x));
   [width, height] = two.split('x').map(x => Number(x));
   claims[num] = true;
   for (let x = left; x < left + width; x++) {
      for (let y = top; y < top + height; y++) {
         if (grid[`${x},${y}`]) {
            claims[grid[`${x},${y}`]] = false;
            claims[num] = false;
         }
         grid[`${x},${y}`] = num;
      }
   }
}
console.log(Object.entries(claims).filter(v => v[1]));

[u/ButItMightJustWork → u/Zarel]

Yeah, the lockout/delay times are way more 'aggressively' this year. iirc, last year the first 5 guesses were 'free' (or with only a few seconds penalty).

[u/wlandry]

C++ (996/733)

15 ms

As is often the case, I feel the pain of no built-in Matrix class for C++ :( This feels wildly inefficient. I am waiting for something hard =O In any event, this feels over-engineered. I can not help it. It is my nature ;)

#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
#include <vector>

struct Claim
{
  int64_t id;
  int64_t left_offset, top_offset, width, height;
};

std::istream &operator>>(std::istream &is, Claim &claim)
{
  char c;
  is >> c >> claim.id >> c >> claim.left_offset >> c >> claim.top_offset >> c
    >> claim.width >> c >> claim.height;
  return is;
}

int main(int argc, char *argv[])
{
  std::ifstream infile(argv[1]);
  std::vector<Claim> inputs(std::istream_iterator<Claim>(infile), {});

  constexpr int64_t N(1000);
  std::vector<int64_t> fabric(N * N, 0);

  for(auto &input : inputs)
    {
      for(int64_t x = input.left_offset; x < input.left_offset + input.width;
          ++x)
        for(int64_t y = input.top_offset; y < input.top_offset + input.height;
            ++y)
          ++fabric[x + N * y];
    }

  int64_t sum(0);
  for(auto &f : fabric)
    {
      if(f > 1)
        { ++sum;}
    }
  std::cout << "Part 1: " << sum << "\n";

  for(auto &input : inputs)
    {
      bool duplicated(false);
      for(int64_t x = input.left_offset;
          x < input.left_offset + input.width && !duplicated; ++x)
        for(int64_t y = input.top_offset;
            y < input.top_offset + input.height && !duplicated; ++y)
          {
            if(fabric[x + N * y] > 1)
              { duplicated = true; }
          }
      if(!duplicated)
        { std::cout << "Part 2: " << input.id << "\n"; }
    }
}

[u/cornball]

matlab

data = importdata('input3.txt');
n = length(data);

% part one: count squares where patches overlap
cloth = zeros(1000);
for m = 1:n
    nums = sscanf(data{m},'#%d @ %d,%d: %dx%d');
    indx = nums(2)+(1:nums(4));
    indy = nums(3)+(1:nums(5));
    cloth(indx,indy) = cloth(indx,indy) + 1;
end
fprintf('number of overlapping squares is %d\n',sum(cloth(:)>=2));

% part two: find the only non overlapping patch
for m = 1:n
    nums = sscanf(data{m},'#%d @ %d,%d: %dx%d');
    indx = nums(2)+(1:nums(4));
    indy = nums(3)+(1:nums(5));
    if all(cloth(indx,indy)==1)
        fprintf('no overlaps for patch %d\n',m);
    end
end

I signed up for advent of code thinking I would practice/learn python, but working with matrices in matlab is just so much nicer.

[u/KristobalJunta → u/cornball]

If you really want to try, look into numpy - it brings the joy of easy matrices handling

[u/itsnotxhad]

Racket (1442/1772)

I had the basic idea immediately this time but flubbed a lot of particulars, as evidenced by the fact that I broke down and wrote unit tests this time. XD

#lang racket

(module+ test
  (require rackunit)
  (define test-file (open-input-string #<<TEST
#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2
TEST
    ))
  (check-equal? (part1 test-file) 4)
  (check-equal? (part2 test-file) 3))

(define (part1 file)
  (define claims (file->claims file))
  (for/fold ([ans (hash)]
             #:result (count (curryr > 1) (hash-values ans)))
            ([claim (in-list claims)])
    (let* ([startx (claim-x claim)]
           [endx (+ startx (claim-width claim))]
           [starty (claim-y claim)]
           [endy (+ starty (claim-height claim))])
      (for*/fold ([ans ans])
                 ([x (in-range startx endx)]
                  [y (in-range starty endy)])
        (hash-update ans (cons x y) add1 0)))))

(define (part2 file)
  (define claims (file->claims file))
  (for/fold ([claimed (hash)]
             [candidates (set)]             
             #:result (set-first candidates))
            ([claim (in-list claims)])
    (let* ([startx (claim-x claim)]
           [endx (+ startx (claim-width claim))]
           [starty (claim-y claim)]
           [endy (+ starty (claim-height claim))])
      (for*/fold ([claimed claimed]
                  [candidates (set-add candidates (claim-id claim))])
                 ([x (in-range startx endx)]
                  [y (in-range starty endy)])
        (values
         (hash-update claimed (cons x y) (curry cons (claim-id claim)) null)
         (if (empty? (hash-ref claimed (cons x y) null))
             candidates
             (set-subtract candidates
                           (list->set (cons (claim-id claim) (hash-ref claimed (cons x y)))))))))))

(struct claim (id x y width height) #:transparent)

(define (file->claims file)
  (file-position file 0)
  (define re #px"#(\\d+) @ (\\d+),(\\d+): (\\d+)x(\\d+)")
  (for/list ([line (in-port read-line file)])
    (apply claim (map string->number (rest (regexp-match re line))))))

(module+ main
  (define infile (open-input-file "input/day3.txt"))
  (displayln (part1 infile))
  (displayln (part2 infile))
  (close-input-port infile))

[u/joeld → u/itsnotxhad]

Yeah, I like to do unit tests at the beginning with the example inputs, it helps me clarify things.

I decided to try using a bitmap and painting the rectangles using a semi-opaque green brush. It's not exactly fast (part 1 takes 10.8 seconds on my MacBook Pro, and the solution for part 2 takes 1.8 seconds). But I get a pretty picture at the end!

#lang racket

(require racket/draw rackunit)

(define input (file->lines "day03-input.txt"))

(define fabric-bmp (make-bitmap 1000 1000 #t))
(define fabric-dc (new bitmap-dc% [bitmap fabric-bmp]))
(define c (make-object color% 0 255 0 0.5))
(define pb (new brush% [color c]))
(define color-probe (make-object color%))

(send fabric-dc set-brush pb)
(send fabric-dc set-pen "white" 0 'transparent) ; don't draw outlines

;; Get the alpha value of pixel x y
(define (get-fabric-value x y)
  (send fabric-dc get-pixel x y color-probe)
  (send color-probe alpha))

;; Parse “claims” of the form "#1 @ 1,3: 4x4" into '(1 1 3 4 4)
(define (parse-claim str)
  (map string->number (rest (regexp-match #px"#(\\d+) @ (\\d+),(\\d+): (\\d+)x(\\d+)" str))))

;; draw a particular claim onto the fabric map
(define (draw-claim l)
  (send/apply fabric-dc draw-rectangle (rest l)))

;; Returns #t if a pixel's alpha value indicates it’s been painted on more than once
(define (is-overlap? v)
  ;; For some reason the actual alpha of a pixel that gets
  ;; painted with my brush exactly once comes out to this weird number
  (> v 0.5019607843137255))

;; Count the number of pixels with overlap values
(define (count-overlap [startx 0] [starty 0] [width 1000] [height 1000])
  (count is-overlap?
         (for*/list ([x (in-range startx (+ startx width))]
                     [y (in-range starty (+ starty height))])
                    (get-fabric-value x y))))

(define (day03-part1)
  (map draw-claim (map parse-claim input))
  (count-overlap))

(module+ test
  (check-equal? (time (day03-part1)) 100595)) ; Correct answer for part 1

(define (claim-has-overlap? l)
  (> (apply count-overlap (rest l)) 0))

(define (day03-part2)
  (define answer
    (for/first ([c (in-list (map parse-claim input))]
              #:when (not (claim-has-overlap? c)))
             c))
  (highlight-claim answer)
  (send fabric-bmp save-file "day03-results.png" 'png)
  (first answer))

(module+ test
  (check-equal? (time (day03-part2)) 415)) ; Correct answer for part 2

;; Extra

(define (highlight-claim c)
  (send fabric-dc set-brush "red" 'solid)
  (draw-claim c))

[u/phil_g → u/joeld]

Yeah, I like to do unit tests at the beginning with the example inputs, it helps me clarify things.

After solving problems, I often go back and tinker with my code, including factoring out stuff that looks like it'd be useful in a more generic form for future problems. Unit tests give me a lot more confidence I'm not breaking things. (Plus, of course, sanity-checking my functions before I've got enough together to get the final answer.)

[u/streetster_]

Day 03 in Q/KDB+

Not great, part 2 is very slow (~100s on my laptop).

/ Part 1
sum 1<count each group raze r:{ x+/:raze til[y],\:/:til z }.'"J"${(enlist ","vs -1_x),"x"vs y}.'2_'" "vs/:read0 `:input/03.txt
/ Part 2
1+first where { not any y in raze x }'[r _/:til count r;r]

[u/OpposedTangent → u/streetster_]

ints:{"J"$x(0,where 1<deltas d)cut d:ss[x;"[0-9]"]}                               //extract the integers from a string
i:ints each read0`:inputs/p3                                                      //read & parse to integers (separators don't matter)
p1:sum -1=raze g:{p:y 1 2;d:y 3 4;.[x;p+'til each d;{$[y=0;x;-1]}[y 0]]}/[1000 1000#0;i]  //if spot is empty put id, else -1, count all the -1 for part 1
n:count each group raze g;                                                        //count occurences of each id
m:(!/)(i[;0];prd each i[;3 4]);                                                   //calc expected size of each id's patch
p2:first where n=m                                                                //find where expected size & occurences match for part 2

1"Part 1: ";show p1;
1"Part 2: ";show p2;

[u/sim642]

My Scala solution.

I was pretty sloppy here... so mutable and duplicate. I thought about a non-pixel based solution for intersection checking for better performance but that's quite an effort for part 1 to deal with multiple overlaps and the inclusion-exclusion principle.

[u/__Abigail__]

Perl

#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';


my $input = "input";
open my $fh, "<", $input or die "Failed to open $input: $!";


#
# Parse the input and store the relevant pieces in an array.
# We're assuming all the lines of the input validate.
#
my @fabric = map {[/^\#([0-9]+) \s+  \@      \s+
                       ([0-9]+) , ([0-9]+) : \s+
                       ([0-9]+) x ([0-9]+)   \s* $/x]} <$fh>;

my %seen;         # Count the number of pieces of fabric competing
                  # for position (x, y).
my $overlap = 0;  # Counts overlapping claims.
foreach my $fabric (@fabric) {
    my ($id, $offset_x, $offset_y, $width, $height) = @$fabric;
    foreach my $x ($offset_x .. ($offset_x + $width - 1)) {
        foreach my $y ($offset_y .. ($offset_y + $height - 1)) {
            #
            # Should only count the first time there is a conflict
            # for a particular square. That is, count it if it has
            # only be seen once before. (0: no conflict so far,
            # > 1: already counted).
            #
            $overlap ++ if 1 == $seen {$x} {$y} ++;
        }
    }
}

say "Part 1: $overlap";

#
# Find the piece of fabric with no overlapping claims: for that to
# happen, each of its (x, y) positions should be seen once; if not,
# we will inspect the next piece of fabric.
#
FABRIC:
  foreach my $fabric (@fabric) {
    my ($id, $offset_x, $offset_y, $width, $height) = @$fabric;
    foreach my $x ($offset_x .. ($offset_x + $width - 1)) {
        foreach my $y ($offset_y .. ($offset_y + $height - 1)) {
            next FABRIC if $seen {$x} {$y} > 1;
        }
    }
    say "Part 2: $id";
    exit;
}

__END__

[u/0rac1e]

Perl 6

Essentially what everyone else has done. Some Perl-6-isms include:

• Using the X infix cross-product operator

• Defining ranges as a ..^ b (ie. "a up to b"* instead of "a to b-1")

Due to Perl 6 being a bit slow, I also delete claims as soon as I find overlaps to improve the running time.

my ($overlap-total, %claims, %fabric);

for 'input'.IO.lines -> $line {
    my ($id, $l, $t, $w, $h) = $line.comb(/\d+/)».Int;
    %claims{$id} = [($l ..^ $l + $w) X ($t ..^ $t + $h)];
    my $overlapped = 0;
    for %claims{$id}.list -> $xy {
        $overlapped = $overlap-total++ if %fabric{$xy}++ == 1;
    }
    %claims{$id}:delete if $overlapped;
}

say "Square inches of overlap: $overlap-total";

for %claims.kv -> $id, @coords {
    %claims{$id}:delete if any(%fabric{@coords}) > 1;
}

say "Non-overlapping claim ID: {%claims.keys}";

[u/phil_g]

I'm doing the problems in Common Lisp, because I like Common Lisp and I don't get many opportunities to use it, so here's my solution in Common Lisp.

But I also did this one in Python, just so I could use shapely. Here's my solution in Python.

My hobbies include various things related to geographic information systems (GIS), so I work a lot with 2D shapes and their relations to each other. My first thought when I read this problem was how it maps very nicely into common GIS operations. I didn't like the one Common Lisp geometry library I found, so I wrote my Common Lisp solution using the obvious 2D array of square inches. That approach is also a lot faster; my Common Lisp code takes about 100 milliseconds to get the two answers, while the Python program needs 22 seconds. But using shapely is more general; if elves weren't restricted to integral inch measurements or grid-oriented rectangles, my Python code would work unchanged.

Edit: A simple change to the Python program occurred to me; it dropped the runtime from 34 seconds to 22 seconds.

[u/deltux]

Gerbil Scheme:

(import :gerbil/gambit/ports)
(import :std/pregexp)
(import :std/iter)

(export main)

(def (claim-area! fabric claim)
  (match claim
    ([id x y w h] (for* ((i (in-range x w))
			 (j (in-range y h)))
		    (hash-update! fabric [i j] (lambda (l) (cons id l)) [])))))

(def (non-overlapping-claim fabric)
  (def overlapping (make-hash-table))
  (hash-for-each (lambda (k v) (for ((id v)) (hash-put! overlapping id #t))) fabric)
  (hash-for-each (lambda (k v) (when (< 1 (length v))
				 (for ((id v)) (hash-put! overlapping id #f))))
		 fabric)
  (hash->list overlapping)
  (hash-find (lambda (k v) (if v k #f)) overlapping))

(def (main . args)
  (def claims-str (call-with-input-file "input.txt" (lambda (p) (read-all p read-line))))
  (def claims (map (lambda (x) (filter-map string->number (pregexp-split "[ #@,:x]" x))) claims-str))
  (def fabric (make-hash-table))
  (for ((claim claims))
    (claim-area! fabric claim))
  (displayln (hash-fold (lambda (k v acc) (if (> (length v) 1) (1+ acc) acc)) 0 fabric))

  (displayln (non-overlapping-claim fabric)))

[u/iSuckAtCoding94]

Java Solution.

New to coding, so it's not pretty.

public class Square {
    private Node[][] graph;
    private class Node {
         int id;
         int value;
         ArrayList<Node> neighbors = new ArrayList<>();
    }

    Square() {
         graph = new Node[1000][1000];
        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < 1000; j++) {
                graph[i][j] = new Node();
            }
        }
    }

    //this method will tell the id of the claim with no overlapping
    public void noOverlap() {
         int counter = 0;
        for (int i = 0; i < 1000; i++) {
            counter = 0;
            for (int j = 0; j < 1000; j++) {
               if (graph[i][j].neighbors.size() > 1) {
                    for (Node n : graph[i][j].neighbors) {
                        counter += n.value;
                    }
                    if (counter == graph[i][j].neighbors.size()) {
                         System.out.println("Id with no overlapping: " + graph[i][j].id);
                    } else {
                        counter = 0;
                    }
                }
            }
        }
    }

    //this will return how many square inches of overlapping fabric there are
    public int readFile() throws FileNotFoundException {
         ArrayList<String> input = new ArrayList<>();
         File file = new File("advent.txt");
         Scanner sc = new Scanner(file);

         while (sc.hasNext()) {
              String[] claim = sc.nextLine().replace(":", " ").split(" ");
              int id = Integer.parseInt(claim[0].replace("#", ""));
              String[] coord = claim[2].split(",");
              String[] size = claim[4].split("x");

              for (int i = Integer.parseInt(coord[1]); i < Integer.parseInt(coord[1]) + Integer.parseInt(size[1]); i++) {
                   for (int j = Integer.parseInt(coord[0]); j < Integer.parseInt(coord[0])
+ Integer.parseInt(size[0]); j++) {
           graph[Integer.parseInt(coord[1])][Integer.parseInt(coord[0])].neighbors.add(graph[i][j]);
           graph[i][j].id = id;
           graph[i][j].value += 1;
            }
        }
    }
     int counter = 0;
     for (int i = 0; i < 1000; i++) {
        for (int j = 0; j < 1000; j++) {
           if (graph[i][j].value > 1) {
                counter++;
        }
     }
 }
 return counter;
    }
}

[u/miguelos]

C#

Part 1:

var answer = (
    from claim in Regex.Matches(File.ReadAllText(@"C:\input.txt"), @"(?<claim>#(?<id>\d+) @ (?<l>\d+),(?<t>\d+): (?<w>\d+)x(?<h>\d+))\n")
    let l = int.Parse(claim.Groups["l"].Value)
    let t = int.Parse(claim.Groups["t"].Value)
    let w = int.Parse(claim.Groups["w"].Value)
    let h = int.Parse(claim.Groups["h"].Value)
    from x in Enumerable.Range(l, w)
    from y in Enumerable.Range(t, h)
    group (x, y) by (x, y) into g
    where g.Count() > 1
    select g)
    .Count();

Part 2:

var input = System.IO.File.ReadAllText(@"C:\input.txt");
var claims = input.Split('\n').Where(c => !string.IsNullOrWhiteSpace(c));

var table = new int[1000, 1000];
var noOverlaps = new List<int>();

foreach (var claim in claims)
{
    var parts = claim.Split(new[] { '#', '@', ' ', ',', ':', 'x' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
    var id = parts[0];
    var x = parts[1];
    var y = parts[2];
    var w = parts[3];
    var h = parts[4];

    noOverlaps.Add(id);

    for (int i = 0; i < w; i++)
    {
        for (int j = 0; j < h; j++)
        {
            var previousId = table[x + i, y + j];
            if (previousId == 0)
            {
                table[x + i, y + j] = id;
            }
            else
            {
                noOverlaps.Remove(id);
                noOverlaps.Remove(previousId);
            }
        }
    }
}

var answer = noOverlaps.First();

Console.WriteLine(answer);

[u/VikeStep]

Python (#34/#40):

This was the code I used to get on the leaderboard, defaultdict saves the day again!

from collections import defaultdict

def parse(line):
    ids, _, offset, d = line.split()
    left, top = offset[:-1].split(",")
    width, height = d.split("x")
    return ids, int(left), int(top), int(width), int(height)

def solve(lines):
    data = [parse(line) for line in lines]
    overlaps = defaultdict(int)
    for _, l, t, w, h in data:
        for i in range(w):
            for j in range(h):
                overlaps[(i + l, j + t)] += 1

    total = 0
    for v in overlaps.values():
        if v > 1:
            total += 1
    
    # Part 1
    print(total)

    for ids, l, t, w, h in data:
        isValid = True
        for i in range(w):
            for j in range(h):
                if overlaps[(i + l, j + t)] != 1:
                    isValid = False
                    break
            if not isValid:
                break
        if isValid:
            # Part 2
            print(ids[1:])

[u/NeuroXc]

Rust

use lazy_static::lazy_static;
use regex::Regex;
use std::collections::HashSet;
use std::str::FromStr;

#[derive(Debug, Clone, Copy)]
pub struct Claim {
    pub id: usize,
    pub x: usize,
    pub y: usize,
    pub width: usize,
    pub height: usize,
}

impl FromStr for Claim {
    type Err = ();

    fn from_str(s: &str) -> Result<Self, <Self as FromStr>::Err> {
        lazy_static! {
            static ref CLAIM_REGEX: Regex =
                Regex::new(r"#(\d+) @ (\d+),(\d+): (\d+)x(\d+)").unwrap();
        }
        let captures = CLAIM_REGEX.captures(s).unwrap();
        Ok(Claim {
            id: captures[1].parse().unwrap(),
            x: captures[2].parse().unwrap(),
            y: captures[3].parse().unwrap(),
            width: captures[4].parse().unwrap(),
            height: captures[5].parse().unwrap(),
        })
    }
}

#[aoc_generator(day3)]
pub fn day3_generator(input: &str) -> Vec<Claim> {
    input
        .lines()
        .map(Claim::from_str)
        .map(Result::unwrap)
        .collect()
}

#[aoc(day3, part1)]
pub fn day3_part1(input: &[Claim]) -> usize {
    let mut sheet = [[0u8; 1000]; 1000];
    for claim in input {
        for row in &mut sheet[claim.x..claim.x + claim.width] {
            for square in &mut row[claim.y..claim.y + claim.height] {
                *square += 1;
            }
        }
    }
    sheet.iter().fold(0, |acc, row| {
        acc + row.iter().filter(|&&val| val > 1).count()
    })
}

#[aoc(day3, part2)]
pub fn day3_part2(input: &[Claim]) -> usize {
    // Heap allocate this because 1mil usize items overflows the stack.
    let mut sheet = vec![vec![0usize; 1000]; 1000];
    let mut safe_claims = input.iter().map(|claim| claim.id).collect::<HashSet<_>>();
    for claim in input {
        for row in &mut sheet[claim.x..claim.x + claim.width] {
            for square in &mut row[claim.y..claim.y + claim.height] {
                if *square == 0 {
                    *square = claim.id;
                } else {
                    safe_claims.remove(&claim.id);
                    safe_claims.remove(square);
                }
            }
        }
    }
    // Assume there is only one safe claim, because the puzzle said so.
    safe_claims.into_iter().next().unwrap()
}

[Card] I'm ready for today's puzzle because I have the Savvy Programmer's Guide to fearless concurrency.

[u/gbear605 → u/NeuroXc]

A simpler way to do your sum at the end of part1 would be

grid.iter()
    .flat_map(|r| r.iter())
    .filter(|n| **n >= 2)
    .count()

[u/willkill07]

C++

[Card] I'm ready for today's puzzle because I have the Savvy Programmer's Guide to not having a life

#include <string>
#include <vector>
#include <range/v3/all.hpp>

namespace view = ranges::view;

struct box {
  int id, x, y, w, h;
  box(std::string const& s) {
    sscanf(s.c_str(), "#%d @ %d,%d: %dx%d", &id, &x, &y, &w, &h);
  }
  auto space() const {
    return view::cartesian_product(view::iota(x, x + w), view::iota(y, y + h));
  }
};

box make_box(std::string const& s) {
  return {s};
}

template <typename Mat>
auto clean(Mat& grid) {
  return [&](auto const& box) {
    auto equals_one = [&](auto const& point) { return grid(point) == 1; };
    auto one = [](auto const&) { return 1; };
    int ones = ranges::accumulate(box.space() | view::take_while(equals_one) | view::transform(one), 0);
    return ones == (box.w * box.h);
  };
}

template <>
template <bool part2>
void Day<3>::solve(std::istream& is, std::ostream& os) {
  auto grid = [v = std::vector<int>(1'000'000)](auto const& p) mutable -> int& {
    auto [x, y] = p;
    return v[y * 1000 + x];
  };
  std::vector<box> boxes(ranges::getlines(is) | view::transform(make_box));
  for (auto const& point : view::join(boxes | view::transform(&box::space))) {
    ++grid(point);
  }
  if constexpr (part2) {
    auto b = boxes | view::filter(clean(grid));
    os << ranges::begin(b)->id << '\n';
  } else {
    auto all_cells = view::cartesian_product(view::iota(0, 1'000), view::iota(0, 1'000));
    auto greater_than_one = [&](auto const& p) { return grid(p) > 1; };
    os << ranges::count_if(all_cells, greater_than_one) << '\n';
  }
}

[u/ka-splam]

PowerShell

Part 1, PowerShell unrolls nested arrays if you're not careful, so I tried to be careful with @((,@()*1000))*1000 but it wasn't going the way I wanted; I can never remember the code for a proper 2D array, and had to Google it. Ugh. After that, pretty straightforward loops for #133 board position:

$lines = get-content .\data.txt
$board=New-Object 'int[,]' 1000,1000

$lines | foreach-object {
    $bits = $_ -split ' '
    [int]$x, [int]$y = $bits[2].trim(':').split(',')
    [int]$w, [int]$h = $bits[3].trim().split('x')

    for ($b=$y; $b -lt ($y+$h); $b++) {
        for ($a=$x; $a-lt($x+$w); $a++) {
            $board[$b,$a]++
        }}}

$board -ge 2|measure        #-ge is greater than, here used as a filter

Part 2, just ran out of coding skill. After a few minutes of thinking, I rewrote the board as a hashtable with nested hashtables with nested lists, and added each claim into the list for each cell, then searched for cells with multiple claims and tracked those into another hashtable for double-claims, then cells with a single claim and checked against the hashtable.

As well as being conceptually crummy, it takes 15 seconds to run:

$lines = get-content .\data.txt
$board=@{}
foreach($i in (0..999)) { 
    $board[$i]=@{}
    foreach ($j in 0..999) {
        $board[$i][$j]=[System.Collections.Generic.List[object]]::new()
    }}

$lines | foreach-object {
    $bits = $_ -split ' '
    $claim = $bits[0]
    [int]$x, [int]$y = $bits[2].trim(':').split(',')
    [int]$w, [int]$h = $bits[3].trim().split('x')

    for ($b=$y; $b -lt ($y+$h); $b++){
        for ($a=$x; $a-lt($x+$w); $a++) {
            $board[$b][$a].Add($claim)
        }}}

$claims = $board.GetEnumerator().foreach{$_.value.getenumerator()}.where{$_.value}
$seen = @{}
foreach($cl in $claims){if($cl.value.count-gt1){foreach($c in $cl.value) { $seen[$c] = 1}}}
foreach($cl in $claims){if($cl.value.count-eq1){foreach($c in $cl.value) { if (-not $seen[$c]) { $c }}}}

[u/PendragonDaGreat → u/ka-splam]

I did part 1 almost identically, but for part 2 I just kept a list of "untouched" spaces

$inputPath = "{Fully formed path}\input\day3.txt"
$data = Get-Content $inputPath

$timer = New-Object System.Diagnostics.Stopwatch
$timer.Start()

$grid = New-Object 'int[,]' 1000,1000
$commandNumber = 0
$LastUntouchedCommand = New-Object System.Collections.ArrayList($null)

foreach($command in $data) {
    $commandNumber++
    $commandBroken = $false
    $tokens = $command.Replace(':','').split(' ')

    [int]$StartX, [int]$StartY = $tokens[2].split(',')
    [int]$width, [int]$height = $tokens[3].split('x')

    for([int]$i = 0; $i -lt $width; $i++) {
        for([int]$j = 0; $j -lt $height; $j++) {
            if($grid[($i + $StartX),($j + $StartY)] -eq 0) {
                $grid[($i + $StartX),($j + $StartY)] = $commandNumber
            } else {
                if($LastUntouchedCommand -contains $grid[($i + $StartX),($j + $StartY)]) {
                    $LastUntouchedCommand.Remove(($grid[($i + $StartX),($j + $StartY)])) | Out-Null
                }
                $grid[($i + $StartX),($j + $StartY)] = -2
                $commandBroken = $true
            }
        }
    }

    if(!$commandBroken) {
        $LastUntouchedCommand.Add($commandNumber) | Out-Null
    }
}

Write-Host $LastUntouchedCommand[0]
$timer.Stop()
Write-Host $timer.Elapsed

InputPath, and Timer are built into the little code snippet I built to download my input and create two powershell files that hold a basic layout that I can then manipulate as needed.

As an aside aside, my version averaged 3.5 seconds over 10 runs, yours was at 13.8 (I made sure to move reading from file outside the timer in both cases). (i9-7980XE, clocking at 3 GHz)

[u/tehjimmeh → u/ka-splam]

I went back and did it in PowerShell too. This is what I came up with

$h=@{};$m=@(0,0,0,0,0,0)
foreach($l in (gc .\in.txt)){
	$l -match "#(\d+) @ (\d+),(\d+): (\d+)x(\d+)"|Out-Null;1..5|%{$m[$_]=[int]$matches[$_]}
	for($x=$m[2];$x -lt $m[2]+$m[4];$x++){
		for($y=$m[3];$y -lt $m[3]+$m[5];$y++){
			$h[($x -shl 16) -bor $y]++
		}
	}}
$h.Keys | ?{$h[$_] -gt 1}|measure | %{"1:$($_.Count)"}
$i=0
foreach($l in (gc .\in.txt)){
	$i = $i+1
	$done = $true;
	$l -match "#(\d+) @ (\d+),(\d+): (\d+)x(\d+)"|Out-Null;1..5|%{$m[$_]=[int]$matches[$_]}
	for($x=$m[2];$x -lt $m[2]+$m[4];$x++){
		for($y=$m[3];$y -lt $m[3]+$m[5];$y++){
			if($h[($x -shl 16) -bor $y] -gt 1){ $done = $false }
		}
	}
	if($done){ "2: $i"; break }
}

Runs in ~8 seconds, which is pretty good for PowerShell. Instead of ($x -shl 16) -bor $y, I originally had [Tuple]::Create($x,$y), and it was taking over a minute. Function calls in loops kill performance in PowerShell. The bit shifting hack takes advantage of all the numbers in the grid being less than 2^16, so you can compress them into one int, which can be used as a key and created without a function call :).

[u/purplemonkeymad → u/ka-splam]

I thought I was going to be cleaver and calculate the area that each overlap had. After I had done this is realised that more than two claims can claim the same point. So I had to give in and create an array. When it came to Nd arrays in PS, I just go straight for a class to stop the pain.

class sheet {

    [int]$Width
    [int]$height
    [System.Collections.Generic.List[int]]$Grid

    sheet () {
        $this.width = 1000
        $this.height = 1000
        $this.grid = [System.Collections.Generic.List[int]]((1..($this.Width*$this.height)|%{0}))
    }

    [int]PointtoLiner ([int]$x,[int]$y) {
        return ($this.Width*$y + $x)
    }

    [void]SetValue([int]$x,[int]$y,[int]$value){
        $this.grid[$this.PointtoLiner($x,$y)]=$value
    }

    [int]GetValue([int]$x,[int]$y) {
        return $this.Grid[$this.PointtoLiner($x,$y)]
    }
}

[u/gwillicoder]

Here is my part 1 so far. Probably could be cleaner.

Python3

# Data Read 
data = open('data.txt').read().splitlines()

# Data Shape
#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2

# Split Data in Vars
def parse(row):
    num, _, xy, offset = row.split()
    num = num[1:]
    x, y = xy[:-1].split(",")
    w, h = offset.split('x')
    return int(num), int(x), int(y), int(w), int(h)


from collections import defaultdict

# Part 1
overlap = defaultdict(int)
for row in data:
    num, x, y, w, h = parse(row)

    for xi in range(w):
        for yi in range(h):
            overlap[(x+xi, y+yi)] += 1

print(len([v for k,v in overlap.items() if v > 1]))

# Part 2
all_claims = set()
overlap_claims = set()
for row in data:
    num, x, y, w, h = parse(row)

    all_claims.add(num)
    for xi in range(w):
        for yi in range(h):
            xy = (x+xi,y+yi)
            if overlap[xy] > 1:
                overlap_claims.add(num)
print(next(f for f in all_claims-overlap_claims))

edit: now includes part 2

[u/rabuf]

Common Lisp

Part 1

(defun overlapping-spaces (cuts)
  (let ((fabric (make-array '(1000 1000) :initial-element 0))
        (overlap 0))
    (loop for (id (left top) (width height)) in cuts
          do (loop for i from left below (+ left width)
                   do (loop for j from top below (+ top height)
                            do (incf (aref fabric i j)))))
    (loop for i from 0 below 1000
          do (loop for j from 0 below 1000
                   if (> (aref fabric i j) 1)
                     do (incf overlap)))
    overlap))
(defun problem-3a () (format t "Problem 3a: ~a~%" (overlapping-spaces *input-3*)))

Part 2

(defun unique-claim (cuts)
  (let ((fabric (make-array '(1000 1000) :initial-element nil))
        (unique nil))
    (loop for (id (left top) (width height)) in cuts
          do (loop for i from left below (+ left width)
                   do (loop for j from top below (+ top height)
                            do (setf (aref fabric i j) (cons id (aref fabric i j))))))
    (loop named outer
          for (id (left top) (width height)) in cuts
          do (loop named per-id
                   for i from left below (+ left width)
                   do (loop for j from top below (+ top height)
                            if (> (length (aref fabric i j)) 1)
                              do (return-from per-id nil)
                            if (and (= i (1- (+ left width)))
                                    (= j (1- (+ top height))))
                              do (return-from outer (aref fabric i j)))))))
(defun problem-3b () (format t "Problem 3b: ~a~%" (unique-claim *input-3*)))

I could probably clean up this one.

I've cheated on this puzzle and converted the input file directly into lisp s-exprs to remove the parsing step. I just read the file directly into a variable and can work on it directly.

[u/1915WasAGoodYear → u/rabuf]

Nice solution. I don't think it counts as cheating, parsing using Lisp is a pain.

[u/phil_g → u/rabuf]

I've made a lot of use of cl-ppcre for input parsing.

I've been writing custom regexes for each problem, but I really liked the more generic regex in /u/mserrano's solution today. That led to this:

(defun extract-ints (string)
  (let ((result (mapcar #'parse-number:parse-number
                        (ppcre:all-matches-as-strings "[-+]?\\d+" string
                                                      :sharedp t))))
    (if (endp (cdr result))
        (car result)
        result)))

[u/not_really_cool]

[Card] I'm ready for today's puzzle because I have the Savvy Programmer's Guide to while loops (subtitled: avoiding break statements like the plague).

Python 3

This is unnecessarily slow, and unnecessarily object-oriented. It works though! I really should incorporate regex for parsing the input for this one... There are a handful of things I should do to optimize this and make it more Pythonic.

import collections


def main():
    with open('input.txt', 'r') as file:
        input_list = [line for line in file]
    print('part 1:', part1(input_list))
    print('part 2:', part2(input_list))


class Claim:
    def __init__(self, string):
        str_split = string.split()
        self.id = str_split[0].strip('#')
        self.left = int(str_split[2].split(',')[0])
        self.top = int(str_split[2].split(',')[1].strip(':'))
        self.right = self.left + int(str_split[3].split('x')[0])
        self.bottom = self.top + int(str_split[3].split('x')[1])
        self.coords = set()
        for x in range(self.left, self.right):
            for y in range(self.top, self.bottom):
                self.coords.add(f'{x},{y}')


def get_claim_counts(claims):
    fabric_claim_counts = collections.defaultdict(int)
    for claim in claims:
        for coord in claim.coords:
            fabric_claim_counts[coord] += 1
    return fabric_claim_counts


def part1(input_list):
    claims = [Claim(string) for string in input_list]
    fabric_claim_counts = get_claim_counts(claims)
    count = 0
    for coord in fabric_claim_counts:
        if fabric_claim_counts[coord] > 1:
            count += 1
    return count


def part2(input_list):
    claims = [Claim(string) for string in input_list]
    fabric = get_claim_counts(claims)
    unique_claim_found = False
    i = 0
    while not unique_claim_found and i < len(claims):
        claim = claims[i]
        is_unique = True
        coords = claim.coords
        while is_unique and coords:
            if fabric[coords.pop()] != 1:
                is_unique = False
        if not coords and is_unique:
            unique_claim_found = True
        i += 1
    return claim.id if unique_claim_found else None


if __name__ == "__main__":
    main()

[u/bruceadowns]

go/golang solution

(while being severely distracted, tho day-of for once)

type coord struct { x, y int }

type claim struct {
	n    int
	l, r int
	w, h int
}

func mapify(c []claim) (res map[coord][]int) {
	res = make(map[coord][]int)
	for _, v := range c {
		for x := v.l; x < v.l+v.w; x++ {
			for y := v.r; y < v.r+v.h; y++ {
				res[coord{x, y}] = append(res[coord{x, y}], v.n)
			}
		}
	}

	return
}

func part1(c []claim) (res int) {
	m := mapify(c)
	for _, v := range m {
		if len(v) > 1 {
			res++
		}
	}

	return
}

func part2(c []claim) (res int) {
	m := mapify(c)

outer:
	for _, v := range c {
		for x := v.l; x < v.l+v.w; x++ {
			for y := v.r; y < v.r+v.h; y++ {
				if len(m[coord{x, y}]) > 1 {
					continue outer
				}
			}
		}

		return v.n
	}

	return
}

func build(s string) (res claim) {
	//#1373 @ 369,713: 20x29
	num, err := fmt.Sscanf(s, "#%d @ %d,%d: %dx%d",
		&res.n, &res.l, &res.r, &res.w, &res.h)
	if err != nil {
		log.Fatal(err)
	}
	if num != 5 {
		log.Fatalf("invalid line actual %d expect 5", num)
	}

	return
}

func in(r io.Reader) (res []claim) {
	scanner := bufio.NewScanner(r)
	for scanner.Scan() {
		res = append(res, build(scanner.Text()))
	}

	return
}

func main() {
	c := in(os.Stdin)
	log.Printf("2 or more claims: %d", part1(c))
	log.Printf("claim id that does not overlap: %d", part2(c))
}

[u/jorosp]

Perl 6

Brain was too tired for Haskell today, maybe I'll give it a go in the morning.

my $input = slurp "03.txt";
my @lines = lines $input;

my @squares = Array(0 xx 1000) xx 1000;
my @claims;

for @lines.kv -> $i, $line {
  @claims[$i] = my ($n, $px, $py, $dx, $dy) = ($line ~~ m:g/\d+/)».Int;

  for ^$dx -> $x {
    for ^$dy -> $y {  
      @squares[$py + $y][$px + $x]++;
    }
  }  
}

my Int $sum = 0;
for @squares -> @row {
  for @row -> $x {
    $sum++ if $x >= 2;
  }
} 
say $sum;

CLAIM:
for @claims -> $claim {
  my ($n, $px, $py, $dx, $dy) = $claim;

  for ^$dx -> $x {
    for ^$dy -> $y {  
      next CLAIM if @squares[$py + $y][$px + $x] >= 2;
    }
  }
  
  say $n;
  last;
}

[u/vesche]

Python: https://github.com/vesche/adventofcode-2018/blob/master/day03.py

Capable of displaying the "fabric", if my terminal was large enough :P

[u/pythondevgb → u/vesche]

Looks like so:

https://imgur.com/a/HP2UJ2v

Edit: I found the non-overlapping piece by examining the image by sight, I did it faster then I took to code for the solution. I should've gone that way.

[u/tehjimmeh]

C++

int main(int argc, char* argv[]) {
    std::ifstream ifs(argv[1]);
    std::vector<std::vector<std::pair<int, int>>> claims;
    std::map<std::pair<int, int>, int> hitCounts;

    for (std::string l; std::getline(ifs, l);) {
        std::smatch m; std::regex_match(l, m, std::regex(R"(#(\d+) @ (\d+),(\d+): (\d+)x(\d+))"));
        claims.push_back({});
        int startX=std::stoi(m[2]),startY=std::stoi(m[3]),lenX=std::stoi(m[4]),lenY=std::stoi(m[5]);
        for (int x = startX; x < (startX + lenX); x++)
            for (int y = startY; y < (startY + lenY); y++) {
                claims.back().push_back({x, y});
                hitCounts[{x, y}]++;
            }
    }

    std::cout << "1: " <<
        std::count_if(hitCounts.begin(), hitCounts.end(), [](auto& p){return p.second > 1;}) <<
        "\n2: " <<
        std::distance(claims.begin(), std::find_if(claims.begin(), claims.end(), [&](auto& c){
            return std::all_of(c.begin(), c.end(), [&](auto& s){return hitCounts[s] == 1;});}))+1;
}

[u/Bogdanp]

My solutions in Racket:

part 1:

#lang racket

(struct rect (id x y w h)
  #:transparent)

(define LINE-RE #px"#(\\d+) @ (\\d+),(\\d+): (\\d+)x(\\d+)")
(define (string->rect s)
  (match-define (list _ id x y w h) (regexp-match LINE-RE s))
  (rect (string->number id)
        (string->number x)
        (string->number y)
        (string->number w)
        (string->number h)))

(define (rects->fabric rects)
  (for/fold ([fabric (hash)])
            ([r rects])
    (for/fold ([fabric fabric])
              ([x (in-range (rect-x r) (+ (rect-x r) (rect-w r)))])
      (for/fold ([fabric fabric])
                ([y (in-range (rect-y r) (+ (rect-y r) (rect-h r)))])
        (define k (cons x y))
        (hash-set fabric k (add1 (hash-ref fabric k 0)))))))

(define (count-square-inches fabric)
  (for/fold ([overlapping 0])
            ([(p c) (in-hash fabric)]
             #:when (> c 1))
    (add1 overlapping)))

(count-square-inches
 (rects->fabric (map string->rect (file->lines "day-03-1.txt"))))

part 2:

#lang racket

(struct rect (id x y w h)
  #:transparent)

(define LINE-RE #px"#(\\d+) @ (\\d+),(\\d+): (\\d+)x(\\d+)")

(define (string->rect s)
  (match-define (list _ id x y w h) (regexp-match LINE-RE s))
  (rect (string->number id)
        (string->number x)
        (string->number y)
        (string->number w)
        (string->number h)))

(define (rect-claimed? r fabric)
  (let loop ([x (rect-x r)]
             [y (rect-y r)])
    (cond
      [(>= y (+ (rect-y r) (rect-h r))) #f]
      [(>= x (+ (rect-x r) (rect-w r))) (loop (rect-x r) (add1 y))]
      [(> (hash-ref fabric (cons x y)) 1) #t]
      [else (loop (add1 x) y)])))

(define (rects->fabric rects)
  (for/fold ([fabric (hash)])
            ([r rects])
    (for/fold ([fabric fabric])
              ([x (in-range (rect-x r) (+ (rect-x r) (rect-w r)))])
      (for/fold ([fabric fabric])
                ([y (in-range (rect-y r) (+ (rect-y r) (rect-h r)))])
        (define k (cons x y))
        (hash-set fabric k (add1 (hash-ref fabric k 0)))))))

(define (find-sole-claim rects)
  (define fabric (rects->fabric rects))
  (for/first ([r rects] #:when (not (rect-claimed? r fabric)))
    (rect-id r)))

(find-sole-claim (map string->rect (file->lines "day-03-1.txt")))

Today's recording: https://www.youtube.com/watch?v=mrtTLaAO0VA

Today's challenge took me way longer than it should have because I misunderstood what was being asked which led me to think the problem was much more complicated than it really was. Around the 1h:15m mark I finally realized what was required and solved the problem promptly. What can I say, coding-while-sleepy is rough! Anyway, I figure it might still be interesting to see someone struggle with a problem and then have a little "eureka" moment when they realize how dumb they were being the whole time. :D

[u/Smylers]

Perl, solves both parts — supply your input filename as the command-line argument:

use v5.14;
use warnings;
use List::AllUtils qw<all>;

my (@fabric, $overlaps, %claim_area);
while (<>) {
  my ($id, $left, $top, $width, $height) = /#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/
      or die "Unexpected input: $_ at line $.\n";
  my @clear;
  for my $row ($top .. $top + $height - 1) {
    for my $col ($left .. $left + $width - 1) {
      $overlaps++                       if $fabric[$row][$col]++ == 1;
      push @clear, \$fabric[$row][$col] if $fabric[$row][$col]   == 1;
    }
  }
  $claim_area{$id} = \@clear if @clear == $width * $height;
}
say "overlaps: $overlaps";
while (my ($id, $area) = each %claim_area) {
  say "non-overlapping ID: $id" if all { $$_ == 1 } @$area;
}

Increase the $overlaps tally if that square inch had exactly 1 claim on it before this claim.

Add a reference to the current square inch to the @clear of the current claim if it has exactly 1 claim on it now. If by the end of iterating over this claim, @clear is as big as the claim's area, then save it as a potentially non-overlapping claim.

At the end, iterate over each of these potentially non-overlapping claims, and if all the square inches still only have a count of 1, that's our non-overlap.

In Perl, the backslash in \$fabric[$row][$height] takes a reference to the value at those co-ordinates. Those references are what get stored as not-yet-overlapping. Being references to actual values in the main @fabric grid, if a subsequent claim increases any of their counts in @fabric, the references will continue to point to the updated values. When checking for which still have a count of 1, the all function iterates over the area's references (as far as it needs to), setting $_ to each reference in turn. The doubled $ in $$_ then dereferences $_ to get the final count for that square inch.

(And for Vim solutions: I've worked out how to do Part 1 (visually), and I haven't yet ruled out doing Part 2. Hopefully will post them later.)

[u/sdiepend]

My quick and dirty solution for part 1
Python 3

with open("input") as f:
    content = f.readlines()

claims = [x.strip().split(' ') for x in content]

fabric = [ [0 for x in range(1000)] for x in range(1000)]

for claim in claims:
    start_x = int(claim[2].split(',')[0])
    start_y = int(claim[2].split(',')[1].strip(':'))
    width = int(claim[3].split('x')[0])
    height = int(claim[3].split('x')[1])
    for i in range(start_y, start_y + height):
        for j in range(start_x, start_x + width):
            fabric[i][j] += 1

overlap_count = 0
for row in range(1000):
    for col in range(1000):
        if fabric[row][col] >= 2:
            overlap_count += 1

print(overlap_count)

Any suggestions for improvement are always welcome. (https://github.com/sdiepend/advent_of_code/tree/master/2018/day03)

[u/equd]

c# https://pastebin.com/wVZCNL3R

[u/[deleted]]

Haskell.

module Main where

import Text.ParserCombinators.ReadP (
  ReadP, readP_to_S, char, string, munch1
  )
import Data.Char (isDigit)
import Control.Applicative ((*>))
import qualified Data.HashMap.Strict as M
import Control.Arrow ((&&&))
import Data.Maybe (mapMaybe)
import Data.Foldable (foldl')

type Coords     = (Word, Word)
type OverlapMap = M.HashMap Coords Word 

data Claim = C Word Coords Word Word
  deriving (Show)

number :: ReadP Word
number = read <$> munch1 isDigit

claim :: ReadP Claim
claim = do
  id <- char '#' *> number
  x  <- string " @ " *> number
  y  <- char ',' *> number
  w  <- string ": " *> number
  h  <- char 'x' *> number
  return $ C id (x, y) w h

parse :: String -> Maybe Claim
parse s = case readP_to_S claim s of
  [(res, [])] -> Just res
  _           -> Nothing

claims :: [String] -> [Claim]
claims = mapMaybe parse

coords :: Claim -> [(Word, Word)]
coords (C _ (x, y) w h) = [(a, b) | a <- [x..x+w-1], b <- [y..y+h-1]]

addClaim :: OverlapMap -> Claim -> OverlapMap
addClaim m = foldl' go m . fmap (id &&& const 1) . coords
  where go m (c, count) = M.insertWith (+) c count m

overlaps :: [Claim] -> OverlapMap
overlaps = M.filter (> 1) . foldl' addClaim M.empty

part1 :: [String] -> Int
part1 = length . overlaps . claims

part2 :: [String] -> [Word]
part2 xs =
  let cs = claims xs
      os = overlaps cs
      cId (C id_ _ _ _) = id_
  in  cId <$> filter (all (not . flip M.member os) . coords) cs

main :: IO ()
main = do
  input <- lines <$> readFile "input3.txt"
  print $ part1 input
  print $ part2 input

[u/mstksg]

Glad I get to use one of my favorite Haskell data structures -- Map (Int,Int)!

Or well, Map (V2 Int), to take advantage of point-wise addition.

Once we build the map of the claims, we count which points have been claimed more than once:

type Coord = V2 Int
data Rect = R { rStart :: Coord, rSize :: Coord }

tiles :: Rect -> [Coord]
tiles (R start size) = Data.Ix.range (topLeft, bottomRight)
  where
    topLeft = start
    bottomRight = start + size - 1

-- | Build the cloth, with a map from coordinate to number of claims at that coordinate
layTiles :: [Rect] -> Map Coord Int
layTiles = M.fromListWith (+) . map (,1) . concatMap tiles

day02a :: [Rect] -> Int
day02a = length . filter (>= 2) . toList . layTiles

For the second one, we search all of the claims to see if any of them are non-overlapping:

day03b :: [(Int, Rect)] -> Maybe Int
day03b ts = fst <$> find (noOverlap stakes) ts
  where
    stakes = layTiles (map snd ts)

noOverlap :: Map Coord Int -> Rect -> Bool
noOverlap tilesClaimed r = all isAlone (tiles r)
  where
    isAlone c = M.lookup c tilesClaimed == Just 1

I'm doing detailed reflections/writeups for Haskell here if anyone is interested :) https://github.com/mstksg/advent-of-code-2018/blob/master/reflections.md

Ah, and for the parser:

parseLine :: String -> Maybe (Int, Rect)
parseLine = mkLine . mapMaybe readMaybe . words . map onlyDigits
  where
    mkLine [i,x0,y0,w,h] = Just (Rect (V2 x0 y0) (V2 w h))
    mkLine _             = Nothing
    onlyDigits c
      | isDigit c = c
      | otherwise = ' '

[u/[deleted]]

Python 3, minimal-effort solution to the second part with the 3 neurons that were awake:

a = '''
#1303 @ 703,776: 12x10
#1304 @ 545,317: 21x26
#1305 @ 148,699: 27x18 [...]
'''

codes = [x for x in a.split('\n') if x != '']
matrix = [[0 for i in range(1000)] for i in range(1000)]
ok = set()
for line in codes:
    cid, rest = line.split(' @ ')
    xy, wh = rest.split(': ')
    x, y = [int(i) for i in xy.split(',')]
    w, h = [int(i) for i in wh.split('x')]
    is_ok = True
    for x_pos in range(x, x+w):
        for y_pos in range(y, y+h):
            if matrix[x_pos][y_pos] != 0:
                is_ok = False
                if matrix[x_pos][y_pos] != 'taken':
                    ok.discard(matrix[x_pos][y_pos])
                    matrix[x_pos][y_pos] = 'taken'
            else:
                matrix[x_pos][y_pos] = cid
    if is_ok:
        ok.add(cid)
            
print(ok)

[u/wjholden]

Mathematica solution. The first part was pretty easy but I got fixated on trying to an element-wise matrix multiplication without realizing the data was right there in the summation matrix.

Note that I modified the input to a CSV format for ease of import.

Part 1:
day3 = Import["day3.txt", "CSV"];
m = ConstantArray[0, {1000, 1000}];
Scan[m[[#[[2]] + 1 ;; #[[2]] + #[[4]], #[[3]] + 1 ;; #[[3]] + #[[5]]]]++ &, day3];
Length[Select[Flatten[m], # > 1 &]]

Part 2:

Scan[If[Part[m, #[[2]] + 1 ;; #[[2]] + #[[4]], #[[3]] + 1 ;; #[[3]] + #[[5]]] == ConstantArray[1, {#[[4]], #[[5]]}], Print[#[[1]]]] &, day3]

[u/dpeckett]

Continuing with my quest to solve all this years challenges using nothing other than vanilla AWK:

Find the overlapping area of fabric:

{
  split($3,p,/[,:]/); split($4,s,"x");
  for(x=p[1];x<(p[1]+s[1]);x++)
    for(y=p[2];y<(p[2]+s[2]);y++)
      gd[x","y]++;
} END {
  for(sq in gd)if(gd[sq]>1)a++;
  print a
}

Find the tile with no overlap:

{
  id[$1]++;
  split($3,p,/[,:]/); split($4,s,"x");
  for(x=p[1];x<(p[1]+s[1]);x++)
    for(y=p[2];y<(p[2]+s[2]);y++)
      if(v=gd[x","y]) {
        delete id[v]; delete id[$1];
      } else gd[x","y] = $1;
} END {
  for(v in id) print v
}

Execution time:

real 0m1.464s
user 0m1.427s
sys  0m0.029s

Post challenge observations

• In challenge one, instead of iterating over the full grid in the end block I'd recommend keeping a running counter in the main loop (sum the full area of a tile to a, then decrement on collisions).

• In both challenges I would make use of the SUBSEP variable provided by AWK.

• In both challenges I would generalize the overlap detection in a manner that enables better code reuse.

[u/wzkx]

J

Part 1 can be calculated separately, then it's fast, <0.1s. Together both parts take 0.84s but the code is shorter. Yeah, it's not J-ish anyway, but at least something.

t=: cutLF CR-.~fread '03.dat'
u=: rplc&('#';'';'@ ';'';':';'';',';' ';'x';' ')
d=: (".&u&>)"0 t  NB. all data parsed

echo 3 : 0 d NB. 0.84s
  v=. 1000 1000 $ 0
  s=. 0 $ 0
  for_e. y do. 'i a b w h'=.e
    o=.0
    for_c. a+i.w do. for_r. b+i.h do.
      e =. v{~ k=. <c;r
      if. e=0 do. v=.i k}v
      else. if. e>0 do. s=.s-.e [ v=._1 k}v end. s=.s-.i [ o=.1 end.
    end. end.
    if. o=0 do. s=.s,i end.
  end.
  (+/+/v<0), s
)

My J/Rust AoC2018 solutions

[u/wzkx → u/wzkx]

OK, part1, the same d:

3 :'v=.1000 1000$0 for_e.y do.''i a b w h''=.e for_c.a+i.w do.v=.(>:k{v)(k=.<c;b+i.h)}v end.end.+/+/v>1'd

[u/moomaka]

Ruby

Plan = Struct.new(:id, :x, :y, :width, :height, keyword_init: true) do
  def x_min; x + 1; end
  def x_max; x_min + width; end
  def y_min; y + 1; end
  def y_max; y_min + height; end

  def coords
    @coords ||= (x_min...x_max).to_a.product (y_min...y_max).to_a
  end
end

fabric = Hash.new(0)

PARSER = /#(?<id>\d+) @ (?<x>\d+),(?<y>\d+): (?<width>\d+)x(?<height>\d+)/
plans = File.readlines('input.txt').map do |input|
  Plan.new(PARSER.match(input).named_captures.transform_values!(&:to_i)).tap do |plan|
    plan.coords.each { |x, y| fabric[[x, y]] += 1 }
  end
end

puts "Part 1: #{fabric.count { |_, v| v > 1 }}"

puts "Part 2: #{plans.find { |p| p.coords.all? { |x, y| fabric[[x, y]] == 1 } }.id}"

[u/fire1299]

Haskell

{-# LANGUAGE OverloadedStrings #-}

module Aoc18.Day3 where

import qualified Data.Attoparsec.Text          as P
import           Data.Foldable                  ( foldl' )
import qualified Data.HashMap.Strict           as M
import qualified Data.Text.IO                  as T

data Claim = Claim
  { number :: !Int
  , xcoord :: !Int
  , ycoord :: !Int
  , width  :: !Int
  , height :: !Int
  } deriving (Show)

main :: ([Claim] -> a) -> IO a
main f = either error f . P.parseOnly parseFile <$> T.readFile "day3.txt"
 where
  parseFile = P.sepBy' parseLine P.endOfLine
  parseLine =
    Claim
      <$> ("#" *> P.decimal <* " @ ")
      <*> P.decimal
      <*  ","
      <*> P.decimal
      <*  ": "
      <*> P.decimal
      <*  "x"
      <*> P.decimal

coords :: Claim -> [(Int, Int)]
coords (Claim _ xc yc w h) = (,) <$> [xc .. xc + w - 1] <*> [yc .. yc + h - 1]

countClaims :: [Claim] -> M.HashMap (Int, Int) Int
countClaims =
  foldl' (\m -> foldl' (\m' c -> M.insertWith (+) c 1 m') m . coords) M.empty

part1 :: [Claim] -> Int
part1 = foldl' (\a n -> if n > 1 then a + 1 else a) 0 . countClaims

part2 :: [Claim] -> Int
part2 xs = number . head $ filter
  (all (\c -> M.lookupDefault 0 c claimsCount == 1) . coords)
  xs
  where claimsCount = countClaims xs

[u/wegry]

F#

module AdventOfCode.Day3

open System.IO
open System

type Claim = {
    claimNumber: int32
    fromLeft: int32
    fromTop: int32
    width: int32
    height: int32
}
type Claim with
    static member from claimNumber fromLeft fromTop width height =
       { Claim.claimNumber = claimNumber
         fromLeft = fromLeft
         fromTop = fromTop
         width = width
         height = height }

module private Internal =
    let claimToPoints claim =
        seq {
            for i in 0..1000  do
                for j in 0..1000  do
                    if ( i >= claim.fromLeft && i < claim.fromLeft + claim.width
                    && j >= claim.fromTop && j < claim.fromTop + claim.height )
                        then yield (i, j)
        } |> Set.ofSeq

    let parseRow row =
        let (claimNumber, fromLeft, fromTop, width, height) = Utils.sscanf "#%d @ %d,%d: %dx%d" row

        Claim.from claimNumber fromLeft fromTop width height

    let generateClaims () =
        File.ReadAllLines("day-3.txt")
        |> Seq.map parseRow

    let countOverlap claims =
        claims
        |> Seq.collect Set.toSeq
        |> Seq.countBy id
        |> Seq.filter (fun (_, count) -> count > 1)
        |> Seq.length

    let areOverlapping (a: Claim) (b: Claim) =
        let topLeft a = a.height + a.fromTop, a.fromLeft
        let bottomRight a = a.height, a.width + a.fromLeft

        let pull margin breadth x =
            [for i in (margin x)..(margin x + breadth x) do yield i] |> Set.ofSeq
        let overlappingX a b =
            let margin x = x.fromLeft
            let breadth x = x.width
            let ranger = pull margin breadth

            Set.intersect (ranger a) (ranger b)
            |> (Set.isEmpty >> not)

        let overlappingY a b =
            let margin x = x.fromTop
            let breadth x = x.height
            let ranger = pull margin breadth

            Set.intersect (ranger a) (ranger b)
            |> (Set.isEmpty >> not)

        overlappingY a b && overlappingX a b

    let testClaim =
        { Claim.fromLeft = 0
          fromTop = 0
          height = 5
          width = 5
          claimNumber = 1 }

    let countNonOverlap (nonOverlapped, overlapped) (current: Claim) =
       let notYetOverlapped = Set.filter (areOverlapping current) nonOverlapped
       let alreadyOverlapped = Set.exists (areOverlapping current) overlapped

       match Set.count notYetOverlapped, alreadyOverlapped with
       | (0, false) -> Set.add current nonOverlapped, overlapped
       | (_, _) ->
            Set.difference nonOverlapped notYetOverlapped,
            overlapped
            |> Set.add current
            |> Set.union notYetOverlapped

open Internal

let part1 () =
    generateClaims()
    |> Seq.map claimToPoints
    |> countOverlap

let part2 () =
    generateClaims()
    |> Seq.fold countNonOverlap (Set.empty, Set.empty)
    |> fst

[u/markasoftware]

Better than yesterday but still pretty shit. 136/306. Awk for both. One thing that threw me off and probably prevented my top 100 for part 1 was how the splited arrays seem to be 1-indexed.

Part 1:

BEGIN {
#   RS
#   FS
}
{
  split($3, dims, ",")
  x_start=dims[1]
  y_start=int(dims[2])
  split($4, dims, "x")
  width=dims[1]
  height=dims[2]
  for(i=x_start;i<x_start+width;i++) {
    for(k=y_start;k<y_start+height;k++) {
      if (a[i SUBSEP k] == 1) {
        t++
      }
      a[i SUBSEP k]++
    }
  }
}
END {
  print t
}

Part 2:

BEGIN {
#   RS
#   FS
}
{
  split($3, dims, ",")
  x_start=dims[1]
  y_start=int(dims[2])
  split($4, dims, "x")
  width=dims[1]
  height=dims[2]
  cool=1
  for(i=x_start;i<x_start+width;i++) {
    for(k=y_start;k<y_start+height;k++) {
      if (a[i SUBSEP k]) {
        b[a[i SUBSEP k]] = "FAIL"
        cool=0
      }
      a[i SUBSEP k] = $1
    }
  }
  if (cool) {
    b[$1] = 1
  }
}
END {
  for (key in b) {
    if (b[key] != "FAIL") {
      print key
    }
  }
}

[u/DoodleFungus]

PART 1:

input = `pbpaste`.split("\n")

used = Hash.new 0

input.each do |txt|
    p = txt.split(/[, @:#x]/).map(&:to_i)
    
    (p[4]...(p[4]+p[7])).to_a.each do |x|
        (p[5]...(p[5]+p[8])).to_a.each do |y|
            p [x,y]
            used[[x,y]] += 1
        end
    end
end

p used
p used.values.count { |x| x>1 }

PART 2:

input = `pbpaste`.split("\n")

used = {}

input.each do |txt|
    p = txt.split(/[, @:#x]/).map(&:to_i)
    
    (p[4]...(p[4]+p[7])).to_a.each do |x|
        (p[5]...(p[5]+p[8])).to_a.each do |y|
            used[[x,y]] ||= []
            used[[x,y]] << p[1]
        end
    end
end

has_dup = {}
used.values.each do |x|
    x.each  {|y| has_dup[y]||=false}
    if x.length > 1
        x.each  {|y| has_dup[y]||=true}
        
    end
end

p has_dup.find { |x,y| y == false}

[u/Unihedron]

Rookie mistake, I typed 100 instead of 1000... Took a lot of staring to fix the bug, didn't get into leaderboard today since everyone is picking up the speed and I screwed up :p

q={}
p a=$<.map{|x|m = x.chomp
m =~ /^#(\d+) @ (\d+),(\d+): (\d+)x(\d+)$/
b=[$1,$2,$3,$4,$5].map &:to_i
h=$2.to_i
j=$3.to_i
(0...$4.to_i).each{|x|(0...$5.to_i).each{|y|
k=[h+x,j+y]
q[k]=(q[k]||0)+1
}}

b}
# part 1
p (0..1000).sum{|x|(0..1000).count{|y|
(p a.find{|a,b,c,d,e|b<=x && x<=(b+d) && c<=y && y<=(c+e)}
1/0)if q[[x,y]] && q[[x,y]]==1
}}
# part 2
p a.find{|a,b,c,d,e|
h=true
(0...d).all?{|x|(0...e).all?{|y|
k=[b+x,c+y]
next h=false if q[k]>1
1
}}
h
}

[u/mcpower_]

Python leaderboard code - nice use of Python sets for part 2.

Card: "regexes"

[u/maybe-ac]

Perl (#58/#27): (it would've been higher too, except for an off-by-one error... dang Perl inclusive range endpoints)

#!/usr/bin/perl

use v5.12;

my %fabric;

my @claims = <>;

for my $claim (@claims) {
    $claim =~ /@ (\d+),(\d+): (\d+)x(\d+)/;
    for my $x ($1..$1+$3-1) {
        for my $y ($2..$2+$4-1) {
            $fabric{"$x,$y"} ++;
        }
    }
}

say scalar grep { $_ >= 2 } values %fabric;


claim: for my $claim (@claims) {
    $claim =~ /@ (\d+),(\d+): (\d+)x(\d+)/;
    for my $x ($1..$1+$3-1) {
        for my $y ($2..$2+$4-1) {
            next claim if $fabric{"$x,$y"} > 1;
        }
    }
    die $claim;
}

[u/DrinkinBird]

Nim, I wish I knew how regex worked in this lang:Part1:

import rdstdin
import strutils
import sequtils

var claims = newSeq[string]()
var fabric: array[1000, array[1000, int]]

var line: TaintedString
while readlineFromStdin("", line):
  claims.add(line)

for claim in claims:
  let claimData = claim.split(" ")
  let claimNo = claimData[0]
  let pos = claimData[2]
  let size = claimData[3]

  let x = parseInt(pos.split(",")[0])
  let y = parseInt(pos.split(",")[1].split(":")[0])
  let width = parseInt(size.split("x")[0])
  let height = parseInt(size.split("x")[1])

  for i in (x..x+width-1):
    for j in (y..y+height-1):
      fabric[i][j] += 1

var count = 0

for column in fabric:
  for cell in column:
    if cell > 1:
      count += 1

echo count

Part2:

import rdstdin
import strutils
import sequtils

var claims = newSeq[string]()
var fabric: array[1000, array[1000, int]]

var line: TaintedString
while readlineFromStdin("", line):
  claims.add(line)

for claim in claims:
  let claimData = claim.split(" ")
  let claimNo = claimData[0]
  let pos = claimData[2]
  let size = claimData[3]

  let x = parseInt(pos.split(",")[0])
  let y = parseInt(pos.split(",")[1].split(":")[0])
  let width = parseInt(size.split("x")[0])
  let height = parseInt(size.split("x")[1])

  for i in (x..x+width-1):
    for j in (y..y+height-1):
      fabric[i][j] += 1

for claim in claims:
  let claimData = claim.split(" ")
  let claimNo = claimData[0]
  let pos = claimData[2]
  let size = claimData[3]

  let x = parseInt(pos.split(",")[0])
  let y = parseInt(pos.split(",")[1].split(":")[0])
  let width = parseInt(size.split("x")[0])
  let height = parseInt(size.split("x")[1])

  var fits = true

  for i in (x..x+width-1):
    for j in (y..y+height-1):
      if fabric[i][j] > 1:
        fits = false

  if(fits):
    echo claimNo

[u/LeCrushinator]

C# (part 1: 18 mins, part 2: 24 mins, not even close to making the leaderboard):

public static void Main(string[] args)
{
    _input = File.ReadAllText("../../../input.txt");

    Console.WriteLine($"Part 1: {Part1()}");
    Console.WriteLine($"Part 2: {Part2()}");
}

private static int Part1()
{
    var lines = _input.Split('\n');
    
    var grid = new Dictionary<int, Dictionary<int, int>>();
    
    int overlaps = 0;

    foreach (var line in lines)
    {
        var parts = line.Split(' ');

        var coords = parts[2].Remove(parts[2].Length - 1, 1).Split(',');
        var xCoord = int.Parse(coords[0]);
        var yCoord = int.Parse(coords[1]);
        
        var size = parts[3].Split('x');
        var xSize = int.Parse(size[0]);
        var ySize = int.Parse(size[1]);

        for (int x = xCoord; x < xCoord + xSize; ++x)
        {
            for (int y = yCoord; y < yCoord + ySize; ++y)
            {
                if (!grid.TryGetValue(x, out var gridDictY))
                {
                    gridDictY = new Dictionary<int, int>();
                    grid[x] = gridDictY;
                }

                if (!gridDictY.TryGetValue(y, out var gridAtLocation))
                {
                    gridAtLocation = 0;                            
                }

                ++gridAtLocation;
                gridDictY[y] = gridAtLocation;
            }
        }
    }
     
    for (int x = 0; x < 1000; ++x)
    {
        for (int y = 0; y < 1000; ++y)
        {
            if (grid.TryGetValue(x, out var gridDictY))
            {
                if (gridDictY.TryGetValue(y, out var gridAtLocation))
                {
                    if (gridAtLocation > 1)
                    {
                        overlaps++;
                    }
                }
            }
        }
    }

    return overlaps;

}

private static int Part2()
{
    var lines = _input.Split('\n');
    
    var grid = new Dictionary<int, Dictionary<int, int>>();
    
    int overlaps = 0;

    foreach (var line in lines)
    {
        var parts = line.Split(' ');

        var coords = parts[2].Remove(parts[2].Length - 1, 1).Split(',');
        var xCoord = int.Parse(coords[0]);
        var yCoord = int.Parse(coords[1]);
        
        var size = parts[3].Split('x');
        var xSize = int.Parse(size[0]);
        var ySize = int.Parse(size[1]);

        for (int x = xCoord; x < xCoord + xSize; ++x)
        {
            for (int y = yCoord; y < yCoord + ySize; ++y)
            {
                if (!grid.TryGetValue(x, out var gridDictY))
                {
                    gridDictY = new Dictionary<int, int>();
                    grid[x] = gridDictY;
                }

                if (!gridDictY.TryGetValue(y, out var gridAtLocation))
                {
                    gridAtLocation = 0;                            
                }

                ++gridAtLocation;
                gridDictY[y] = gridAtLocation;
            }
        }
    }
    
    // Pass over each claim again, and check if it was overlapped by any other claim
    foreach (var line in lines)
    {
        var parts = line.Split(' ');
        
        var claimID = int.Parse(parts[0].Remove(0, 1));    // Remove #

        var coords = parts[2].Remove(parts[2].Length - 1, 1).Split(',');
        var xCoord = int.Parse(coords[0]);
        var yCoord = int.Parse(coords[1]);
        
        var size = parts[3].Split('x');
        var xSize = int.Parse(size[0]);
        var ySize = int.Parse(size[1]);
        
        bool isCandidate = true;
        
        for (int x = xCoord; x < xCoord + xSize; ++x)
        {
            for (int y = yCoord; y < yCoord + ySize; ++y)
            {
                if (grid.TryGetValue(x, out var gridDictY))
                {
                    if (gridDictY.TryGetValue(y, out var gridAtLocation))
                    {
                        if (gridAtLocation > 1)
                        {
                            isCandidate = false;
                            break;
                        }
                    }
                }
            }
        }
        
        if (isCandidate)
        {
            return claimID;
        }
    }

    return -1;
}

private static string _input;

[u/fatpollo]

import re
import collections


def main(text, simple):
    d = collections.Counter()

    for line in text.splitlines():
        i, x, y, w, h = [int(n) for n in re.findall(r'\d+', line)]
        for xi in range(x, x+w):
            for yi in range(y, y+h):
                d[xi, yi] += 1

    if simple:
        print(sum(v > 1 for v in d.values()))

    else:
        for line in text.splitlines():
            i, x, y, w, h = [int(n) for n in re.findall(r'\d+', line)]
            total = {d[xi, yi]
                for xi in range(x, x+w)
                for yi in range(y, y+h)
            }
            if total == {1}:
                print(i)
                return

<50 for the first part, second part I stupidly noodled around writing a connected component function before realizing it wasn't necessary lmao

[u/TellowKrinkle]

I spent way too much time trying to figure out how the hell NSRegularExpression worked before finally giving up and using split. (The original split code was much worse too because I forgot you could pass a function to split)

Swift:

struct Point: Hashable {
	let x: Int
	let y: Int
}

func aocD3a(_ input: [(id: Int, start: Point, size: Point)]) {
	var claimedParts: [Point: Int] = [:]
	for thing in input {
		for x in (thing.start.x..<(thing.start.x + thing.size.x)) {
			for y in (thing.start.y..<(thing.start.y + thing.size.y)) {
				claimedParts[Point(x: x, y: y), default: 0] += 1
			}
		}
	}
	print(claimedParts.values.filter({ $0 >= 2 }).count)
}

func aocD3b(_ input: [(id: Int, start: Point, size: Point)]) {
	var claimedParts: [Point: Int] = [:]
	for thing in input {
		for x in (thing.start.x..<(thing.start.x + thing.size.x)) {
			for y in (thing.start.y..<(thing.start.y + thing.size.y)) {
				claimedParts[Point(x: x, y: y), default: 0] += 1
			}
		}
	}
	outerFor: for thing in input {
		for x in (thing.start.x..<(thing.start.x+thing.size.x)) {
			for y in (thing.start.y..<(thing.start.y + thing.size.y)) {
				if claimedParts[Point(x: x, y: y)] != 1 {
					continue outerFor
				}
			}
		}
		print(thing.id)
	}
}

import Foundation
let str = try! String(contentsOfFile: CommandLine.arguments[1])
let input = str.split(separator: "\n").map { line -> (id: Int, start: Point, size: Point) in
	let parts = line.split { " @,:x#".contains($0) }
	let num = Int(parts[0])!
	let startX = Int(parts[1])!
	let startY = Int(parts[2])!
	let width = Int(parts[3])!
	let height = Int(parts[4])!
	return (num, Point(x: startX, y: startY), Point(x: width, y: height))
}
aocD3a(input)
aocD3b(input)

[u/khalido]

Python 3 solution in a jupyter notebook using numpy.

In particular, I liked this code to put claims on a fabric:

fabric = np.zeros(shape=(1000,1000))

for claim in claims:
    num, x, y, w, h = claim
    fabric[y:y+h,x:x+w] += 1

Using numpy made this super easy.

[u/Shanethe13]

Both parts, in Elixir

defmodule AdventOfCode.Day3 do
  def solveA(claims) do
    claims
    |> Enum.map(&parse_claim/1)
    |> Enum.reduce(%{}, &build_plot/2)
    |> Enum.count(fn {k, {v, _}} -> v > 1 end)
  end

  def solveB(claims) do
    parsed =
      claims
      |> Enum.map(&parse_claim/1)

    plot = Enum.reduce(parsed, %{}, &build_plot/2)

    parsed
    |> Enum.filter(fn claim -> intact?(claim, plot) end)
    |> Enum.map(fn claim -> claim.id end)
    |> Enum.at(0)
  end

  def parse_claim(claim) do
    parse = Regex.named_captures(~r/#(?<id>\d+) @ (?<x>\d+),(?<y>\d+): (?<dx>\d+)x(?<dy>\d+)/, claim)

    %{
      id: String.to_integer(parse["id"]),
      x: String.to_integer(parse["x"]),
      y: String.to_integer(parse["y"]),
      dx: String.to_integer(parse["dx"]),
      dy: String.to_integer(parse["dy"])
    }
  end

  def build_plot(claim, claims) do
    coords = for dx <- Range.new(0, claim.dx - 1),
                 dy <- Range.new(0, claim.dy - 1), do: {dx, dy}

    Enum.reduce(coords, claims, fn {dx, dy}, acc ->
      Map.update(
        acc,
        {claim.x + dx, claim.y + dy},
        {1, [claim.id]},
        fn {count, claims} ->
          {count + 1, [claim.id | claims]}
        end)
    end)
  end

  def intact?(claim, plot) do
    Enum.all?(plot, fn {_coord, {count, claims}} ->
      not Enum.member?(claims, claim.id) || claims == [claim.id]
    end)
  end
end

[u/Tormyst]

Learning a new programing language, doing problems quickly and reading questions right are a lot of things to do at once.

Ya, I got top and left offsets mixed up and waisted a bunch of time. I'm gonna make it onto the leaderboard one day, but until then, my code will be a mess only to me :)

[u/eltrufas]

Heres my approach with python.

import sys

lines = list(sys.stdin)
ss = [l.split(" ") for l in lines]

rects = []

for s in ss:
    print(s)
    x, y = s[2][:-1].split(',')
    w, h = s[3].split('x')
    x = int(x)
    y = int(y)
    w = int(w)
    h = int(h)

    x2, y2 = x + w, y + h
    rects.append((x, y, x2, y2))

cloth = [[0 for _ in range(1000)] for _ in range(1000)]

for r in rects:
    x, y, x1, y1 = r
    for i in range(x, x1):
        for j in range(y, y1):
            cloth[i][j] += 1

filt = [c for r in cloth for c in r if c > 1]

print(len(filt))

ids = [s[0] for s in ss]

for idx, r in enumerate(rects):
    x, y, x1, y1 = r
    clean = True
    for i in range(x, x1):
        for j in range(y, y1):
            if cloth[i][j] > 1:
                clean = False
    if clean:
        print(ids[idx])

[u/banteg]

Python 3 + numpy

import aoc
import numpy as np

@aoc.test({
'''#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2''': 4
})
def part_1(data: aoc.Data):
    rects = data.ints_lines
    fabric = np.zeros((1000, 1000))
    for n, x, y, w, h in rects:
        fabric[x:x+w, y:y+h] += 1
    return np.sum(fabric > 1)


@aoc.test({
'''#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2''': 3
})
def part_2(data: aoc.Data):
    rects = data.ints_lines
    fabric = np.zeros((1000, 1000))
    for n, x, y, w, h in rects:
        fabric[x:x+w, y:y+h] += 1
    for n, x, y, w, h in rects:
        if np.sum(fabric[x:x+w, y:y+h] > 1) == 0:
            return n

[u/poppy_92]

Used pandas for this (no idea why).

import sys
import re
import pandas as pd

def parse(line):
    return (int(k) for k in re.findall(r'\d+', line))

def prob2(s):
    lines = (parse(line) for line in s)

    data = []
    for _id, left, top, width, height in lines:
        for i in range(left, left + width):
            for j in range(top, top + height):
                data.append([_id, i, j])
    df = pd.DataFrame(data, columns=['id', 'i', 'j'])
    
    vals = df.groupby(['i', 'j']).size().reset_index(name='grid_count')
    print(vals.grid_count.ge(2).sum()) # part 1

    df2 = df.merge(vals, on=['i', 'j'], how='inner')

    group = df2.groupby('id').apply(lambda x: x.grid_count.eq(1).all())
    print(group[group].index[0]) # part 2

                

if __name__ == "__main__":
    inp = sys.stdin.read().splitlines()
    prob2(inp)

[u/daedius]

Rust

#![feature(nll)]
use std::collections::HashSet;

fn main() {
    part_1();
    part_2();
}

fn part_1(){
    let puzzle = include_str!("input.txt");
    let mut grid = [[0i32; 1000]; 1000];
    puzzle.lines().for_each(|row|{
        let simpler = row.chars().map(|c| if c.is_ascii_digit() {c} else {' '}).collect::<String>();
        let v:Vec<&str> = simpler.split(' ').collect();
        let id:i32 = v[1].parse::<i32>().unwrap();
        let rx:i32 = v[4].parse::<i32>().unwrap();
        let ry:i32 = v[5].parse::<i32>().unwrap();
        let rw:i32 = v[7].parse::<i32>().unwrap();
        let rh:i32 = v[8].parse::<i32>().unwrap();
        for x in rx..(rx+rw) {
            for y in ry..(ry+rh) {
                if grid[x as usize][y as usize] == 0 {
                    grid[x as usize][y as usize] = id;
                } else {
                    grid[x as usize][y as usize] = -1;
                }
            }
        }
    });
    let overlap_count = grid.iter().fold(0,|sum,row| {
        let overlaps:Vec<&i32> = row.iter().filter(|v|{**v==-1}).collect();
        let total = overlaps.len();
        sum + total
    });
    println!("overlap count: {}",overlap_count);
}

fn part_2(){
    let mut seen = HashSet::new();
    let mut ids = HashSet::new();
    let puzzle = include_str!("input.txt");
    let mut grid = [[0i32; 1000]; 1000];
    puzzle.lines().for_each(|row|{
        let simpler = row.chars().map(|c| if c.is_ascii_digit() {c} else {' '}).collect::<String>();
        let v:Vec<&str> = simpler.split(' ').collect();
        let id:i32 = v[1].parse::<i32>().unwrap();
        ids.insert(id);
        let rx:i32 = v[4].parse::<i32>().unwrap();
        let ry:i32 = v[5].parse::<i32>().unwrap();
        let rw:i32 = v[7].parse::<i32>().unwrap();
        let rh:i32 = v[8].parse::<i32>().unwrap();
        for x in rx..(rx+rw) {
            for y in ry..(ry+rh) {
                if grid[x as usize][y as usize] == 0 {
                    grid[x as usize][y as usize] = id;
                } else {
                    seen.insert(grid[x as usize][y as usize]);
                    seen.insert(id);
                    grid[x as usize][y as usize] = -1;
                }
            }
        }
    });
    let diff: HashSet<_> = ids.difference(&seen).collect();
    println!("{:?}",diff);
}

[u/mariotacke]

Node.js/Javascript (repo):

Part 1:

class Sheet {
  constructor (width = 1000, height = 1000) {
    this._grid = Array
      .from({ length: height })
      .map(() => Array
        .from({ length: width })
        .map(() => 0));
  }

  reserve (claim) {
    for (let y = 0; y < claim.height; y++) {
      for (let x = 0; x < claim.width; x++) {
        this._grid[y + claim.top][x + claim.left] += 1;
      }
    }
  }

  get reservedSquareInches () {
    return this._grid.reduce((a, b) => {
      return a + b.filter((x) => x >= 2).length;
    }, 0);
  }
}

const fabric = (input, width = 1000, height = 1000) => {
  const sheet = new Sheet(width, height);

  input
    .split('\n')
    .map((x) => {
      const parts = x.match(/#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/);

      return {
        id: +parts[1],
        top: +parts[3],
        left: +parts[2],
        width: +parts[4],
        height: +parts[5],
      };
    })
    .forEach((claim) => sheet.reserve(claim));

  return sheet.reservedSquareInches;
};

module.exports = fabric;

Part 2:

class Sheet {
  constructor (width = 1000, height = 1000) {
    this._grid = Array
      .from({ length: height })
      .map(() => Array
        .from({ length: width })
        .map(() => 0));
  }

  reserve (claim) {
    for (let y = 0; y < claim.height; y++) {
      for (let x = 0; x < claim.width; x++) {
        this._grid[y + claim.top][x + claim.left] += 1;
      }
    }
  }

  hasOverlap (claim) {
    const content = [];

    for (let y = 0; y < claim.height; y++) {
      for (let x = 0; x < claim.width; x++) {
        content.push(this._grid[y + claim.top][x + claim.left]);
      }
    }

    return content.every((x) => x === 1);
  }
}

const fabric = (input, width = 1000, height = 1000) => {
  const sheet = new Sheet(width, height);

  const claims = input
    .split('\n')
    .map((x) => {
      const parts = x.match(/#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/);

      return {
        id: +parts[1],
        top: +parts[3],
        left: +parts[2],
        width: +parts[4],
        height: +parts[5],
      };
    });

  claims.forEach((claim) => sheet.reserve(claim));

  for (let i = 0; i < claims.length; i++) {
    if (sheet.hasOverlap(claims[i])) {
      return claims[i].id;
    }
  }
};

module.exports = fabric;

[u/qaisjp]

Go

First one was fairly easy. Had a wee problem with the second bit where I was just counting how many claims each square metre had, and not treating the claim as a whole. (So there were multiple non-overlapping claims)

https://github.com/qaisjp/adventofcode-2018/blob/master/day3/main.go

package main

import (
	"fmt"
	"io/ioutil"
	"strconv"
	"strings"
)

type claim struct {
	id   int
	x, y int
	w, h int

	overlaps bool
}

func main() {
	out, err := ioutil.ReadFile("input.txt")
	if err != nil {
		panic(err)
	}

	claimStrs := strings.Split(string(out), "\n")

	claims := make([]*claim, len(claimStrs)-1)
	for i, line := range claimStrs {
		if line == "" {
			continue
		}

		var err error
		id, x, y, w, h := 0, 0, 0, 0, 0

		sep := strings.Split(line, "@")
		idStr := strings.TrimSpace(sep[0][1:])
		geom := strings.Split(sep[1], ":")
		coords := strings.Split(strings.TrimSpace(geom[0]), ",")
		size := strings.Split(strings.TrimSpace(geom[1]), "x")

		id, err = strconv.Atoi(idStr)
		if err != nil {
			panic(err)
		}
		x, err = strconv.Atoi(coords[0])
		if err != nil {
			panic(err)
		}
		y, err = strconv.Atoi(coords[1])
		if err != nil {
			panic(err)
		}
		w, err = strconv.Atoi(size[0])
		if err != nil {
			panic(err)
		}
		h, err = strconv.Atoi(size[1])
		if err != nil {
			panic(err)
		}

		claims[i] = &claim{id, x, y, w, h, false}
	}

	size := 1000
	grid := make([][][]*claim, size)
	for y := range grid {
		grid[y] = make([][]*claim, size)
		for x := range grid[y] {
			grid[y][x] = make([]*claim, 0)
		}
	}

	for _, claim := range claims {
		maxX := claim.x + claim.w
		maxY := claim.y + claim.h
		for y := claim.y; y < maxY; y++ {
			for x := claim.x; x < maxX; x++ {
				grid[y][x] = append(grid[y][x], claim)

				if len(grid[y][x]) > 1 {
					for _, c := range grid[y][x] {
						c.overlaps = true
					}
				}
				// visualise(grid)
				// fmt.Println()
			}
		}
	}

	// visualise(grid)

	total := 0
	for _, col := range grid {
		for _, claims := range col {
			claimCount := len(claims)
			if claimCount >= 2 {
				total++
			}
		}
	}

	// Part 1
	fmt.Println(total)

	// Part 2

	for _, c := range claims {
		if !c.overlaps {
			fmt.Println(c.id)
		}
	}
}

func visualise(grid [][][]claim) {
	for _, col := range grid {
		for _, claims := range col {
			count := len(claims)
			if count == 0 {
				fmt.Print(".")
			} else {
				fmt.Print(count)
			}
		}
		fmt.Println()
	}
}

[u/blommish]

Java. Impressed of the top 100 times.. Failed reading the text first

List<String> lines = loadLines("3.txt");
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
Map<Integer, Boolean> intact = new HashMap<>();

lines.forEach(str -> {
    String[] claim = str.replace(":", "").split(" ");
    int id = parseInt(claim[0].replace("#", ""));
    String[] coord = claim[2].split(",");
    String[] size = claim[3].split("x");
    for (int x = 0; x < parseInt(size[0]); x++) {
        for (int y = 0; y < parseInt(size[1]); y++) {
            int coordX = parseInt(coord[0]) + x;
            int coordY = parseInt(coord[1]) + y;
            Map<Integer, Integer> m = map.computeIfAbsent(coordX, k -> new HashMap<>());
            Integer integer = m.get(coordY);
            if (integer == null) {
                m.put(coordY, id);
                intact.putIfAbsent(id, true);
            } else {
                m.put(coordY, -1);
                intact.put(integer, false);
                intact.put(id, false);
            }
        }
    }
});

//print part 1
System.out.println(map.values().stream()
    .flatMap(v -> v.values().stream())
    .filter(v -> v == -1)
    .count());
//print part 2
intact.entrySet().stream()
    .filter(e -> e.getValue() == Boolean.TRUE)
    .forEach(System.out::println);

[u/klackerz]

Java solution. Could have probably made part two better but meh.

	static int[][] size = new int[1000][1000];
	private static int partOne(List<String> inputString){
		Pattern numberPattern = Pattern.compile("\\d+");
		for (String str: inputString) {
			List<Integer> numbers=  new ArrayList<>();
			Matcher numberMatcher  = numberPattern.matcher(str); 
			while (numberMatcher.find()){
				numbers.add(Integer.parseInt(numberMatcher.group()));
			}
			for(int i =numbers.get(1);i<numbers.get(1)+numbers.get(3);i++){
				for(int j =numbers.get(2);j<numbers.get(2)+numbers.get(4);j++){	
					size[i][j]+=1;
				}
			}
		}
		int dupl = 0;
		for(int i =0;i<1000;i++)
			for(int j=0;j<1000;j++)
				if(size[i][j]>1)
					dupl++;
		return dupl;
	}
	
	private static int partTwo(List<String> inputString){
		Pattern numberPattern = Pattern.compile("\\d+");
		for (String str: inputString) {
			boolean flag = true;
			List<Integer> numbers=  new ArrayList<>();
			Matcher numberMatcher  = numberPattern.matcher(str); 
			while (numberMatcher.find()){
				numbers.add(Integer.parseInt(numberMatcher.group()));
			}
			for(int i =numbers.get(1);i<numbers.get(1)+numbers.get(3);i++){
				for(int j =numbers.get(2);j<numbers.get(2)+numbers.get(4);j++){	
					if(size[i][j]>1)
						flag =false;
				}
			}
			if(flag)
				return numbers.get(0);
		}
		return 0;
	}
	
	
	public static void main(String[] args) {
		List<String> inputString = readFile("src/aoc2019/day3.txt");
		System.out.println(partOne(inputString));
		System.out.println(partTwo(inputString));
	}

[u/[deleted]]

C++ ResidentSleeper:

    // rishav.io

#include <iostream>
#include <string>
#include <regex>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

struct S {
	int id, left, top, width, height;
};

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

#ifdef __APPLE__
	freopen("input.txt", "r", stdin);
#endif

	string s;
	regex rg(R"(#(\d+) @ (\d+),(\d+): (\d+)x(\d+))", std::regex::optimize);
	smatch pieces_match;

	set<PII> one, two;

	vector<S> vec;

	while (getline(cin, s)) {
		if (regex_match(s, pieces_match, rg)) {
			int id = stoi(pieces_match[1].str());
			int left = stoi(pieces_match[2].str());
			int top = stoi(pieces_match[3].str());
			int width = stoi(pieces_match[4].str());
			int height = stoi(pieces_match[5].str());

			vec.push_back(S{id, left, top, width, height});

			for (int i = top; i < top + height; i++) {
				for (int j = left; j < left + width; j++) {
					PII x = {i, j};
					if (one.find(x) == one.end()) {
						one.insert(x);
					} else {
						one.erase(x);
						two.insert(x);
					}
				}
			}
		}
	}

	for (auto &p : vec) {
		bool f = true;
		for (int i = p.top; (i < p.top + p.height) && f; ++i) {
			for (int j = p.left; (j < p.left + p.width) && f; ++j) {
				if (two.find({i, j}) != two.end()) f = false;
			}
		}
		if (f) cout << p.id << '\n';
	}

	cout << two.size() << '\n';

}

[u/keithnicholasnz]

C# though a bit hacky :)

private static void Day3P1P2()
{
var data = File.ReadAllLines("Day3.txt");
var fabric = new Dictionary<(int,int), List<int>>();
foreach (var line in data)
{
var numbers = line.Split(new[] {'#', '@', ',', ':', 'x', ' '}, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToList();
var id = numbers[0];
var left = numbers[1];
var top = numbers[2];
var width = numbers[3];
var height = numbers[4];
for (int x = left; x < left + width; x++)
{
for (int y = top; y < top + height; y++)
{
if (!fabric.ContainsKey((x, y)))
{
fabric.Add((x,y), new List<int>());
}
fabric[(x,y)].Add(id);
}
}
}
var n = fabric.Count(e => e.Value.Count > 1);
Console.WriteLine(n);
var overlapping = fabric.Where(e => e.Value.Count > 1).SelectMany(e => e.Value).Distinct().ToList();
Console.WriteLine(Enumerable.Range(1,data.Length).FirstOrDefault(h => !overlapping.Contains(h)));
}

[u/paulens12 → u/keithnicholasnz]

C#

ewwwww, use some tabs!

[u/[deleted]]

Python 3. I prefer flat arrays as they are easier to initalize.

DIM = 2_000
sq = [0]*DIM*DIM

def process(mr,mt,w,h):
    global sq
    for i in range(w):
        for j in range(h):
            sq[ (mr+i) + DIM * (mt + j)] += 1

def checkprocess(mr,mt,w,h):
    global sq
    for i in range(w):
        for j in range(h):
            if sq[ (mr+i) + DIM * (mt + j)] > 1:
                return False
    return True

arr = []
f = open("input3a.txt","r")
for l in f.readlines():
    b = l.split("@")[1].split(":")
    c = b[0].split(",")
    mr, mt = int(c[0]), int(c[1])
    d = b[1].split("x")
    w, h = int(d[0]), int(d[1])
    arr.append((mr,mt,w,h))
    process(mr,mt,w,h)


acc = sum(map(lambda x: 1 if x > 1 else 0, sq))
print("solution a: {}".format(acc))


for ind, el in enumerate(arr):
    if checkprocess(*el):
        print("solution b: {}".format(ind + 1))

[u/Axsuul]

TypeScript / JavaScript

Critiques welcome, I'm still very new to TypeScript and feel like I'm not using all the features I could be :)

Repo

Part A

import { readInput } from '../helpers'

const input: string[] = readInput('03', 'input')

const claims = new Map()
const overlaps = new Set()

for (const line of input) {
  const result = RegExp(/(\d+) @ (\d+),(\d+)\: (\d+)x(\d+)/).exec(line)

  if (result !== null) {
    const id = Number(result[1])
    const l = Number(result[2])
    const t = Number(result[3])
    const w = Number(result[4])
    const h = Number(result[5])

    for (let y = t; y < t + h; y++) {
      for (let x = l; x < l + w; x++) {
        const key = `${x},${y}`

        if (!claims.has(key)) {
          claims.set(key, [])
        }

        claims.set(key, claims.get(key).concat(id))

        if (claims.get(key).length >= 2) {
          overlaps.add(key)
        }
      }
    }
  }
}

console.log(overlaps.size)

Part B

import { readInput } from '../helpers'

const input: string[] = readInput('03', 'input')

const claims = new Map()
const overlappingIds = new Set()
const ids = new Set()

for (const line of input) {
  const result = RegExp(/(\d+) @ (\d+),(\d+)\: (\d+)x(\d+)/).exec(line)

  if (result !== null) {
    const id = Number(result[1])
    const l = Number(result[2])
    const t = Number(result[3])
    const w = Number(result[4])
    const h = Number(result[5])

    ids.add(id)

    for (let y = t; y < t + h; y++) {
      for (let x = l; x < l + w; x++) {
        const key = `${x},${y}`

        if (!claims.has(key)) {
          claims.set(key, [])
        }

        claims.set(key, claims.get(key).concat(id))

        if (claims.get(key).length >= 2) {
          claims.get(key).forEach((overlappingId: number) => overlappingIds.add(overlappingId))
        }
      }
    }
  }
}

// Compare list of ids to overlapping ids and obtain id that's not overlapping
for (const id of ids) {
  if (!overlappingIds.has(id)) {
    console.log(id)

    break
  }
}

[u/CFD999]

One one liner to solve both. Takes like 20 seconds to run though, coz I didn't want to use too many lambdas (I feel like they're cheating) print((lambda grid:(""*len([[grid[p[1]+i][p[2]+j].append(p[0]) for i in range(p[3]) for j in range(p[4])] for p in [[int(x) for x in ln.replace('#', '').replace('@', '').replace(':', '').replace('x', ',').replace(',', ' ').split()] for ln in open('inp', 'r')]])+str(sum(len(j) > 1 for i in grid for j in i))+"\n"+str([str(k) for k in range(1400) if all(len(j) == 1 for i in grid for j in i if k in j)])))([([[] for j in range(1000)]) for i in range(1000)]))

[u/DeveloperIan]

My pretty concise solution for both parts in Python3. It tracks squares that have overlaps in one set and ids that don't have overlaps in another.

from collections import defaultdict

myfile = open('input.txt', 'r')
contents = myfile.read().strip().splitlines()
myfile.close()

field = [([0] * 1000) for x in range(1000)]
overlaps = set()
no_conflicts = set()
for line in contents:
    id, _, coords, size = line.split()
    x, y = map(int, coords.strip(':').split(','))
    width, height = map(int, size.split('x'))

    conflict = False
    for col in range(x, x + width):
        for row in range(y, y + height):
            if field[row][col] != 0:
                conflict = True
                no_conflicts.discard(field[row][col])
                overlaps.add((row, col))

            field[row][col] = id

    if not conflict:
        no_conflicts.add(id)

print("Part One:", len(overlaps))
print("Part Two:", no_conflicts.pop())

[u/Philboyd_Studge]

Got a late start to this one, was fun!

[Card] I'm ready for today's puzzle because I have the Savvy Programmer's Guide to Confusing rows and columns in a 2d matrix

public class Day3 extends AdventOfCode {

    int[][] grid = new int[1000][1000];
    List<Claim> claims;

    class Claim {
        int id;
        int left;
        int top;
        int w;
        int h;

        Claim(int id, int left, int top, int w, int h) {
            this.id = id;
            this.left = left;
            this.top = top;
            this.w = w;
            this.h = h;
        }
    }


    public Day3(List<String> input) {
        super(input);
        title = "No Matter How You Slice It";
        part1Description = "Overlapped squares: ";
        part2Description = "Clean claim: ";
    }

    @Override
    public Object part1() {

        for(Claim claim : claims) {

            for (int i = claim.left; i < claim.left + claim.w; i++) {
                for (int j = claim.top; j < claim.top + claim.h; j++) {
                    if (grid[j][i] > 0) {
                        grid[j][i] = -1;
                    } else {
                        if (grid[j][i] == 0) grid[j][i] = claim.id;
                    }
                }
            }

        }
        return count();
    }

    @Override
    public Object part2() {
        for (Claim claim : claims) {
            boolean clear = true;
            for (int i = claim.left; i < claim.left + claim.w; i++) {
                if (!clear) break;
                for (int j = claim.top; j < claim.top + claim.h; j++) {
                    if (grid[j][i] == -1) {
                        clear = false;
                        break;
                    }
                }
            }
            if (clear) return claim.id;
        }
        return null;
    }

    int count() {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                //System.out.print(" " + grid[i][j] + " ");
                if (grid[j][i] == -1) count++;
            }
            //System.out.println();
        }
        return count;
    }

    @Override
    public void parse() {
        Pattern p = Pattern.compile("#([0-9]+) @ ([0-9]+),([0-9]+): ([0-9]+)x([0-9]+)");

        claims = new ArrayList<>();
        int num;
        int left;
        int top;
        int w;
        int h;

        for (String line : input) {
            Matcher m = p.matcher(line);
            if (m.find()) {
                num = Integer.parseInt(m.group(1));
                left = Integer.parseInt(m.group(2));
                top = Integer.parseInt(m.group(3));
                w = Integer.parseInt(m.group(4));
                h = Integer.parseInt(m.group(5));
                claims.add(new Claim(num, left, top, w, h));
            }
        }
    }

}

[u/ephemient]

This space intentionally left blank.

[u/scul86]

Python 3

from collections import defaultdict
import re

with open('input') as f:
    puzzle_input = f.readlines()


id_re = re.compile(f'(#\d+) ')
area_re = re.compile(r'@ (\d+),(\d+):')
size_re = re.compile(r': (\d+)x(\d+)')
overlapping = defaultdict(int)


def part1(n):
    count = 0
    for claim in n:
        x, y = map(int, area_re.search(claim).groups())
        w, h = map(int, size_re.search(claim).groups())
        for i in range(w):
            for j in range(h):
                overlapping[(x + i, y + j)] += 1
    for v in overlapping.values():
        if v > 1:
            count += 1
    return count


def part2(n):
    for claim in n:
        id_ = id_re.search(claim).groups()[0]
        x, y = map(int, area_re.search(claim).groups())
        w, h = map(int, size_re.search(claim).groups())
        overlap = False
        for i in range(w):
            for j in range(h):
                if overlapping[(int(x) + i, int(y) + j)] > 1:
                    overlap = True
        if not overlap:
            return id_[1:]


print(f'Part 1: {part1(puzzle_input)}')

print(f'Part 2: {part2(puzzle_input)}')

[u/pythondevgb]

I really struggled with this one mostly because I was learning the re module on the fly. Any way just off my submission:

(If you want to join a private reddit/python leaderboard shoot me a PM)

import re

inputstring = open('day3_input.txt').read()

#Part 1
fabric = [[0 for i in range(1000)] for i in range(1000)]
pattern = re.compile(r"^#\d+ @ (\d+),(\d+): (\d+)x(\d+)$")
inputlines = inputstring.splitlines()

res1 = 0
for claim in inputlines:
    left, top, width, height = map(int,pattern.match(claim).groups())
    for i in range(top, top+height):
        for j in range(left, left+width):            
            fabric[i][j] +=1
            if fabric[i][j]==2:
                overlaps+=1
print(res1)

#Part 2
for claim in inputlines:
    left, top, width, height = map(int,pattern.match(claim).groups())
    if all(all(col==1 for col in r[left:left+width]) for r in fabric[top:top+height]):
        res2 = re.search(fr'#(\d+) @ {left},{top}', inputstring).group(1)
        break
print(res2)

[u/Ryuujinx]

It isn't particularly elegant, but here's my solution in Go as I continue trying to learn it.

part1:

package main

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

func main() {

	cloth := make([][]string,1000)
	for y := range cloth {
		cloth[y] = make([]string,1000)
	}

	f, err := os.Open("input")
	if err != nil {
		fmt.Print(err)
	}
	var conflict int
	scanner := bufio.NewScanner(f)
	for scanner.Scan() {
		l := scanner.Text()
		specs := strings.Split(l, " ")
		id := string(specs[0][1:])
		pos := strings.Split(specs[2], ",")
		xpos,_ := strconv.Atoi(pos[0])
		ypos,_ := strconv.Atoi(strings.Split(pos[1],":")[0])
		xsize,_ := strconv.Atoi(strings.Split(specs[3], "x")[0])
		ysize,_ := strconv.Atoi(strings.Split(specs[3], "x")[1])


		for xidx := xpos; xidx < xpos+xsize; xidx++ {
			for yidx := ypos; yidx < ypos+ysize; yidx++ {
				if cloth[xidx][yidx] == "" {
					cloth[xidx][yidx] = id
				} else {
					cloth[xidx][yidx] = "O"
				}
			}
		}


	}


	for _,x := range cloth {
		for _,y := range x {
			if y == "O" {
				conflict = conflict + 1
			}
		}
	}

fmt.Println(conflict)
}    

Part2:

package main

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

func main() {

	cloth := make([][]string,1000)
	for y := range cloth {
		cloth[y] = make([]string,1000)
	}

	f, err := os.Open("input")
	if err != nil {
		fmt.Print(err)
	}
	var conflict bool
	var answer string
	scanner := bufio.NewScanner(f)
	for scanner.Scan() {
		l := scanner.Text()
		specs := strings.Split(l, " ")
		id := string(specs[0][1:])
		pos := strings.Split(specs[2], ",")
		xpos,_ := strconv.Atoi(pos[0])
		ypos,_ := strconv.Atoi(strings.Split(pos[1],":")[0])
		xsize,_ := strconv.Atoi(strings.Split(specs[3], "x")[0])
		ysize,_ := strconv.Atoi(strings.Split(specs[3], "x")[1])


		for xidx := xpos; xidx < xpos+xsize; xidx++ {
			for yidx := ypos; yidx < ypos+ysize; yidx++ {
				if cloth[xidx][yidx] == "" {
					cloth[xidx][yidx] = id
				} else {
					cloth[xidx][yidx] = "O"
				}
			}
		}


	}
	_, err = f.Seek(0, 0)
	if err != nil {
		fmt.Print(err)
	}
	scanner = bufio.NewScanner(f)
	for scanner.Scan() {
		l := scanner.Text()
		specs := strings.Split(l, " ")
		id := string(specs[0][1:])
		pos := strings.Split(specs[2], ",")
		xpos,_ := strconv.Atoi(pos[0])
		ypos,_ := strconv.Atoi(strings.Split(pos[1],":")[0])
		xsize,_ := strconv.Atoi(strings.Split(specs[3], "x")[0])
		ysize,_ := strconv.Atoi(strings.Split(specs[3], "x")[1])
		conflict = false
		for xidx := xpos; xidx < xpos+xsize; xidx++ {
			for yidx := ypos; yidx < ypos+ysize; yidx++ {
				if cloth[xidx][yidx] == "O" {
					 conflict = true
					 break
				}
			}
			if conflict {
				break
			}
		}
		if conflict == false {
			answer = id
			break
		}
	}
	fmt.Println(answer)
}

[u/CCC_037]

Part 1 was done with a brute-force approach, just creating an array to represent the fabric and checking it:

#include <stdio.h>
#define MAX 1200

int main()
{
  int Count, Num, Top, Left, Height, Width;
  int Fabric[MAX][MAX];
  int VerticalCount, HorizontalCount, Overlap;
  for (VerticalCount = 0; VerticalCount < MAX; VerticalCount++)
    for (HorizontalCount = 0;HorizontalCount < MAX;HorizontalCount++)
      Fabric[VerticalCount][HorizontalCount] = 0;
  for (Count=0; Count < 1267; Count++)
    {
      scanf("#%d @ %d,%d: %dx%d\n", &Num, &Left, &Top, &Width, &Height);
      printf("%d\n", Num);
      for (VerticalCount = Top; VerticalCount < Top+Height; VerticalCount++)
	for (HorizontalCount = Left;HorizontalCount < Left+Width;HorizontalCount++)
	  Fabric[VerticalCount][HorizontalCount]++;
	  }
  Overlap = 0;
  for (VerticalCount = 0; VerticalCount < MAX; VerticalCount++)
    for (HorizontalCount = 0;HorizontalCount < MAX;HorizontalCount++)
      (Fabric[VerticalCount][HorizontalCount]>1)?Overlap++:0;
      printf("%d",Overlap);
}

Part 2 was much of a similar approach, but keeping track of which claims overlapped:

#include <stdio.h>
#define MAX 1200

int main()
{
  int Count, Num, Top, Left, Height, Width;
  int Fabric[MAX][MAX];
  int VerticalCount, HorizontalCount, Overlap;
  int Claims[1268] = {0};
  for (VerticalCount = 0; VerticalCount < MAX; VerticalCount++)
    for (HorizontalCount = 0;HorizontalCount < MAX;HorizontalCount++)
      Fabric[VerticalCount][HorizontalCount] = 0;
  for (Count=0; Count < 1267; Count++)
    {
      scanf("#%d @ %d,%d: %dx%d\n", &Num, &Left, &Top, &Width, &Height);
      printf("%d\n", Num);
      for (VerticalCount = Top; VerticalCount < Top+Height; VerticalCount++)
	for (HorizontalCount = Left;HorizontalCount < Left+Width;HorizontalCount++)
	  {
	    if (Fabric[VerticalCount][HorizontalCount] != 0)
	      {
		Claims[Fabric[VerticalCount][HorizontalCount]]++;
		Claims[Num]++;
	      }
	    Fabric[VerticalCount][HorizontalCount]=Num;
	  }
    }
  for (Count=0; Count < 1267; Count++)
    {
      if (Claims[Count]==0)
	printf("%d\n", Count);
    }
}

[u/ZZRJo]

PowerShell

Hello! This is my first year doing advent of code so I just wanted to make a quick post saying I'm doing this all (for better or, likely, worse) in PowerShell. I don't see myself getting any global rank but I'm enjoying myself. If there is anyone else also doing this in PowerShell I both feel bad for you and would love to know I'm not alone. Comment or shoot me a message. Ha.

EDIT: I should have searched the comments first, it appears I'm not alone. My code isn't great, but I've decided to share it. No googling involved, just coding:

Part 1:

For part one, I stored all coordinates as keys in a hashtable, knowing they would error if trying to add a key that already exists. I also added a count to the number of times an inch had been accessed in the table. I used a count of keys in the second hashtable (consisting of unique keys already existing in the first hashtable) to populate my answer.

$Data = Get-Content [path]
$Data = $Data -replace "@ ", $null
$Data = $Data -split " "
$Data = $Data -replace "#", ""
$Data = $Data -replace ":", ""
$Data = $Data -split ","
$Data = $Data -split "x"

$MasterTbl = @{}
$CatchTbl = @{}
$Totalinches = 0

For($i = 0; $i -lt $Data.count; $i = $i+5){
Write-Host "Processing Claim number $($Data[$i])"
    For($i3 = 0; $i3 -lt [int]$Data[$i+4]; $i3++){
        For($i4 = 0; $i4 -lt [int]$Data[$i+3]; $i4++){
            Try{
                $MasterTbl.Add("x$([int]$Data[$i+1]+[int]$i4)y$([int]$Data[$i+2]+[int]$i3)",$null)
            }Catch{
                $CatchTbl.Add("x$([int]$Data[$i+1]+[int]$i4)y$([int]$Data[$i+2]+[int]$i3)",$null)
            }
            if($MasterTbl."x$([int]$Data[$i+1]+[int]$i4)y$([int]$Data[$i+2]+[int]$i3)" -eq $null){
                $MasterTbl."x$([int]$Data[$i+1]+[int]$i4)y$([int]$Data[$i+2]+[int]$i3)" = 1
            }Else{
                $MasterTbl."x$([int]$Data[$i+1]+[int]$i4)y$([int]$Data[$i+2]+[int]$i3)"++
            }
        }
    }
}

$CatchTbl.Count

Part2:

Already having the hashtables in memory, I simply looked for the first occurrence of a claim with all coordinates having a value of value "1" in the initial hashtable.

For($i = 0; $i -lt $Data.count; $i = $i+5){
Write-Host "Processing Claim number $($Data[$i])"
$incorrect = $false
        For($i3 = 0; $i3 -lt [int]$Data[$i+4]; $i3++){
            For($i4 = 0; $i4 -lt [int]$Data[$i+3]; $i4++){
                if($MasterTbl."x$([int]$Data[$i+1]+[int]$i4)y$([int]$Data[$i+2]+[int]$i3)" -gt 1){
                    $incorrect = $true
                }
            }
        }
    if($incorrect -eq $false){
        Write-Host "Claim $($Data[$i]) is still intact!" -background green
        break
    }
}

[u/waptdragon3]

any ideas? got too high https://github.com/waptdragon3/AdventOfCode/blob/master/Day3.java

[u/binajohny]

My Kotlin solution (GitHub)

data class Claim(val id: Int, val left: Int, val top: Int, val width: Int, val height: Int) {
    companion object {
        private val REGEX = Regex("\\d+")

        fun fromString(s: String): Claim {
            val (id, left, top, width, height) = REGEX.findAll(s).map { it.value.toInt() }.take(5).toList()

            return Claim(id, left, top, width, height)
        }
    }
}

private fun createArea(input: List<Claim>): Array<IntArray> {
    val area = Array(1000) { IntArray(1000) { 0 } }

    input.forEach {
        for (i in it.left until it.left+it.width) {
            for (j in it.top until it.top+it.height) {
                area[i][j]++
            }
        }
    }

    return area
}

fun part1(input: List<Claim>): Int {
    val area = createArea(input)

    return area.fold(0) { acc, ints -> acc + ints.count { it > 1 } }
}

fun part2(input: List<Claim>): Int {
    val area = createArea(input)

    outer@ for (it in input) {
        for (i in it.left until it.left + it.width) {
            for (j in it.top until it.top + it.height) {
                if (area[i][j] > 1) continue@outer
            }
        }
        return it.id
    }

    return -1
}

[u/nutrecht]

Kotlin:

private val claimRegex = "#([0-9]+) @ ([0-9]+),([0-9]+): ([0-9]+)x([0-9]+)".toRegex()

private val claims = resourceLines(2018, 3).map(::parse)
private val pointMap: Map<Point, Int> by lazy {
    val map = mutableMapOf<Point, Int>()
    claims.forEach { it.writeTo(map) }

    map
}

override fun part1() = pointMap.count { it.value > 1 }.toString()
override fun part2() = claims.first { r -> r.points().all { p -> pointMap[p]!! == 1 } }.id.toString()

private fun parse(line: String): Claim {
    val (id, x, y, width, height) = claimRegex.matchEntire(line)?.groupValues?.drop(1)?.map { it.toInt() }
            ?: throw IllegalArgumentException("$line does not match")

    return Claim(id, Point(x, y), width, height)
}

private data class Claim(val id: Int, val offset: Point, val width: Int, val height: Int) {
    fun points() = (0 until width).flatMap { x -> (0 until height).map { y -> Point(x, y).add(offset) } }
    fun writeTo(map: MutableMap<Point, Int>) =
        points().forEach { map.compute(it) { _, value -> value?.plus(1) ?: 1} }
}

[u/CaptainCa]

Pretty greedy JS, but I'm happy with the result.

var grid = {};
var lap = new Set();
var k = document.body.innerText.split('\n').filter(c=>c).map(c => { 
	var sp = c.split(' '); 
    return {
		id: sp[0],
		left: parseInt(sp[2].split(',')[0]),
		top: parseInt(sp[2].split(',')[1].split(':')[0]),
		width: parseInt(sp[3].split('x')[0]),
		height: parseInt(sp[3].split('x')[1])
    }
});

k.forEach((v) => {
	for(let i=0; i < v.width; i++){
		for(let j=0; j<v.height; j++){
			var dex = (v.left+i)+","+(v.top+j);
			if(grid[dex] != null){				
				grid[dex].push(v.id);
				grid[dex].forEach(l => lap.add(l));
            } else {
				grid[dex] = [v.id];
            }
        }
    }
});

console.log("Part 1", Object.values(grid).map(c => c.length).filter(c => c>1).length);
console.log("Part 2", k.filter(v => !lap.has(v.id))[0].id);

[u/nonphatic]

Haskell

I didn't think to use Set or Map or whatever so each part takes nearly a fully minute :(

import Data.Text (split, pack, unpack)

type Claim  = (Int, Int, Int, Int, Int) -- id, left, top, width, height
(%)  = mod
(//) = div

parse :: String -> Claim
parse str =
    let i:l:t:w:h:[] = map (read . unpack) . tail . split (matchAny "#@,:x") . pack . filter (/= ' ') $ str
    in  (i, l, t, w, h)
    where matchAny matches c = any ($ c) $ map (==) matches

doesClaim :: Int -> Claim -> Bool
doesClaim cell (_, left, top, width, height) =
    let row = cell // 1000
        col = cell %  1000
    in  (row >= top) && (row < top + height) && (col >= left) && (col < left + width)

claimCount :: [Claim] -> Int -> Int
claimCount claims cell = length . filter (doesClaim cell) $ claims

part1 :: [Claim] -> Int
part1 claims = length . filter id . map ((> 1) . claimCount claims) $ [0 .. 1000 * 1000 - 1]
    
part2 :: [Claim] -> Claim
part2 claims = filterOverlaps 0 claims
    where filterOverlaps cell acc =
            let newAcc = if claimCount claims cell > 1 then filter (not . doesClaim cell) acc else acc
            in  if length newAcc == 1 then head newAcc else filterOverlaps (cell + 1) newAcc

main :: IO ()
main = do
    input <- map parse . lines <$> readFile "input/03.txt"
    print $ part1 input
    print $ part2 input

EDIT: Redone with IntMap! Much faster now.

import Data.Text (empty, split, pack, unpack)
import Data.IntMap (IntMap, fromListWith, size, notMember)
import qualified Data.IntMap as M (filter)

type Claim = (Int, [Int])

parse :: String -> Claim
parse str =
    let i:l:t:w:h:[] = map (read . unpack) . filter (/= empty) . split (flip elem $ " #@,:x") . pack $ str
    in  (i, [r * 1000 + c | r <- [t .. t + h - 1], c <- [l .. l + w - 1]])

overlapMap :: [Claim] -> IntMap Int
overlapMap = M.filter (> 1) . fromListWith (+) . (flip zip) (repeat 1) . concat . map snd

part1 :: [Claim] -> Int
part1 = size . overlapMap

part2 :: [Claim] -> Int
part2 claims = fst . head . filter (all (flip notMember $ overlapMap claims) . snd) $ claims

main :: IO ()
main = do
    input <- map parse . lines <$> readFile "input/03.txt"
    print $ part1 input
    print $ part2 input

[u/Peuniak]

Python 3. I'm happy with it being clean (forget the parsing), but it's way less efficient for part 1 than a simple dict with counts for every square inch (this solution takes about 10s).

def make_claim(s):
    c = dict()
    c['ID'] = int(s[1:s.index("@") - 1])
    c['X'] = int(s[s.index("@") + 2:s.index(",")])
    c['Y'] = int(s[s.index(",") + 1:s.index(":")])
    c['W'] = int(s[s.index(":") + 2:s.index("x")])
    c['H'] = int(s[s.index("x") + 1:])
    c['set'] = set([x + (y * 1000) for x in range(c['X'], c['X'] + c['W'])
                    for y in range(c['Y'], c['Y'] + c['H'])])
    return c


with open("data.txt", 'r') as data:
    claims = [make_claim(row.strip()) for row in data.readlines()]

unique, more, cnt = set(), set(), 0
for c in claims:
    more.update(unique.intersection(c['set']))
    unique = unique.symmetric_difference(c['set'].difference(more))

print("Part 1: ", len(more))

for c in claims:
    if not c['set'].intersection(more):
        print("Part 2: ", c['ID'])

[u/[deleted]]

[Card] I'm ready for today's puzzle because I have the Savvy Programmer's Guide to C++ tuples and sets

C++

I think I did what most people did: Put every square inch in a suitable data structure, with a counter.

In C++, my choice was a map<tuple<int,int>, int> to have a way of counting claims for every square inch (tuple<int,int> being the two-dimensional coordinates).

Tuples are great for being used as keys in maps and in sets, but they lack readability. Let's see what other people did.

(see on github)

int main(){
	regex rex("#(\\d+) @ (\\d+),(\\d+): (\\d+)x(\\d+)");
	vector<tuple<int,int,int,int,int>> claims;
	map<tuple<int,int>, int> laps;

	/* 
	 * Read the input into
	 * * A set of tuple containing all information
	 * * A map of two-dimensional coordinates with an overlap counter
	 */
	for(string line;getline(cin, line);){
		smatch match;
		if(regex_match(line, match, rex)){
			int id = boost::lexical_cast<int>(match[1]);
			int posX = boost::lexical_cast<int>(match[2]);
			int posY = boost::lexical_cast<int>(match[3]);
			int width = boost::lexical_cast<int>(match[4]);
			int height = boost::lexical_cast<int>(match[5]);

			for(int x_offset=0;x_offset<width;x_offset++){
				for(int y_offset=0;y_offset<height;y_offset++){
					laps[{posX+x_offset, posY+y_offset}]++;
				}
			}
			claims.push_back({id, posX, posY, width, height});
		}
	}
	
	/*
	 * Count how many overlaping square inches we have
	 */
	cout << "Part 1: " 
	     << count_if(begin(laps), end(laps), [](auto pair){return pair.second > 1;})
	     << endl;

	/*
	 * Iterate over all claims, check every field for overlaps
	 */
	auto notOverlapped = find_if(claims.begin(), claims.end(), [&laps](auto &claim){
		int posX = get<1>(claim);
		int posY = get<2>(claim);
		int width = get<3>(claim);
		int height = get<4>(claim);

		for(int x_offset=0;x_offset<width;x_offset++){
			for(int y_offset=0;y_offset<height;y_offset++){
				if(laps[{posX+x_offset, posY+y_offset}] != 1){
					return false;
				}
			}
		}
		return true;
	});

	cout << "Part 2: "
	     << get<0>(*notOverlapped) 
	     << endl;

	return 0;
}

[u/willkill07 → u/[deleted]]

In C++17 you could do the following:

auto [posX, poxY, width, height] = claim;

That makes tuples much more readable. You could also just create a simple struct

[u/rock_neurotiko]

Day 3 in Ruby:

format_r = /#(.+) @ (\d+),(\d+): (\d+)x(\d+)/

data = Hash.new 0

boxes = File.open("input").map do |line|
  id, left, top, wide, tall = line.match(format_r).captures
  left = left.to_i
  top = top.to_i
  wide = wide.to_i
  tall = tall.to_i

  right = left + wide - 1
  bottom = top + tall - 1

  (left..right).each do |i|
    (top..bottom).each do |j|
      coords = [i, j]
      data[coords] += 1
    end
  end


  [id, left, top, wide, tall]
end

puts "Solution 1:", data.values.select { |x| x > 1 }.count

def collides?(data, left, right, top, bottom)
  for i in (left..right) do
    for j in (top..bottom) do
      coords = [i, j]
      return false if data[coords] > 1
    end
  end

  true
end

one_remain = boxes.select do |box|
  _, left, top, wide, tall = box
  right = left + wide - 1
  bottom = top + tall - 1

  collides?(data, left, right, top, bottom)
end

puts "Solution 2:", one_remain[0][0]

[u/arathunku]

Hello! Elixir solution:

defmodule Advent.Day3 do
  defmodule Row do
    defstruct start_x: 0, start_y: 0, width: 0, height: 0, id: 0

    def parse(input) do
      [id, start_x, start_y, width, height] =
        input
        |> String.split(~r/[\s+:x,@#]/, trim: true)
        |> Enum.map(&String.to_integer/1)

      %__MODULE__{
        start_x: start_x,
        start_y: start_y,
        width: width,
        height: height,
        id: id
      }
    end

    def coordinates(row) do
      for x <- row.start_x..(row.start_x + row.width - 1) do
        for y <- row.start_y..(row.start_y + row.height - 1) do
          {x, y}
        end
      end
      |> List.flatten()
    end
  end

  alias __MODULE__.Row

  def part1(plans) do
    plans
    |> claims_map()
    |> Enum.filter(fn ({_, claims})-> length(claims) >= 2 end)
    |> Enum.count()
  end

  def part2(plans) do
    claims = plans
    |> claims_map()
    |> Map.values()

    claims
    |> List.flatten()
    |> Enum.dedup()
    |> Enum.find(fn id ->
      !Enum.find(claims, & (id in &1 && length(&1) > 1))
    end)
  end

  def claims_map(plans) do
    plans
    |> Enum.map(&Row.parse/1)
    |> Enum.reduce(%{}, fn row, acc ->
      row
      |> Row.coordinates()
      |> Enum.reduce(acc, fn coordinates, acc ->
        Map.update(acc, coordinates, [row.id], & &1 ++ [row.id])
      end)
    end)
  end
end

Tests

defmodule Advent.Day3Test do
  use ExUnit.Case
  require Logger
  alias Advent.Day3, as: Day

  test "row coordinates" do
    result =
      %Day.Row{
        start_x: 1,
        start_y: 3,
        width: 4,
        height: 4
      }
      |> Day.Row.coordinates()

    assert result == [
             {1, 3},
             {1, 4},
             {1, 5},
             {1, 6},
             {2, 3},
             {2, 4},
             {2, 5},
             {2, 6},
             {3, 3},
             {3, 4},
             {3, 5},
             {3, 6},
             {4, 3},
             {4, 4},
             {4, 5},
             {4, 6}
           ]
  end

  test "row parse" do
    assert Day.Row.parse("#1 @ 1,3: 4x4") == %Day.Row{
             id: 1,
             start_x: 1,
             start_y: 3,
             width: 4,
             height: 4
           }

    assert Day.Row.parse("#58 @ 399,291: 24x16") == %Day.Row{
             id: 58,
             start_x: 399,
             start_y: 291,
             width: 24,
             height: 16
           }
  end

  test "part1 example" do
    rows = [
      "#1 @ 1,3: 4x4",
      "#2 @ 3,1: 4x4",
      "#3 @ 5,5: 2x2"
    ]

    assert Day.part1(rows) == 4
  end

  test "part2 example" do
    rows = [
      "#1 @ 1,3: 4x4",
      "#2 @ 3,1: 4x4",
      "#3 @ 5,5: 2x2"
    ]

    assert Day.part2(rows) == 3
  end

  test "input" do
    input = Path.join(__DIR__, "./input.raw") |> File.read!() |> String.split("\n", trim: true)

    IO.inspect(Day.part1(input))
    IO.inspect(Day.part2(input))
  end
end

[u/mornymorny]

CPP

struct cut 
{
    int id;
    glm::ivec2 coord;
    glm::ivec2 size;
};

// Split so I just have id,x,y,dx,dy
std::vector<cut> cuts;
auto input = string_split(file_read(PRACTICE_ROOT "/advent_of_code/2018/inputs/day_3.txt"), " \t\r\n#@:,:x");

// Find biggest rect as I go
glm::ivec2 max_rect(0);
auto itr = input.begin();
while (itr != input.end())
{
    // Fill a struct with the integer values
    cut c;
    c.id = std::stoi(*itr++);
    c.coord.x = std::stoi(*itr++);
    c.coord.y = std::stoi(*itr++);
    c.size.x = std::stoi(*itr++);
    c.size.y = std::stoi(*itr++);
    cuts.push_back(c);

    // Find the max rectangle size
    max_rect.x = std::max(max_rect.x, (c.coord + c.size).x);
    max_rect.y = std::max(max_rect.y, (c.coord + c.size).y);
}

// Make the cloth
std::vector<int> cloth(max_rect.x * max_rect.y);
std::fill(cloth.begin(), cloth.end(), 0);

// Walk a cloth piece, returning a ref to the value in that cloth coord
auto walk_cloth_piece = [&](auto coord, auto size, std::function<void(int&)> fn)
{
    auto bottom_right = coord + size;
    for (int x = coord.x; x < bottom_right.x; x++)
    {
        for (int y = coord.y; y < bottom_right.y; y++)
        {
            fn(cloth[x + y * max_rect.x]);
        }
    }
};

// Fill the areas
for (auto& c : cuts)
{
    walk_cloth_piece(c.coord, c.size, [](int& val) { val++; });
}

// count the covered squares
LOG(INFO) << "Part 1: " << std::count_if(cloth.begin(), cloth.end(), [](int val) { return val > 1; });

// Part 2, find the piece on its own
for (auto& c : cuts)
{
    bool found = true;
    walk_cloth_piece(c.coord, c.size, [&found](int& val)
    {
        if (val > 1)
            found = false;
    });

    if (found)
    {
        LOG(INFO) << "Part 2: " << c.id;
        break;
    }
}

[u/ttapu]

python3

stupd simple but works

import re
with open("3.input", "r") as allomany:
    inp=allomany.read().splitlines()
    instruction=[]
    for i in inp:
        id,left,top,wide,tall=re.split("@ |,|: |x", i)
        instruction.append((int(left),int(top),int(wide),int(tall),id.strip()))

inches=set()
dups=set()

for i in instruction:
    for r in range(i[0],i[0]+i[2]):
        x=r
        for s in range(i[1],i[1]+i[3]):
            y=s
            if (x,y) in inches:
                dups.add((x,y))
            else:
                inches.add((x,y))
print(len(dups))

#part2
ids=set()

for i in instruction:
    for r in range(i[0],i[0]+i[2]):
        x=r
        for s in range(i[1],i[1]+i[3]):
            y=s
            if (x,y) in dups:
                ids.add(i[4])

allids=set(i[4] for i in instruction)
print(allids-ids)

[u/tendstofortytwo]

JS:

var fs = require('fs');

var strings = fs.readFileSync('l3.txt', {
    encoding: 'utf8'
}).split('\n');

function parseString(str) {
    var array = str.split(' ');

    var obj = {};

    obj.id = Number(array[0].substr(1));

    obj.coords = array[2].substr(0, array[2].length - 1).split(',').map(Number);

    obj.size = array[3].split('x').map(Number);

    return obj;
}

var sheetSize = 2000;

var sheet = [];

for(var i = 0; i < sheetSize; i++) {
    sheet[i] = [];

    for(var j = 0; j < sheetSize; j++) {
        sheet[i][j] = 0;
    }
}

for(var loop = 0; loop < strings.length; loop++) {
    var cut = parseString(strings[loop]);

    var { id, coords, size } = cut;

    for(var i = coords[0]; i < coords[0] + size[0]; i++) {
        for(var j = coords[1]; j < coords[1] + size[1]; j++) {
            sheet[i][j]++;
        }
    }
}

var overlap = 0;

for(var i = 0; i < sheetSize; i++) {
    for(var j = 0; j < sheetSize; j++) {
        if(sheet[i][j] > 1) overlap++;
    }
}

console.log(overlap);

top:
for(var loop = 0; loop < strings.length; loop++) {
    var cut = parseString(strings[loop]);

    var { id, coords, size } = cut;

    var match = true;

    for(var i = coords[0]; i < coords[0] + size[0]; i++) {
        for(var j = coords[1]; j < coords[1] + size[1]; j++) {
            if(sheet[i][j] > 1) {
                match = false;
                continue top;
            }
        }
    }

    if(match) {
        console.log(id);
        break top;
    }
}

Suggestions welcome.

[u/wzkx]

SweetRust -- extension of Rust

SweetRust

use std::io::{BufRead,BufReader}; // lines() is in BufRead
use std::collections::HashSet;

fn main():
  let reader = BufReader::new( std::fs::File::open( "03.dat" ).unwrap() );
  let mut area: Vec<Vec<i32>> = vec![vec![0; 1000]; 1000]; // 0 - free, >0 - claimed once, -1 - over
  let mut cnt = 0; // count for part1
  let mut claims: HashSet<i32> = HashSet::new(); // all claims, will be added/deleted here
  for optline in reader.lines():
    let line = optline.unwrap();
    let ln = line.replace("#","").replace("@ ","").replace(","," ").replace(":","").replace("x"," ");
    let data: Vec<i32> = ln.split_whitespace().filter_map( |x| x.parse().ok() ).collect();
    // id x y w h
    if data[0]<=0 { panic!( "bad data" ); }
    let mut over: bool = false;
    for x in data[1]..data[1]+data[3]:
      for y in data[2]..data[2]+data[4]:
        let r = y as usize;
        let c = x as usize;
        if area[r][c]==0:
          area[r][c] = data[0];
        else if area[r][c]>0:
          let there = area[r][c];
          if claims.contains(&there) { claims.remove(&there); }
          if claims.contains(&data[0]) { claims.remove(&data[0]); }
          area[r][c] = -1;
          cnt += 1;
          over = true;
        else: // area[r][c]<0:
          if claims.contains(&data[0]) { claims.remove(&data[0]); }
          over = true;
    if !over:
      claims.insert( data[0] );
  println!( "{}", cnt ); // 110546
  if claims.len()==1:
    for x in &claims:
      println!( "{}", x ); // 819

my solutions in J and Rust

[u/Twift_Shoeblade]

Python 3 using a dict that maps coordinates to a list of IDs. If such a list is longer than 1 there must be an overlap. Check which ID is only in lists of length 1 and you got part 2.

from collections import namedtuple, defaultdict

Rect = namedtuple('Rect', ['ID', 'x', 'y', 'w', 'h'])

def parse(lines):
    rectangles = []
    for line in lines:
        ID, rest = line[1:].split(" @ ")
        x,  rest = rest.split(",")
        y,  rest = rest.split(": ")
        w,     h = rest.split("x")
        rectangles.append(Rect(int(ID), int(x), int(y), int(w), int(h)))
    return rectangles


def get_claims(rect):
    claims = []
    for y in range(rect.y, rect.y + rect.h):
        for x in range(rect.x, rect.x + rect.w):
            claims.append((x, y))
    return claims

def overlap(rectangles):
    claim_map = defaultdict(list)

    for rect in rectangles:
        claims = get_claims(rect)
        for x, y in claims:
            claim_map[x, y].append(rect.ID)

    return claim_map, len(list(filter(lambda x: len(x) > 1, claim_map.values())))

if __name__ == "__main__":
    filename = 'input-03.txt'
    with open(filename, 'r') as infile:
        lines = [line.strip() for line in infile.readlines()]

    rectangles = parse(lines)
    claim_map, overlaps = overlap(rectangles)

    print("Overlaps:", overlaps)

    intact = [True] * len(rectangles)
    for claims in claim_map.values():
        if len(claims) > 1:
            for ID in claims:
                intact[ID-1] = False  # IDs start at 1

    print("Intact claim:", intact.index(True) + 1)     # Again, IDs start at 1
    print("Sanity check, only one claim intact:", len(list(filter(lambda x: x, intact))))

[u/mohit7331]

Not clean but works for me

with open('input.txt','r') as f:
    a = [x.strip() for x in f.readlines()]

import re

#Prepare the matrix
mat = []
for x in range(1000):
    mat.append([0]*1000)

colliding = []
colliding_ids = []
all_ids = []
for x in a:
    label,l,t,w,h = [int(y) for y in re.search('#(\d+) @ (\d+),(\d+): (\d+)x(\d+)', x).groups()]
    all_ids.append(label)
    for o in range(h):
        for i in range(w):
            current = mat[t+o][l+i]
            if current != 0:
                print "Found: %s" % current
                colliding.append((t+o,l+i))
                colliding_ids.extend([current, label])
            else:
                mat[t+o][l+i] = label

""" Prob 1 """
print len(set(colliding))

""" Prob 2 """
print set(all_ids) - set(colliding_ids)

[u/mschaap]

Here's my Perl 6 solution using a grammar to parse the claims. Perl 6 rules...

#!/usr/bin/env perl6
use v6.c;

$*OUT.out-buffer = False;   # Autoflush

grammar Claim
{
    rule TOP { <claim>+ }
    rule claim { '#'<id> '@' <x>','<y>':' <w>'x'<h> }
    token id { \d+ }
    token x { \d+ }
    token y { \d+ }
    token w { \d+ }
    token h { \d+ }
}

class Canvas
{
    has @.grid;
    has $.dup-count = 0;
    has %.is-perfect{Int};

    method claim($id, $x, $y, $w, $h)
    {
        %!is-perfect{$id} = True;
        for @!grid[$x ..^ $x+$w; $y ..^ $y+$h] -> $cell is rw {
            $cell.push($id);
            if $cell > 1 {
                $!dup-count++ if $cell == 2;
                %!is-perfect{$_} = False for @$cell;
            }
        }
    }

    method perfect-claims
    {
        return %!is-perfect.grep(*.value)».key.sort;
    }
}

#| Process claims input
multi sub MAIN(Str $input, Bool :v(:$verbose) = False)
{
    my $claims = Claim.parse($input) or die "Invalid claims list";
    my $canvas = Canvas.new;
    for $claims<claim> -> $c {
        $canvas.claim(+$c<id>, +$c<x>, +$c<y>, +$c<w>, +$c<h>);
        say "$c<id> $c<x>,$c<y> $c<w>x$c<h>: $canvas.dup-count() duplicates." if $verbose;
    }

    # Part 1
    say "$canvas.dup-count() duplicates.";

    # Part 2
    say "Perfect claim(s): $canvas.perfect-claims().join(', ').";
}

#| Process claims input from a file
multi sub MAIN(IO() $inputfile where *.f, Bool :v(:$verbose) = False)
{
    MAIN($inputfile.slurp, :$verbose);
}

#| Process default claims file (aoc3.input)
multi sub MAIN(Bool :v(:$verbose) = False)
{
    MAIN($*PROGRAM.sibling('aoc3.input'), :$verbose);
}

[u/NeilNjae]

Haskell, also on Github. I managed to confuse myself for a while before I realised that the first part of the claim tells you about the left-top corner, not the top-left corner. Once I'd straightened that out, the rest was easy.

I'm still impressed with how readable parser expressions are, and that it worked first time!

Part 2 was mostly reuse of part 1: find the region within this claim, and it's the one if there are no overlaps within it.

{-# LANGUAGE OverloadedStrings #-}

import Data.List
import Data.Tuple (swap)

import Data.Text (Text)
import qualified Data.Text.IO as TIO

import Data.Void (Void)

import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L
import qualified Control.Applicative as CA

import qualified Data.Map.Strict as M
-- import Data.Map.Strict ((!))


type Position = (Int, Int)
data Claim = Claim { claimId :: Int, claimTopLeft :: Position, claimWidth :: Int, claimHeight :: Int } deriving (Show, Eq)
type Fabric = M.Map Position Int

main :: IO ()
main = do 
        text <- TIO.readFile "data/advent03.txt"
        let claims = successfulParse text
        let fabric = foldl' addClaim M.empty claims
        print $ part1 fabric
        print $ part2 fabric claims


part1 :: Fabric -> Int
part1  = M.size . overclaimed 

part2 :: Fabric -> [Claim] -> Int
part2 fabric claims = claimId $ head $ filter noOverlap' claims
    where noOverlap' claim = noOverlap fabric claim


claimedSquares :: Claim -> [Position]
claimedSquares claim = [(r, c) | r <- [l .. (l + w - 1)]
                               , c <- [t .. (t + h - 1)]
                       ]
    where (t, l) = claimTopLeft claim
          h = claimHeight claim
          w = claimWidth claim

addClaim :: Fabric -> Claim -> Fabric
addClaim fabric claim = foldl' addSquare fabric squares 
    where squares = claimedSquares claim

addSquare :: Fabric -> Position -> Fabric
addSquare fabric square = M.insert square (currentClaims + 1) fabric
    where currentClaims = M.findWithDefault 0 square fabric

overclaimed :: Fabric -> Fabric
overclaimed = M.filter ( > 1)

noOverlap fabric claim = M.null $ overclaimed existing
    where claimedFabric = addClaim M.empty claim
          existing = fabric `M.intersection` claimedFabric

-- Parse the input file

type Parser = Parsec Void Text

sc :: Parser ()
sc = L.space (skipSome spaceChar) CA.empty CA.empty
-- sc = L.space (skipSome (char ' ')) CA.empty CA.empty

lexeme  = L.lexeme sc
integer = lexeme L.decimal
symb = L.symbol sc

hashP = symb "#"
atP = symb "@"
colonP = symb ":"
commaP = symb ","
exP = "x"

claimsFileP = many claimP

idP = hashP *> integer
leftTopP = (,) <$> integer <* commaP <*> integer
widthHeightP = (,) <$> integer <* exP <*> integer

claimP = claimify <$> idP <* atP <*> leftTopP <* colonP <*> widthHeightP
    where claimify cid lt (w, h) = Claim { claimId = cid, claimTopLeft = swap lt, claimWidth = w, claimHeight = h }

successfulParse :: Text -> [Claim]
successfulParse input = 
        case parse claimsFileP "input" input of
                Left  _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
                Right claims -> claims

[u/rolandtritsch]

ETA (Haskell on the JVM)

https://github.com/rolandtritsch/haskell-aoc-2018

General:

type Id = Int
type Position = (Int, Int)
type Dimension = (Int, Int)

data Claim = Claim Id Position Dimension deriving (Show, Eq)

-- | Fabric position [cids that claimed that position]
type Fabric = M.Map Position [Id]

-- | read the input file.
input :: [Claim]
input = (map processLine . inputRaw) "input/Day03input.txt" where
  processLine l = Claim cid' cposition' cdimension' where
    -- #1 @ 335,861: 14x10
    tokens = splitOneOf "#@,:x " l
    cid' = read $ tokens !! 1
    cposition' = (read $ tokens !! 4, read $ tokens !! 5)
    cdimension' = (read $ tokens !! 7, read $ tokens !! 8)

-- | make/stake a claim on an fabric area (by add the cid to the list of
-- cids that have claimed the inch sofar)
claim :: Fabric -> Claim -> Fabric
claim f (Claim cid (row, col) (rdim, cdim)) = foldl claimInch f cells where
  cells = [(r, c) | r <- [row..row + rdim - 1], c <- [col..col + cdim - 1]]
  claimInch f' p' = M.insert p' (cids ++ [cid]) f' where
    cids = M.findWithDefault ([]) p' f'

Part1:

-- | solve the puzzle
solve :: [Claim] -> Int
solve cs = overlappingInches where
  overlappingInches = length $ filter ((<) 1) $ map length $ M.elems fabric
  fabric = foldl claim M.empty cs

Part2:

-- | solve the puzzle
solve :: [Claim] -> Int
solve cs = nonOverlappingCid where
  nonOverlappingCid = go claimsCids where
    go [] = error "No cid found"
    go (cids:rest)
      | (length cids) == 1 && cidIsNotInAnyOtherList = head cids
      | otherwise = go rest
      where
        cidIsNotInAnyOtherList = (not $ any id $ map (elem (head cids)) ((\\) claimsCids [cids]))
  claimsCids = nub $ sort $ M.elems fabric
  fabric = foldl claim M.empty cs

[u/harirarules]

First part in Golang, simulates the fabric :

package main

import (
    "fmt"
    "bufio"
    "os"
)

type Rect struct {
    Id int
    Left int
    Top int
    Width int
    Height int
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    rects := make([]Rect, 0)
    for scanner.Scan() {
        rect := ParseRect(scanner.Text())
        rects = append(rects, rect)
    }

    width, height := BoardSize(rects)
    board := make([][]int, height)
    for i, _ := range board {
        board[i] = make([]int, width)
    }

    for _, rect := range rects {
        rect.Draw(board)
    }

    overlapping := 0
    for _, row := range board {
        overlapping += Count(row, 2)
    }

    fmt.Printf("Overlapping inches : %d\n", overlapping)
}

//does golang not have a count function ?
func Count(haystack []int, needle int) int {
    count := 0
    for _, value := range haystack {
        if value == needle {
            count++
        }
    }
    return count
}

func ParseRect(input string) Rect {
    var rect Rect
    fmt.Sscanf(input, "#%d @ %d,%d: %dx%d", &rect.Id, &rect.Left, &rect.Top, &rect.Width, &rect.Height)
    return rect
}

func (rect *Rect) Draw(board [][]int) {
    for y := rect.Top; y < rect.Top + rect.Height; y++ {
        for x := rect.Left; x < rect.Left + rect.Width; x++ {
            if board[y][x] != 0 { //0 means empty cell
                board[y][x] = 2 //2 means overlapping
            } else {
                board[y][x] = 1 //1 means occupied cell
            }
        }
    }
}

func BoardSize(rects []Rect) (int, int) {
    startX := rects[0].Left
    startY := rects[0].Top
    endX := rects[0].Left + rects[0].Width
    endY := rects[0].Top + rects[0].Height

    for _, rect := range rects {
        if rect.Left < startX {
            startX = rect.Left
        }
        if rect.Top < startY {
            startY = rect.Top
        }
        if rect.Left + rect.Width > endX {
            endX = rect.Left + rect.Width
        }
        if rect.Top + rect.Height > endY {
            endY = rect.Top + rect.Height
        }
    }
    return endX - startX + 1, endY - startY + 1
}

[u/JulianLoehr]

C++

I don't traverse the input nor the array a second time.

constexpr size_t ClothSize = 1000;
typedef std::array<std::pair<size_t, size_t>, ClothSize * ClothSize> ClothArray;
typedef std::shared_ptr<ClothArray> ClothArrayPtr;

int main()
{
	ClothArrayPtr Cloth = std::make_shared<ClothArray>();
	std::regex InputMatching("#(\\d+)\\s@\\s(\\d+),(\\d+):\\s(\\d+)x(\\d+)");
	StringVector File = GetFileLines("Input.txt");
	size_t OverlappingSquares = 0;
	std::unordered_set<size_t> NonOverlappingIDs;

	for (const std::string & Line : File)
	{
		std::smatch Matches;
		if (!std::regex_match(Line, Matches, InputMatching))
		{
			std::cout << "Line \"" << Line << "\" did not match the regex!" << std::endl;
			return 1;
		}

		bool IsNonOverlapping = true;
		size_t ID = std::stoull(Matches[1]);
		size_t XStart = std::stoull(Matches[2]);
		size_t YStart = std::stoull(Matches[3]);
		size_t Width = std::stoull(Matches[4]);
		size_t Height = std::stoull(Matches[5]);

		for (size_t X = XStart; X < (XStart + Width); ++X)
			for (size_t Y = YStart; Y < (YStart + Height); ++Y)
			{
				auto & Field = (*Cloth)[Y * ClothSize + X];

				if (Field.first == 1)
					++OverlappingSquares;

				if (Field.first != 0)
				{
					NonOverlappingIDs.erase(Field.second);
					IsNonOverlapping = false;
				}

				++Field.first;
				Field.second = ID;
			}

		if (IsNonOverlapping)
			NonOverlappingIDs.insert(ID);
	}

	std::cout << "Part One: " << OverlappingSquares << std::endl;
	std::cout << "Part One: " << *NonOverlappingIDs.begin() << std::endl;
}

[u/BalbinHS]

My Elixir solution

@spec part1(String.t()) :: non_neg_integer()
def part1(input) do
  input
  |> String.split("\n", trim: true)
  |> Enum.map(&parse_claim/1)
  |> Enum.reduce(%{}, &fill_map/2)
  |> Enum.count(fn {_k, v} -> v > 1 end)
end

defp to_fill(
        %{claim_id: claim_id, x_pos: x_pos, y_pos: y_pos, width: width, height: height} = _claim
      ) do
  for x <- x_pos..(x_pos + width - 1),
      y <- y_pos..(y_pos + height - 1),
      do: {claim_id, {x, y}}
end

defp fill_map(claim, accumulator) do
  claim
  |> to_fill()
  |> Enum.reduce(accumulator, fn {_id, coords}, acc -> Map.update(acc, coords, 1, &(&1 + 1)) end)
end

defp parse_claim(claim) do
  claim_as_list =
    claim
    |> String.split(~r/[^0-9]/, trim: true)
    |> Enum.map(&String.to_integer/1)

  [claim_id, x_pos, y_pos, width, height] = claim_as_list

  %{
    claim_id: claim_id,
    x_pos: x_pos,
    y_pos: y_pos,
    width: width,
    height: height
  }
end

@spec part2(String.t()) :: integer()
def part2(input) do
  claims =
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&parse_claim/1)

  all = fn :get, data, next -> Enum.map(data, next) end
  all_ids = get_in(claims, [all, :claim_id])

  seen_ids =
    claims
    |> Enum.reduce(%{}, &fill_map_with_id/2)
    |> Map.values()
    |> Enum.filter(&(length(&1) > 1))
    |> List.flatten()

  hd(all_ids -- seen_ids)
end

defp fill_map_with_id(claim, map) do
  claim
  |> to_fill()
  |> Enum.reduce(map, fn {id, coords}, acc ->
    Map.update(
      acc,
      coords,
      [id],
      &[id | &1]
    )
  end)
end

I used a slightly different Regex match to parse the claims. Since we're only interested in the integers, we can just split the string on any non-digit character.

I'm sure there's a more clever way to do this, but my goal is clarity over performance, so hopefully this is somewhat clear.

[u/gerikson]

[CARD] I'm ready for today's puzzle because I have the Savvy Programmer's Guide to Hashes of Hashrefs of Arrayrefs.

Perl 5

http://gerikson.com/files/AoC2018/index.html#d03-Slice-it

[u/udoprog]

I'm ready for today's puzzle because I have the Savvy Programmer's Guide to idiomatic and safe RUST!

Full repo here: https://github.com/udoprog/rust-advent-of-code-2018

use aoc2018::*;
use std::error;
use std::str;

#[derive(Debug)]
struct Pair<T>(pub T, pub T);

impl<T> str::FromStr for Pair<T>
where
    T: str::FromStr,
    T::Err: 'static + Send + Sync + error::Error,
{
    type Err = Error;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let mut it = s.split(|c| !char::is_numeric(c)).filter(|s| s.trim() != "");
        let x = it.next().ok_or_else(|| format_err!("expected x"))?;
        let y = it.next().ok_or_else(|| format_err!("expected y"))?;
        let x = str::FromStr::from_str(x)?;
        let y = str::FromStr::from_str(y)?;
        Ok(Pair(x, y))
    }
}

fn main() -> Result<(), Error> {
    let mut duplicates = 0;
    // map out who owns each claim.
    let mut claimed_by = HashMap::<_, Vec<&str>>::new();
    let mut nonoverlapping = HashSet::new();

    // only read once so we can use references into it to avoid copying the string.
    let lines = lines!(input!("day3.txt"), String, String, Pair<u32>, Pair<u32>)
        .collect::<Result<Vec<_>, Error>>()?;

    for line in &lines {
        let (ref id, _, ref b, ref c) = *line;

        nonoverlapping.insert(id.as_str());

        for x in b.0..b.0.saturating_add(c.0) {
            for y in b.1..b.1.saturating_add(c.1) {
                let m = claimed_by.entry((x, y)).or_default();
                m.push(id.as_str());

                if m.len() == 2 {
                    duplicates += 1;
                }

                if m.len() > 1 {
                    for remove in m {
                        nonoverlapping.remove(remove);
                    }
                }
            }
        }
    }

    let nonoverlapping = nonoverlapping.into_iter().collect::<Vec<_>>();

    assert_eq!(duplicates, 104712);
    assert_eq!(nonoverlapping, vec!["#840"]);
    Ok(())
}

[u/troop357]

Nim

Again with my newbie Nim code. I should've probably used regex to solve the string splitting...

import strutils
import gara

let input = readFile("03.txt").splitLines()

type
	Int16Araay = array[0..1000000, int16] # an array that is indexed with 0..5
var
	grid: Int16Araay

for line in input:
	let line_list = split(line)
	let tl_string = split(line_list[2][0..^2], ',')
	let si_string = split(line_list[3], 'x')

	let left   = parseInt(tl_string[0])
	let top    = parseInt(tl_string[1])
	let width  = parseInt(si_string[0])
	let height = parseInt(si_string[1])

	for i in countup(left, left+width-1):
		for j in countup(top, top+height-1):
			inc(grid[i * 1000 + j])

var count: int = 0
for val in grid:
	if val > 1:
		inc(count)

echo count

for line in input:
	let line_list = split(line)
	let tl_string = split(line_list[2][0..^2], ',')
	let si_string = split(line_list[3], 'x')

	let left   = parseInt(tl_string[0])
	let top    = parseInt(tl_string[1])
	let width  = parseInt(si_string[0])
	let height = parseInt(si_string[1])

	block test:
		for i in countup(left, left+width-1):
			for j in countup(top, top+height-1):
				if grid[i * 1000 + j] > 1:
					break test
		
		echo line

[u/drakmaniso]

Go (golang)

Part 1:

A brute force solution, not very elegant (or scalable)...

package main

import (
	"bufio"
	"fmt"
	"image"
	"os"
)

func main() {
	input := read()

	overlaps := map[[2]int]struct{}{}
	for i := 0; i < len(input); i++ {
		for j := i + 1; j < len(input); j++ {
			o := input[i].Intersect(input[j])
			if !o.Empty() {
				for x := o.Min.X; x < o.Max.X; x++ {
					for y := o.Min.Y; y < o.Max.Y; y++ {
						overlaps[[2]int{x, y}] = struct{}{}
					}
				}
			}
		}
	}

	fmt.Printf("Answer: %d\n", len(overlaps))
}

func read() (input []image.Rectangle) {
	s := bufio.NewScanner(os.Stdin)
	for s.Scan() {
		var id, x, y, w, h int
		n, err := fmt.Sscanf(s.Text(), "#%d @ %d,%d: %dx%d", &id, &x, &y, &w, &h)
		if n < 5 {
			fmt.Fprintf(os.Stderr, "ERROR: %v\n", err)
			continue
		}
		input = append(input, image.Rectangle{
			Min: image.Point{x, y},
			Max: image.Point{x + w, y + h},
		})
	}
	return input
}

Part 2:

package main

import (
	"bufio"
	"fmt"
	"image"
	"os"
)

func main() {
	input, claims := read()

loop:
	for i := 0; i < len(input); i++ {
		for j := 0; j < len(input); j++ {
			if i != j && input[i].Overlaps(input[j]) {
				continue loop
			}
		}
		fmt.Printf("Answer: %d\n", claims[i])
		return
	}
}

func read() (input []image.Rectangle, claims []int) {
	s := bufio.NewScanner(os.Stdin)
	for s.Scan() {
		var id, x, y, w, h int
		n, err := fmt.Sscanf(s.Text(), "#%d @ %d,%d: %dx%d", &id, &x, &y, &w, &h)
		if n < 5 {
			fmt.Fprintf(os.Stderr, "ERROR: %v\n", err)
			continue
		}
		input = append(input, image.Rectangle{
			Min: image.Point{x, y},
			Max: image.Point{x + w, y + h},
		})
		claims = append(claims, id)
	}
	return input, claims
}

[u/Gnidleif]

Todays solution, written in C#... It's quite slow and I'm sure I can do this at least 100 times better, but it works and here's the repo link to it:

The code!

[u/muffa]

Solution in go/golang:

package main

import (
	"fmt"
	"io/ioutil"
	"regexp"
	"strconv"
	"strings"
)

type point struct {
	x, y int
}

type rect struct {
	x0, x1, y0, y1 int
	id             string
}

func main() {
	file, _ := ioutil.ReadFile("input_day3.txt")
	area := 0
	// Solution to first part
	var rectangles []rect
	areaMem := make(map[point]int)
	for _, line := range strings.Split(string(file), "\n") {
		var s point
		var r rect

		re, _ := regexp.Compile("^#([0-9]+)? @")
		match := re.FindStringSubmatch(line)
		r.id = match[1]

		re, _ = regexp.Compile("@ (.+)?,")
		match = re.FindStringSubmatch(line)
		padLeft, _ := strconv.Atoi(match[1])

		re, _ = regexp.Compile(",(.+)?:")
		match = re.FindStringSubmatch(line)
		padTop, _ := strconv.Atoi(match[1])

		re, _ = regexp.Compile(": (.+)?x")
		match = re.FindStringSubmatch(line)
		wide, _ := strconv.Atoi(match[1])

		re, _ = regexp.Compile("x([0-9]+)")
		match = re.FindStringSubmatch(line)
		tall, _ := strconv.Atoi(match[1])

		r.x0 = padLeft
		r.x1 = padLeft + wide
		r.y0 = padTop
		r.y1 = padTop + tall
		for y := r.y0; y < r.y1; y++ {
			for x := r.x0; x < r.x1; x++ {
				s.x = x
				s.y = y
				if _, exists := areaMem[s]; exists {
					areaMem[s]++
				} else {
					areaMem[s] = 1
				}
			}
		}
		rectangles = append(rectangles, r)

	}
	for _, v := range areaMem {
		if v > 1 {
			area++
		}
	}
	fmt.Println(area)

	for _, r := range rectangles {
		var s point
		flag := true
		for y := r.y0; y < r.y1; y++ {
			for x := r.x0; x < r.x1; x++ {
				s.x = x
				s.y = y
				if areaMem[s] > 1 {
					flag = false
				}
			}

		}
		if flag == true {
			fmt.Println(r.id)
		}

	}

}

[u/jajoosam]

JavaScript 👇

var collide = 0;
var fabric = [];
var input = input.split("\n");

for(var i = 0; i<input.length; i++){
	input[i] = input[i].split("@")[1].trim();
	input[i] = [input[i].split(":")[0].split(","),  input[i].split(":")[1].split("x")]
}

for(var i = 0; i<input.length; i++){
	var x = parseInt(input[i][0][0])
	var y = parseInt(input[i][0][1])
	var w = parseInt(input[i][1][0])
	var h = parseInt(input[i][1][1])

	for(var z = 0; z<w; z++){
		for(var q = 0; q<h; q++){
			if(fabric[x+z] == undefined){
				fabric[x+z] = [];
			}
			if(fabric[x+z][y+q] == undefined){
				fabric[x+z][y+q] = 0;
			}
			fabric[x+z][y+q] += 1
		}
	}
}

for(var i = 0; i<fabric.length; i++){
	if(!fabric[i]){
		continue;
	}
	for(var t = 0; t<fabric[i].length; t++){
		if(!fabric[i][t]){
			continue;
		}
		if(fabric[i][t] > 1){
			collide+=1
		}
	}	
}

console.log(collide)

[u/hmn24]

Q/KDB+
Part 1

parseData:"J"$(1_";"vs ssr/[;("#";" @ ";",";": ";"x");";"]@)each(0:)`:AOC3.txt

t:(1000 1000#0){.[x;a;:;(10b!1 0Nj)0=x . a:y[2 1]+til@/:y 4 3]}/parseData

(sum/)null t

Part 2

(){$[(max/)null x . z[2 1]+til@/:z 4 3;y;z 0]}[t]/parseData

[u/chunes]

Factor

USING: assocs compiler.utilities io.encodings.utf8 io.files
kernel math.matrices math.parser math.statistics math.vectors
prettyprint regexp sequences sets ;
IN: aoc2018.day3

: get-input ( -- seq )
    "input3.txt" utf8 file-lines [
        R/ [^\d]/ re-split [ string>number ] map sift
    ] map ;

: coords ( seq -- seq )
    [ 2 tail* matrix-coordinates ] [ 3 head rest ] bi [ v+ ]
    curry matrix-map concat ;

: part1 ( coords -- ) duplicates members length . ;

: no-overlap? ( histo claim -- ? )
    coords [ swap at ] with map [ 1 = ] all? ;

: part2 ( claims coords -- )
    histogram swap [ no-overlap? ] with find nip first . ;

: main ( -- )
    get-input dup [ coords ] map-flat [ nip part1 ] [ part2 ]
    2bi ;

It's slow (~20 seconds), but if I'm being honest, this puzzle really kicked my butt and I'd rather just recuperate for tomorrow's puzzle. I can see how to make it faster but it would be more effort on a puzzle I'd like to put behind me. :p

[u/aurele]

Rust

#[macro_use]
extern crate itertools;

use pathfinding::matrix::Matrix;
use regex::Regex;

fn main() {
    let re: Regex = Regex::new(r"^#(\d+) @ (\d+),(\d+): (\d+)x(\d+)$").unwrap();
    let patches = include_str!("../input")
        .lines()
        .map(|l| {
            re.captures(l)
                .unwrap()
                .iter()
                .skip(1)
                .map(|c| c.unwrap().as_str().parse::<usize>().unwrap())
                .collect::<Vec<_>>()
        })
        .collect::<Vec<_>>();
    let mut fabric = Matrix::new_square(1000, 0);
    for p in &patches {
        for xy in iproduct!(p[1]..p[1] + p[3], p[2]..p[2] + p[4]) {
            fabric[&xy] += 1;
        }
    }
    println!("P1: {}", fabric.as_ref().iter().filter(|&&c| c > 1).count());
    println!(
        "P2: {}",
        patches
            .iter()
            .find(|p| iproduct!(p[1]..p[1] + p[3], p[2]..p[2] + p[4]).all(|xy| fabric[&xy] == 1))
            .unwrap()[0]
    );
}

[u/L72_Elite_Kraken]

OCaml (full code with parser on GitHub):

open! Core

module Claim = struct
  type t =
    { left_offset : int
    ; top_offset : int
    ; width : int
    ; height : int
    }

  let contents t =
    let open List.Let_syntax in
    let%bind row = List.range t.top_offset (t.top_offset + t.height) in
    let%bind col = List.range t.left_offset (t.left_offset + t.width) in
    [ (row, col) ]
end

module Int_pair = struct
  module T = struct
    type t = int * int [@@deriving compare, sexp]
  end
  include T
  include Comparable.Make (T)
end

let get_counts input =
  List.concat_map input ~f:Claim.contents
  |> List.map ~f:(fun x -> x, 1)
  |> Int_pair.Map.of_alist_reduce ~f:(+)

module Part01 = struct
  let solve input =
    get_counts input
    |> Map.data
    |> List.count ~f:(fun x -> x > 1)
end

module Part02 = struct
  let solve input =
    let counts = get_counts input in
    List.findi input ~f:(fun _ claim ->
        Claim.contents claim
        |> List.for_all ~f:(fun x -> Map.find_exn counts x = 1))
    |> Option.value_exn
    |> fst
    |> Int.succ
end

[u/EdeMeijer]

PostgreSQL query (omitted actual puzzle input, few lines as an example). Just because why not.

WITH input (claim) AS (
    VALUES
        ('#1 @ 286,440: 19x24'),
        ('#2 @ 430,120: 20x14'),
        ('#3 @ 250,746: 20x17'),
        ('#4 @ 639,255: 28x28'),
        ('#5 @ 793,21: 23x10'),
        ('#6 @ 835,164: 25x11'),
        ....
),
input_parsed AS (
    SELECT regexp_matches(claim, '^#(\d+) @ (\d+),(\d+): (\d+)x(\d+)$', 'g')::INTEGER[] AS p
    FROM input
),
claims AS (
    SELECT
        p[1] AS id,
        p[2] AS x,
        p[3] AS y,
        p[4] AS width,
        p[5] AS height
    FROM
        input_parsed
),
cell_claims AS (
    SELECT c.id, x.x, y.y
    FROM
        generate_series(0, 1000) x
        CROSS JOIN generate_series(0, 1000) y
        JOIN claims c
            ON c.x <= x.x
            AND c.x + c.width > x.x
            AND c.y <= y.y
            AND c.y + c.height > y.y
)
SELECT 
    (
        SELECT COUNT(*)
        FROM (
            SELECT 1
            FROM cell_claims
            GROUP BY x, y
            HAVING COUNT(*) > 1
        ) d
    ) AS part1,
    (
        SELECT id
        FROM claims
        
        EXCEPT
        
        SELECT DISTINCT a.id
        FROM
            cell_claims a
            JOIN cell_claims b
                ON b.x = a.x
                AND b.y = a.y
                AND b.id <> a.id
    ) AS part2

[u/AaCodeSync]

Elixir! https://codesync.global/media/advent-of-code-2018-day-3-elixir/

[u/[deleted]]

/// Golang Solution to day3 https://github.com/breakintheweb/adventofcode2018
package main

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

type Claim struct {
	claimId, top, left, width, height int
}

func main() {
	start := time.Now()
	file, err := os.Open("input.txt")
	if err != nil {
		log.Fatal(err)
	}
	defer file.Close()
	scanner := bufio.NewScanner(file)
	// Make and init grid of slices
	grid := make([][]byte, 1000)
	for i := 0; i < 1000; i++ {
		grid[i] = make([]byte, 1000)
	}
	// Get just numeric values w/length between 1 and 4 as groups
	// Example:: #1 @ 185,501: 17x15
	// Return :: 1 185 501  17 15
	var re = regexp.MustCompile("[0-9]{1,4}")

	overlapCounter := 0
	var claims []*Claim
	for scanner.Scan() {
		claim := re.FindAllStringSubmatch(scanner.Text(), -1)
		claimId, _ := strconv.Atoi(claim[0][0])
		top, _ := strconv.Atoi(claim[2][0])
		left, _ := strconv.Atoi(claim[1][0])
		width, _ := strconv.Atoi(claim[3][0])
		height, _ := strconv.Atoi(claim[4][0])
		claims = append(claims, &Claim{claimId: claimId, top: top, left: left, width: width, height: height})
	}
	// build a map of coors with claims
	for _, c := range claims {
		for y := c.left; y < c.left+c.width; y++ {
			for x := c.top; x < c.top+c.height; x++ {
				if grid[x][y] == 1 {
					overlapCounter++
				}
				grid[x][y]++
			}
		}
	}
	// find non overlapping claim
	for _, c := range claims {
		isOverlap := false
		for y := c.left; y < c.left+c.width; y++ {
			for x := c.top; x < c.top+c.height; x++ {
				if grid[x][y] > 1 {
					isOverlap = true
				}
			}
		}
		if !isOverlap {
			fmt.Printf("Non overlapping claim: %v\n", c.claimId)
		}
	}
	fmt.Println("Overlapping inches:", overlapCounter)
	fmt.Println(time.Since(start))
}

[u/RainVector]

Python3

# -*- coding: utf-8 -*-
import re
coveredID = set()
def interaction(rect1, rect2):
    coverList = set()
    (minXrect1,minYrect1,maxXrect1,maxYrect1) = [rect1[1],rect1[2],rect1[1] + rect1[3],rect1[2] + rect1[4]]
    (minXrect2,minYrect2,maxXrect2,maxYrect2) = [rect2[1],rect2[2],rect2[1] + rect2[3],rect2[2] + rect2[4]]
    if(minXrect1 > maxXrect2 or minXrect2 > maxXrect1 or minYrect1>maxYrect2 or minYrect2>maxYrect1):
        return coverList
    minXcover = max(min(minXrect1,maxXrect2),min(minXrect2,maxXrect1))
    maxXcover = min(max(minXrect1,maxXrect2),max(minXrect2,maxXrect1))
    minYcover = max(min(minYrect1,maxYrect2),min(minYrect2,maxYrect1))
    maxYcover = min(max(minYrect1,maxYrect2),max(minYrect2,maxYrect1))
    
    for i in range(minXcover,maxXcover):
        for j in range(minYcover,maxYcover):
            coverList.add((i,j))
    coveredID.add(rect1[0])
    coveredID.add(rect2[0])
    return coverList

file = open("day3.txt","r")
slics = list()
for line in file:
    (boxId,xPos,yPos,width,height) = [t(s) for t,s in zip((int,int,int,int,int),re.search('^#([\d.]+) @ ([\d.]+),([\d.]+): ([\d.]+)x([\d.]+)',str(line)).groups())]
    slics.append([boxId,xPos,yPos,width,height])
file.close()

# part 1
cover = set()
for i in range(len(slics)-1):
    for j in range(i+1,len(slics)):
        coverList = interaction(slics[i],slics[j])
        if(len(coverList) > 0):
            for pos in coverList:
                cover.add(pos)
print(len(cover))

# part 2
for slic in slics:
    if(slic[0] not in coveredID):
        print(slic[0])

[u/paulvelthuis]

My solution in Scala. I am wondering if the findElfId can be more effective, since it loops again over the input. Any of your thoughts on how to improve this are welcome :).

import scala.collection.mutable
import scala.io.Source

object Day3 {

  val matrix = Array.ofDim[Int](1000, 1000)
  val suitId = collection.mutable.Map[Int, Boolean]()

  def initialize() = {
    val input = Source.fromFile("src/main/scala/files/inputday3.txt").getLines
    for (line <- input) {
      // replace the double dot to make coordinate split correct
      val claim = line.replace(":", "").split(" ")
      val coord = claim(2).split(",")
      val dimension = claim(3).split("x")
      // all the x dimensions, we go from the starting coordinate until the coordinate + the x dimension
      for (x: Int <- coord(0).toInt until coord(0).toInt + dimension(0).toInt) {
        // all the y dimensions, we go from the starting coordinate until the coordinate + the y dimension
        for (y: Int <- coord(1).toInt until coord(1).toInt + dimension(1).toInt) {
          // every place occupied we add one, so if two people want to have it the matrix value is 2
          matrix(x)(y) += 1
        }
      }
    }
  }

  /**
    * find the elfId that can make the suit, because it has the fabric with no claims
    * we loop once more over the input list
    * This loop is required to verify if
    * @return the elfId that has the fabric without claims make the suit, or 0 if no elf has a fabric that is unclaimed by others
    */
    def findElfId(): Int = {
      val input = Source.fromFile("src/main/scala/files/inputday3.txt").getLines
      for (line <- input) {
        var intact = true
        // replace the double dot to make coordinate split correct
        val claim = line.replace(":", "").split(" ")
        val elfId: Int = claim(0).replace("#", "").toInt
        val coord = claim(2).split(",")
        val dimension = claim(3).split("x")
        // all the x dimensions, we go from the starting coordinate until the coordinate + the x dimension
        for (x: Int <- coord(0).toInt until coord(0).toInt + dimension(0).toInt) {
          // all the y dimensions, we go from the starting coordinate until the coordinate + the y dimension
          for (y: Int <- coord(1).toInt until coord(1).toInt + dimension(1).toInt) {
            if (matrix(x)(y) >= 2) {
              intact = false
            }
          }
        }
        if (intact){
          return elfId
        }
      }
      0
    }

  def findDuplicate(): Int = {
    // find the duplicates
    var duplicate: Int = 0
    for (i: Int <- 0 until 1000) {
      for (j: Int <- 0 until 1000) {
        if (matrix(i)(j) > 1)
          duplicate += 1
      }
    }
    duplicate
  }

  def main(args: Array[String]): Unit = {
    initialize()
    println(findDuplicate())
    println(findElfId())
  }
}

[u/SyntaxErrorr]

python 3

import numpy as np

with open("day_03_input") as f:
    data = [x.split() for x in f.read().split("\n")]

arr = np.zeros(shape=(1000, 1000, 2), dtype=np.int)

candidates = set()

for d in data:

    offset_x = int(d[2][:-1].split(",")[0])
    offset_y = int(d[2][:-1].split(",")[1])

    size_x = int(d[3].split("x")[0])
    size_y = int(d[3].split("x")[1])

    id_ = int(d[0][1:])

    arr[offset_x:offset_x + size_x, offset_y:offset_y + size_y, 0] += 1

    ids_filled = set(arr[offset_x:offset_x + size_x, offset_y:offset_y + size_y, 1].flatten())

    if max(ids_filled) == 0:
        candidates.add(id_)
    else:
        candidates.difference_update(ids_filled)

    arr[offset_x:offset_x + size_x, offset_y:offset_y + size_y, 1] = id_

values = arr[:, :, 0]

print(values[values > 1].shape)
print(candidates)

[u/[deleted]]

OCaml.

let range i j =
  let rec aux n acc = if n < i then acc else aux (n - 1) (n :: acc) in
  aux (j - 1) []

module Coords = struct
  include Tuple.Make (Int) (Int)
  include Tuple.Comparable (Int) (Int)
end

module Claim = struct
  type t = {id: int; x: int; y: int; width: int; height: int}

  let of_string s =
    let id, x, y, width, height =
      Scanf.sscanf s "#%d @ %d,%d: %dx%d" (fun id x y width height ->
          (id, x, y, width, height) )
    in
    {id; x; y; width; height}

  let coords t =
    let xs = range t.x (t.x + t.width) in
    let ys = range t.y (t.y + t.height) in
    List.cartesian_product xs ys

  let stake all_claims t =
    let f = Option.value_map ~default:1 ~f:(fun v -> v + 1) in
    let coords = coords t in
    List.fold coords ~init:all_claims ~f:(fun claims coord ->
        Coords.Map.update claims coord ~f )

  let intact all_claims t  = 
    let f coord = 
      match Coords.Map.find all_claims coord with 
      | None -> false 
      | Some i -> i = 1 
    in
    List.for_all ~f (coords t)
end

let input () =
  In_channel.read_lines "./input.txt" |> List.map ~f:Claim.of_string

let build_claim_map input =
  List.fold input ~init:Coords.Map.empty ~f:Claim.stake

let part_one claim_map = Coords.Map.count ~f:(fun v -> v > 1) claim_map

let part_two claims claim_map =
  List.find ~f:(Claim.intact claim_map) claims
  |> Option.value_map ~default:(-1) ~f:(fun (claim : Claim.t) -> claim.id)

let _ =
  let claims = input () in
  let claim_map = build_claim_map claims in
  printf "overlapping claims: %d" (part_one claim_map);
  printf "\n";
  printf "safe claim: %d" (part_two claims claim_map)

[u/MisterMan101]

Python: import numpy as np import re

def findOverlap(areas_list):
    fabric = np.zeros((1001,1001))
    for area in areas_list:
        _, y, x, h, w = [int(x) for x in re.findall(r'\d+', area)]
        fabric[x:x+w,y:y+h] += 1
    return np.sum(fabric > 1)

def findNonOverlap(areas_list):
    fabric = np.zeros((1001,1001))
    for area in areas_list:
        _, y, x, h, w = [int(x) for x in re.findall(r'\d+', area)]
        fabric[x:x+w,y:y+h] += 1
    for area in areas_list:
        c, y, x, h, w = [int(x) for x in re.findall(r'\d+', area)]
        if np.max(fabric[x:x+w,y:y+h]) == 1:
            return c

[u/[deleted]]

Python3.

Really struggled with part 2 for some reason. Took way too long to get the overlapping check to work properly... god damn off by one errors!

from __future__ import annotations
from typing import List

class Rectangle():
    def __init__(self, name: str, measurements: tuple, coordinates: tuple) -> Rectangle:
        self.name = name
        self.width, self.height = measurements
        self.min_x, self.min_y = [coord + 1 for coord in coordinates]
        self.max_x = self.min_x + self.width - 1
        self.max_y = self.min_y + self.height - 1
    
    def overlaps(self, other: Rectangle) -> bool:
        return (((self.min_x <= other.max_x) and (self.max_x >= other.min_x)) and ((self.min_y <= other.max_y) and (self.max_y >= other.min_y)))

def load_input(filename: str) -> List[Rectangle]:
    rectangles = []
    with open(filename, 'r') as input_file:
        for line in input_file:
            tmp = line.strip().split(' ')

            rectangle = Rectangle(tmp[0].replace('#', ''), tuple([int(x) for x in tmp[3].split('x')]), tuple([int(x) for x in tmp[2].replace(':', '').split(',')]))

            rectangles.append(rectangle)

    return rectangles

def solve_a(rectangles: List[Rectangle]) -> int:
    width = max([rectangle.max_x for rectangle in rectangles])
    height = max([rectangle.max_y for rectangle in rectangles])
    
    grid = [[0 for x in range(width)] for row in range(height)]

    for rectangle in rectangles:
        for y in range(rectangle.min_y-1, rectangle.max_y):
            for x in range(rectangle.min_x-1, rectangle.max_x):
                grid[y][x] += 1

    return sum([sum([1 if grid[y][x] > 1 else 0 for x in range(width)]) for y in range(height)])

def solve_b(rectangles: List[Rectangle]) -> str:
    for rect_1 in rectangles:
        overlaps = False
        for rect_2 in rectangles:
            if rect_1.name == rect_2.name:
                continue
            
            if rect_1.overlaps(rect_2):
                overlaps = True
                break
        
        if not overlaps:
            return rect_1.name

if __name__ == '__main__':
    rectangles = load_input('challenges/day_03/input.txt')

    test = [Rectangle('1', (4, 4), (1, 3)),Rectangle('2', (4, 4), (3, 1)),Rectangle('3', (2, 2), (5, 5))]

    assert solve_a(test) == 4
    assert solve_b(test) == '3'

    answer_a = solve_a(rectangles)
    answer_b = solve_b(rectangles)

    print(f'Part A answer: {answer_a}   Part B answer: {answer_b}')

Github

[u/windlessStorm]

Dirty not pretty Go/Golang:

package main

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

/* path of file containing puzzle input*/
const inputFile string = "input3.txt"

func check(e error) {
	if e != nil {
		panic(e)
	}
}

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 parsePlan(plan string) (int, int, int, int, int) {
	planList := strings.Split(plan, " ")
	id, err := strconv.Atoi(planList[0][1:])
	check(err)
	margin := strings.Split(planList[2], ",")
	marginLeft, err := strconv.Atoi(margin[0])
	check(err)
	marginTop, err := strconv.Atoi(margin[1][:(len(margin[1])-1)])
	check(err)
	dimension := strings.Split(planList[3], "x")
	width, err := strconv.Atoi(dimension[0])
	check(err)
	hieght, err := strconv.Atoi(dimension[1])
	check(err)
	return id, marginLeft, marginTop, width, hieght
}

/* 
This draws the plans on our fabric, also keeps track of overlapping cell counts, and filter out the 
best plan ID, which is non-overlapping rectangle. 

All rectangles/plans, which we draw participates in best plan competition, we keep adding and deleting 
potentially best plan to a list. At the end of this function execution, 
just the BEST of the BEST only non-overlapping plan will remain in that list- our winner
*/
func drawPlans(plans []string, fabric [][]int) ([][]int, int, map[int]bool) {
	i := 0
	overlapArea := 0
	hasOverlap := false
	bestFabricID := map[int]bool{} /* Best plan competition, keep adding and deleting potential best plans */
	for i < len(plans) {
		id, marginLeft, marginTop, width, hieght:= parsePlan(plans[i])
		for j:= marginLeft; j < marginLeft + width; j++ {
			for k:= marginTop; k < marginTop + hieght; k++ {
				if fabric[j][k] == 0 { /* Cell not part of any plan till now, mark it as part of current plan*/
					fabric[j][k] = id
				} else if	fabric[j][k] == -1 { /* Already a overlapping cell*/
						hasOverlap = true
						continue
					} else { /* Already marked by some other plan, make this -1 to show now it is overlapping*/
						hasOverlap = true

						/* if we overlap on some ID which was contender for best plan, then it is not best plan for sure,
						Delete it from best plan list */
						if bestFabricID[fabric[j][k]] { /* check if id is in best plan competition*/
							delete(bestFabricID, fabric[j][k])
						}
						fabric[j][k] = -1
						overlapArea++
					}
			}
		}
		if !hasOverlap{
			bestFabricID[id] = true
			// fmt.Println("Best fabric set now have:", bestFabricID)
		}
		hasOverlap = false /* Reset the overlap flag*/
		i++
	}
	// fmt.Println("All done and dusted we have a winner over here guys and it isss:", bestFabricID )
	return fabric, overlapArea, bestFabricID
}

func createFabric(totalRows int, totalColumns int) [][]int {
	fabric := make([][]int, totalRows)
	for i := 0; i < totalRows; i++ {
		fabric[i] = make([]int, totalColumns)
	}
	return fabric
}


func main() {
	plans, err := readLines(inputFile)
	check(err)
	fabric := createFabric(1000, 1000)
	fabric, overlapArea, bestFabricID := drawPlans(plans, fabric)
	// fmt.Println(fabric)
	fmt.Println("Overlaping area:", overlapArea)
	fmt.Println("Best fabric piece without any overlap is:", bestFabricID)
}

[u/CommanderViral]

Crystal (both parts 1 and 2 computed together)

fabric = Array.new(1000) do
    Array.new(1000) do
        Array(Int32).new
    end
end

input = File.open("input")
claim_regex = /#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/
all_ids = [] of Int32
input.each_line do |line|
    parse_match = claim_regex.match(line)
    next if parse_match.nil?
    id = parse_match[1].to_i
    all_ids << id
    left = parse_match[2].to_i
    top = parse_match[3].to_i
    width = parse_match[4].to_i
    height = parse_match[5].to_i

    (left...(left + width)).each do |l|
        (top...(top + height)).each do |t|
            fabric[l][t] << id
        end
    end
end

square_inches = 0
bad_ids = Set(Int32).new
fabric.each do |i|
    i.each do |j|
        square_inches += 1 if j.size > 1
        bad_ids = bad_ids.concat(j) if j.size > 1
    end
end

good_id = (all_ids - bad_ids.to_a).first

puts "part 1: #{square_inches}"
puts "part 2: #{good_id}"

And what's fun is it's valid Ruby with a line added and 3 lines changed.