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

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

. `point`

s also have a total ordering via `compare`

, a `map2`

for combining s and 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 is easily in the size of the list, 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 where is the number of wires (2, in these cases) and 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.

The next big change is the solution: we collect a list of functions from intersection to origin, 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