# Cmput 455 sample code
# Estimate number of states in a DAG for games such as TicTacToe or GoMoku.
# Ignores rules of the game, just counts how many ways there are to
# place stones on the board
# Written by Martin Mueller

import math

# Uses "Pascal's Triangle" to compute the choose(.,.) values
def computeChooseTable(n):
    def nextrow(row):
        prev = 0
        nr = []
        for x in row:
            nr.append(prev + x)
            prev = x
        nr.append(1)
        return nr

    row = [1]
    rows = []
    rows.append(row)
    for _ in range(n):
        row = nextrow(row)
        rows.append(row)
    return rows

# Access table entry, with error checking
def get(table, n, k):
    assert n>=0
    assert k>=0
    assert k <= n
    assert len(table) > n
    return table[n][k]
    
# Level by level number of positions in DAG
# n points total on the board, black moves first
def computeGameDAGSize(n):
    choose = computeChooseTable(n)
    # print(choose)
    positionsAtDepth = [0] * (n+1) # possible depths are 0,...,n
    for nuStones in range(n+1):
        white = nuStones // 2
        black = nuStones - white
        positionsAtDepth[nuStones] = get(choose, n, black) * get(choose, n-black, white)
        if nuStones > 0:
            print("Branching factor:", positionsAtDepth[nuStones] /
                                       positionsAtDepth[nuStones-1])
        print(positionsAtDepth[nuStones], "positions at depth ", nuStones)
    print("Total positions: ", sum(positionsAtDepth))
    print("Compare with factorial:", math.factorial(n))

print("Simplified 7x7 Go:")
computeGameDAGSize(49)