8 Day 8: A Small Screen

Read the description of today’s puzzle. Here is my input, a list of instructions for manipulating a 50×6 pixel screen.

This was the puzzle where I fell off the bandwagon. It’s not inherently difficult, but I deliberately chose to take the scenic route, which ended up taking longer than I anticipated. I am pleased with the results however, and the esoteric knowledge I scummed into my head in the process.

8.1 How many of the screen’s pixels do the instructions leave on?

For this problem I’m going to need some macros.

Macros can transform and expand basically any string of text into Racket code. Racket does these transformations and expansions, and once they’re all finished it executes the resulting source code.

The instructions start out life inside the day08input.txt file looking like this:

rect 5x1

rotate row y=0 by 2

rotate column x=0 by 1

....

The convert-input-to-screen-functions macro reads this file and injects its contents into the source code in this form:

(update-screen (list (screen-macro rect 5x1)

(screen-macro rotate row y=0 by 2)

(screen-macro rotate column x=0 by 1)

....))

The screen-macro macro finishes the transformation:

(update-screen (list (list rect 5 1)

(list rotate-row 0 2)

(list rotate-column 0 1)

....))

In this way each instruction is converted into a list containing an identifier and some numeric parameters. The identifiers will be bound to functions which I will define.

The functions rect, rotate-row and rotate-column take a scr parameter to represent the screen that they will draw on, and return the modified screen. That screen is simply a list of lists, where each inner list represents a row on the screen. The elements of the row-lists — the pixels — are either 1 (on) or 0 (off).

The update-screen function connects the drawing functions above to the actual instructions we generate from our input file. You may have noticed that my macros didn’t the convert each input instruction into an actual function call, but into a list containing a function identifier and some numbers to use as parameters. The update-screen function iterates through these lists, calling the named function and giving it the numeric parameters, and inserting a third parameter, the screen to draw on. To the first instruction it passes a blank screen created with (make-screen 50 6). The for/fold loop saves the resulting screen returned by each instruction and passes it in turn to the function in the next instruction.

Since update-screen itself returns a screen — a list of lists whose whose innermost values are either 1 or 0 — we can apply the + function to a flattened version of that list to see how many pixels are on at the end of the instructions.

8.2 What is the password displayed on the screen?

To solve the second part of the puzzle I have to read what’s displayed on the screen.

If I simply execute the convert-input-to-screen-functions macro, I get the raw list representing the screen in its finished state:

'((0 1 1 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0)

(1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0)

(1 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0)

(1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0)

(1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0)

(1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0))

If you squint a little, you’ll quickly notice that the “on” pixels do indeed form letter shapes!

So there are two ways to solve this puzzle. The first is a pure programming approach: write code that can recognize the letter-shapes in the screen and convert them into characters programmatically. The second is just to use your eyeballs and read what you see.

I decided to take the second approach, but to write a little more code to make the screen easier for a human to read. Racket comes with a handy library called pict for drawing simple shapes and snapping them together.

The pict module’s functions treat shapes as another kind of list element, so I can very easily convert a list of ones and zeros into a list of colored squares.

Plugging that long list of ones and zeroes into the display-screen function, I get something much more readable:

8.3 Brilliant Personal Anecdote

Here’s my little tale about why I didn’t finish writing up this solution until near the end of January.

The puzzle input is basically a block of source code written in a miniature programming language. I reasoned that if I could write an interpreter for this language, then I could just run the program and get the answer! I’ve been reading Matthew Butterick’s online book Beautiful Racket. So I proposed to put my still-flaky DSL-implementation knowledge to the test.

And I succeeded. I was able to implement a reader and expander that could read the puzzle input as source code and execute it. It took me a good deal longer than it would have using a less-highfalutin’ approach, but I was learning something complicated and useful, so I didn’t mind. That was Delay, Part 1.

But, you’ll recall, my self-inflicted goal here isn’t only to produce working code for the solutions, but also to write about the code, and finally to interweave the code and the writing (using scribble/lp2) into a single “literate program” (the thing you’re reading now). When I got to this part I realized that Beautiful Racket teaches its methods in a custom Racket dialect, br/quicklang, and custom dialects don’t seem to mix well with the Scribble lp2 environment. In order to incorporate my Day 8 code into the same document structure as the rest of my solutions, I ended up rewriting it. It still uses some of the same basic techniques, but it isn’t a full-fledged #lang reader anymore. That was Delay, Part 2.

Finally, since the second half of the puzzle involved graphical output, I wanted the Scribble document for the solution to include that graphical output, and I wanted that to happen in a Scribble-esque way — that is, the images should be generated directly by the program and included in the document automatically. I knew this was possible because I’d seen it before, but it took a few days of tinkering before I discovered the correct method for doing this. That was Delay, Part 3.

And after all that learning, tinkering and rewriting just this one problem, there was never any hope of finishing all the puzzles before the end of the year. But the result was so obviously worth it. Right?

8.4 Testing Day 8