Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Solution for the first question of the Google Code Jam 2018. (It passes the first round of tests, but is to slow for the second; thus requires runtime optimization. Can you see what could be changed? :) )
from collections import deque
import sys
def get_damage(sequence):
current_strength = 1
damage = 0
for char in sequence:
if char == "C":
current_strength *= 2
if char == "S":
damage += current_strength
return damage
def get_nodes(sequence):
list_sequence = list(sequence)
children = list()
for idx in range(len(list_sequence) - 1):
new_node = list_sequence.copy()
new_node[idx], new_node[idx + 1] = new_node[idx + 1], new_node[idx]
children.append("".join(new_node))
return children
def get_moves(initial_sequence, shield):
q = deque()
# tupel in queue:
# (damage, node, num_swaps)
visited = dict()
current_best = (get_damage(initial_sequence),initial_sequence, 0)
q.appendleft(current_best)
while q:
damage, node, num_swaps = q.pop()
if damage <= shield:
return (damage, node, num_swaps)
if damage < current_best[0]:
current_best = (damage, node, num_swaps)
if node in visited:
continue
visited[node] = (damage, num_swaps)
for child in get_nodes(node):
dmg = get_damage(child)
q.appendleft((dmg, child, num_swaps + 1))
return (current_best[0],current_best[1],"IMPOSSIBLE")
# do pruning on minimum damage and max
def read_file(location):
with open(location, "r") as f:
return next_case(f)
def next_case(file):
test_cases = list()
num_cases = file.readline()
for line in file:
line = line[:-1]
shield, sequence = line.split(" ")
test_cases.append((int(shield), sequence))
return test_cases
if __name__ == "__main__":
#test_cases = read_file("foo.txt")
test_cases = next_case(sys.stdin)
for idx, case in enumerate(test_cases):
shield, sequence = case
num_moves = get_moves(sequence, shield)
print("Case #%d: %s" % (idx+1, str(num_moves[2])))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment