re: Advent of Code 2019 Solution Megathread - Day 3: Crossed Wires VIEW POST

TOP OF THREAD FULL DISCUSSION
re: 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 ...
 

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.

code of conduct - report abuse