I decided to write a web-based brainteaser puzzle after seeing a puzzle in the August 2023 Mensa Bulletin that reminded me of an electronic game that I liked to play many years ago. I decided to recreate that game using the layout and rules of the Mensa puzzle.
I have since made this daily puzzle available to the public and here it is: FlipIT
In this blog article, I will discuss some of the design aspects of this program/web-app.
This article is a work in progress that discusses design and coding aspects of the FlipIT web application.
Introduction
About the puzzle
This is a puzzle based on Magic Square where the objective is to flip the disks to achieve the desired pattern. When you flip a disk, all the adjacent disks flip as well (including the diagonals). The final pattern has all the outside disks black and the inside disks white. This version of the puzzle uses a four-by-four grid where the daily and random setups can always be solved in three moves.
As you flip the disks, the squares where you clicked are highlighted so you can see your moves. You can undo any move at any time by simply clicking on that square again. It doesn’t matter if the move you are undoing was your last move, first move, or otherwise. With the daily and random puzzles, the solution will have three squares highlighted. If you type in a puzzle number, you will end up with a puzzle that requires any number of square clicks to solve.
Why click order doesn't matter
Whether a disk ends up in a flipped state or not is not related to the order of your flips. Because each disk can only have two states, this is a binary problem. If there are an odd number of adjacent squares clicked (including itself), then the disk will be flipped. An even number or zero will result in the disk not ending in a flipped state. So the final combination of clicked squares gives you the flipped state of every disk.
Algorithms
Making sure the puzzle is solvable in three moves
this program keeps track of its state by using a one-dimensional array of 16 bits. A zero bit represents a white disk and a one for a black disk.
It doesn’t matter if you use one dimension where you have to derive the X and Y value of each cell, or two dimensions where you have to derive the X and Y of a random cell selection – the random selection will be a number between 0 and 15 as it would be wasteful to compute two random numbers to get X and Y. One way or another, a conversion is necessary so I went with the simpler storage mechanism.
The absolute easiest algorithm for creating a random puzzle is to start with the final pattern as an array and then randomly click three cells to get to a starting pattern. You just have to make sure that no two random cells are the same cell. So, you create three random and unique numbers between 0 and 15 and then change those bits of the final pattern along with their adjacent bits to get the starting pattern. The function that changes the adjacent cells knows that the cell above is random (R) - 4 and below is R + 4. Add or subtract one from those values to get the diagonal adjacents.
Everyone gets same random daily puzzle
As described above, creating a puzzle involves computing three unique random numbers. To make sure everyone around the world sees the same daily puzzle requires using the date at a specific time zone to generate those numbers.
It used to be that random number generators required that the programmer generate a seed value to feed the generator from which it would produce a continuous string of seemingly unrelated numbers. It was common to use the computers “timer” value which was either the number of ticks since the computer was turned on or the current time represented as ticks since midnight. It is up to the computer to determine the number of ticks per second and this was usually done in hardware. Any given seed value would always generate the same sequence of random numbers.
JavaScript doesn’t offer a mechanism for providing the seed. How the seed is generated is browser dependent and obfuscated as this is one of the points of attack for finding holes in security algorithms. In our case, however, we don’t need the generator to be truly random or have uncorrelated, uniform coverage. So, I added my own generator using a common algorithm.
So, feeding the date to this generator creates a series of random numbers that is the same in every browser around the world. The time zone I selected is UTC although perhaps EST (New York) would have made more sense. With UTC, you may get a new puzzle in the middle of the day instead of midnight depending on where you are. While that is true of any time zone, there are already a lot of puzzles that use EST, so the expectations would be the same.
To improve the entropy of the seed, I put it through a hashing function. A hash is a series of bit manipulations where a trivial change between inputs will result in completely uncorrelated outputs. It is like putting the bits in a blender – there is no way to figure out the order of the original bits by looking at the output. Hash functions also produce the same length output regardless of input. If the input is longer than the output, then the hash represents a loss of data which is good as it makes it even more impossible to derive the input from the output. While this may seem like overkill, I felt it was necessary because two strings made from dates that are near each other will be mostly the same unless you hash them. “January 3, 2024” is too similar to “January 18, 2024” even though they are 15 days apart.
There are some considerations here. While using the date guarantees that no seed is ever reused, hashing it removes that guarantee. It is extremely rare but possible for two dates to produce the same hash and thus the same sequence of random numbers. A bigger limitation is that with only 16 cells, there are only so many unique combinations of three cell clicks. There are even fewer if you exclude puzzle rotation equivalents. Including rotations, I believe there are 3,360 (16 x 15 x 14) possible puzzles – enough for 9 years. Still, that is far more unique than Wordle’s 239 puzzles.
Every puzzle gets a number
The easiest way to associate a puzzle with a unique number is to use its initial pattern as bits in a 16 bit number. Above I talked about how I am already using a one-dimensional array of 16 bits. If this was stored as consecutive bits in a single memory location, then I could just read it as an integer. But this is not the case here. Still, the assembly is almost trivial. In JavaScript this is:
- pattern is my array
- slice() is a cheap way of creating a copy of the original array so that my changes don’t affect the original array
- reverse() allows me to consider the first cell as the least significant bit. This reduces the steps needed to turn a number into a patern.
- Join() is a cheap way of turning the array into a string
- parseInt() converts the string into an integer. The “2” parameter tells parseInt() that the string represents a binary number.
Converting a number into a binary array is a little more work.
[...Array(b)].map((x,i)=>(n>>i)&1);
const Bitarr = bits(number,16);
0 comments:
Post a Comment