L   =   -U

Or: Hours of Fun from 4 ASCII characters

This page describes one of my recent bizarre creations: a method of representing 16 challenging puzzles using only four printable ASCII characters. This may set a record for the smallest description of a puzzle: on average, each puzzle is represented using only two binary bits! (Actually, it's slightly less since a couple of the 32 bits are not used.)

The extremely compact representation is a combination of an idea for describing 16 puzzles of a certain kind using a single 4x4 matrix of the letters A-J, combined with a compression scheme for encoding the matrix. You might contend that not including the description of the rules for extracting the definition of the 16 puzzles from the ASCII characters in the "information count" is cheating, but I don't. It's analogous to not including the description of the rules of chess in a chess problem. The rules of my "game" are even simpler than chess, and once you learn them you can take any ASCII string representing a problem of this type and solve it with no additional side information.

I'll describe the method starting from the compressed representation of the puzzle as a string of 8-bit ASCII characters. Note the fact that I say "8-bit". ASCII is, strictly speaking, only 7 bits, and really only 96 of those characters are printable. However, in interpreting the description of the puzzle as an ASCII string, consider each letter as an 8-bit (not 7-bit) number. To put it another way, think of it as a char[] string in the C language, in which each character is 8 bits.

Here are the steps to do, starting with the ASCII string:

(1) Subtract 33 from the ASCII value of each character, and convert to binary.

(2) For each character, take the binary result of step (1) and reverse the order of the bits.

(3) Write down the 8 bits (resulting from step 2) for the first character in the string. Then, to the right of that, write down the 8 bits for the second character. Continue until all characters are exhausted. You now have a linear sequence of bits.

(4) Draw a 4x4 grid of boxes.

(5) From here on, I will say "decode a value" several times. This means to do a Huffman decoding operation on the linear string of bits, starting at whatever position you're currently at. This will consume some number of bits in the bit sequence, and return a decimal value. The rule for this is: 

if the next 3 bits have a binary value b = 000, 001, ... 110
  consume 3 bits and return(b)
else (must be 111)
{
  throw away the 111, consume the next 2 bits (call these n)
  return(n+7)
}
Observe that this procedure returns a value in the range 0 to 10.

(6) Decode a value. This value plus 1 says how many consecutive letters of the alphabet to fill into the 4x4 array starting at the upper left corner and going left to right and top to bottom. For example, if value+1 is 5, the array would now look like 

      A B C D
      E - - -
      - - - -
      - - - -
where - is an empty cell.

(7) For each remaining cell in the grid, decode a value. If the value is 0, write in the earliest letter of the alphabet that does not appear in the grid. If the value is a non-zero value n, write A if n=1, B if n=2, etc.

At this point you're done with the puzzle reconstruction. Now you just need to know what the 16 puzzles are.

Here is the first one. Think of the 4x4 array as a handwritten addition sum, where the first three rows are the addends and the bottom row is the sum. The puzzle is to find an assignment of letters to the decimal digits 0 through 9 that results in a valid addition sum. The usual rules apply: a given letter always stands for the same digit, and a given digit is always represented by the same letter. Finally, you are to try to find the solution that has the largest numerical value for the sum.

Here is the second puzzle: Do it again, trying to minimize the sum.

Here are 6 more puzzles: Rotate the grid by 90, 180, and 270 degrees. For each version, solve the resulting puzzle both ways (maximizing and minimizing the sum).

And finally, here are the last 8. Hold the array up to a mirror, and rotate it all four ways, and solve those four puzzles both ways.

Got that?
Here is a four-character ASCII string that conforms to the above definition. You should be able to apply the decompression algorithm to get the 4x4 array and then solve the resulting 16 puzzles.

L   =   -U

(That's a minus sign before the U.) This puzzle also has another amazing feature (which I consider a requirement, but is by no means an easy feature for your humble puzzle constructor to guarantee):

Each of the 16 arithmetic puzzles has a unique solution!

I haven't yet created a page with the solution (but trust me - there is one!). Someday I'll create a solution page, and also some more puzzles of this type...

Back to Mike's home page