I feel like an electrical engineer, unscrambling these wires…

Part 1

c8087e4

Just adding the input files.

bddbdb6

Talk about abstraction on top of abstraction. We start with the Step structure, which provides an abstraction over a direction and a distance to go. Notice that I write little map functions which can decompose these tuples, because it’s annoying to write

let
  val (d,i) = someStep
in
  (* use d and i somewhere *)
end

Instead, I write

Step.map (fn (d,i) => ...) someStep

which makes the decomposition easier. It also helps to keep track of which variable belongs to which.

Next we have the Path structure, which provides a list of Steps. (I’m skipping the parser code for most of these, but it’s there).

Then there is the Point structure. map really came in handy here, because the syntax for decomposing records {x,y} is really a pain when you want to use variable names other that x,y. 2-D points also have a total ordering via compare, a map2 for combining \(x\)s and \(y\)s, and a Manhattan distance calculator.

Then, points compose with steps by being able to move in the direction of a step, but they can also trace out a path (list of points) in a given direction. This is going to be useful for collecting the points of a given wire.

We create a PointSet out of the RedBlackSetFn provided by SML/NJ for use with the wires.

Finally, a wire is a list of points! Converting a path to a wire requires tracing out all the steps, starting from the origin.

Then we deal with the intersections. The naïve method of searching is easily \(O(n^w)\) in the size of the number of wires and their lengths. (Consider for each point in a wire \(w_i\) searching through the points in the other wires, whose sizes are assumed to be \(O(n)\).) And since we have lists on the order of 150,000 points, that’s not going to be feasible. Using sets brings us down to \(O(w \sum{n_i})\) where \(w\) is the number of wires (2, in these cases) and \(n_i\) are the individual wire lengths. This ends up being a cut of two orders of magnitude.

The solution, then, ends up being computing all the intersections and filtering out the origin. I really banged my head on this one for hours before I managed to figure it out—and it was important that 2-dimensional points have a total order, or I wouldn’t have been able to build the set. The spaghetti code that failed to compute the intersections before I wrote this was horrible.

Part 2

1a1d129

Next we have a quick re-ordering of the wires, to put them in the “correct” order. We need this for other properties to work out.

74d823a

Then, it turned out we were double-counting the origin point, which we don’t want. Both this and the last commit are aimed at not over-counting the path to the intersection.

fdd7bf2

And so is this one—here, we were double counting corners.

15bef57

Now I finally copy over the code and modify it.

The first big change is stepsFromTo, which recursively seeks out a path from one point to another in the wire and returns its length. Of note, we don’t include the source point in this path-length. This guy is really just a clever recursive accumulator: given a particular wire, we keep marching through it until we find the origin point. Then, and only then, do we keep start tracking points seen along the way. We return when we find the destination. Thus this is similar to a list fold, but the state includes points between origin and destination and a “seen origin” boolean. Plus, we bail out early.

The next big change is the solution: we collect a list of functions from origin to intersection, one for each intersection, and apply them to each of the wires. From there, we sum the distances per intersection and grab the minima.

Categories: Blog