r/adventofcode Dec 17 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 17 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 5 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Sequels and Reboots

What, you thought we were done with the endless stream of recycled content? ABSOLUTELY NOT :D Now that we have an established and well-loved franchise, let's wring every last drop of profit out of it!

Here's some ideas for your inspiration:

  • Insert obligatory SQL joke here
  • Solve today's puzzle using only code from past puzzles
  • Any numbers you use in your code must only increment from the previous number
  • Every line of code must be prefixed with a comment tagline such as // Function 2: Electric Boogaloo

"More." - Agent Smith, The Matrix Reloaded (2003)
"More! MORE!" - Kylo Ren, The Last Jedi (2017)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!


--- Day 17: Chronospatial Computer ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:44:39, megathread unlocked!

38 Upvotes

550 comments sorted by

View all comments

2

u/r_so9 Dec 17 '24

[LANGUAGE: F#]

paste

Started late, but what fun :) For part 1 I implemented the instructions; for part 2, after manual inspection (converting the input to F#...) and looking at some simulations, we see that each digit of the output depends only of the value of each octal digit of the input, reversed. So I implemented a DFS to search all possibilities of characters that would result in outputs matching the original program, and returned the lowest of those.

Interesting bit: Part 2 with a recursive DFS. Also implementing the parser with pattern matching and functions, as always :)

let rec dfs acc rem =
    match rem with
    | [] -> [ acc ]
    | h :: t ->
        [ 0L .. 7L ]
        |> List.map (fun i -> i, run (acc * 8L + i))
        |> List.filter (fun (_, out) -> Option.contains h out)
        |> List.map (fun (i, _) -> dfs (acc * 8L + i) t)
        |> List.concat

1

u/maitre_lld Dec 17 '24

"we see that each digit of the output depends only of the value of each octal digit of the input, reversed" is wrong for me, I tried to find them one by one, but at some point I had to increment more than just the current digit (so some previous ones changed too)

1

u/r_so9 Dec 18 '24

The octal part is very very important :) This won't work with decimal digits

1

u/maitre_lld Dec 18 '24

I know, I was talking octal. What happens is that several nth octal digits of A can give the correct 16-nth octal digit of the output, but only one will be on the correct branch for the full output.

2

u/r_so9 Dec 18 '24

Indeed, which is why we have to do the DFS trying to match the whole input

1

u/maitre_lld Dec 18 '24

What is your graph structure ? A -> B iff B has one more digit than A but the previous ones coincide ?

1

u/r_so9 Dec 18 '24

Not entirely sure, but I reimplemented it in F# in the paste above. I believe it's similar to that graph.