Given a grid of characters, generate valid phone numbers based on the specified parameters

phone_number_chess.py

# International prefixes is a vague statement. Does that mean '+'' is allowed? Not clarified so assuming not.

# Notes on possible improvements:
# - Can create an inheritable/extensible method structure to support any piece's
#   possible movements given a current position and a board instead of the current hard-coded methods

# The complexity of this solution depends on the size of the board
# and the length of the phone number being generated

def get_next_bishop_positions(x, y, x_lim, y_lim):
    direction_vectors = [(1,1), (1,-1), (-1,1), (-1,-1)]
    res = []
    
    for dir in direction_vectors:
        cur_x, cur_y = x, y
        while True:
            cur_x = cur_x + dir[0]
            cur_y = cur_y + dir[1]
            
            # Stop moving the piece if we moved off the board or hit the end
            if cur_x >= x_lim or cur_x < 0 or cur_y >= y_lim or cur_y < 0:
                break
            
            res.append((cur_x, cur_y)) 
    return res

def get_next_knight_positions(x, y, x_lim, y_lim):
    """ There is a maximum of eight legal positions for a knight to move """
    """ If there were more, it may have been worth working iteratively """
    position_deltas = [(1, 2), (2, 1),      # bottom right
                       (2, -1), (1, -2),    # bottom left
                       (-1, 2), (-2, 1),    # top right
                       (-1, -2), (-2, -1)]  # top left
    res = []
    
    for dir in position_deltas:
        cur_x, cur_y = x+dir[0], y+dir[1]
        
        if cur_x >= x_lim or cur_x < 0 or cur_y >= y_lim or cur_y < 0:
            continue
        
        res.append((cur_x, cur_y))
    return res

def is_valid_position(x, y):
    """ Check if the character in the position is a number or not """
    return is_number(board[x][y])

def is_number(char):
    try:
        val = int(char)
    except ValueError:
        return False
    return True

def get_next_chars(i, j, piece):
    global board
    if piece == "bishop":
        positions = get_next_bishop_positions(i, j, len(board), len(board[0]))
    elif piece == "knight":
        positions = get_next_knight_positions(i, j, len(board), len(board[0]))
    
    # Let's fetch the character and store it in a new tuple
    # Improvement: Could use something immutable here instead of creating new structures
    chars = [(board[pos[0]][pos[1]], pos[0], pos[1]) for pos in positions if is_valid_position(pos[0], pos[1])]
    return chars

def build_number(phone_num, i, j, piece):
    # Have we built a possible candidate phone number?
    if len(phone_num) == len_number:
        phone_nums.add(phone_num)
        return
    
    # What are the next possible characters to move to with this piece?
    next_chars = get_next_chars(i, j, piece)
    for char in next_chars:
        temp_phone_num = phone_num + char[0]
        build_number(temp_phone_num, char[1], char[2], piece)
    
def main():
    # Result variable
    global phone_nums
    phone_nums = set()
    
    # Let's read the necessary input from standard in
    piece = raw_input()
    if piece != "knight" and piece != "bishop":
        raise NotImplementedError('Invalid piece specified')
    
    global len_number
    len_number = raw_input()
    if not is_number(len_number):
        raise Exception('Length of number must be a number')
    len_number = int(len_number)
        
    row = raw_input()
    valid_start_digits = row.split()
    
    row_len = raw_input()
    col_len = raw_input()
    
    if not is_number(row_len) or not is_number(col_len):
        raise Exception('Row/column dimensions must be a number')
    row_len = int(row_len)
    col_len = int(col_len)
    
    global board
    
    for i in xrange(0, row_len):
        inp = raw_input()
        row = inp.split()
        board.append(row)
        
    # Find the starting position legal characters by brute-force looping through the array
    for i in xrange(0, row_len):
        for j in xrange(0, col_len):
            if board[i][j] in valid_start_digits:
                build_number(board[i][j], i, j, piece)
    # Make a recursive call starting with the empty string and let it multiplicatively expand to keep adding more
    # Give current position, string so far and the piece we are moving with, size of the board and the actual board
    # When it hits the base case, add the result to a global set
    # Return the count of the size of the list
    print len(phone_nums)
    
phone_nums = None
len_number = None
board = []
main()