Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Berserk Rook by cimarronm
def capturable_enemies(berserker, enemies):
# four possible capturing moves
left = [enemy for enemy in enemies
if enemy[1] == berserker[1] and enemy[0] < berserker[0]]
if left:
yield max(left)
right = [enemy for enemy in enemies
if enemy[1] == berserker[1] and enemy[0] > berserker[0]]
if right:
yield min(right)
up = [enemy for enemy in enemies
if enemy[0] == berserker[0] and enemy[1] > berserker[1]]
if up:
yield min(up)
down = [enemy for enemy in enemies
if enemy[0] == berserker[0] and enemy[1] < berserker[1]]
if down:
yield max(down)
def berserk_rook(berserker, enemies):
enemy_count = len(enemies)
queue = [(berserker, enemies)]
best = 0
# DFS search of entire tree with premature exit if we capture all
# enemies while traversing one branch
while queue:
berserker, enemies = queue.pop()
if not enemies:
return enemy_count
else:
best = max(best, enemy_count - len(enemies))
for enemy in capturable_enemies(berserker, enemies):
queue.append((enemy, enemies - {enemy}))
return best
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"
April 25, 2015
