evan_tech

Previous Entry Share Next Entry
01:42 pm, 25 Jul 06

cool programming problem

Here's a description of the problem I spent a lot of time (way too much, really) on. I enjoyed both the programming challenge and the story that accompanied it.

For background, remember that earlier we built a virtual machine and were now running an image on it, and it had dropped you into a Unix-like system.

One account on that system had a Zork-like IF game in it. After walking around a bit in the game, you discover you need to rebuild various machines that are built from many small pieces, and that the pieces themselves are interdependent. Some of the parts you find have a description that just says REDACTED, and you also find a note that tells you that the "Censory Engine" is blocking your perception and that you need to find the blueprint by rebuilding these machines. That's the first main programming part -- writing a rebuilding solver. For example, the EPROM burner was broken like this: it is (a EPROM burner missing (a T-0010-BQH missing a X-1623-GTO and a X-1623-GTO and (a X-1623-GTO missing a T-0010-BQH))) missing ((a X-1623-GTO missing a T-0010-BQH and a T-0010-BQH) missing a B-4292-LWV and (a T-0010-BQH missing a X-1623-GTO and a X-1623-GTO) and (a T-0010-BQH missing a F-9887-QAE and a X-1623-GTO and a B-4292-LWV and a F-9887-QAE and a X-1623-GTO and a X-1623-GTO) and (a J-6458-VDL missing a T-0010-BQH and a F-9887-QAE) and a F-9887-QAE).

(An aside: After you solved the first puzzle manually, you find a note from yourself that says "try switching your goggles". Of course, you didn't know you had goggles on, but that lets you switch the interfaces into s-expressions. This trick really reminds me of one I saw in another IF game, where you're wandering around a maze completely lost and eventually you start feeling hot. When you take off your shirt, it says, "You remove your shirt and stretch out your wings." It was such a great a-ha moment! The simple command "fly" solved the maze.)

Anyway, you eventually build the "downloader" and "uploader", and when you run the downloader you get a dump of source code -- it turns out that you're a robot and this is the source code to yourself! The code (which is vaguely ML-like) describes some of the limitations you've been encountering in the game, like only being able to hold six items, but it's also not the complete game: the main body is a function that takes a command and produces a response. So you edit this code to make it so that the "humming" action jumps you to the place where the blueprint is located, only to discover that the blueprint is also REDACTED.

It turns out that the type system in the language makes it so that any data derived from the "get item description" function on any censored item, when output, also comes out REDACTED! But at one point you discover a "proof" object, which when you examine reads:
The proof is long and complicated, purporting to prove the correctness of the Censory Engine. You have the feeling something is wrong with it, but you keep getting lost in the details. Too bad it's not in machine-checkable form.
Combining it with some other hints, I realized that while you couldn't read the censored values directly, you can use the censored values to call the few mutable functions: the one that jumps between rooms, and, more importantly, the "transfer item to inventory" one.

So then I wrote a program (which was a total pain in this ML-like language, since it had no loops or if statements anything like that -- you had to write it all functionally with pattern-matching) that, for each letter in the blueprint, retrieved an item where the first letter of the item matched the letter in the blueprint! From there, I then examined my inventory, grabbed all the first letters from the items listed, and got out strings like "mostenighteningtshosthatthebasementhodsasecretachineoom", from which I eventually pieced out the name of the thing I needed to destroy. With that, I could re-upload a new program to destroy it.

This was a great puzzle! I recognized the proof as a snide comment from a programming language purist: the Censory Engine was perfect at hiding censored data, but the proof alluded to a weakness. Although the censoring of data was likely provably correct, since the language allowed some side effects, you could use those functions to make a change in state that was then observable in a circuitous sort of way. Rad problem.