DEV Community

Discussion on: Advent of Code 2019 Solution Megathread - Day 3: Crossed Wires

Collapse
 
katafrakt profile image
Paweł Świątkowski

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.

Collapse
 
avalander profile image
Avalander

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.

Collapse
 
aspittel profile image
Ali Spittel

This is how I did it last night! Ended up being way slower and the code was much uglier.

Thread Thread
 
avalander profile image
Avalander

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.

Collapse
 
jbristow profile image
Jon Bristow • Edited

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.

Collapse
 
mustafahaddara profile image
Mustafa Haddara

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...

Thread Thread
 
jbristow profile image
Jon Bristow • Edited

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)

Thread Thread
 
mustafahaddara profile image
Mustafa Haddara

you could have kept that information (UDLR) alongside the line segment definition

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!

Thread Thread
 
jbristow profile image
Jon Bristow

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!