Disorderly Escape

Created: Oct 28, 2026

Last modified: Oct 28, 2026

* AI-generated from the code I used in Google Foobar

TL, DR.

Show challenge description

You made it off the station, but Lambda's starfighters are on your tail and you need to jump to hyperspace. To pick where to jump, you have to count how many different configurations each quadrant can have. Strip away the story and here's the problem: a grid w wide and h tall, where every cell is in one of s states, and two grids count as the same if you can turn one into the other by swapping rows and columns. How many truly different grids are there?

Full disclosure up front: I didn't crack this one on my own. Like the other level 5 problem, I got there with outside help, and the idea behind it is the Pólya enumeration theorem. What I can do is walk you through how it works, step by step.

# When are two grids the same?

A 2 × 2 grid with two states has 2⁴ = 16 possible grids, and the statement says only 7 of them are different. The demo groups them by brute force: it tries every way of reordering rows and columns and puts together the grids that match. Each card is one group, showing one of its grids and how many it holds. Click a card to see them all, and play with w, h and s to watch it grow.

There are 16 grids of 2 × 2 with 2 states, but only 7 different ones.

The first thing you'll notice is that the groups come in different sizes. On a 2 × 2 grid, the all-silent one is alone, the one with a single noisy cell comes in 4 versions, and the one with a noisy row comes in 2. So dividing 16 by the 4 ways to reorder doesn't work. And a 12 × 12 grid with 20 states has 20¹⁴⁴ possible grids, so grouping them by hand is out of the question too. We need a different way to count.

# Burnside's lemma

The trick is to flip the question around. Instead of grouping grids, take each way of reordering rows and columns and count how many grids it leaves unchanged. The average of those counts is exactly the number of groups:

Why does that work? Pick a group in the demo and look at the last sentence: the group's size times the number of permutations that leave each of its grids alone always gives the total, which is 4 for a 2 × 2 grid. The all-silent grid is alone, but none of the 4 permutations changes it. Each of the 4 grids with a single noisy cell only stays put if you move nothing. So every group adds up to exactly 4, whatever its size, and dividing by 4 leaves a 1 per group. For 2 × 2, the sum is 4 + 4 + 4 + 16 = 28, and 28 / 4 = 7.

# How many grids stay the same?

Reordering rows and columns moves the cells around in cycles: cell A goes where B was, B goes where C was, and eventually something lands back on A. For the grid to look the same, every cell in a cycle must be in the same state. Each cycle picks its state freely, so with c cycles there are s^c grids that don't change.

Now we just need to count the cycles, and that's where the gcd comes in. If some rows turn in a cycle of length a and some columns in a cycle of length b, their a · b cells all come home after lcm(a, b) steps. So every cycle of cells has that length, and there are

of them. For example, 2 rows swapping and 3 columns rotating make one single cycle of 6 cells. Add up the gcd of every row cycle with every column cycle, and you have the total.

# Grouping by cycle type: Pólya

One problem left: with 12 rows and 12 columns there are 12! · 12! ≈ 2.3 × 10¹⁷ ways to reorder, far too many to go through one by one. But the number of cycles only depends on the lengths of the cycles, not on which rows are actually moving. Swapping rows 0 and 1 works out the same as swapping rows 3 and 7.

The cycle lengths of a permutation of n items form a partition of n: 3 = 3 = 2 + 1 = 1 + 1 + 1. The number 12 only has 77 partitions, so checking 77 × 77 pairs is enough. All that's missing is how many permutations have each shape. If the partition has m_k cycles of length k, there are

With 3 rows, for instance, there are 3! / 3 = 2 permutations that rotate all three and 3! / (1 · 2) = 3 that swap two and leave one alone. Grouping permutations by their cycles like this is called the cycle index, and using it to count configurations is the Pólya enumeration theorem.

# The whole sum

This demo builds the entire sum. Each row of the table is a pair of partitions, one for the rows and one for the columns. Click one and a permutation of that shape is drawn on top: the arrows show where each row and column goes, and cells in the same cycle share a color. Try 2 × 3 with s = 4, the statement's other example, to land on 430.

There is 1 pair of permutations of this shape, and each splits the cells into 2 cycles, so each leaves 2² grids unchanged. Adding up all 4 rows gives 28, and dividing by the 4 pairs leaves 7.

# The code

Here's the code I submitted, written for Python 2.7, which is what Foobar ran:

from collections import Counter


def factorial_memo(n, mem=dict()):
    if n in mem:
        return mem[n]
    if n <= 1:
        return 1
    mem[n] = n * factorial_memo(n - 1)
    return mem[n]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def cycle_count(c, n):
    cc = factorial_memo(n)
    for a, b in Counter(c).items():
        cc //= (a ** b) * factorial_memo(b)
    return cc


def cycle_partition(n, i=1):
    yield [n]
    for i in range(i, n // 2 + 1):
        for p in cycle_partition(n - i, i):
            yield [i] + p


def solution(w, h, s):
    grid = 0
    for partitionW in cycle_partition(w):
        for partitionH in cycle_partition(h):
            m = cycle_count(partitionW, w) * cycle_count(partitionH, h)
            grid += m * (s ** sum([sum([gcd(i, j) for i in partitionW]) for j in partitionH]))
    return str(grid // (factorial_memo(w) * factorial_memo(h)))

# Wrapping up

Whenever you need to count things "regardless of order" or "regardless of how you turn them", counting head-on rarely works, because the groups come in different sizes. Burnside swaps the question for an easier one: how many things does each move leave alone? Pólya makes it easier still, since only the shape of the cycles matters. What looked like 20¹⁴⁴ grids ends up as a sum of 77 × 77 terms.