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.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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.