Here’s a puzzle from the informal coding competition code with meaning by Computas (an IT company in Norway). For each problem solved, Computas donates money to a good cause.

The objective is to press the buttons so the dials are all turned to the “sunrise” position (in green):

There are \(5\) buttons and \(6\) dials. Here I will quickly show how to formulate this as a mathematical problem, then solve it using abelian (software I wrote for my master’s thesis).

Let \(A\) be a matrix in which each column represents the action of pressing a button. The entry \(0\) means no rotation, \(1\) means rotating a quarter turn with the clock, \(2\) means rotating two quarter turns with the clock, and so forth. In general \(a_{ij}\) is the number of quarter turns dial \(j\) makes when button \(i\) is pushed.

from sympy.matrices import Matrix

# The start position of the dials
start_pos = Matrix([0, 3, 3, 3, 0, 1])

# The final position of the dials
final_pos = Matrix([0, 0, 0, 0, 0, 0])

# Matrix encoding the button actions
A = Matrix(
    [
        [3, 0, -1, 1, -2], # Button A
        [2, 0, 1, 1, 2],   # Button B
        [1, 1, -2, 1, 0],  # Button C
        [1, 0, 1, 0, -2],  # Button D
        [0, 1, -2, 3, 2],  # Button E
        [0, 0, 1, 1, -2],  # Button F
    ]
)

We have to solve \(\boldsymbol{s} + A \boldsymbol{x} = \boldsymbol{0} \mod 4\), which is equivalently expressed as

Here’s how to solve it using the general purpose solver in abelian:

from abelian.linalg.solvers import solve

# Solve A x = 0 - s mod 4
x = solve(A, final_pos - start_pos, p=Matrix([4] * 6))
x % 4 # Take modulus of the solution

As you can see below, this is indeed the solution:

Group theory

This problem is best thought of as a group theoretic one. The matrix \(A\) represents a homomorphish between two groups.

• The source group is \(\mathbb{Z}_+^5\), since \(5\) buttons can be pushed \(0\) or more times.
• The target group is \(\mathbb{Z}_4^6\), since there are \(6\) dials with period \(4\).

We can construct this homomorphism as follows:

from abelian import LCA, HomLCA
from IPython.display import display, Math


def show(arg):
    """Pretty printing in notebook"""
    return display(Math(arg.to_latex()))


# The source groups is Z_+^5 (5 buttons can be pushed 0 or more times)
source = LCA(orders=[0] * 5, discrete=[True] * 5)

# The target group is Z_4^6 (6 dials with a period of 4)
target = LCA(orders=[4] * 6, discrete=[True] * 6)

# Phi is a homomorphism between elementary locally compact Abelian groups
phi = HomLCA(A, target, source)
show(phi)

Notice those negative numbers? Lets get rid of those, since e.g. rotating \(-1\) quarter-turns is the same as rotating \(3\) quarter-turns. This is called a canonical target projection.

show(phi.project_to_target())

There’s also a canonical source prjection, which determines the periodicity of the source group.

phi = phi.project_to_source().project_to_target()
show(phi)

Now we have \(\phi\) in canonical form—completely equivalent, but easier to read. Drifting off on a tangent, I want to mention that completely analogous to the fundamental theorem of linear algebra, there exists a fundamental theorem of finitely generated Abelian groups:

abelian is capable of solving for these homomorphisms. I wrote about this in Chapter 5 in my thesis “Fourier analysis on abelian groups; theory and applications”.