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

  • @Acters
    1•2 days ago

    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())
    • @iAvicenna
      2•2 days ago

      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.

      • @Acters
        1•1 day ago

        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