This paper will focus on two aspects in the TED talk “Scott Kim takes apart the art of puzzles” of Scott Kim who is professional in problem maker especially puzzles. Both aspects will be considered under data structure perspective. The first aspect will discuss about how we can apply a technique of using both the “picture space” and the “background space” which are mentioned in the talk to create a data structure. The second aspect focusses on whether using such a data structure similar to “puzzle with overlap” is useful or not.
Using “picture space” and “background space”, we can create a data structure with enough basic operations such as deleting, merging, inserting, and moving. When you move a block, if there is any overlap pixel, for example the black pixels are overlapped, number of black pixel will decrease which means there is a black pixel that was deleted. Likewise, this operation creates new white pixels, or we can say it inserts new white pixels.
Moving a block next to or overlap another same color block is equivalent to merging two blocks. Moving a block but not making any overlap is equivalent to swapping two blocks. Interesting enough, moving of one block can be seen as “XOR” operation of that block with the same size block at destination place. Suppose white represents bit 0, while black represents bit 1. If a pixel in the moving block is as same color as the destination pixel, the destination color does not change, which means 0 XOR 0 is 0, 1 XOR 1 is 1. On the other hand, if they are in different color, then the destination color will change, means 0 XOR 1 is 1, or 1 XOR 0 is 1.
Techniques used in the talk can be seen in several different ways in real life, not only in the puzzle. For example in Photoshop or GIMP or other image processing software, we have layers. Now each time a block of “picture space” or “background space” is moved, the equivalent operation in such software is to select the desired block by selection tool such as Magic Wand Tool and then inverse the selection block color, finally create new layer that copies content of the block and process this new layer separately from the original layer.
Although we seldom keep data in more than one place or more than one form, but data structure which is similar to the “puzzle overlap” is useful in some cases. Overlap can be understood as redundant. We often use redundant for recovering information from lost or encryption.
We also use redundant for enhancing data availability. Computer memory structure is composed of many sectors, clusters which are allocation unit whose capacities are fixed, for example 512 bytes or 1kB, 2kB, 4kB… If the information amount is less than capacity of a cluster, that information still occupies one cluster and the rest capacity of the cluster will be wasted.
This leads to disk fragmentation. We can take advantage of the wasted memory to store the redundant data such as the “puzzle overlaps” structure mentioned above. This will be useful when data accidently lost. While disk fragmentation is reduced, unwanted lost data might be recovered by such redundant information.
Following will be another example to be considered for usefulness of “puzzle overlap” data structure. In telecommunications, in order to transmit a digital data over radio, the data is encrypted first, and then modulated from the digital form to analog signal. The resulted analog signal is then moved from low frequency to high frequency (kHz for AM, MHz for FM, and GHz for satellite) for transmission. To the receiver, received signal is then baseband filtered and demodulated back to digital form.
Finally, it is decrypted to reveal the original data. Because of long transmission path and lots of processes, there are a lot of risks can be happened during transmission, for example, fading, phase shift, noise… These risks lead to data lost or wrong data receiving. Therefore, such data structure as “puzzle overlaps” can help reducing those risks, for example, it can enhance phase synchronization, avoid phase shift problem.
In conclusion
Although Kim’s perspective is of a problem maker or an artist, it is useful to take into account his idea and move to a data structure perspective to see more interesting aspects that can help us realize more about data structure in the real world, not just limit in computer science point of view.
