Day 7: Bridge Repair
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Python
It is a tree search
def parse_input(path):
with path.open("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][1:].split(' ')] for line in lines]
return roots, node_lists
def construct_tree(root, nodes, include_concat):
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) and include_concat:
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(file_name, include_concat):
roots, node_lists = parse_input(Path(cwd, file_name))
valid_roots = []
for root, nodes in zip(roots, node_lists):
top = construct_tree(root, nodes[::-1], include_concat)
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.append(root)
return sum(valid_roots)
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.
code
def main(input_data):
input_data = input_data.replace('\r', '')
parsed_data = {int(line[0]): [int(i) for i in line[1].split()[::-1]] for line in [l.split(': ') for l in input_data.splitlines()]}
part1 = 0
part2 = 0
for item in parsed_data.items():
root, num_array = item
part_1_branches = [set() for _ in range(len(num_array)+1)]
part_2_branches = [set() for _ in range(len(num_array)+1)]
part_1_branches[0].add(root)
part_2_branches[0].add(root)
for level,i in enumerate(num_array):
if len(part_1_branches[level]) == 0 and len(part_2_branches[level]) == 0:
break
for branch in part_1_branches[level]:
if branch == i:
part_1_branches[level+1] = set() # clear next level to prevent adding root again
part1 += root
break
if branch % i == 0:
part_1_branches[level+1].add(branch//i)
if branch - i > 0:
part_1_branches[level+1].add(branch-i)
for branch in part_2_branches[level]:
if branch == i or str(branch) == str(i):
part_2_branches[level+1] = set() # clear next level to prevent adding root again
part2 += root
break
if branch % i == 0:
part_2_branches[level+1].add(branch//i)
if branch - i > 0:
part_2_branches[level+1].add(branch-i)
if str(i) == str(branch)[-len(str(i)):]:
part_2_branches[level+1].add(int(str(branch)[:-len(str(i))]))
print("Part 1:", part1, "\nPart 2:", part2)
return [part1, part2]
if __name__ == "__main__":
with open('input', 'r') as f:
main(f.read())
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:
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())
Wow I got thrashed by chatgpt. Strictly speaking that is correct, it is more akin to Tree Search. But even then not strictly because in tree search you are searching through a list of objects that is known, you build a tree out of it and based on some conditions eliminate half of the remaining tree each time. Here I have some state space (as chatgpt claims!) and again based on applying certain conditions, I eliminate some portion of the search space successively (so I dont have to evaluate that part of the tree anymore). To me both are very similar in spirit as both methods avoid evaluating some function on all the possible inputs and successively chops off a fraction of the search space. To be more correct I will atleast replace it with tree search though, thanks. And thanks for taking a close look at my solution and improving it.
idk why my gpt decided to be like that. I expected a long winded response with a little bit of ai hallucinations. I was flabbergasted, and just had to post it.
I seemingly realized that working forward through the list of integers was inefficient for me to do, and I was using multiprocessing to do it too! which my old solution took less than 15 seconds for my input. your solution to reverse the operations and eliminate paths was brilliant and made it solve it in milliseconds without spinning up my fans, lol
