Day three! Our DEV leaderboard is up to 44 people, which is awesome!
Also, check out the much classier cover images for these posts that @aspitte...
For further actions, you may consider blocking this person and/or reporting abuse
Solved last night, refactored this morning! Actually pretty proud of this. Python solution:
I love how clean this solution is!
Thank you so much -- that means a lot (I've been super sad this morning because somebody was mean about my solution on Twitter).
🙄People can be the worst sometimes. Sorry you had to deal with that.
If someone still doesn't get how to do it, I put up a pretty simple explaination with the code on my repo And here's the matrix that I got!
Cool visual!
Thanks! Love using p5.js
Kotlin Solution
UGH! This one seemed like a reversal, the first part was much harder than the second part.
I started out as I always do when pretending to be a video game developer: swearing loudly because my rectangles were overlapping and I forgot that it's way easier to find out if they're not overlapping.
Then I kept trying to optimize, but that wasn't getting me anywhere. I ended up brute-forcing my way through. This is ugly... maybe 25 seconds to chunk through.
Part 1
Part 2
After calming down a little (rectangles are dumb), I set in to work on the second part. This turned out much simpler. It was just another n2 with an early escape function. Almost identical to yesterday. The key is making sure our find eliminates candidates as fast as possible. Enter
none
, which returns false as soon as we see an overlap with our current. Yes, I was lazy and just added a quick "same id == no overlap" check instead of making sure I was checking unique pairs. I'm getting sleepy, and the first one frustrated me more than I would have liked.From my pain, your gain! An image of the overlapping areas plotted.
I totally agree that the second part seemed so much easier that the first. It really threw me off.
I initially thought that I should use my data structure from part one to solve part 2, but while figuring it out I realized that a different structure was much more effective. I like to make my functions for the first and second parts independent anyway, so it didn’t bother me to do it again. And it came out much smaller!
My messy af Python solutions. If I’m feeling energetic later today I’ll clean these up and write a Golang solution and benchmark the 2 :)
Part 1:
Part 2
github.com/thejessleigh/aoc18/tree...
I saw someone on the Clojurian's Slack talking about AoC day 3, and made the statement "mutable arrays FTW!" This made me think to try using the core.matrix library. I'm always looking for excuses to get better at using that library, since it can give direct GPU access when doing linear algebra.
Part the First
This uses the same
lines
function as the last 2 days, andas-long
is a trivial wrapping of Java interop so I can map it over the numbers found in each line. I could have just mapped an anonymous function, but I just wish Clojure would include as-long/as-double by default, which is why I named it.My parsing is far more effort than is needed. Someone else pointed out that the regular nature of the input meant that I could just have split the line with:
(re-seq #"\d+" s)
I decided to leave mine alone, partly because it's what I came up with, and partly because it's defensive programming. This puzzle is fine, but in the real world my code will one day see a file containing data that breaks simplistic parsing. That's not saying that my code is solid: for instance, I never check if the rectangles are within the 1000x1000 boundaries, but I like to practice at least a little bit of defensive coding.
The loop is destructuring the parse results then iterating until it's done. Then comes the nice part of core.matrix: pulling out a submatrix (the current rectangle) and updating it. The final line uses the nice trick of using
eq
to represent booleans as 0/1 and adding them. I learnt to count up booleans that way via APL.Part the Second
This part was actually easier, and ran significantly faster!
In an imperative language I would update the elements of the submatrix as I checked for overlaps. I could do that here too, but the code above is just much cleaner.
As it is, it keeps a set of the ids that currently don't overlap. The
ereduce
step first assumes that the current id won't overlap and adds it to the set. Then it checks if each cell has been written to, and if so it removes from the set the id of that cell, and the id that is being processed right now. Then theassign!
updates the whole rectangle with the current id.I liked using core.matrix here. It forced me to go through the docs to look for useful functions (like
eq
), and I also learnt some interesting gotchas with the library, which will be valuable to know.Part 1
I really struggled with part 1. Not because I couldn't figure out the problem, or get my code to compile. I had my tests running pretty quickly! But I kept getting the wrong answer! I was on the very precipice of giving up and checking the subreddit when I realized that
str.matches(|c| c.is_digit(10))
only finds single digit at a time -- it doesn't build consecutive digits into a single "find." So with input string#1 @ 55,22: 10x10
, it was reading this asid: 1, left: 5, top: 5, width: 2, height: 2
and throwing away the rest. 💩After scratching my head and then bringing in my first external dependency ever in Rust (pretty painless, all things considered) things worked out just fine.
Since the dependency I brought in was just a
regex
crate, which would be built-in in some languages, I figured that was OK. I wasn't bringing in thefind-overlapping-squares
crate.Anyhow, here's part 1:
Part 2
Actually, for part 1, I didn't even keep track of the ID of the claims -- I just threw that data away! And then I read part two and sat there in sadness for a few minutes.
But!
Then I realized that I wouldn't have to come up with an entirely new approach. I could process the claims like normal, and then re-run through the claims and recheck all of their squares, to see if any have all cells with only one claim on them. Yeah, it doubles the run-time, but O(n) is O(n), even if you double it (sort of). Anyways, I'm pretty happy with today's challenge. Especially my top level functions
count_conflicting_squares
andfind_unconflicting_id
: I was able to make them abstract enough that they're pretty easy to read and figure out.I made the exact same mistake with my initial attempt, where I was only grabbing the first digit with my regex. I'm glad it wasn't just me 😅I was so frustrated because the test input worked, since each number in the test input was only one digit! Sometimes I wish that AoC gave just a little more test data to work with before grabbing your final input.
Yes! The first test input kept passing, and then I wrote like 4 or 5 more tests to check different things, and they all passed! But I never checked double-digit numbers. :|
Here goes my
Typescript
solution:This seemed like a natural job for Fortran!
Part 1
No, really, it has nice array operation and slicing syntax! I've just stretched out a big array, added 1 everywhere there's a claim, and then counted the number of elements where there's an element greater than 1.
Part 2
Part 2 was trickier, and I had to use a similar solution to @rpalo , going over each claim again; but then I checked whether the sum of the cut elements was the same as its area to determine whether it was a unique claim. I could have done a similar
count
-based method to part 1, but I thought of this way first.I don't write a lot of Fortran, and peering at about 7 descriptions of how advanced IO worked didn't get me very far, so I used
sed
to strip out everything that wasn't a number or a space and that made it much more amenable to Fortran'sread
input preferences.Woah, this is super cool! The right tool for the right job, huh? 😎 thanks for sharing!
PHP
One of those days when there's a big hint in the name, seems like. The slice/splice functions did the heavy lifting on this one.
Part 1:
Part 2:
c# again
Tests:
My solution (Elixir) for the first part was:
Takes about a second. The first version used lists and list-diffing to find duplicates, but this took minutes to compute. Maps were much faster at this size (hundeds of thousands of entries).
I should mention I'm just learning Elixir, so this is not to be understood as "good code" or "knows what he's doing".
Here's the code:
Cool! Thanks for sharing!
Just a heads up, you can put the word “elixir” immediately after the opening triple backtick, and your code will show up with syntax highlighting. 😁
I've been solving all of these in Elixir thus far, and it's been pretty fun! Day 3 is the first time I dealt with "off by one" errors...
Javascript solution using regex capture groups (
/^#(?<id>\d*)\s@\s(?<left>\d*),(?<top>\d*):\s(?<width>\d*)x(?<height>\d*)$/
):readFile.js
03a.js
03b.js
Puh, that was a tough one for me today. I started out by counting the number of claims for each square on the "canvas" which gave me a correct aswer. However, I later misunderstand part 2 thinking I should find completely unclaimed squares that could be filled out by one claim...
After cheating a little and getting inspirations for solutions I have implemented a Golang solution for today. At least I am happy that I could implement it in Golang without any prior experience using Golang:
Part 1 and 2 together:
Hi guys! Here is my solution on #typescript.
Repo: github.com/room-js/adventOfCode201...
Perl solutions. The first part was easy, just counting how many times each square occurred. The second part was trickier and the naive solution was too slow, so I summoned some regular expressions to help me:
Part 1
Part 2
F# again - I think I really like this language.
This is very suboptimal - it repeats a ton of work to solve for part two. It applies all the claims and then checks every cell again for every single claim, grabbing cells with no overlaps anywhere in the grid. I'd like to revisit this and see if I can manipulate claims as a whole as opposed to just leaving "claim breadcrumbs" in each cell.
Ah, regexes and string splitting. The One True Way to parse text is with parser combinators.
Part 1
I really wanted to do Part 1 geometrically by splitting and merging claims into non-overlapping regions. It would be O(N²) however, and I was short of actual time to build it so went for the big map of positions like many others:
That uses a modified
Claim
class as follows:Part 2
Fairly simple extension. The tricky bit was remembering to remove both overlapping claims from the candidate result set:
Solution in Elixir below.
It took me a while to figure out the best way to store the fabric because matrices are not really a thing in Elixir. And it's a bit harder for me (coming from an OOP background), as everything is immutable in a functional language like Elixir. A mindset switch is necessary sometimes.
Part one:
Part two:
Common:
Wow, nice! Elixir really does seem like a big brain shift.
Node.js
Reused my work for part 1 in part 2.
I make the 1000 x 1000 array and fill it every slot with a
*
.First time a claim is added, it gets a
#
If a claim overlaps with another, those cells get marked with an
X
.Part 1: Filter matrix for all
X
values.Part 2: Check every coordinate for each claim. If every coordinate is a
#
, then that claim is the answer.Main.js:
I did my part 1 similarly: I wrote the ID to each cell in it’s rectangle, unless the cell wasn’t zero, in which case I wrote -1. At the end, I counted the -1 values.
The second step was a little different. First of all, I added the ID to a set of IDs that were OK. Then I went through each cell of its rectangle. If the cell is zero, then update it to the current row’s ID. If it had a number in it, then that’s the ID of the most recent rectangle to overlap that cell; so remove the found ID and the current ID from the set of good IDs. Then set all the cells in the entire rectangle to its ID. At the end, the set of good IDs has a single element.
It sounds tricky, but it’s literally just a couple of lines of code
Adding my Clojure solution here - will write another post at some point. I'm oncall this week and got paged at 3am for something out of my control, so I figured "hey, I'm up, might as well."
get-overlap
solves part 1, whilefind-no-overlap
solves part 2. Second part is a little brute-force, but still worked.Wow, this is really clear and nice! Ruby has so. Many. Convenience methods that I really miss when I go to other languages sometimes.