I asked ChatGPT to explain your code and mentioned you said it was a binary search. idk why, but it output a matter of fact response that claims you were wrong. lmao, I still don't understand how your code works
This code doesn’t perform a classic binary search. Instead, it uses each input node to generate new possible states or “branches,” forming a tree of transformations. At each level, it tries up to three operations on the current value (remove digits, divide, subtract). These expansions create multiple paths, and the code checks which paths end in a successful condition. While the author may have described it as a “binary search,” it’s more accurately a state-space search over a tree of possible outcomes, not a binary search over a sorted data structure.
I understand it now! I took your solution and made it faster. it is now like 36 milliseconds faster for me. which is interesting because if you look at the code. I dont process the entire list of integers. I sometimes stop prematurely before the next level, clear it, and add the root. I don't know why but it just works for my input and the test input.
however what I notice is that the parse_input causes it to be the reason why it is slower by 20+ milliseconds. I find that even if I edited your solution like so to be slightly faster, it is still 10 milliseconds slower than mine:
:::spoiler code
def parse_input():
with open('input',"r") as fp:
lines = fp.read().splitlines()
roots = [int(line.split(':')[0]) for line in lines]
node_lists = [[int(x) for x in line.split(': ')[1].split(' ')] for line in lines]
return roots, node_lists
def construct_tree(root, nodes):
levels = [[] for _ in range(len(nodes)+1)]
levels[0] = [(root, "")]
# level nodes are tuples of the form (val, operation) where both are str
# val can be numerical or empty string
# operation can be *, +, || or empty string
for indl, level in enumerate(levels[1:], start=1):
node = nodes[indl-1]
for elem in levels[indl-1]:
if elem[0]=='':
continue
if (a:=elem[0])%(b:=node)==0:
levels[indl].append((a/b, '*'))
if (a:=elem[0]) - (b:=node)>0:
levels[indl].append((a - b, "+"))
return levels[-1]
def construct_tree_concat(root, nodes):
levels = [[] for _ in range(len(nodes)+1)]
levels[0] = [(str(root), "")]
# level nodes are tuples of the form (val, operation) where both are str
# val can be numerical or empty string
# operation can be *, +, || or empty string
for indl, level in enumerate(levels[1:], start=1):
node = nodes[indl-1]
for elem in levels[indl-1]:
if elem[0]=='':
continue
if elem[0][-len(str(node)):] == str(node):
levels[indl].append((elem[0][:-len(str(node))], "||"))
if (a:=int(elem[0]))%(b:=int(node))==0:
levels[indl].append((str(int(a/b)), '*'))
if (a:=int(elem[0])) - (b:=int(node))>0:
levels[indl].append((str(a - b), "+"))
return levels[-1]
def solve_problem():
roots, node_lists = parse_input()
valid_roots_part1 = []
valid_roots_part2 = []
for root, nodes in zip(roots, node_lists):
top = construct_tree(root, nodes[::-1])
if any((x[0]==1 and x[1]=='*') or (x[0]==0 and x[1]=='+') for x in top):
valid_roots_part1.append(root)
top = construct_tree_concat(root, nodes[::-1])
if any((x[0]=='1' and x[1]=='*') or (x[0]=='0' and x[1]=='+') or (x[0]=='' and x[1]=='||') for x in top):
valid_roots_part2.append(root)
return sum(valid_roots_part1),sum(valid_roots_part2)
if __name__ == "__main__":
print(solve_problem())