Solutions for Act I Scene 4 - Encoded

There's no obvious place to start with this puzzle, but there are some observations that can be made. For example:

  • Counting the cells or question marks reveals that the grid size is 64 by 64, which is a power of 2.
  • The arrows and quadrants point in upper-left, upper-right, lower-left, lower-right directions.
  • There's a fully black circle at (32, 32) in the centre of the grid.
  • There are circles at (16, 16), (16, 48), (48, 16) and (48, 48). For the last three points, there are no circles in the direction of the white quadrant.
  • Less obviously, the intersections which do have circles have x, y coordinates such that their lowest 1 bits are in the same position (this is what causes the grid to look like it has many groups of circles on the same diagonal line)

The intuitive leap is then to realise that the grid can be filled in the following way:

  • Look at the central circle: black means there's at least one shaded cell in that quadrant, white otherwise.
  • Recurse and repeat for each quadrant separately.

In computer science terms, the grid and circles form a representation of a quadtree, which can be used to compress images by storing less information about sections of similar colour.

Filling in the grid produces:

The message reads USE BASE 64. Base64 is an encoding for converting binary data into printable ASCII characters. Of note is the fact that base64's output assigns each of the values from 0 to 63 to one of ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/, in that order.

This gives us a way to fill in the row and column of question marks, but we still need to make use of the arrows. Noting that there are 6 arrows in each row and 26 = 64, we can follow the arrows to traverse the tree and select cells in the grid. For instance, the first row means select the lower-right quadrant, then within that quadrant select the upper right quadrant, and so on.

Doing so gives 8 cells in the grid, which we can translate to pairs of letters/numbers via the base64 mapping. For example, the first row of arrows produces the letters 1i, and the second row produces 9x. Continuing in this fashion forms the message 1952PrefixCodeBy via reading down the two columns obtained.

This gives the answer as HUFFMAN, who developed the eponymous Huffman coding optimal prefix code scheme in their 1952 paper.

Design notes:
The main problem with this puzzle was that, if one squints hard enough at the black parts of each circle, it's possible to guess what the filled in grid would look like without realising the quadtree nature of the grid. As such, the answer couldn't simply be a picture or message formed by the grid. The arrows were the solution to this since even if one could make out the message, without fully understanding how the message was formed it would be difficult to extract the answer. Letters were also deliberately aligned so that large blocks of shaded squares exist.

Initial versions of this puzzle lacked the question marks and used 0123 in place of the arrows. Once it was realised that the puzzle may be harder than initially thought, these components were changed to lessen ambiguities and to serve as additional hints.

The answer is: huffman