2011-06-30: Professor Layton and the Diabolical Box, Puzzle #132

I try to solve a puzzle of some kind every morning. I use Sudoku, Picross, and often, Professor Layton. Sometimes it is convenient to write a program to solve some of the more annoying "search" puzzles. I’ll post the Racket programs with a little bit of commentary.

-

This is for Puzzle 132. Here is the puzzle:

> Two brothers have inherited their parents’ five-piece art collection. According to the will, the older brother will get a set of paintings worth twice what the younger brother gets. In order to ascertain the value of the paintings, the brothers called in an appraiser, who valued each painting as shown below. For his services, the appraiser was promised the one painting left over after the brothers divided the art according to their parents’ wishes.

> Assuming that individual paintings can’t be divided, which one does the appraiser get?

There is then a picture of five paintings with prices underneath. They are: A worth 20,000, B worth 60,000, C worth 55,000, D worth 45,000, E worth 95,000.

I encoded this information into a vector in Racket:

We won’t keep track of the labels, we’ll just remember that, for example, 0 is A and 4 is E. Also, we divide everything by 1,000 so we don’t have to type so much.

The basic algorithm we’ll use is a trivial search: try assigning each painting to each brother and stop when the value of the older brother’s paintings is twice that of the younger.

The trick, however, is that we’ll represent the assignment as the older brother’s set combined with the younger brother’s set. We’ll do this simultaneously with a bit-vector, where the 1s indicate that the older brother gets it and the 0s indicate that the younger brother does. We’ll independently pick one painting which will be "left over" that the appraiser will get. Here’s the main loop:

One thing to note here: for* is like a nested for—we loop over the assignments /and/ loop over every painting each round. (This, by the way, means that we do twice as much work because we consider both assignments for the appraiser’s painting.)

Two other cute things: First, we use a literal binary number to write down the completely full set, but we have to add one to actually visit it. Second, the assignment->value function (below) will take an argument to determine whether to add up the 1s or the 0s. Here’s it’s definition

The for/sum variant adds up the result of each iteration of the loop, the #:unless clause skips the iteration where the appraiser’s painting is considered, and the if determines which brother we’re considering.

If you know anything about Racket, there may be one more confusing thing about the code in <valuation>... return! Expressions in Racket don’t normally have non-local returns like that. How can we make the inner area of the loop stop and return the appraiser painting that works? It’s simple: bind return to an escape continuation:

Was this faster or slower than doing it the old fashion way...? Who knows.

Can you work out what the answer is...?

By the way, if you use this code at home, make sure you put the code in this order: