December 7, 2020

Advent of Code 2019 day 25

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.