Solving a math puzzle with Python’s generator expressions

Recently James Grime of numberphile-fame posted a puzzle on YouTube. The video is right here but the question is (if you don’t care to watch): „How many ways are there to completely fill a Noughts and Crosses (tic-tac-toe) board, with four noughts and five crosses? Not including rotations and reflections.“

So I am not much of a mathematician and I also did not really care for fopping about much so I wrote a small program in python to find the solution. And I took the chance to make a post about generator expressions in python as well.

A generator expression can take two general forms:

def gen(count):
  c = 10
  while c > 0:
    yield c
    c = c - 1

Here the yield keyword is what it’s all about. This will generate an iterable object that returns the yielded items. The cool thing is, that computation of this method is suspended until the next item is needed.

If you already have an iterable you can create a new generator expression from it:

g = (x for x in gen(10))

Here you can filter or map the value of x as you will see. And again, this is only a generator. No computation happens unless you actually want to print any values or you manifest them into a list.

you will find the source code of my solution below the fold

"""
How many ways are there to completely fill a Noughts and Crosses (tic-tac-toe)
board, with four noughts and five crosses? Not including rotations and reflections.
"""

# nought = 0
# cross = 1

import numpy

def combinations():
    # build first permutation
    latest = numpy.array(list(0 for _ in range(9)))
    while not latest.all():
        latest = numpy.array(latest)
        latest[8] = latest[8] + 1
        for i in reversed(range(1,9)):
            if latest[i] == 2:
                latest[i] = 0
                latest[i-1] = latest[i-1] + 1
        yield latest

#to arrays
combinations2D = (numpy.matrix(c) for c in combinations())
# reshape them and filter false combinations
combinations2D = (c.reshape((3,3)) for c in combinations2D if c.sum() == 5)

uniqueCombinations = []

for c in combinations2D:

    #create mirrored and rotated views
    cMirrors = [
        numpy.fliplr(c),
        numpy.rot90(c, 1),
        numpy.rot90(c, 2),
        numpy.rot90(c, 3),
        numpy.rot90(numpy.fliplr(c), 1),
        numpy.rot90(numpy.fliplr(c), 2),
        numpy.rot90(numpy.fliplr(c), 3)
    ]

    for mirror in cMirrors:
        for i in reversed(range(len(uniqueCombinations))):
            if numpy.array_equal(uniqueCombinations[i], mirror):
                uniqueCombinations.pop(i)
    uniqueCombinations.append(c)

print len(uniqueCombinations)
for c in uniqueCombinations:
    print 20*'-'
    print c

Nothing but the uniqueCombinations will ever make it into memory. Every generator inbetween is consumed.

And there we have it. 23 unique combinations:

23
——————–
[[0 1 0] [1 1 1] [0 1 0]] ——————–
[[1 0 1] [0 1 0] [1 0 1]] ——————–
[[1 1 0] [0 0 1] [1 0 1]] ——————–
[[1 1 0] [0 0 1] [1 1 0]] ——————–
[[1 1 0] [0 1 0] [0 1 1]] ——————–
[[1 1 0] [0 1 0] [1 0 1]] ——————–
[[1 1 0] [0 1 0] [1 1 0]] ——————–
[[1 1 0] [0 1 1] [0 0 1]] ——————–
[[1 1 0] [0 1 1] [0 1 0]] ——————–
[[1 1 0] [0 1 1] [1 0 0]] ——————–
[[1 1 0] [1 0 1] [0 0 1]] ——————–
[[1 1 0] [1 0 1] [0 1 0]] ——————–
[[1 1 0] [1 1 0] [0 0 1]] ——————–
[[1 1 0] [1 1 1] [0 0 0]] ——————–
[[1 1 1] [0 0 0] [1 0 1]] ——————–
[[1 1 1] [0 0 0] [1 1 0]] ——————–
[[1 1 1] [0 1 0] [0 1 0]] ——————–
[[1 1 1] [0 1 0] [1 0 0]] ——————–
[[1 1 1] [1 0 0] [0 0 1]] ——————–
[[1 1 1] [1 0 0] [0 1 0]] ——————–
[[1 1 1] [1 0 0] [1 0 0]] ——————–
[[1 1 1] [1 0 1] [0 0 0]] ——————–
[[1 1 1] [1 1 0] [0 0 0]]

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.