7 Day 7

The puzzle. Our input describes an electrical circuit, with each line of the file describing the signal provided to a particular wire.

7.1 What’s the signal on wire a?

The first question we should ask is — how do we model a wire? We’re told that it’s a thing with inputs that can be evaluated to get a value. So it sounds a lot like a function. Thus, what we’ll do is convert our wire descriptions into functions, and then run the function called a.

In other languages, creating functions from text strings would be a difficult trick. But this facility is built into Racket with define-syntax. Essentially our program will run in two phases: in the syntax-transformation phase, we’ll read in the list of wire descriptions and expand them into code that represents functions. In the second phase, the program — including our new functions, created via syntax transformation — will compile & run as usual.

The convert-input-to-wire-functions transformer takes the input strings and first converts each into a datum — that is, a fragment of Racket code. So an input string like this:

"bn RSHIFT 2 -> bo"

becomes a datum like this:

(wire bn RSHIFT 2 -> bo)

Next, this transformer converts the datums into syntax, a process that adds contextual information (for instance, the meanings of identifiers) so the code can be evaluated.

Then the wire transformer moves the arguments around to define functions, by matching the three definition patterns that appear in the input. Thus, syntax like this:

(wire bn RSHIFT 2 -> bo)

becomes:

(define (bo) (RSHIFT (evaluate-arg bn) (evaluate-arg 2)))

evaluate-arg lets us handle the fact that some of the arguments for our wires are other wires, and some arguments are numbers. Rather than detect these differences during the syntax-transformation phase, we’ll just wrap every input argument with evaluate-arg, which will do the right thing in the next phase.

(wire-value-cache is just a performance enhancement, so that wire values don’t have to be computed multiple times.)

One gotcha when using syntax transformers is that identifiers introduced by a transformer can silently override others (in the same way that identifiers defined inside a let will override those with the same name outside the let). For instance, one of the wires in our input is named if. When our syntax transformer defines the if function, it will override the usual meaning of if. There are plenty of elegant ways to prevent these name collisions. (The most important of which is called syntax hygiene, and permeates the design of Racket’s syntax-transformation system.) But because this is a puzzle, we’ll take the cheap way out: we won’t use if elsewhere in our code, and instead use cond.

We also need to implement our 16-bit math operations. As we saw above, our syntax transformers are generating code that looks like, for instance, (RSHIFT (evaluate-arg bn) (evaluate-arg 2)). This code won’t work unless we’ve defined an RSHIFT function too.

These next definitions use define-syntax-rule as a shortcut, which is another syntax transformer. (Thanks to Jay McCarthy for the 16-bit operations.)

After that, we just evaluate wire function a to get our answer.

7.2 What’s the signal on wire a if wire b is overridden with a’s original value?

Having done the heavy lifting, this is easy. We’ll redefine wire function b to produce the new value, and then check the value of a again.

Ordinarily, as a safety measure, Racket won’t let you redefine functions. But we can circumvent this limitation by setting compile-enforce-module-constants to #f. We’ll also need to reset our cache, since this change will affect the other wires too.

7.3 Testing Day 7