taijy.py

taijy.py

import collections
import functools

# TODO(adaboville): represent grids using an immutable grid class with those
# methods:
# * get_n()
# * transpose()
# * replace(i, j, e)


def check_number_of_zeros(row, n):
    return row.count(0) == (n // 2)


def check_contiguous(row):
    # this method only works with even-sized rows (which isn't an issue since
    # according to the rules all rows have to have an even number of elements)
    deque = collections.deque(row[:2], 3)

    for e in row[2:]:
        deque.append(e)

        if len(set(deque)) == 1:
            # 3 contiguous elements in a row
            return False

    return True


def row_for_i(i, n):
    i_padded_in_base_2 = bin(i).lstrip('0b').rjust(n, '0')
    return tuple(0 if c == '0' else 1 for c in i_padded_in_base_2)


def gen_rows(n):
    for i in range(2 ** n):
        yield row_for_i(i, n)


@functools.lru_cache(5)
def gen_valid_rows(n):
    return set(row for row in gen_rows(n)
               if check_number_of_zeros(row, n) and check_contiguous(row))


def transpose(grid):
    return list(zip(*grid))


def has_dupe_full_rows(grid):
    full_rows = [row for row in grid if not row.count(None)]
    return len(full_rows) != len(set(full_rows))


def solved(grid):
    n = len(grid)
    valid_rows = gen_valid_rows(n)
    transposed = transpose(grid)

    return (all(row in valid_rows for row in grid) and
            all(row in valid_rows for row in transposed) and
            not has_dupe_full_rows(grid) and
            not has_dupe_full_rows(transposed))


def match(row, full_row):
    return all(a is None or a == b for a, b in zip(row, full_row))


def improve_if_single_match(row):
    n = len(row)
    valid_rows = gen_valid_rows(n)
    matches = [valid for valid in valid_rows if match(row, valid)]
    return matches[0] if len(matches) == 1 else row


def fill_rows(grid):
    return [improve_if_single_match(row) for row in grid]


def fill_according_to_valid_rows(grid):
    grid = fill_rows(grid)
    return transpose(fill_rows(transpose(grid)))


def find_first_missing(grid):
    # this could be sped up by keeping track of the last guess since we know
    # that there isn't any None before the last guess
    for i, row in enumerate(grid):
        for j, e in enumerate(row):
            if e is None:
                return i, j

    return None


def replace(grid, i, j, choice):
    copied_grid = list(grid)  # shallow copy, since tuples are immutable
    copied_grid[i] = tuple(e if jj != j else choice for jj, e in
                           enumerate(grid[i]))
    return copied_grid


def looks_valid(grid):
    n = len(grid)
    valid_rows = gen_valid_rows(n)
    transposed = transpose(grid)

    return (any(match(row, valid_row)
                for row in grid
                for valid_row in valid_rows)
            and
            any(match(row, valid_row)
                for row in transposed
                for valid_row in valid_rows)
            and
            not has_dupe_full_rows(grid)
            and
            not has_dupe_full_rows(transposed))


def solve(grid):
    assert grid is not None
    n = len(grid)
    assert n % 2 == 0
    assert all(len(row) == n for row in grid)

    if not looks_valid(grid):
        return None

    improved = fill_according_to_valid_rows(grid)
    while improved != grid:
        grid = improved
        improved = fill_according_to_valid_rows(grid)

    if solved(grid):
        return grid

    missing = find_first_missing(grid)

    if missing is None:
        return None  # grid not solvable

    i, j = missing

    for choice in (0, 1):
        guessed_grid = replace(grid, i, j, choice)
        result = solve(guessed_grid)

        if result is not None:
            return result

    # grid not solvable
    return None


if __name__ == '__main__':
    import pprint

    grid = [(None, 0, None, 1, None, 0, 0, None),
            (None, 0, 0, None, None, None, None, 0),
            (0, None, None, None, None, None, None, None),
            (None, None, 0, 1, 0, None, None, None),
            (None, 0, None, 0, None, None, 0, None),
            (None, None, None, 0, None, 0, 1, None),
            (1, 0, None, None, 0, 1, None, None),
            (0, None, None, 0, None, None, 0, None)]

    # grid = [(1, None, 1, 1, None, 1, None, 0),
    #         (None, None, 1, None, None, None, None, None),
    #         (0, None, None, None, None, None, None, 0),
    #         (0, None, 0, None, None, 1, 1, None),
    #         (1, None, None, None, 0, None, None, 1),
    #         (None, None, None, None, 1, None, None, None),
    #         (None, 0, 1, 1, 0, 1, None, None),
    #         (None, 1, None, 0, None, None, 0, None)]

    pprint.pprint(solve(grid))