From 879988b4a618a218a8bc78507717b330b1030c3a Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Fri, 23 Dec 2016 18:10:27 +0000 Subject: [PATCH] Day 23 --- adventofcode16/adventofcode16.cabal | 10 ++ adventofcode16/app/advent23.hs | 198 ++++++++++++++++++++++++++++ adventofcode16/data/advent23.txt | 26 ++++ day23.html | 167 +++++++++++++++++++++++ 4 files changed, 401 insertions(+) create mode 100644 adventofcode16/app/advent23.hs create mode 100644 adventofcode16/data/advent23.txt create mode 100644 day23.html diff --git a/adventofcode16/adventofcode16.cabal b/adventofcode16/adventofcode16.cabal index 39c0942..6216e51 100644 --- a/adventofcode16/adventofcode16.cabal +++ b/adventofcode16/adventofcode16.cabal @@ -332,6 +332,16 @@ executable advent22library , hashable default-language: Haskell2010 +executable advent23 + hs-source-dirs: app + main-is: advent23.hs + ghc-options: -O2 -threaded -rtsopts -with-rtsopts=-N + build-depends: base + , adventofcode16 + , parsec + , parsec-numbers + , mtl + default-language: Haskell2010 executable adventofcode16-exe hs-source-dirs: app diff --git a/adventofcode16/app/advent23.hs b/adventofcode16/app/advent23.hs new file mode 100644 index 0000000..42cd15f --- /dev/null +++ b/adventofcode16/app/advent23.hs @@ -0,0 +1,198 @@ +module Main(main) where + +import Text.Parsec hiding (State) +import Text.ParserCombinators.Parsec.Number +import Control.Monad.State.Lazy +-- import Debug.Trace + +data Location = Literal Int | Register Char deriving (Show, Eq) +data Instruction = Cpy Location Location + | Inc Location + | Dec Location + | Jnz Location Location + | Tgl Location + deriving (Show, Eq) + +data Machine = Machine { a :: Int + , b :: Int + , c :: Int + , d :: Int + , pc :: Int + , instructions :: [Instruction]} + deriving (Show, Eq) + + +testInstructions = "cpy 2 a\n\ +\tgl a\n\ +\tgl a\n\ +\tgl a\n\ +\cpy 1 a\n\ +\dec a\n\ +\dec a" + + +emptyMachine :: Machine +emptyMachine = Machine {a=0, b=0, c=0, d=0, pc=0, instructions=[]} + +main :: IO () +main = do + text <- readFile "data/advent23.txt" + let instructions = successfulParse $ parseIfile text + part1 instructions + part2 instructions + + +part1 :: [Instruction] -> IO () +part1 instrs = + do let m0 = emptyMachine {instructions=instrs, a = 7} + let mf = snd $ runState runMachine m0 + print (a mf) + +part2 :: [Instruction] -> IO () +part2 instrs = + do let m0 = emptyMachine {instructions=instrs, a = 12} + let mf = snd $ runState runMachine m0 + print (a mf) + + +runMachine :: State Machine () +runMachine = + do m <- get + if (pc m) >= (length $ instructions m) + then return () + else do executeStep + runMachine + +executeStep :: State Machine () +executeStep = + do m <- get + let i = (instructions m)!!(pc m) + put (executeInstructionPeep i m) + -- put (executeInstruction i m) + +executeInstructionPeep :: Instruction -> Machine -> Machine +executeInstructionPeep i m = + if sample1 == sample1Target + -- then trace ("Peeping 1 " ++ (show m) ++ " to " ++ (show m1)) m1 + then m1 + else if sample2 == sample2Target + -- then trace ("Peeping 2 " ++ (show m) ++ " to " ++ (show m2)) m2 + then m2 + else executeInstruction i m + where sample1 = take (length sample1Target) $ drop (pc m) $ instructions m + sample1Target = [ Cpy (Literal 0) (Register 'a') + , Cpy (Register 'b') (Register 'c') + , Inc (Register 'a') + , Dec (Register 'c') + , Jnz (Register 'c') (Literal (-2)) + , Dec (Register 'd') + , Jnz (Register 'd') (Literal (-5)) ] + m1 = m {a = b m * d m, c = 0, d = 0, pc = pc m + (length sample1)} + sample2 = take (length sample2Target) $ drop (pc m) $ instructions m + sample2Target = [ Dec (Register 'b') + , Cpy (Register 'b') (Register 'c') + , Cpy (Register 'c') (Register 'd') + , Dec (Register 'd') + , Inc (Register 'c') + , Jnz (Register 'd') (Literal (-2)) ] + m2 = m {b = b m - 1, c = (b m - 1) * 2, d = 0, pc = pc m + (length sample2)} + + +executeInstruction :: Instruction -> Machine -> Machine +executeInstruction (Inc r@(Register _)) m = m' {pc=pc1} + where pc1 = (pc m) + 1 + v = evaluate m r + m' = writeValue m r (v+1) +executeInstruction (Inc (Literal _)) m = m {pc=pc1} + where pc1 = (pc m) + 1 +executeInstruction (Dec r@(Register _)) m = m' {pc=pc1} + where pc1 = (pc m) + 1 + v = evaluate m r + m' = writeValue m r (v-1) +executeInstruction (Dec (Literal _)) m = m {pc=pc1} + where pc1 = (pc m) + 1 +executeInstruction (Cpy s d@(Register _)) m = m' {pc=pc1} + where pc1 = (pc m) + 1 + v = evaluate m s + m' = writeValue m d v +executeInstruction (Cpy s (Literal _)) m = m {pc=pc1} + where pc1 = (pc m) + 1 +executeInstruction (Jnz s d) m + | v == 0 = m {pc=pc1} + | otherwise = m {pc=pcj} + where pc1 = (pc m) + 1 + ed = evaluate m d + pcj = (pc m) + ed + v = evaluate m s +executeInstruction (Tgl a) m + | v < (length $ instructions m) = m {instructions = (replace (instructions m) i' v), + pc=pc1} + | otherwise = m {pc=pc1} + where pc1 = pc m + 1 + v = evaluate m a + pc m + i = (instructions m)!!v + i' = case i of + Inc x -> Dec x + Dec x -> Inc x + Tgl x -> Inc x + Cpy x y -> Jnz x y + Jnz x y -> Cpy x y + replace xs x i = take i xs ++ [x] ++ drop (i+1) xs + + +evaluate :: Machine -> Location -> Int +evaluate _ (Literal i) = i +evaluate m (Register r) = + case r of + 'a' -> (a m) + 'b' -> (b m) + 'c' -> (c m) + 'd' -> (d m) + +writeValue :: Machine -> Location -> Int -> Machine +writeValue m (Literal i) _ = m +writeValue m (Register r) v = + case r of + 'a' -> m {a=v} + 'b' -> m {b=v} + 'c' -> m {c=v} + 'd' -> m {d=v} + + +instructionFile = instructionLine `sepEndBy` newline +-- instructionLine = choice [cpyL, incL, decL, jnzL] +instructionLine = incL <|> decL <|> cpyL <|> jnzL <|> tglL + +-- incL = incify <$> (string "inc" *> spaces *> (oneOf "abcd")) +-- where incify r = Inc (Register r) +incL = (Inc . Register) <$> (string "inc" *> spaces *> (oneOf "abcd")) +-- decL = decify <$> (string "dec" *> spaces *> (oneOf "abcd")) +-- where decify r = Dec (Register r) +decL = (Dec . Register) <$> (string "dec" *> spaces *> (oneOf "abcd")) +cpyL = cpyify <$> (string "cpy" *> spaces *> ((Literal <$> int) <|> ((Register . head) <$> (many1 letter)))) + <*> (spaces *> (oneOf "abcd")) + where cpyify s r = Cpy s (Register r) +jnzL = jnzify <$> (string "jnz" *> spaces *> ((Literal <$> int) <|> ((Register . head) <$> (many1 letter)))) + <*> (spaces *> ((Literal <$> int) <|> ((Register . head) <$> (many1 letter)))) + where jnzify r o = Jnz r o +tglL = Tgl <$> (string "tgl" *> spaces *> ((Literal <$> int) <|> ((Register . head) <$> (many1 letter)))) + -- where tglify r = Tgl r + + +-- readLocation :: Int -> Location +-- readLocation l = Literal l + +-- readLocation :: String -> Location +-- readLocation l +-- | all (isDigit) l = Literal (read l) +-- | otherwise = Register (head l) + +parseIfile :: String -> Either ParseError [Instruction] +parseIfile input = parse instructionFile "(unknown)" input + +parseIline :: String -> Either ParseError Instruction +parseIline input = parse instructionLine "(unknown)" input + +successfulParse :: Either ParseError [a] -> [a] +successfulParse (Left _) = [] +successfulParse (Right a) = a \ No newline at end of file diff --git a/adventofcode16/data/advent23.txt b/adventofcode16/data/advent23.txt new file mode 100644 index 0000000..93f25d2 --- /dev/null +++ b/adventofcode16/data/advent23.txt @@ -0,0 +1,26 @@ +cpy a b +dec b +cpy a d +cpy 0 a +cpy b c +inc a +dec c +jnz c -2 +dec d +jnz d -5 +dec b +cpy b c +cpy c d +dec d +inc c +jnz d -2 +tgl c +cpy -16 c +jnz 1 c +cpy 94 c +jnz 99 d +inc a +inc d +jnz d -2 +inc c +jnz c -5 \ No newline at end of file diff --git a/day23.html b/day23.html new file mode 100644 index 0000000..27e2e00 --- /dev/null +++ b/day23.html @@ -0,0 +1,167 @@ + + + + +Day 23 - Advent of Code 2016 + + + + + + +

Advent of Code

Neil Smith (AoC++) 46*

   0xffff&2016

+ + + +
+

--- Day 23: Safe Cracking ---

This is one of the top floors of the nicest tower in EBHQ. The Easter Bunny's private office is here, complete with a safe hidden behind a painting, and who wouldn't hide a star in a safe behind a painting?

+

The safe has a digital screen and keypad for code entry. A sticky note attached to the safe has a password hint on it: "eggs". The painting is of a large rabbit coloring some eggs. You see 7.

+

When you go to type the code, though, nothing appears on the display; instead, the keypad comes apart in your hands, apparently having been smashed. Behind it is some kind of socket - one that matches a connector in your prototype computer! You pull apart the smashed keypad and extract the logic circuit, plug it into your computer, and plug your computer into the safe.

+

Now, you just need to figure out what output the keypad would have sent to the safe. You extract the assembunny code from the logic chip (your puzzle input).

+

The code looks like it uses almost the same architecture and instruction set that the monorail computer used! You should be able to use the same assembunny interpreter for this as you did there, but with one new instruction:

+

tgl x toggles the instruction x away (pointing at instructions like jnz does: positive means forward; negative means backward):

+
    +
  • For one-argument instructions, inc becomes dec, and all other one-argument instructions become inc.
    • +
  • For two-argument instructions, jnz becomes cpy, and all other two-instructions become jnz.
    • +
  • The arguments of a toggled instruction are not affected.
    • +
  • If an attempt is made to toggle an instruction outside the program, nothing happens.
    • +
  • If toggling produces an invalid instruction (like cpy 1 2) and an attempt is later made to execute that instruction, skip it instead.
    • +
  • If tgl toggles itself (for example, if a is 0, tgl a would target itself and become inc a), the resulting instruction is not executed until the next time it is reached.
    • +
+

For example, given this program:

+
cpy 2 a
+tgl a
+tgl a
+tgl a
+cpy 1 a
+dec a
+dec a
+
+
    +
  • cpy 2 a initializes register a to 2.
    • +
  • The first tgl a toggles an instruction a (2) away from it, which changes the third tgl a into inc a.
    • +
  • The second tgl a also modifies an instruction 2 away from it, which changes the cpy 1 a into jnz 1 a.
    • +
  • The fourth line, which is now inc a, increments a to 3.
    • +
  • Finally, the fifth line, which is now jnz 1 a, jumps a (3) instructions ahead, skipping the dec a instructions.
    • +
+

In this example, the final value in register a is 3.

+

The rest of the electronics seem to place the keypad entry (the number of eggs, 7) in register a, run the code, and then send the value left in register a to the safe.

+

What value should be sent to the safe?

+
+

Your puzzle answer was 14346.

--- Part Two ---

The safe doesn't open, but it does make several angry noises to express its frustration.

+

You're quite sure your logic is working correctly, so the only other thing is... you check the painting again. As it turns out, colored eggs are still eggs. Now you count 12.

+

As you run the program with this new input, the prototype computer begins to overheat. You wonder what's taking so long, and whether the lack of any instruction more powerful than "add one" has anything to do with it. Don't bunnies usually multiply?

+

Anyway, what value should actually be sent to the safe?

+
+

Your puzzle answer was 479010906.

Both parts of this puzzle are complete! They provide two gold stars: **

+

At this point, you should return to your advent calendar and try another puzzle.

+

If you still want to see it, you can get your puzzle input.

+

You can also this puzzle.

+
+ + + + + + \ No newline at end of file -- 2.34.1