For all those little papers scattered across your desk

I feel like an electrical engineer, unscrambling these wires…

Just adding the input files.

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 `Step`

s. (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 `point`

s also have a total ordering via
`compare`

, a `map2`

for combining \(x\)s and \(y\)s, and a Manhattan distance
calculator.

Then, `point`

s compose with `step`

s by being able to move in the direction of a
`step`

, but they can also trace out a path (list of `point`

s) 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 `point`

s! 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*.

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.

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.

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

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.

Load Comments