Regular Tic-Tac-Toe is boring.

That's why in this Kata you will be playing  Tic-Tac-Toe in **3D** using a 4 x 4 x 4 matrix!



# Kata Task

Play the game. Work out who wins.

Return a string

* `O wins after  moves`
* `X wins after  moves`
* `No winner`

# Rules

* Player `O` always goes first
* Input `moves` is list/array/tuple of `[x,y,z]` (zero based)
* Each player takes a turn until you find a winner, or there are no moves left
* Four of the same symbols in a row wins
* There may be more moves provided than are necessary to finish the game - that is for you to figure out



Good Luck!
DM

Difficulty: introductory

Starter code:

def play_OX_3D(moves):
	

Solutions:
from itertools import product

def winning_lines(size, dimension):
    if dimension == 1: return frozenset({frozenset({(n,) for n in range(size)})})
    lines = set()
    for line, idx, val in product(winning_lines(size, dimension - 1), range(dimension), range(size)):
        lines.add(frozenset({cell[:idx] + (val,) + cell[idx:] for cell in line}))
    for dirs in product((-1, 1), repeat=dimension - 1):
        lines.add(frozenset(zip(*(range(size)[::d] for d in [1] + list(dirs)))))
    return lines

def play_OX_3D(moves):
    grid, lines = [], winning_lines(4, 3)
    for m in moves:
        grid.append(tuple(m))
        if any(line <= set(grid[-1::-2]) for line in lines):
            return '{} wins after {} moves'.format('XO'[len(grid) % 2], len(grid))
    return 'No winner'

def checker(board, i, j, k, turn):
          
        return all(n == turn for n in board[i][j])                           or \
               all(n == turn for n in [m[k] for m in board[i]])              or \
               all(board[i][n][n] == turn for n in range(4))                 or \
               all(board[i][n][3 - n] == turn for n in range(4))             or \
               all(bn[j][k] == turn for bn in board)                         or \
               all(board[n][n][n] == turn for n in range(4))                 or \
               all(board[n][n][3 - n] == turn for n in range(4))             or \
               all(board[n][3 - n][3 - n] == turn for n in range(4))         or \
               all(board[n][3 - n][n] == turn for n in range(4))             or \
               all(board[n][3 - n][k] == turn for n in range(4))             or \
               all(board[n][n][k] == turn for n in range(4))                 or \
               all(board[n][j][n] == turn for n in range(4))                 or \
               all(board[n][j][3 - n] == turn for n in range(4))
    
def play_OX_3D(moves):
    board = [[[' ' for _ in range(4)] for _ in range(4)] for _ in range(4)]
    turn = 'O'

    for ind, (i, j, k) in enumerate(moves, 1):
        board[i][j][k] = turn
    
        if checker(board, i, j, k, turn):
            return f'{turn} wins after {ind} moves'
  
        turn = 'OX'[turn == 'O']
        
    return 'No winner'

def play_OX_3D(moves):
    d = [], []
    for n, (x, y, z) in enumerate(moves, 1):
        c = d[n%2]
        c += zip(range(13),(x,x,y,x,x,y,y,z,z,x+y,y+x,z+x,x-y),(y,z,z,y+z,y-z,x+z,x-z,x+y,x-y,x+z,y+z,z+y,y-z))
        if 4 in map(c.count, c):
            return 'XO'[n%2] + ' wins after %d moves' % n
    return 'No winner'


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


def is_won(moves):
    for line in lines:
        if all(x in moves for x in line):
            return True
    return False


def play_OX_3D(moves):
    idx = -1
    players = [{'name': 'O', 'moves': []}, {'name': 'X', 'moves': []}]
    for i, mov in enumerate(moves):
        idx = (idx+1) % 2
        player = players[idx]
        player['moves'].append(list(mov))
        if is_won(player['moves']):
            return f'{player["name"]} wins after {i+1} moves'
    return "No winner"

def find_winner(grid):
    for x in range(4):
        for y in range(4):
            if grid[x][y][0] and len({grid[x][y][i] for i in range(4)}) == 1:
                return grid[x][y][0]
            if grid[0][x][y] and len({grid[i][x][y] for i in range(4)}) == 1:
                return grid[0][x][y]
            if grid[x][0][y] and len({grid[x][i][y] for i in range(4)}) == 1:
                return grid[x][0][y]
            if x == 0 and grid[0][y][0] and len({grid[i][y][i] for i in range(4)}) == 1:
                return grid[0][y][0]
            if x == 3 and grid[3][y][0] and len({grid[3-i][y][i] for i in range(4)}) == 1:
                return grid[3][y][0]
            if y == 0 and grid[x][0][0] and len({grid[x][i][i] for i in range(4)}) == 1:
                return grid[x][0][0]
            if y == 3 and grid[x][3][0] and len({grid[x][3-i][i] for i in range(4)}) == 1:
                return grid[x][3][0]
    for z in range(4):
        if grid[0][0][z] and len({grid[i][i][z] for i in range(4)}) == 1:
            return grid[0][0][z]
        if grid[3][0][z] and len({grid[3-i][i][z] for i in range(4)}) == 1:
            return grid[3][0][z]
    if grid[0][0][0] and len({grid[i][i][i] for i in range(4)}) == 1:
        return grid[0][0][0]
    if grid[0][3][0] and len({grid[i][3-i][i] for i in range(4)}) == 1:
        return grid[0][3][0]
    if grid[0][0][3] and len({grid[i][i][3-i] for i in range(4)}) == 1:
        return grid[0][0][3]
    if grid[0][3][3] and len({grid[i][3-i][3-i] for i in range(4)}) == 1:
        return grid[0][3][3]
            

def play_OX_3D(moves):
    grid = [[[None for _ in range(4)] for _ in range(4)] for _ in range(4)]
    
    players = ['O', 'X']
    
    for i, (x, y, z) in enumerate(moves):
        player = players[i%len(players)]
        grid[x][y][z] = player
        winner = find_winner(grid)
        
        if winner:
            return f'{player} wins after {i+1} moves'
    
    return 'No winner'


def check_victory(board):
    size = len(board)
    
    depth_sums = [[0] * size for i in range(size)]
    down_cross_sums = [[0,0] for i in range(size)]
    side_cross_sums = [[0,0,0,0] for i in range(2)]
    diag_sums = [
        [0,0],
        [0,0]
    ]

    for z in range(0, size):
        col_sums = [0] * size
        front_cross_sums = [0,0]
        
        for y in range(0, size):
            row_sum = 0
            
            for x in range(0, size):
                val = board[z][y][x]
            
                row_sum += val
                col_sums[x] += val
                depth_sums[y][x] += val
                
                if (x == y):
                    front_cross_sums[0] += val
                    if (y == z):
                        diag_sums[0][0] += val
                    if ((y + z) == (size - 1)):
                        diag_sums[1][0] += val
                
                if (x == z):
                    down_cross_sums[y][0] += val
                if ((x + z) == (size - 1)):
                    down_cross_sums[y][1] += val
                    
                if (y == z):
                    side_cross_sums[0][x] += val
                if ((y + z) == (size - 1)):
                    side_cross_sums[1][x] += val
                
                if ((x + y) == (size - 1)):
                    front_cross_sums[1] += val
                    if (y == z):
                        diag_sums[0][1] += val
                    if ((y + z) == (size - 1)):
                        diag_sums[1][1] += val

                if (row_sum == size
                    or col_sums[x] == size
                    or front_cross_sums[0] == size
                    or front_cross_sums[1] == size
                    or depth_sums[y][x] == size
                    or down_cross_sums[y][0] == size
                    or down_cross_sums[y][1] == size
                    or side_cross_sums[0][x] == size
                    or side_cross_sums[1][x] == size
                    or diag_sums[0][0] == size
                    or diag_sums[0][1] == size
                    or diag_sums[1][0] == size
                    or diag_sums[1][1] == size
                    ):
                    return 1
                
                if (row_sum == -size
                    or col_sums[x] == -size
                    or front_cross_sums[0] == -size
                    or front_cross_sums[1] == -size
                    or depth_sums[y][x] == -size
                    or down_cross_sums[y][0] == -size
                    or down_cross_sums[y][1] == -size
                    or side_cross_sums[0][x] == -size
                    or side_cross_sums[1][x] == -size
                    or diag_sums[0][0] == -size
                    or diag_sums[0][1] == -size
                    or diag_sums[1][0] == -size
                    or diag_sums[1][1] == -size
                    ):
                    return -1
    
    return 0


def play_OX_3D(moves):
    board = [
        [
            [0,0,0,0],
            [0,0,0,0],
            [0,0,0,0],
            [0,0,0,0]
        ],
        [
            [0,0,0,0],
            [0,0,0,0],
            [0,0,0,0],
            [0,0,0,0]
        ],
        [
            [0,0,0,0],
            [0,0,0,0],
            [0,0,0,0],
            [0,0,0,0]
        ],
        [
            [0,0,0,0],
            [0,0,0,0],
            [0,0,0,0],
            [0,0,0,0]
        ],
    ]
    
    move_cnt = 0
    play_num = 1
    
    for move in moves:
        board[move[2]][move[1]][move[0]] = play_num
        move_cnt += 1
        
        victor = check_victory(board)
        if (victor >= 1):
            print(moves)
            return "O wins after " + str(move_cnt) + " moves"
        if (victor <= -1):
            print(moves)
            return "X wins after " + str(move_cnt) + " moves"
        play_num *= -1
    
    print(moves)
    return "No winner"


def print_board(board):
    for x in board:
        for y in x:
            for z in y:
                print(z,end=' ')
            print()
        print()

def check_if_win(board, x, y, z):
    diags = [
    [(0,0,0), (1,1,1), (2,2,2), (3,3,3)],
    [(0,0,3), (1,1,2), (2,2,1), (3,3,0)],
    [(0,3,0), (1,2,1), (2,1,2), (3,0,3)],
    [(0,3,3), (1,2,2), (2,1,1), (3,0,0)],
    
    [(0,0,0), (0,1,1), (0,2,2), (0,3,3)],
    [(0,0,3), (0,1,2), (0,2,1), (0,3,0)],
    [(1,0,0), (1,1,1), (1,2,2), (1,3,3)],
    [(1,0,3), (1,1,2), (1,2,1), (1,3,0)],
    [(2,0,0), (2,1,1), (2,2,2), (2,3,3)],
    [(2,0,3), (2,1,2), (2,2,1), (2,3,0)],
    [(3,0,0), (3,1,1), (3,2,2), (3,3,3)],
    [(3,0,3), (3,1,2), (3,2,1), (3,3,0)]
    ]
    
    for diag in diags:
        if (x,y,z) in diag:
            d = []
            for i,j,k in diag:
                d.append(board[i][j][k])
            if diag[0] != '_' and are_the_same(d): return True
    
    hold_xy = []
    hold_yz = []
    hold_xz = []
    
    for i in range(4):
        hold_xy.append(board[x][y][i])
        hold_yz.append(board[i][y][z])
        hold_xz.append(board[x][i][z])
    
    if hold_xy[0] != '_' and are_the_same(hold_xy): return True
    if hold_yz[0] != '_' and are_the_same(hold_yz): return True
    if hold_xz[0] != '_' and are_the_same(hold_xz): return True
    
    return False

def are_the_same(array):
    first = array[0]
    for c in array[1:]:
        if first != c: return False
    return True

def play_OX_3D(moves):
    P=({},{})
    for counter,(x,y,z) in enumerate(moves,1):
        A=(x,x,y,x  ,x  ,y  ,y  ,z  ,z  ,x+y,y+x,z+x,x-y)
        B=(y,z,z,y+z,y-z,x+z,x-z,x+y,x-y,x+z,y+z,z+y,y-z)
        C=P[counter%2]
        for x in zip(range(13),A,B):C[x]=C.get(x,0)+1
        if 4 in C.values():return'XO'[counter%2]+' wins after %d moves'%counter
    return'No winner'
    
def play_OX_3DS(moves):
    turn = 'O'
    counter = 0
    board = [[['_' for k in range(4)] for j in range(4)] for i in range(4)]
    
    for move in moves:
        x,y,z = move
        board[x][y][z] = turn
        counter += 1
        
        if check_if_win(board, x, y, z):
            return f'{turn} wins after {counter} moves'
            
        if turn == 'O':
            turn = 'X'
        else:
            turn = 'O'
            
        print_board(board)
        print(counter)
    
    return 'No winner'

from itertools import chain

ORTHO = lambda move, i: lambda c: c[i] == move[i] and c[(i+1)%3] == move[(i+1)%3]
DIAG = lambda move, i, s: lambda c: c[i] == (c[(i+1)%3] if s else 3-c[(i+1)%3]) and c[(i+2)%3] == move[(i+2)%3]
CORN = lambda i: lambda c: c[i%3] == c[(i+1)%3] == (3 - c[(i+2)%3] if i else c[(i+2)%3])

def play_OX_3D(moves):
    p = 0
    board = (set(), set())
    for move in moves:
      board[p].add(tuple(move))
      if any(chain(
        (len(list(filter(ORTHO(move, i), board[p]))) == 4 for i in range(3)),
        (len(list(filter(DIAG(move, i, s), board[p]))) == 4 for i in range(3) for s in (0,1)),
        (len(list(filter(CORN(i), board[p]))) == 4 for i in range(3))
        )):
        return '{} wins after {} moves'.format(['O','X'][p], sum(map(len,board)))
      p = 1 - p
    return 'No winner'