Day 3: Crossed Wires

---

Links:

• Puzzle on adventofcode.com
• Source Code

It seems like every year includes some sort of “ascii line map” puzzle. This year it’s finding intersections, last year it was simulating mine carts on rails, and the year before involved something with pipes if I recall correctly. I’m definitely not saying that’s bad. Quite the opposite, actually, I really enjoy this kind of puzzle.

I hope that there’s another one of these this year, because the core concept of today’s puzzle was rather simple, most likely due to today only being the third day. The hardest part is converting the instructions to a meaningful data structure.

Solving today’s puzzle took me quite a bit longer than it probably should have. This is because I encountered some Rust errors I had never seen before and I wanted to learn more about them. Before you ask, no, I don’t really remember what they were about but it had to do with Rust being unable to determine lifetimes.

Incidentally I discovered that my map_{lines, csv} functions had incomplete lifetime assignments.

i.map_lines(|l| l.split(',').collect()).collect()

Didn’t work at first, because l didn’t live long enough. Changing the map_lines function so that the function’s input (the line in this case) also has the lifetime ‘a - which is the lifetime of the surroundings - solved the issue.

pub fn map_lines<'a, T>(&'a self, f: impl FnMut(&'a str) -> T + 'a) -> impl Iterator<Item = T> + 'a

Approach

Today marks the first day I think it’s even worth talking about the approach I went with. Day one and two were both relatively clear-cut so I didn’t have anything worth saying.

First I want to make it clear that I’m using these puzzles to play around with the language. I strive to write “good” code, but when I have the chance to play around with some features I will gladly do so even if it ends up more convoluted.

That being said, let’s take a gander at my approach. I created a new data type representing a position on the grid. Before you scream at me, yes, I basically just wrote my own lackluster 2D vector implementation. This so called “Position” structure can be created directly from the wire segments (ex: “R42” -> Position(42, 0)). I should mention that I didn’t bother making the parsing logic crash-safe (i.e. invalid inputs will crash the program).

Having written this data structure I created a function that returns all possible positions on the wire in order of appearance.

That concludes the boring part, let’s move on to the “finding intersections” part.

For the first part: Create a set containing all points of the first wire and then for each point in the second wire, check whether that point lies on the first wire. If it does, get the point’s (Manhattan) distance to the origin. Now just keep track of the lowest distance and return it.

For the second part: Map each point on the first wire to the amount of steps required to reach it. If the wire crosses over itself, only use the first occurrence. Now take each point on the second wire and check if it also lies on the first one. If it does, add the amount of steps required to reach it on the second wires to the amount on the first to get the total steps. Keep track of the smallest total steps value and return it.

Both of these are descriptions of the two wire case. My code can handle any number of wires though (It wasn’t really an active decision, it just so happened that I was already iterating over all wires).

In the case of multiple wires it finds the shortest distance to a crossing between any two wires.

---

Overview
Previous day Next day