Moving code around with branches
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.
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 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
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
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)
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.