How Many Ways Can You Raise the Dots?

A braille character is a pattern of raised dots in a cell of three rows and two columns. Each of the six places is raised or not, so there are $2^6 = 64$ possible characters, counting the blank cell. The $26$ letters of the Latin alphabet use $26$ different patterns, and although some letters are rotations or reflections of one another, no two are translations of one another: no letter is another letter slid up, down, left or right within the cell. For instance, $A$ is the only letter with a single dot. What is the largest set of the $64$ characters in which no two are translations of each other?

The Fiddler, Zach Wissner-Gross, August 4, 2023(original post)

The official solution appeared in the post of August 11, 2023 and gives $45$ (or $44$ leaving out the blank cell) for the main puzzle and $15{,}499{,}265$ (or $15{,}499{,}264$) for the Extra Credit, agreeing with the answers below.

Solution

Call two patterns equivalent when one is a translation of the other. Sliding a pattern and then sliding the result is again a slide, so this sorts the $64$ patterns into classes, and two patterns in the same class are exactly the pairs the set may not contain together. The largest allowed set takes one pattern from each class, so the answer is the number of classes.

To count the classes, pick a standard member of each. Slide a nonempty pattern up as far as it will go and then left as far as it will go. The result has a dot in the top row and a dot in the left column, and it is the only member of the class with both properties, since any other member is the same shape shifted down or right. The figure shows one class of four patterns and its standard member.

So the question becomes: how many patterns have at least one dot in the top row and at least one in the left column? Count them by subtracting the failures. Of all $2^6$ patterns, those with an empty top row number $2^4$ (any pattern on the other four places), those with an empty left column number $2^3$, and those with both empty number $2^2$, the pattern on the bottom two places of the right column. Patterns with both an empty top row and an empty left column have been subtracted twice, so they are added back once: $$2^6 - 2^4 - 2^3 + 2^2 \;=\; 64 - 16 - 8 + 4 \;=\; 44 .$$ Those are the nonempty classes. The blank cell is a class of its own, with no translations at all, so $$\boxed{\ 45 \text{ characters}, \text{ or } 44 \text{ leaving out the blank cell}. \ }$$

The same count works for any cell. With $m$ rows and $n$ columns the number of classes, including the blank one, is $$2^{mn} - 2^{(m-1)n} - 2^{m(n-1)} + 2^{(m-1)(n-1)} + 1 .$$

The computation

The check slides every pattern up and left, for every one of the $2^6$ patterns and, in the Extra Credit, every one of the $2^{24}$, and counts how many different results there are. A pattern is stored as a whole number whose bit $r \cdot \text{cols} + c$ is the dot in row $r$ and column $c$, so sliding up by $t$ rows is a right shift by $t \cdot \text{cols}$ bits, and sliding left by $\ell$ columns is a right shift by $\ell$ bits, which stays inside each row because no dot lies left of column $\ell$.

import numpy as np

def classes(rows, cols):
    """Count dot patterns in a rows-by-cols cell up to
    translation: slide each as far up and left as it goes,
    then count the different results."""
    # bit r*cols + c of p is the dot in row r, column c
    p = np.arange(2**(rows*cols), dtype=np.int64)
    row_mask = (1 << cols) - 1
    col_mask = sum(1 << (r*cols) for r in range(rows))
    top = np.full(p.shape, rows)     # first row with a dot
    for r in reversed(range(rows)):
        top[(p >> (r*cols)) & row_mask != 0] = r
    left = np.full(p.shape, cols)    # first column with a dot
    for c in reversed(range(cols)):
        left[(p >> c) & col_mask != 0] = c
    top[p == 0], left[p == 0] = 0, 0
    # no dot lies left of column `left`, so the second shift
    # moves dots within their rows
    slid = (p >> (top*cols)) >> left
    return len(np.unique(slid))

print("3 by 2 cell:", classes(3, 2), "including the blank cell")

It prints

3 by 2 cell: 45 including the blank cell

Extra Credit

Double the cell in each direction, to six rows and four columns, with $2^{24}$ possible characters. How many are in the largest set with no two characters translations of each other?

Solution

Nothing in the argument depended on the size of the cell. The nonempty classes again correspond to patterns with a dot in the top row and a dot in the left column. With $m = 6$ and $n = 4$, the top row has $4$ places, the left column $6$, and they share one, so $$\begin{aligned} 2^{24} - 2^{20} - 2^{18} + 2^{15} &\;=\; 16{,}777{,}216 - 1{,}048{,}576 \\ &\qquad - 262{,}144 + 32{,}768 \\ &\;=\; 15{,}499{,}264 . \end{aligned}$$ Adding the blank cell, $$\boxed{\ \begin{array}{c} 15{,}499{,}265 \text{ characters}, \\ \text{or } 15{,}499{,}264 \text{ leaving out the blank cell} \end{array} \ }$$ Almost every pattern is now the standard member of its class. Only $1{,}277{,}952$ patterns, under $8$ per cent of the $2^{24}$, miss the top row or the left column, so translation merges far fewer patterns than in the small cell, where $19$ of the $64$ were merged away.

The computation

The function above handles the larger cell unchanged, sliding all $16{,}777{,}216$ patterns.

print("6 by 4 cell:", classes(6, 4), "including the blank cell")

It prints

6 by 4 cell: 15499265 including the blank cell