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

  • iAvicenna@lemmy.world
    2·
    2 days ago

    If you havent already done so, doing it in the form of “tree search”, the code completes in the blink of an eye (though on a high end cpu 11th Gen Intel® Core™ i7-11800H @ 2.30GHz). posted the code below

    • stevenviola
      1·
      3 days ago

      Thanks! yup, I figured there would be a way. You’re right, much faster, on my machine with your code, this is the speed:

      $ time python3 day7.py 
4555081946288
227921760109726

real    0m0.171s

      I’ll have to take a look to understand how that works to be better.

      • Acters@lemmy.world
        1·
        2 days ago

        I posted my solution here and found my way to finish 30 milliseconds faster.(~100ms for his, and ~66 ms for mine) However, as I noted I stop prematurely sometimes. Which seems to work with my given input. but here is the one that makes sure it gets to the end of the list of integers:

        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 level==len(num_array)-1:
                    if branch == i:
                        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 level==len(num_array)-1:
                    if (branch == i or str(branch) == str(i)):
                        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))].rjust(1,'0')))
    
    print("Part 1:", part1, "\nPart 2:", part2)
    return [part1, part2]

if __name__ == "__main__":
    with open('input', 'r') as f:
        main(f.read())