15 puzzle for wix interview process

15puzzle.py

#! /usr/bin/python
import argparse
from random import randrange, randint, shuffle 
from prettytable import PrettyTable
import os


EMPTY_VALUE = " "


####### board #######

def initBoard(N, shuffle_board=False, safe=False):
    board_list = range(1,N*N)
    board_list.append(EMPTY_VALUE)
    if shuffle_board:
        shuffle(board_list)
    
    puzzle_board = listToBoard(board_list, N)
    if safe:
        while not isSolvable(puzzle_board):
            shuffle(board_list)
            puzzle_board = listToBoard(board_list, N)

    return puzzle_board


def isSolved(puzzle_board):
    board_list = boardToList(puzzle_board)

    if board_list[0] != 1 or board_list[-1] != EMPTY_VALUE:
        return False

    for tile_index in range(1, len(board_list)-1):
        if board_list[tile_index] - board_list[tile_index-1] != 1:
            return False

    return True


def isSolvable(puzzle_board):
    N = len(puzzle_board)
    inversion_count = countInversions(puzzle_board)
    if N % 2 == 1: # odd N
        return (inversion_count % 2 == 0)
    else: #even N
        blank_row_index, _ = findValueCoords(puzzle_board, EMPTY_VALUE)
        black_idx_from_bottom = (N - blank_row_index)
        return (((inversion_count % 2 == 0) and (black_idx_from_bottom % 2 == 1)) or
                ((inversion_count % 2 == 1) and (black_idx_from_bottom % 2 == 0)))


def findValueCoords(puzzle_board, value):
    for i, row in enumerate(puzzle_board):
        for j, tile in enumerate(row):
            if tile == value:
                return i, j
    return None, None


def countInversions(puzzle_board):
    board_list = boardToList(puzzle_board)
    inversion_count = 0
    # there is probably a more efficient way of doing this (guessing nlogn)
    #  but for readabuility sake this would due
    for i, x in enumerate(board_list):
        if x == EMPTY_VALUE:
            continue
        for j in range(i):
            y = board_list[j]
            if  y != EMPTY_VALUE and y > x:
                inversion_count = inversion_count + 1
    return inversion_count


def boardToList(puzzle_board):
    board_list = []
    for row in puzzle_board:
        board_list.extend(row)
    return board_list


def listToBoard(board_list, N):
    return [board_list[i:i+N] for i in range(0, len(board_list), N)]



####### movement ##########

def moveTileValue(puzzle_board, value, empty_coords=None):

    empty_ri, empty_ti = empty_coords or findValueCoords(puzzle_board, EMPTY_VALUE)
    if puzzle_board[empty_ri][empty_ti] == EMPTY_VALUE:
        ri, ti = findTileCoordsAround(puzzle_board, value, empty_ri, empty_ti)
        if ri is not None:
            puzzle_board[empty_ri][empty_ti] = value
            puzzle_board[ri][ti] = EMPTY_VALUE
            return puzzle_board, (ri, ti)


def findTileCoordsAround(puzzle_board, value, empty_ri, empty_ti):
    N = len(puzzle_board)
    valid_index_pairs = [
        (max(0, empty_ri-1), empty_ti),   # up
        (empty_ri, max(0, empty_ti-1)),   # left
        (min(N-1, empty_ri+1), empty_ti), # down
        (empty_ri, min(N-1, empty_ti+1)), # right
    ]

    for index_pair in valid_index_pairs:
        if puzzle_board[index_pair[0]][index_pair[1]] == value:
            return index_pair
    return None, None


###### UI ########

def printState(puzzle_board):
    printable = PrettyTable(header=False)
    for row in puzzle_board:
        printable.add_row(row)
    print(printable)


def printUI(puzzle_board, N):
    while True:
        os.system('clear')
        printState(puzzle_board)
        if isSolved(puzzle_board):
            print("SOLVED!")
        if not isSolvable(puzzle_board):
            print("UNSOLVEABLE!")
        print("Which tile whould you like to move? (0 to exit)")

        try:
            choice = raw_input(" >>  ")
        except (EOFError, KeyboardInterrupt):
            return None

        try:
            c = int(choice)
            if not (-1 < c < N*N): 
                raise ValueError
            if c == 0:
                return None
            
        except ValueError:
            return puzzle_board

        puzzle_board, new_empty_coords= moveTileValue(puzzle_board, c)
        return puzzle_board



################## MAIN ####################

if __name__ == "__main__":
    parser = argparse.ArgumentParser(description='Puzzle ex for Wix')
    parser.add_argument(dest='n', type=int, default=4,
        help='The N size for the board')
    parser.add_argument('--shuffle', dest='shuffle', 
        action='store_true', default=False, 
        help='Suffle the board on initialization')
    parser.add_argument('--safe', dest='safe', 
        action='store_true', default=False,
        help='Initialize into a solvable board')

    args = parser.parse_args()
    
    print("N size:<%s>" % args.n)
    print("shuffle:<%s>" % args.shuffle)
    print("safe:<%s>" % args.safe)

    puzzle_board = initBoard(args.n, args.shuffle, args. safe)
    while puzzle_board is not None:
        puzzle_board = printUI(puzzle_board, args.n)