**Introduction**

Suppose that you are the owner of a new hotel chain, and that you want to implement a mechanical key card locking system on all of the hotel room doors. Each key card will have a unique pattern of holes in it, so that when a card is inserted into the corresponding room’s door lock, a system of LEDs and detectors inside the lock will only recognize that unique pattern of holes as an indication to unlock the door.

(I have vague childhood memories of family vacations and my parents letting me use just such an exotic gadget to unlock our hotel room door.)

When you meet with a lock manufacturer, he shows you some examples of his innovative square key card design, with the “feature” that a key card may be safely inserted into the slot in a door lock in any of its eight possible orientations: any of the four edges of the square key card may be inserted first, with either side of the key card facing up. Each key card has a pattern of up to 36 holes aligned with a 6×6 grid of sensors in the lock that may “scan” the key card in any orientation.

The lock manufacturer agrees to provide locks and corresponding key cards for each room, with the following requirements:

- A manufacturer-provided key card will only open its assigned manufacturer-provided lock and no other; and
- A manufacturer-provided key card will open its assigned manufacturer-provided lock when inserted into the slot in
*any*orientation.

How many distinct safely-locked rooms can the manufacturer support?

**A simpler lock is a harder problem**

The problem as stated above is a relatively straightforward application of Pólya counting, using the cycle index of the dihedral group of symmetries of the key card acting on (2-colorings of) the grid of possible holes in the card. When is even, the cycle index (recently worked out in a similar problem here) is

Evaluating at yields a total of 8,590,557,312 distinct key cards– and corresponding hotel room door locks– that the manufacturer can provide.

However, these locks are expensive: the second requirement above means that each lock must contain not only the sensing *hardware *to scan the pattern of holes in a key card, but also the *software *to compare that detected pattern against the eight possibly distinct rotations and reflections of the pattern that unlocks the door. (For example, the key card on the left in the figure above “looks the same” to the sensor in any orientation; the key card in the middle, however, may present any of four distinct patterns of scanned holes; and the key card on the right “looks different” in each of its eight possible rotated or flipped orientations.)

Which leads to the problem that motivated this post: to reduce cost, let’s modify the second requirement above– but still retaining the first requirement– so that a manufacturer-provided key card will only open its assigned manufacturer-provided lock when inserted into the slot in a *single *correct orientation labeled on the key card. This way, the sensing hardware in the lock only needs to “look for” a single pattern of holes.

Now how many distinct key cards and corresponding room locks are possible?

**Counting regular orbits**

The idea is that, referring again to the figure above, key cards may only have patterns of holes like the example on the far right, without any rotation or reflection symmetries. In other words, given the (dihedral) group of symmetries acting on colorings of the set of possible key card hole positions, we are counting only *regular* orbits of this action– i.e., those orbits whose colorings are “fully asymmetric,” having a trivial stabilizer.

So how can we do this? My approach was to use inclusion-exclusion, counting those colorings fixed by *none *of the symmetries in . To start, we represent each element of as a list of lists of elements of , corresponding to the disjoint cycles in the permutation of . For a given subset in the inclusion-exclusion summation, consider the equivalence relation on relating two key card hole positions if we can move one to the other by a sequence of symmetries in . Then the desired number of -colorings fixed by is , where is the number of equivalence classes.

We can compute this equivalence relation using union-find to incrementally “merge” the sets of disjoint cycles in each permutation in (all of the code discussed here is available on GitHub):

def merge(s, p): """Merge union-find s with permutation p (as cycles).""" def find(x): while s[x] != x: x = s[x] return x def union(x, y): x = find(x) s[find(y)] = x return x for cycle in p: reduce(union, cycle) for x in range(len(s)): s[x] = find(x) return s

It remains to compute the inclusion-exclusion alternating sum of these over all subsets .

def cycle_index_term(s, k=2): """Convert union-find s to cycle index monomial at x[i]=k.""" #return prod(x[i]**j for i, j in Counter(Counter(s).values()).items()) return k ** sum(Counter(Counter(s).values()).values()) def asymmetric_colorings(group, k=2): """Number of k-colorings with no symmetries in the given group.""" # Group G acts on (colorings of) X = {0, 1, 2, ..., n-1}. G = list(group) n = sum(len(cycle) for cycle in G[0]) # Compute inclusion-exclusion sum over subsets of G-e. G = [g for g in G if len(g) < n] return sum((-1) ** len(subset) * cycle_index_term(reduce(merge, subset, list(range(n))), k) for subset in chain.from_iterable(combinations(G, r) for r in range(len(G) + 1)))

Evaluating the result– and dividing by the size of each orbit — yields 8,589,313,152 possible “fully asymmetric” key cards satisfying our requirements.

**Questions**

At first glance, this seems like a nice solution, with a concise implementation, that doesn’t require much detailed knowledge about the structure of the symmetry group involved in the action… but we get a bit lucky here. The time to compute the inclusion-exclusion summation is exponential in the order of the group, which just happens to be small in this case.

For a more complex example, imagine coloring each face of a fair die red or blue; how many of these colorings are “orientable,” so that if the die rests on a table and we pick it up, put it in a cup and shake it and roll the die to a random unknown orientation, we can inspect the face colors to unambiguously determine the die’s original resting orientation? We can use the same code above to answer this question for a cube or tetrahedron (0 ways) or octahedron (120/24=5 ways)… but the dodecahedron and icosahedron are beyond reach, with rotational symmetry groups of order 60.

Of course, in those *particular *cases, we can lean on the additional knowledge about the structure of the subgroup inclusion partial order to solve the problem with fewer than the -ish operations required here. But is there a way to improve the efficiency of this algorithm in a way that is still generally applicable to arbitrary group actions?

Interesting that your hotel key answer is ever slightly MORE than 2^33. 33.00010458 according to my calculator. So less than 3 “bits” of information were consumed encoding the orientation.

Right! This makes sense; the order of the symmetry group is 8=2^3, and although “most” of the orbits of the action are regular, some are smaller, comprising those key cards with some symmetries; so the total *number* of orbits is *greater* than 2^36/2^3.

Similarly, in the second part of the post, we are counting *just* those regular orbits, discarding all key cards with any symmetries, so that the resulting number of such orbits is *less* than 2^36/2^3.

I was investigating a very similar problem last week evaluating British Square positions, though I was focused entirely on the “software to compare that detected pattern against the eight possibly distinct rotations” part. Since I still had those details in mind, I worked out the bit transforms for a 6×6 grid and wrote a program to count the possibilities by brute force:

https://gist.github.com/skeeto/1718d6613dc47a7aff13333942a40776

It visits the entire space in under 3 minutes (Clang, 8 hyper-threads), and its final count exactly matches yours (of course).

Nice! For readers’ context, see Chris’s recent article about solving the referenced board game, with a good description of the board encoding used in the linked source.

We can make this even more efficient: since orbit membership is an equivalence relation, in

`valid(x)`

we don’t need to check all pairs of elements of the orbit for equality. We can just visit each element of the orbit, always comparing against the initial input board`x`

(gist).And we can also skip the restriction to only counting the canonical (minimum) representative of each orbit. Since we are explicitly counting orbits all of the same size, we can just divide the total by the order of the symmetry group (8) when we’re done.

You’re right! Your modification is a nearly 2x speedup.