user3759953 user3759953 - 6 months ago 28
Python Question

Checking a series of binary states

I suppose the easiest way to explain this is to use the analogy of tictactoe.
A board of tictactoe can be expressed as a 2D array of binary states.

So the board # can be shown as [[1,2,3],[1,2,3],[1,2,3]]
And each index of this array has a binary value (X or O)
So to check if a polayer has won, you check if all 3 squares in a winning pattern share the same state.

Now, in this analogy you could hardcode the winning solutions and have the board checked against that independently, but in my circumstance I'd prefer not to hard code them as I need to (eventually) generate the arrays and the patterns during runtime. So currently I can just check manually or hardcode them but I need to find a way to check these patterns without hardcoded solutions.

Here's the smallest array I have currently to give an example:

[[[1,a], [2,a], [3,a]],
[[3,a], [1,a], [2,a]],
[[1,a], [2,a], [3,a]]]


Now 'a' is the blank state, which will be replaced with either a 'b' or 'c' (or any two designations) and 1, 2 & 3 designate 'lines'.

A visual way of showing this can be seen as:
Visual Description

See how the 'lines' cross over each other?
Well the patterns in this array are:


  • any 3 horizontally

  • any 3 on a single 'line' (not straight up and
    down)

  • and the specific patterns of row 1 line 1, r2l2, r3l3 & r1l3,
    r2l2, r3l1



In larger arrays there are more patterns but heres the simplest I can do.

Can anyone help me figure out a solution to to finding the patterns generated so I can check their states?
I'm testing this in python but I can also work with purely mathematical solutions

Answer

One way to do it is to scan the grid row by row and for every position keep track of track of pattern length in all possible directions. In this case directions would be top left -> down right, top right -> down left, left -> right and along the 'line'. When processing each position increment the value of previous patterns by one if state matches else set values to 0. Stop whenever the target length is found or grid has been completely iterated over.

Here's a short example of above where cells have binary state:

grid = [
    [[1, 0], [2, 0], [3, 1]],
    [[3, 1], [1, 0], [2, 0]],
    [[1, 0], [2, 0], [3, 1]]
]

def find(g, length):
    # Top left -> bottom right, top right -> bottom left
    # and left -> right lengths are stored here
    prev = [[0] * 3 for _ in xrange(len(g[0]))]
    # 'Line' length is stored here for efficiency
    prev_line = {}
    for row in grid:
        cur = []
        cur_line = {}
        for i in xrange(len(row)):
            tl = line = tr = left = 0
            if row[i][1] == 1:
                # Up left
                tl = 1 + (prev[i-1][0] if i else 0)
                # Line
                line = 1 + prev_line.get(row[i][0], 0)
                # Up right
                tr = 1 + (prev[i+1][1] if i < len(row) - 1 else 0)
                # Straight Left
                left = 1 + (cur[i-1][2] if i else 0)

            if any(x == length for x in (tl, line, tr, left)):
                return True
            cur.append([tl, tr, left])
            cur_line[row[i][0]] = line

        prev = cur
        prev_line = cur_line

    return False

find(grid, 3) # True