shut up and code

[suac-blog]

Facebook Hacker Cup: Chess 2

This problem appeared in round 1, sub-round 2:

After decades of shadowy demonstrations and delays from the game’s maker, Chess 2 has finally been released. You waited in line all night to be one of the first to purchase an example of the hot sequel to the classic original, and now you are finally getting a chance to open up your new investment and take a look inside. What you find is slightly puzzling; in addition to the traditional pieces, the game has been expanded to contain a number of pieces that are not actually original. The best-known piece that has been added to the game is the nightrider. The nightrider can make any number of knight moves in a single direction, i.e., its offset from its initial position will be 2*m in one dimension and m in the other for some nonzero integer m. Like other "sliding" pieces, if one of the knight moves would cause it to take another piece it is not able to traverse beyond that point The archbishop is also part of Chess 2. The archbishop can simply make any move that a knight or bishop could legally make. The strangest new piece is the kraken. The kraken can move to any square on the board, regardless of the position of any other pieces, including its own current position. You don't feel like reading the manual to learn about how the new pieces fit into the standard chess opening positions, so instead you place some of the pieces randomly on the board. The game you’ve decided to play is simply to count how many pieces on the board are currently being threatened. A piece is threatened if another piece is able to move into its cell and take it (note that if the kraken moves into its own cell it does not take itself).

Input

Your input file will consist of a single integer N followed by N test cases. Each case will consist of, all separated by whitespace, an integerP followed by the identities and positions of P Chess 2 pieces. Pieces are described by a single character C to denote their type (see specification below) followed by two integers R and F, the 1-based rank and file, respectively, of the piece. You've decided to ignore the colors of the pieces in this game. The color of the pieces will not be reflected in the input and so cannot affect your output.  To make room for the new pieces, the Chess 2 board is a 16 by 16 grid. No specified pieces will fall outside the board, and no two pieces will occupy the same position. The types of pieces will be specified as follows, and no entries not present in this table will appear on the board:

Output

Output a single integer, the number of threatened pieces on the board, for each test case separated by whitespace.

Constraints

N = 20 3 <= P <= 64 1 <= R, F <= 16 C will be one of K, Q, R, B, N, S, A or E

I failed on the actual input because I didn't account for the fact that the contest input would be formatted slightly differently. I depended too heavily on list manipulation and couldn't 'fix' the input file fast enough to get my answer in on time.

It looks like everything is chess around here at the moment, and here's another solution. I've decided to post it up sans edits to show what sort of panicky foolishness a person can crank out in 3 hours.

import itertools def build_board(pieces): board = [] for rows in range(16): board.append([]) for row in board: for i in range(16): row.append('0') pieces = [piece for piece in pieces if piece != ''] while pieces: curr_piece = pieces[:3] pieces = pieces[3:] piece, piece_rank, piece_file = tuple(curr_piece) piece_rank = int(piece_rank) piece_file = int(piece_file) board[piece_rank - 1][piece_file - 1] = piece return board def king_threat(x, y, board, threat_list): horiz_min = x - 1 if x > 0 else x horiz_max = x + 1 if x < 16 else x vert_min = y - 1 if y > 0 else y vert_max = y + 1 if y < 16 else y for i in range(horiz_min, horiz_max, 1): for j in range(vert_min, vert_max, 1): if board[i][j] != '0' and i != x and j != y: threat_list.add(str(i) + str(j) + board[i][j]) return threat_list def queen_threat(x, y, board, threat_list): """docstring for queen_threat""" rook_list = rook_threat(x, y, board, threat_list) bishop_list = bishop_threat(x, y, board, threat_list) if rook_list: threat_list.union(rook_list) if bishop_list: threat_list.union(bishop_list) return threat_list pass def rook_threat(x, y, board, threat_list): """docstring for rook_threat""" for i in range(x, -1, -1): if board[i][y] != '0' and i != x: threat_list.add(str(i) + str(y) + board[i][y]) break for i in range(x, 16, 1): if board[i][y] != '0' and i != x: threat_list.add(str(i) + str(y) + board[i][y]) break for j in range(y, -1, -1): if board[x][j] != '0' and j != x: threat_list.add(str(x) + str(j) + board[x][j]) break for j in range(y, 16, 1): if board[x][j] != '0' and j != x: threat_list.add(str(x) + str(j) + board[x][j]) break return threat_list pass def bishop_threat(x, y, board, threat_list): """docstring for bishop_threat""" horz_lt = range(x, -1, -1) vert_lt = range(y, -1, -1) horz_gt = range(x, 16, 1) vert_gt = range(y, 16, 1) up_left = zip(horz_lt, vert_lt) up_right = zip(horz_gt, vert_lt) down_left = zip(horz_lt, vert_gt) down_right = zip(horz_gt, vert_gt) for move in up_left: if board[move[0]][move[1]] != '0' and move[0] != x and move[1] != y: threat_list.add(str(move[0]) + str(move[1]) + board[move[0]][move[1]]) break for move in up_right: if board[move[0]][move[1]] != '0' and move[0] != x and move[1] != y: threat_list.add(str(move[0]) + str(move[1]) + board[move[0]][move[1]]) break for move in down_left: if board[move[0]][move[1]] != '0' and move[0] != x and move[1] != y: threat_list.add(str(move[0]) + str(move[1]) + board[move[0]][move[1]]) break for move in down_right: if board[move[0]][move[1]] != '0' and move[0] != x and move[1] != y: threat_list.add(str(move[0]) + str(move[1]) + board[move[0]][move[1]]) break return threat_list pass def knight_threat(x, y, board, threat_list): """docstring for knight_threat""" moves_list = [] moves = [-1, -2, 1, 2] moves_list = [i for i in itertools.product(moves,moves)] moves_list = [i for i in moves_list if (x + i[0] > 0)] moves_list = [i for i in moves_list if (x + i[0] < 16)] moves_list = [i for i in moves_list if (y + i[1] > 0)] moves_list = [i for i in moves_list if (y + i[1] < 16)] for i in moves_list: if board[x + i[0]][y + i[1]] != '0': threat_list.add(str(x + i[0]) + str(y + i[1]) + str(board[x + i[0]][y + i[1]])) return threat_list def night_threat(x, y, board, threat_list): """docstring for night_threat""" moves_list = [] moves = [-1, -2, 1, 2] moves_list = [i for i in itertools.product(moves,moves)] moves_list = [i for i in itertools.product(moves,moves)] moves_list = [i for i in moves_list if (x + i[0] > 0)] moves_list = [i for i in moves_list if (x + i[0] < 16)] moves_list = [i for i in moves_list if (y + i[1] > 0)] moves_list = [i for i in moves_list if (y + i[1] < 16)] for i in moves_list: for r in range(1, 17, 1): if x + i[0] * r > 0 and x + i[0] * r < 16: if y + i[1] * r > 0 and y + i[1] * r < 16: if board[x + i[0]*r][y + i[1]*r] != '0': threat_list.add(str(x + i[0]) + str(y + i[1]) + str(board[x + i[0]][y + i[1]])) break return threat_list pass def archbishop_threat(x, y, board, threat_list): """docstring for archbishop_threat""" knight_list = knight_threat(x, y, board, threat_list) bishop_list = bishop_threat(x, y, board, threat_list) if knight_list: threat_list.union(knight_list) if bishop_list: threat_list.union(bishop_list) return threat_list pass def kraken_threat(x, y, board, threat_list): for i in range(16): for j in range(16): if board[i][j] != '0': threat_list.add(str(i) + str(j) + board[i][j]) return threat_list """docstring for kraken_threat""" pass def no_threat(x, y, board, threat_list): """docstring for no_threat""" return threat_list def threatened_pieces(board): threat_list = set([]) pieces = ( ('K', king_threat), ('Q', queen_threat), ('R', rook_threat), ('B', bishop_threat), ('N', knight_threat), ('S', night_threat) , ('A', archbishop_threat), ('E', kraken_threat), ('0', no_threat)) threat_list = set([]) for i in range(16): for j in range(16): for piece in pieces: if board[i][j] == piece[0]: threats = piece[1](i,j, board, threat_list) if threats: threat_list.union(threats) print len(threat_list) # K = King, Q = Queen, R = Rook, B = Bishop, N = Knight, S = Knightrighter, #'A' = Archbishop, 'E' = Kraken f = open('chess_.txt', 'r') file_input = f.readlines()[1:] file_input = [curr_line.replace('\n', '') for curr_line in file_input] file_input = [curr_line.split(' ') for curr_line in file_input] print file_input for curr_case in file_input: #Build the board. curr_board = build_board(curr_case[1:]) threatened_pieces(curr_board) #For each piece #Mark the pieces that are threatened.

[suac-blog]

Backtracking and N-Queens

One of the problem-solving techniques that comes up at least reasonably often in algorithmics is backtracking. It is, in essence, a mechanism for creating all permutations of a given set that satisfy some constraint. Having never written a backtracking algorithm before and given its popularity and in fact arguable dominance in some of our local competitions, I figured it was time to sit down and bang one out.

#My internet is down and I've never written one of these so... N-QUEENS import time def is_complete(candidate, size): """Given the candidate and the size of the board we are solving for, returns a boolean value indicating whether this is a valid solution.""" return len(candidate) == size def is_valid_candidate(candidate, size): """Given the candidate and the size, ensure that the latest addition to the candidate solution is legal. Takes candidate and size, returns boolean.""" if len(candidate) == 1: return True for i in candidate[:-1]: #Check to see if any queens share a column. if i == candidate[-1]: return False #Check to see if any queens share a diagonal. horiz_distance = abs(candidate[-1] - i) vert_distance = abs(len(candidate) - 1 - candidate.index(i)) if horiz_distance == vert_distance: return False return True def process_solution(candidate): """Given a final candidate, output the results.""" for i in candidate: line = '' for j in range(i-1): line += '.' line += '*' line += '.' * (len(candidate) - i) print line print "" def backtrack(candidate, size): """The meat of the algorithm. Builds a candidate, checks it, recurses to build final sol'n""" for i in range(1, size + 1, 1): candidate[-1] = i if is_valid_candidate(candidate, size): if is_complete(candidate, size): process_solution(candidate) return new_candidate = candidate[:] new_candidate.append(0) backtrack(new_candidate, size) return candidate = [0] x = time.time() backtrack(candidate, 8) print time.time() - x

The classic problem used to explain backtracking is N-Queens, which is defined thus: given a chess board that is n squares in height and n in width, how many ways can n queens be placed upon the board such that none of them is able to capture each other?

The way backtracking works is by using partial solutions or candidates to construct a full solution. The algorithm runs through each possibility for that candidate and, if they are valid, uses them to build a more complete candidate and so on until a complete solution is formed.

Because the solution is recursive, it implicitly constructs a tree of all of the candidates. Any candidate that is rejected is omitted, and we're left with an interesting situation where all of the remaining leaves of that tree are solutions.

Once again Python steps up with a short, sweet answer that was fun to write and (i hope) easy to read.

[suac-blog]

AppleScript and iCal

I'm not so much a fan of AppleScript, mostly because it's pretty different syntactically from most languages, so it takes awhile to write anything. What it does have, though, is hooks into nearly every application I use.

Since I don't have a cell phone right now and I wanted a system to give people a vague idea of where I was, I wrote this to fire on certain calendar events. It will change my Adium status to reflect the name of whatever calendar event is currently running.

set now to current date set early to now - 1 * hours set late to now + 1 * hours set currentEvents to {} set thisCalendar to "Ottawa Routine" tell application "iCal" tell calendar thisCalendar set currentEvents to (summary of (events whose start date > early and start date < late)) end tell end tell tell application "Adium" go away with message item 1 of currentEvents end tell