I have completed this challenges part two: https://adventofcode.com/2022/day/21 .
This is the code which I came up for it: (i have uploaded the input to the program here)
import sys
import pstats
import time
#def f8_alt(x):
# return "%14.12f" % x
#pstats.f8 = f8_alt
#PART2 = True
RUN_COUNT = 1000
glob_input = None
def parse_monkeys() -> dict:
global glob_input
if glob_input == None:
glob_input = sys.stdin.read()
lines = glob_input.split("\n")
# Each line represents one monkey.
# Each monkey name is four characters long. The line is of the format aaaa: bbbb + cccc
out_dict = {}
types = {}
for line in lines:
#print("line == "+str(line))
monkey_name = line[:4]
expression = line[6:]
#out_dict[monkey_name] = expression.split(" ")
#print("expression == "+str(expression))
if expression.isnumeric():
out_dict[monkey_name] = [expression]
types[monkey_name] = 1 # one means number, zero means other expression
continue
types[monkey_name] = 0
out_dict[monkey_name] = [expression[0:4], expression[5], expression[7:]]
return out_dict, types
'''
def parse_monkeys() -> dict:
stdin_input = sys.stdin.read()
lines = stdin_input.split("\n")
# Each line represents one monkey.
# Each monkey name is four characters long. The line is of the format aaaa: bbbb + cccc
out_dict = {}
for line in lines:
monkey_name = line[:4]
expression = line[6:]
out_dict[monkey_name] = expression.split(" ")
return out_dict
'''
def evaluate_monkeys(monkeys: dict, cur_monkey: str) -> int:
#if cur_monkey == "humn" and PART2:
# print("Error!")
# exit(1)
tokens = monkeys[cur_monkey]
if len(tokens) == 1:
token = tokens[0]
if token.isnumeric():
return int(token) # plain number
else:
return evaluate_monkeys(monkeys, token)
else:
val_1 = evaluate_monkeys(monkeys, tokens[0])
val_2 = evaluate_monkeys(monkeys, tokens[2])
op_string = tokens[1]
match op_string:
case "+":
return val_1 + val_2
case "-":
return val_1 - val_2
case "*":
return val_1 * val_2
case "/":
return (val_1 // val_2)
case _:
print("Invalid operation for monkey "+str(monkey_name)+" : "+str(op_string))
exit(1)
def get_route(monkeys: dict, wanted_monkey: str, moves: list, cur_monkey: str, types: dict):
if cur_monkey == wanted_monkey:
#print("Returning moves")
return moves
#print("start")
for monkey in monkeys:
if types[monkey]:
continue
expression = monkeys[monkey]
if cur_monkey in expression:
if cur_monkey == expression[0]:
#print("left")
return get_route(monkeys, wanted_monkey, [0]+moves, monkey, types)
else:
return get_route(monkeys, wanted_monkey, [1]+moves, monkey, types)
'''
def get_route(monkeys: dict, wanted_monkey: str, moves: list, cur_monkey: str, types: dict):
if cur_monkey == wanted_monkey:
#print("Returning moves")
return moves
#print("start")
for monkey in monkeys:
if types[monkey]:
continue
expression = monkeys[monkey]
if cur_monkey == expression[0]:
#print("left")
return get_route(monkeys, wanted_monkey, [0]+moves, monkey, types)
elif cur_monkey == expression[2]:
return get_route(monkeys, wanted_monkey, [1]+moves, monkey, types)
'''
def get_value(monkeys: dict, route: list):
if route[0] == 0:
# The humn leaf is on the left so the other value is on the right side.
#value_monkey = monkeys["root"].split(" ")[2]
value_monkey = monkeys["root"][2]
else:
# The humn leaf is on the right side, so the other value is on the left side
#value_monkey = monkeys["root"].split(" ")[0]
value_monkey = monkeys["root"][0]
# Calculate lhs
# def evaluate_monkeys(monkeys: dict, cur_monkey: str) -> int:
lhs = evaluate_monkeys(monkeys, value_monkey)
return lhs
def get_monkey_name(monkeys: dict, name: str, move:int):
expression = monkeys[name]
if move == 0:
#return expression.split(" ")[0] # left
return expression[0]
else:
#return expression.split(" ")[2] # right
return expression[2]
def traverse_backwards(monkeys, route, value):
# This function traverses the binary tree backwards to get the appropriate value for humn.
# First get the monkey names which we traverse along to get to humn.
cur_name = "root"
monkey_names = ["root"]
for move in route:
cur_name = get_monkey_name(monkeys, cur_name, move)
monkey_names.append(cur_name)
#print("Monkey names which we traverse to get to humn: "+str(monkey_names))
# reverse route and the monkey names along that route
#monkey_names.reverse()
#route.reverse()
cur_name = "root"
counter = 0
monkey_names.pop(0)
#print("monkey_names == "+str(monkey_names))
route.pop(0)
#print("monkey_names == "+str(monkey_names))
#print("Initial value: "+str(value))
while cur_name != "humn":
cur_name = monkey_names[counter]
# value is lhs
#
if cur_name == "humn":
#print("qqqqqqqqqqqq")
break
if route[counter] == 1:
# humn thing is on the right, so calculate left.
cor_index = 0
else:
# humn is on the left so calculate right
cor_index = 2
tokens = monkeys[cur_name]
other_monkey_name = tokens[cor_index]
val_2 = evaluate_monkeys(monkeys, other_monkey_name)
match tokens[1]: # Match operator and apply the reverse operator
case "+":
value = value - val_2
case "-":
# Same as with division:
if cor_index == 0:
# Humn thing is on the right aka value = aaaa - humn => humn = aaaa - value
value = val_2 - value
else:
# Humn thing is on the left, so value = humn - aaaa => humn = value + aaaa
value = value + val_2
case "*":
# sanity check
#if value % val_2 != 0:
# print("counter == "+str(counter))
# print("value % val_2 != 0")
# exit(1)
value = value // val_2
case "/":
if cor_index == 0:
# Left is constant, so the divisor is actually the human thing. value = x / humn => humn = value / x
value = value / val_2
else:
# Right is constant, so just multiply by val_2
value = (value * val_2)
case _:
print("Invalid operation for monkey "+str(monkey_name)+" : "+str(op_string))
exit(1)
counter += 1
return value
def get_monkey_names(monkeys: dict, route: list):
cur_name = "root"
monkey_names = ["root"]
for move in route:
cur_name = get_monkey_name(monkeys, cur_name, move)
monkey_names.append(cur_name)
return monkey_names
def solve_equation(monkeys: dict, types: dict) -> int:
# First get the route to the humn monkey and reverse it.
route = get_route(monkeys, "root", [], "humn", types)
monkey_names = get_monkey_names(monkeys, route)
value = get_value(monkeys, route)
humn_value = traverse_backwards(monkeys, route, value)
#print("humn_value == "+str(humn_value))
return humn_value
def main() -> int:
start_time = time.time()
for _ in range(RUN_COUNT):
monkeys, types = parse_monkeys()
result = solve_equation(monkeys, types)
#result = evaluate_monkeys(monkeys, "root") # find value of root.
#print(result)
end_time = time.time()
tot_time = end_time - start_time
print(str(RUN_COUNT)+" runs tooks "+str(tot_time)+ " seconds.")
print("Average run time was "+str(tot_time / RUN_COUNT)+" seconds.")
return 0
if __name__=="__main__":
exit(main())
I am now wondering why the non-commented version of "get_route" is faster than the commented one, because when trying with the commented out version of get_route I am getting slower execution speeds for each run. It doesn't make sense for me because the monkeys[monkey] list has a list of tokens, if the monkey just yells a number, then it only has that token, but if it is an expression (aka aaaa + bbbb for example), then it has ["aaaa", "+", "bbbb"] as its elements. When running this program with python3 -m cProfile -s time prof.py < input.txt I get this next results:
1000 runs tooks 20.217543363571167 seconds.
Average run time was 0.020217543363571167 seconds.
9674013 function calls (7041013 primitive calls) in 20.218 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
70000/1000 14.009 0.000 14.009 0.014 prof.py:88(get_route)
2633000/69000 2.855 0.000 3.160 0.000 prof.py:59(evaluate_monkeys)
1000 2.423 0.002 2.684 0.003 prof.py:11(parse_monkeys)
4054000 0.262 0.000 0.262 0.000 {method 'isnumeric' of 'str' objects}
2633000 0.211 0.000 0.211 0.000 {built-in method builtins.len}
1 0.159 0.159 20.218 20.218 prof.py:259(main)
1000 0.119 0.000 2.923 0.003 prof.py:159(traverse_backwards)
1000 0.093 0.000 0.093 0.000 {method 'split' of 'str' objects}
138000 0.039 0.000 0.039 0.000 prof.py:149(get_monkey_name)
1000 0.033 0.000 0.059 0.000 prof.py:236(get_monkey_names)
138000 0.010 0.000 0.010 0.000 {method 'append' of 'list' objects}
1000 0.003 0.000 17.375 0.017 prof.py:247(solve_equation)
1000 0.001 0.000 0.380 0.000 prof.py:130(get_value)
2000 0.000 0.000 0.000 0.000 {method 'pop' of 'list' objects}
1 0.000 0.000 20.218 20.218 prof.py:1(<module>)
2 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {method 'read' of '_io.TextIOWrapper' objects}
1 0.000 0.000 0.000 0.000 <frozen _sitebuiltins>:19(__call__)
1 0.000 0.000 0.000 0.000 {method 'close' of '_io.TextIOWrapper' objects}
1 0.000 0.000 20.218 20.218 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method _codecs.utf_8_decode}
1 0.000 0.000 0.000 0.000 <frozen codecs>:319(decode)
2 0.000 0.000 0.000 0.000 {built-in method time.time}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
But when I uncomment the other version and use it instead I get this:
1000 runs tooks 23.656423330307007 seconds.
Average run time was 0.023656423330307007 seconds.
9674013 function calls (7041013 primitive calls) in 23.657 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
70000/1000 17.517 0.000 17.517 0.018 prof.py:109(get_route)
2633000/69000 2.818 0.000 3.104 0.000 prof.py:59(evaluate_monkeys)
1000 2.392 0.002 2.672 0.003 prof.py:11(parse_monkeys)
4054000 0.285 0.000 0.285 0.000 {method 'isnumeric' of 'str' objects}
2633000 0.185 0.000 0.185 0.000 {built-in method builtins.len}
1 0.155 0.155 23.656 23.656 prof.py:259(main)
1000 0.120 0.000 2.874 0.003 prof.py:159(traverse_backwards)
1000 0.096 0.000 0.096 0.000 {method 'split' of 'str' objects}
138000 0.039 0.000 0.039 0.000 prof.py:149(get_monkey_name)
1000 0.034 0.000 0.061 0.000 prof.py:236(get_monkey_names)
138000 0.011 0.000 0.011 0.000 {method 'append' of 'list' objects}
1000 0.003 0.000 20.829 0.021 prof.py:247(solve_equation)
1000 0.001 0.000 0.375 0.000 prof.py:130(get_value)
2000 0.000 0.000 0.000 0.000 {method 'pop' of 'list' objects}
1 0.000 0.000 23.657 23.657 prof.py:1(<module>)
2 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {method 'read' of '_io.TextIOWrapper' objects}
1 0.000 0.000 0.000 0.000 <frozen _sitebuiltins>:19(__call__)
1 0.000 0.000 0.000 0.000 {method 'close' of '_io.TextIOWrapper' objects}
1 0.000 0.000 23.657 23.657 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 <frozen codecs>:319(decode)
1 0.000 0.000 0.000 0.000 {built-in method _codecs.utf_8_decode}
2 0.000 0.000 0.000 0.000 {built-in method time.time}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
The other version is doing more comparisons with the if cur_monkey in expression: and then later with the if cur_monkey == expression[0]: check, but it is somehow faster. Are array accesses that slow in python?
The reason for this is the difference in the low level bytecode. The disassembly of the slower version yields this as bytecode (disassembled):
124 >> 106 LOAD_FAST 3 (cur_monkey)
108 LOAD_FAST 6 (expression)
110 LOAD_CONST 2 (2)
112 BINARY_SUBSCR
116 COMPARE_OP 40 (==)
120 POP_JUMP_IF_TRUE 1 (to 124)
122 JUMP_BACKWARD 52 (to 20)
when as the faster version yields this:
99 48 LOAD_FAST 3 (cur_monkey)
50 LOAD_FAST 6 (expression)
52 CONTAINS_OP 0
54 POP_JUMP_IF_TRUE 1 (to 58)
56 JUMP_BACKWARD 19 (to 20)
Thanks to Charles Duffy for the answer!