Advent of Code 2019 day 9

Day 9 sees yet another return to the Intcode machine. If you weren't able to get along with this sort of challenge, there's a lot of this year's Advent of Code you won't be able to access.

There are four changes in the Intcode machine today.

1. Larger, potentially unbounded, values in memory locations. The indirect addressing also means the address can be arbitrarily large as well.
2. A new addressing mode, Relative.
3. The contents of a memory cell default to 0 if it's not been access before.
4. The use of addressing modes when determining where to write a value. (Up until now, only Position mode has been allowed for this.)

Dealing with these changes doesn't require great changes in the logic of the Intcode interpreter, but it does mean some changes in the low-level aspects of its implementation.

Large values mean that a lot of Int parameters now become Integer. Because we need Integer keys for memory, the Memory changes from an IntMap to a more generic Map. The Machine also has a relative base, _rb; makeMachine sets that to 0.

type Memory = M.Map Integer Integer

data Machine = Machine { _memory :: Memory
                       , _ip :: Integer
                       , _inputIndex :: Int
                       , _rb :: Integer
                       } 
               deriving (Show, Eq)

type ProgrammedMachine = RWS [Integer] [Integer] Machine

data ParameterMode = Position | Immediate | Relative deriving (Ord, Eq, Show)

generateMode gets an extra term in its case statement for the new mode.

The use of the Relative mode means the relative base has to be passed into perform, and any changed relative base returned from that function. perform also needs an extra clause to deal with operation 9.

perform 9 ip modes rb mem = (mem, ip + 2, rb + a)
    where a = getMemoryValue (ip + 1) (modes!!0) rb mem

fetchInput also needs to be passed the mode, so that it knows where to write the fetched value.

The combination of the extra mode, its use in writing values, and the requirement to provide a default value on read, all mean that getMemoryValue and iInsert have to change. M.findWithDefault gives the desired default value. For the non-immediate modes, I have an explicit second function call to find the actual location to use.

getMemoryValue :: Integer -> ParameterMode -> Integer -> Memory -> Integer
getMemoryValue loc Position rb mem = getMemoryValue loc' Immediate rb mem
    where loc' = M.findWithDefault 0 loc mem
getMemoryValue loc Immediate _ mem = M.findWithDefault 0 loc mem
getMemoryValue loc Relative rb mem = getMemoryValue loc' Immediate 0 mem
    where loc' = rb + M.findWithDefault 0 loc mem

-- indirect insert
iInsert loc Position _rb value mem = M.insert loc' value mem
    where loc' = M.findWithDefault 0 loc mem
iInsert loc Immediate _rb value mem = M.insert loc value mem
iInsert loc Relative rb value mem = M.insert loc' value mem
    where loc' = rb + M.findWithDefault 0 loc mem

Beyond that, there's not much to do with the interpreter.

Observations

I have a couple of comments on the puzzle, though. One is that the puzzle text claims this is a "complete" Intcode interpreter. I don't believe that for a minute! If nothing else, why are there nine operations defined, but two digits reserved for opcodes? What will that extra digit be used for?

The other comment was the very useful test program for this day. I started by ignoring the parameter modes for writing, on the basis that I could handle it if I got the wrong answer. When I ran the test program, it generated code 203, showing the opcode of failure (the read operation, using Relative mode for storing the value). That led me straight to the fix I had to make. Well done Eric for the useful utility!

I'm tempted to move this Intcode implementation off into a separate module, loadable into all the Intcode-using solutions. But I'm expecting it will need to change in subsequent puzzles, so I'm not sure much will be gained from it.

Finally, I seem to have quite accidentally created something efficient. Several people in the solution megathread commented that their Part 2 takes a long time to run, and executes some 370,000 Intcode instructions. My implementation runs almost instantly.

Code

The code is available on this domain, and on Github.

Refactoring: the Intcode module

I've also moved the Intcode interpreter into a separate module. Using this required changes to what I wrote for day 2, day 5, and day 7. Eric (and friends) and assured me that the interpreter won't change. We shall see!