Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
colin_beserk_rook solution in Clear category for Berserk Rook by colinmcnicholl
def closest_enemy(beserk_coord, enemy_coords):
"""Input: beserk_coord as a tuple, e.g. (4,3) == "d3" representing the cell
on the board the beserk rook is positioned (columns start at index 1). First
number in tuple is the column index, second number in tuple is row index.
enemy_coords as a set of tuples, e.g. {(2,6),(4,6), (2,8), (7,6), (7,4), (3,8)}
representing the cells on the board the enemy rooks are positioned.
Function searches board, records positions of enemy rooks that are on the
same row or column as the beserk rook. When enemies are on same row or
same column it chooses enemy positions nearest the center of the board and
adds these to a list 'target_enemies' that contains the co-ordinates of
target_enemies that can be taken.
Output: A list of target_enemies as tuples, e.g. [(3,6)] representing the
co-ordinates on the board of enemy rooks for which it is possible for the
beserk rook to capture. Could be an empty list."""
look_left = [rook for rook in enemy_coords if rook[0] < beserk_coord[0] and rook[1] == beserk_coord[1]]
look_right = [rook for rook in enemy_coords if rook[0] > beserk_coord[0] and rook[1] == beserk_coord[1]]
look_down = [rook for rook in enemy_coords if rook[0] == beserk_coord[0] and rook[1] < beserk_coord[1]]
look_up = [rook for rook in enemy_coords if rook[0] == beserk_coord[0] and rook[1] > beserk_coord[1]]
target_enemies = []
if look_left:
target_enemies.append(max(look_left))
if look_right:
target_enemies.append(min(look_right))
if look_down:
target_enemies.append(max(look_down))
if look_up:
target_enemies.append(min(look_up))
return target_enemies
def berserk_rook(berserker, enemies):
"""Input: Berserk rook position as a string and enemy rook positions as a
set of strings.
Function loops through all possible paths the beserk rook can take to
capture enemy rooks, keeping track of the path of maximum length.
Output: The maximum possible number of captured enemy rooks as an integer.
"""
beserk_coord = (ord(berserker[0])-96, int(berserker[1])) # -96 columns start at index 1.
enemy_coords = {(ord(cell[0])-96, int(cell[1])) for cell in enemies}
max_captured = 0 # Initialize counter for number enemy rooks captured.
stack = [(beserk_coord, set())] # Initialize stack
while stack: # While there remain enemy rooks in the path of the beserk rook.
'''remove last item from stack, current is tuple containing current cell
position of beserk rook and path is a set containing tuples representing
enemy rook cell positions visited by beserk rook.'''
current, path = stack.pop()
max_captured = max(max_captured, len(path)) # Update counter.
target_enemies = closest_enemy(current, enemy_coords - path) # targets not yet visited
for enemy in target_enemies:
'''Loop over target rooks which beserk rook may take and add to
end of stack.'''
stack.append( (enemy, path | {enemy}) )
return max_captured
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert berserk_rook('d3', {'d6', 'b6', 'c8', 'g4', 'b8', 'g6'}) == 5, "one path"
assert berserk_rook('a2', {'f6', 'f2', 'a6', 'f8', 'h8', 'h6'}) == 6, "several paths"
assert berserk_rook('a2', {'f6', 'f8', 'f2', 'a6', 'h6'}) == 4, "Don't jump through"
July 23, 2018
