It's day 3, and we've gone from code interpreters to spatial mapping.
Day 3 - The Problem
Looks like someone wasn't very organized when doing the wiring for our fuel management system! While we have the time, let's get in there and untangle the shorting out wires and replace it with its more ideal version.
Part 1 was fairly straightforward, but since I didn't know how to convert this into nice intersecting systems of equation, my brute force solution ran into a heapspace problem.
Part 2 was a bit hairy, because I had to back out one of my optimizations for part 1, which revealed (eventually) an issue with how I was calculating the points it passed through.
Overall I would rate this a fairly difficult day 3!
Ongoing Meta
Dev.to List of Leaderboards
-
120635-5c140b9a
- provided by Linda Thompson
If you were part of Ryan Palo's leaderboard last year, you're still a member of that!
If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)
I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.
There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.
Neat Statistics
I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?
Top comments (37)
Not sure if it's the most efficient way of doing it, but this is how I solved it
So, I see everyone did it like I did - recording all visited nodes on the grid and checking for intersections. Now, without considering part 2, is there a smarter way? I'm pretty sure there has to be.
You can generate segments with only the start and end points and check where they intersect, which would require less memory. But the math is more complicated and I'm not sure it's faster, since you can't use a hash table to find the intersections.
This is how did it (I assumed the memory requirement of enumerating all of the visited nodes in the grid would be too much).
buuut the code got really messy and I don't know if there's a cleaner way to do it.
It's so long I don't want to reproduce it here 😱 github.com/MustafaHaddara/advent-o...
The only thing I can see right off the bat is that you’re checking for vertical/horizontal via start/end points, but you could have kept that information (UDLR) alongside the line segment definition. Other than that it makes sense, and other than being too deeply nested for my compulsive refactoring instinct, it doesn’t look much longer than my full-point enumerator.
(If you use a linked list, it doesn’t take more than 30 seconds or so for part b)
d'oh that would have made things much more readable.
I was complaining to a coworker that I've done collision detection for 2d games before, and this felt similar, but is sort of like "hard mode" because I didn't necessarily know which endpoint of each line was on the left/right or top/bottom. Keeping that info would have made things more straightforward!
It’s why I love working with people who know the same codebase as me! When you PR or rubber duck, you often get some perspective that makes the “ugly” bits fall into place that you were too close to see!
I think I have a way it wouldn’t be ridiculous, but you have to process the list with both solutions in mind so you only have to do one Cartesian join.
First precalculate all the start/end points of each instruction in each wire.
Then, for each piece of wire a, go looking for all pieces of wire b that intersect. You should do this while keeping track of how far you’ve come on wire a. Likewise, while looping through wire b, you should keep track of your distance so it can be recorded in the data structure that captures the intersection point. Anyway, flatmap this all into one list.
Once you have them all, then you can do two different minBy type lookups to find answers a and b.
It seems more space and memory efficient. The processor efficiency seems like it’s a wash though.
I think my solution has a similar big O: 3n+n2 (aka n2 ), but the size of n in this pseudo code is the number of instructions, not points. In my input, the number of points is several orders of magnitude higher than the number of instructions and intersection points. Additionally, the code for calculating the “bend positions” of the wire is also way less complicated since you’re not appending lists to lists.
This is how I did it last night! Ended up being way slower and the code was much uglier.
That's what I suspected would happen. I think the best optimization is to calculate the list of points for both paths and then convert one of them to a hash table and iterate over the other one and filter out the elements that are not in the hash table. This is complexity O(n) because iterating over one list is O(n) and checking whether a random element exists in a hash table is still O(1). I don't think any smart trick with segments can get a better complexity.
PHP, because I'm having to learn it at my internship at the moment. Something isn't right here, because it takes several minutes to run, but at least the solution appears eventually.
If you’re enumerating every point you’re operating with two lists of hundreds of thousands of items. Worse, I don’t think there’s a way around a cartesian join of the two sets (potentially squaring your already hideous number of data).
Running into performance problems is expected, driving the solution into minutes if you’re not careful (I crashed my jvm and lost a few minutes manually killing it and my ide as they consumed as much processor and memory power as they could)
I was able to improve the speed hugely with just a little tweaking, from over 7 minutes to around 0.1 seconds!
Took me an extra day to clean it up so I wasn't disgusted with it. I definitely followed the Advent of Code "Brute Force until proven otherwise" approach. I considered doing it by only considering each leg of wire as two endpoints and calculating the intersections, but this was easier and more straightforward.
I also tried out Rust's type aliases to make things read a bit easier, which I'm really happy with.
Part 2 almost got me with a sneaky "Off by Two" error. I forgot to count the step off of the origin on both wires, leading me to be short by 2 on my final answer. A quick test case based on the examples provided showed I landed at 608 instead of 610 and I got suspicious.
Altogether much happier with this than I was last night. :)
Had to reach for Haskell again. This may happen on the hard ones! Solved it using correct line segment intersections rather than enumerating every single coordinate.
Scratched my head on part 2 for a bit then realised each segment could store the accumulated length, then it was a simple shortening calculation for each line at the intersections.
I'm not proud of that
intersection
function. 12 variables in scope. The horror!I still have nightmares from previous year's assignment based on coordinates, but luckily this wasn't as bad. Here's my solution for part two in Elixir:
Check part one here
Woo! Day 3 is in the bag. :D
I'm hosting my solutions on repl.it, and this one they don't let me finish calculating - I'm gonna have to look for some better optimization in order to let it finish within the resource boundary they set.
Anyway, I was able to handle the calculation locally and got the answers. I used the instructions to create sets of visited points, and then used set intersection to find the crossings. From there, it was finding either the minimum distance from the origin, or finding the minimum walk distance.
C++
Part 1
Part 2
Beautiful code Sr. Really straight forward and easy to read and understand.
I way over thought this last night, and had a solution that worked but it was gnarly. Refactored this morning:
More browser antics. I think I can refactor this, and possibly make it faster, but it's fast enough.