this post was submitted on 17 Dec 2024
8 points (100.0% liked)

Advent Of Code

920 readers
63 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
[email protected]
[email protected]
[email protected]
8
🖥️ - 2024 DAY 17 SOLUTIONS - 🖥️ (programming.dev)
submitted 2 days ago by [email protected] to c/[email protected]
13 comments fedilink hide all child comments
 

Day 17: Chronospatial Computer

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

you are viewing a single comment's thread
view the rest of the comments
[–] VegOwOtenks 2 points 1 day ago

Haskell

Part 2 was tricky, I tried executing the algorithm backwards, which worked fine for the example but not with the input program, because it uses one-way functions .-. Then I tried to write an algorithm that would try all valid combinations of powers of 8 and but I failed, I then did it by hand.

Solution Codeblock

import Control.Arrow
import Data.Bits
import qualified Data.Char as Char
import qualified Data.List as List

replace c r c' = if c' == c then r else c'

parse :: String -> ([Integer], [Int])
parse = map (replace ',' ' ')
        >>> filter ((Char.isDigit &&& Char.isSpace) >>> uncurry (||))
        >>> words
        >>> splitAt 3
        >>> (map read *** map read)

type InstructionPointer = Int

adv = 0
bxl = 1
bst = 2
jnz = 3
bxc = 4
out = 5
bdv = 6
cdv = 7

lookupCombo _    0 = 0
lookupCombo _    1 = 1
lookupCombo _    2 = 2
lookupCombo _    3 = 3
lookupCombo regs 4 = regs !! 0
lookupCombo regs 5 = regs !! 1
lookupCombo regs 6 = regs !! 2
lookupCombo regs 7 = error "Invalid operand"

execute :: InstructionPointer -> [Integer] -> [Int] -> [Int]
execute ip regs@(regA:regB:regC:[]) ops
        | ip >= length ops = []
        | instruction == adv = execute (ip + 2) [regA `div` (2 ^ comboValue), regB, regC] ops
        | instruction == bxl = execute (ip + 2) [regA, xor regB (toInteger operand), regC] ops
        | instruction == bst = execute (ip + 2) [regA, comboValue `mod` 8, regC] ops
        | instruction == jnz && regA == 0 = execute (ip + 2) regs ops
        | instruction == jnz && regA /= 0 = execute operand regs ops
        | instruction == bxc = execute (ip + 2) [regA, xor regB regC, regC] ops
        | instruction == out = (fromIntegral comboValue) `mod` 8 : execute (ip + 2) regs ops
        | instruction == bdv = execute (ip + 2) [regA, regA `div` (2 ^ comboValue), regC] ops
        | instruction == cdv = execute (ip + 2) [regA, regB, regA `div` (2 ^ comboValue)] ops
        where
                (instruction, operand) = (ops !! ip, ops !! (succ ip))
                comboValue             = lookupCombo regs operand

part1 = uncurry (execute 0)
        >>> List.map show
        >>> List.intercalate ","

valid i t n = ((n `div` (8^i)) `mod` 8) `xor` 7 `xor` (n `div` (4*(8^i))) == t

part2 = const 247839653009594

main = getContents
        >>= print
        . (part1 &&& part2)
        . parse
```haskell