#!/usr/bin/python3
"""How many tiles do you need to have a complete set?

I mean, like, Wang tiles, with colors on both the edges and corners,
if reflections and rotations are generated automatically, and you want
to ensure you always have a piece to fill any possible blank hole.

It seems like the answer is 43; the equivalence classes vary widely in
size:

    00: 00
    01: 01 02 04 08 10 20 40 80
    03: 03 0c 30 c0
    05: 05 0a 14 28 41 50 82 a0
    06: 06 18 60 81
    07: 07 0e 1c 38 70 83 c1 e0
    09: 09 24 42 90
    0b: 0b 0d 2c 34 43 b0 c2 d0
    0f: 0f 3c c3 f0
    11: 11 22 44 88
    12: 12 21 48 84
    13: 13 23 31 32 4c 8c c4 c8
    15: 15 2a 45 51 54 8a a2 a8
    16: 16 1a 58 61 68 85 86 a1
    17: 17 3a 5c 71 8e a3 c5 e8
    19: 19 26 46 62 64 89 91 98
    1b: 1b 36 63 6c 8d b1 c6 d8
    1d: 1d 2e 47 74 8b b8 d1 e2
    1e: 1e 78 87 e1
    1f: 1f 3e 7c 8f c7 e3 f1 f8
    25: 25 29 49 4a 52 92 94 a4
    27: 27 39 4e 72 93 9c c9 e4
    2b: 2b 35 4d 53 ac b2 ca d4
    2d: 2d 4b b4 d2
    2f: 2f 3d 4f bc cb d3 f2 f4
    33: 33 cc
    37: 37 3b 73 b3 cd ce dc ec
    3f: 3f cf f3 fc
    55: 55 aa
    56: 56 59 65 6a 95 9a a6 a9
    57: 57 5d 75 ab ae ba d5 ea
    5a: 5a 69 96 a5
    5b: 5b 6b 6d ad b5 b6 d6 da
    5e: 5e 79 7a 97 9e a7 e5 e9
    5f: 5f 7d af be d7 eb f5 fa
    66: 66 99
    67: 67 6e 76 9b 9d b9 d9 e6
    6f: 6f bd db f6
    77: 77 bb dd ee
    7b: 7b b7 de ed
    7e: 7e 9f e7 f9
    7f: 7f bf df ef f7 fb fd fe
    ff: ff

But I’m not confident that computation is correct.

"""

def bit_reverse(n, k=8, m=0):
    """Reverse the last k bits of n, prepending m."""
    if k == 0:
        return m
    return bit_reverse(n >> 1, k-1, (m << 1) | (n & 1))

assert bit_reverse(3, 4) == 12
assert bit_reverse(5, 4) == 10
assert bit_reverse(1, 8) == 128

def rotate_right(n, k=8):
    """Rotate n right by 1 bit, treating it as a k-bit number."""
    return (n >> 1) | ((n & 1) << (k-1))

assert rotate_right(3, 4) == 9
assert rotate_right(5, 4) == 10
assert rotate_right(1, 8) == 128

def classes(k=8):
    result = {}
    for n in range(2**k):
        # What’s the lowest number we can get from n by reversals and
        # even rotations?
        best = m = n
        for i in range(k):
            m = rotate_right(m, k)
            m = rotate_right(m, k)
            best = min(m, best)

        m = bit_reverse(n, k)
        for i in range(k):
            m = rotate_right(m, k)
            m = rotate_right(m, k)
            best = min(m, best)

        if best not in result:
            result[best] = []
        result[best].append(n)

    return result

if __name__ == '__main__':
    result = classes()
    for i in sorted(result):
        print(f'{i:02x}: {" ".join("{:02x}".format(n) for n in result[i])}')