Braille
Fiddler – Braille Problem
The following is my write-up for this weeks Fiddler problem, which asks
Of the 64 total potential Braille characters, how many are in the largest set such that no two characters consist of raised dot patterns that are translations of each other?
What Is A Translation ?
As described in the problem statement, a Braille character or configuration consists of a \(3 \times 2\) grid of cells, where each cell can be raised or empty. Let \(A\) and \(B\) denote two Braille configurations. We say \(A \equiv B\) if we can move each raised dot of \(A\) by the same distance and in the same direction to get to \(B\). NOTE: When moving raised dots, we are not allowed to wrap around the edges of the grid (as clarified in the comments section of the problem). The animation below describes Braille configurations that are equivalent to each other.
Formalising The Problem
Given any grid with \(r\) rows and \(c\) columns there are total of \(2^{r\times c} -1\) possible braille configurations1. Now consider any mini rectangle of height \(1 \leq h \leq r\) and width \(1 \leq w \leq c\) inside the main \(r \times c\) grid. (See picture below)
Given a mini-rectangle of area \(h\times w\), the total number of ways we can slide it around is \((r - h +1) \times (c - w + 1)\). The first term gives the number of ways you can go up/down and the second term describes the number of times you can slide left/right. The plus \(+1\) includes the current config if there is no room to slide around.
For some configuration of raised dots that fit inside this rectangle – all configurations formed by sliding this rectangle around are equivalent.
So the question now becomes: How many such rectangles can we make? This answer is simple- Each \(h\) and \(w\) is constrained to be in the set \(\{1, \dots, r \}\) and \(\{1, \dots, c \}\). Taking the cross product we get \(r\times c\) possible rectangles.
Ok! But given a rectangle of certain size – how many different Braille configurations can we fit in. Note for the rectangle to have an area \(h \times w\), the max length between any two raised dots inside the rectangle must be \(w\) and max height must be \(h\) (See picture below).
How many configurations per rectangle
If we have \(h=1\), then for any \(w \in \{1, \dots, c\}\) we have the total possible braille configurations that fit inside this rectangle is simply \(2^{w-2}\). (We subtract two because we need to put two dots at the two extremes to ensure the width is \(w\). Once we have placed these two dots, then we can arrange the inner dots any way we want).
Similarly, if we have \(w=1\), then for any \(h=\{1, \dots, r\}\), we have the total possible Braille configurations to be \(2^{h-2}\).
If we have \(w=1\) and \(h=1\) then there is only one way to fill out the square (NOTE we do not allow the grid with no raised dots)
Ok. All the edge cases are done. Next we look at configurations for general \(h \geq 2\) and \(w \geq 2\). The following picture summarises the possibilities.
As we have to ensure that the width and height of the rectangle is \(w\) and \(h\), we have to be careful how we handle the corners. For example, when none of the corners are raised, we have to avoid the top row or bottom row to have the all cells NOT raised. As two top corners are blank, there are \(2^{w-2}\) ways to configure the top row. However, we must exclude the possibility that all cells are blank, which is included in \(2^{w-2}\) possibilities. Hence we get \(2^{w-2} -1\) possibilities for the top or bottom row. A similar argument holds for the left and right edges.
Next we iterate all the different kinds of corners that are possible and use a similar argument as above to describe how to handle each of these cases (see below):
The following lines of code compute the different configurations for a given mini-rectangle.
Finally, to get the total number of configurations we just loop through all possible rectangles and sum the different configurations
Giving us a solution of 44 configurations.
Extra Credit: Replace the \(r=6\) and \(c=4\) in the above snippet and we get 15,499,264.
We subtract by -1 to exclude the configuration without any raised dots.↩︎