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

  • @VegOwOtenksEnglish
    2•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