Riddler Classic, Dec 11: https://fivethirtyeight.com/features/how-high-can-you-count-with-menorah-math/

riddler.py

"""fivethirtyeight.com Riddler Classic, Dec 11
https://fivethirtyeight.com/features/how-high-can-you-count-with-menorah-math/


'''
From Alex van den Brandhof comes a matter of life and death:

The Potentate of Puzzles decides to give five unlucky citizens a test. The potentate has countless red hats, green hats and blue hats. She says to the citizens, “Tomorrow, you will all be blindfolded as I place one of these hats on each of your heads. Once all the hats are placed, your blindfolds will be removed. At this point, there will be no communication between any of you! As soon as I give a signal, everyone must guess — at the same time — the color of the hat atop their own head. If at least one of you guesses correctly, all of you will survive! Otherwise …”

The potentate continues: “The good news is that there’s a little more information you’ll have. I will be arranging you into two rows facing each other, with two of you in one row and three of you in the other. Citizens in the same row cannot see each other, but they can see all the citizens in the other row. Finally, each citizen will know their placement within their own row — that is, whether they are seated on the left or right or in the middle.”

Can the citizens devise a strategy beforehand that ensures their survival? If so, what is the strategy?
'''

Formal problem description:

Let pQ be a person wearing a hat of color Q.
Any Q has one of the values 0, 1 or 2. Define Q+n as Q+n modulo three for any integer n.
Each pQ must emit a color sQ.
Given five persons pA, pB, pX, pY, pZ,
for all possible hat colorings A, B, X, Y, Z,
they must emit colors such that sQ == Q for at least one person.
pA and pB can observe X, Y, Z.
pX, pY, pZ can observe A and B.
Emissions must be based on observations only.
Each person knows their own identity and the identity of the observed persons.


Solution:

sX, sY:
    if A != B:
        => A, B  (circular strategy)
    if A == B:
        => A+1, A+1 (modified strategy)

sA, sB:
    if X != Y:
        => Y, X  (circular strategy)
    if X == Y:
        if Z == X:
            => X+1, X+1 (modified strategy)
        else:
            => X, X (special-case strategy)

sZ:
    => A

Rationale:
Let's take the subset pX, pY, pA, pB.
This subset is symmetrical, each row having the same information about the other row.
Success for the subset means success for the whole problem.

For the subset, we can classify the hat coloring into the following cases:
- Standard case where no colors within a row are the same.
- Single-degenerate case where both colors are the same within one of the two rows.
- Double-degenerate case where both colors are the same within both rows, but not between rows.
- Triple-degenerate case where all four colors are the same.

The standard case is solved using the circular strategy (the circle is pX => pA => pY => pB => pX).
The modified strategy is adopted in the case where a row observes a degenerate row.
This solves the single-degenerate and double-degenerate cases.

For the triple-degenerate case (A = X), pZ is needed.
sZ = A solves directly the case where all five colors are the same (Z = A = X).
For Z != A, the special-case strategy is needed for the other row.

"""

# Code to verify the solution

import itertools
hats = itertools.product(
    range(3),
    range(3),
    range(3),
    range(3),
    range(3),
)

def next_color(color, offset):
    return (color + offset) % 3

for config in hats:
    X, Y, Z, A, B = config

    # pX observes A, B
    if A != B:
        sX = A
    else:
        sX = next_color(A, 1)
    if sX == X:
        break

    # pY observes A, B
    if A != B:
        sY = B
    else:
        sY = next_color(A, 1)
    if sY == Y:
        break

    # pA observes X, Y, Z
    if X != Y:
        sA = Y
    else:
        if Z == X:
            sA = next_color(X, 1)
        else:
            sA = X
    if sA == A:
        break

    # pB observes X, Y, Z
    if X != Y:
        sB = X
    else:
        if Z == X:
            sB = next_color(X, 1)
        else:
            sB = X
    if sB == B:
        break

    # pZ observes A, B
    sZ = A
    if sZ == Z:
        break

    response = sX, sY, sZ, sA, sB
    raise Exception("""FAILURE:
configuration: {}
response:      {}
    """.format(config, response))