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.


    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 =
            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
            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.


    You can get the code from this server or Github.

    Neil Smith

    Read more posts by this author.