# Advent of Code 2019 day 25

Day 25 was fairly straightforward, once again building on Ascii generation from IntCode, as in day 17. In this puzzle, the output of the machine turned it into a simple text adventure game. All you had to do was find the correct items to carry to pass the security check.

Straight away, I ran into a problem, in that my Intcode machine fell over. It turned out that the bug was when I was detecting when the machine should Block due to wanting input that wasn't available. I was checking for the opcode to be a literal 3, when I should have been interpreting the opcode, accounting for addressing modes. Once I had that sorted, things went well.

## Exploration

The first thing to do was understand what this adventure game looked like. That meant cobbling together an interaction loop with the Intcode machine. I ended up writing three functions to help this.

runCommand :: [Integer] -> [String] -> (Machine, String)
runCommand mem inputs = ( machine, decodeOutput output )
where (_state,  machine, output) = runProgram inputCodes mem
inputCodes = encodeCommands inputs

runGame :: [Integer] -> [String] -> IO ()
runGame mem inputs =
do let (_, outputs) = runCommand mem inputs
putStrLn outputs
nextIn <- getLine
runGame mem (inputs ++ [nextIn])

runGameM :: Machine -> [String] -> IO ()
runGameM machine inputs =
do nextIn <- getLine
let (_s, machine1, output1) = runMachine (encodeCommands (inputs ++ [nextIn])) machine
putStrLn $decodeOutput output1 runGameM machine1 (inputs ++ [nextIn])  runCommand takes the Intcode program (from the input file) and a single command and returns the output after giving that command (and the machine state at this point). runGame uses runCommand. runGame takes an Intcode program and a sequence of inputs, runs the machine on those inputs, presents the output, then asks for the next input and runs the machine with it. That's enough to play the game from scratch and explore the world. runGameM takes an Intcode machine (not just the program), gets some input, and then executes it. This is an easier way to run a bunch of commands and ignore their output. I used it once I'd determined a set of commands to run before I took over manually. I also wrote a couple of functions to convert between the lists of numbers the Intcode machine used, and the strings that I could understand. encodeCommands :: [String] -> [Integer] encodeCommands = map (fromIntegral . ord) . concat . map (++ "\n") decodeOutput :: [Integer] -> String decodeOutput = map (chr . fromIntegral)  Using the combination of runGame and runGameM, I interacted at the terminal with the game, finding the rooms, working out where the objects were (and which ones to avoid!), and where the security station was. I added those commands to a text file, which was read and used by runPreamble to pick up all the safe items and move to the security station, ready for the next stage of the process. main :: IO () main = do text <- TIO.readFile "data/advent25.txt" let mem = parseMachineMemory text print$ length mem
(machine, instructions, items) <- runPreamble mem
-- runGameM machine instructions
putStrLn $passSecurity machine instructions items runPreamble :: [Integer] -> IO (Machine, [String], [String]) runPreamble mem = do instr <- TIO.readFile "data/advent25-instructions.txt" let instructions = lines$ T.unpack instr
-- runGame mem $lines$ T.unpack instructions
let (machine, _output) = runCommand mem instructions
let (_s, _machine1, output1) = runMachine (encodeCommands (instructions ++ ["inv"])) machine
putStrLn $decodeOutput output1 let items = extractItems$ decodeOutput output1
return (machine, instructions, items)


## Finding the right items to carry

With eight items, there are 28 = 256 different subsets of items to attempt. I could do something clever with eliminating different sets of items based on what I already knew (if a set of items is too heavy, any superset of it will also be too heavy; simllarly, if a set of items is too light, and subset of it will also be too light). But that would have involved some effort and there were only 256 options. Brute force was good enough.

This was also an instance where functional purity came into play. After running the preamble, I had the machine in a state where the player was in the right place with all the items. I could drop some items, try to pass security and, if that failed, just revert back to the original machine state. It saved a lot of hassle of picking up items that had been dropped.

The basic idea was to find the powerset of the carried items. Then, for each set in the powerset, drop those items and attempt to pass the security control. That is essentially a filter on the sets of items, finding the sets that pass. I can then use one of those sets to run the machine and find the code.

Note: there are a few layers to this, and the state of the machine (after doing the preamble) is only used in the lowest layers. This means I ended up using a Reader monad to tidy up the plumbing a bit, calling runReader at the top level and extracting the data in runCachedMachine, a function that wraps runMachine.

type CachedMachine a = Reader (Machine, [String]) a

runCachedMachine :: [String] -> CachedMachine String
runCachedMachine dropCommands =
do (machine, instructions) <- ask
let (_, _, output) = runMachine (encodeCommands (instructions ++ dropCommands ++ ["north"])) machine
return $decodeOutput output  Working up from that lowest level, attemptSecurity takes a list of items to drop. It issues commands to drop all of them, attempts to pass the security check, and returns the result. attemptSecurity :: [String] -> CachedMachine String attemptSecurity drops = do let dropCommands = map ("drop " ++ ) drops output <- runCachedMachine dropCommands return output  passesSecurity detects if the attempt contains the word 'Alert', which signifies not passing. passesSecurity :: [String] -> CachedMachine Bool passesSecurity drops = do output <- attemptSecurity drops return$ not ("Alert" isInfixOf output)


passSecurity uses passesSecurity as the predicate in a filter, finding the set of dropped items that allows you to pass security. It also redoes the successful attempt and echoes the output, so you can read the answer!

passSecurity :: Machine -> [String] -> [String] -> String
passSecurity machine instructions items = "You keep: " ++ (intercalate ", " keeps) ++ "\n\n" ++ successResponse
where
env = (machine, instructions)
dropsets = powerList items
validDropset = head \$ filter (\ds -> runReader (passesSecurity ds) env) dropsets
successResponse = (runReader (attemptSecurity validDropset) env)
keeps = items \\ validDropset


And that's it! As is traditional, the 50th star is a freebie.

## Code

You can get the code from this server or Github.