Where We Build a Computer

Posted on Nov 20, 2020

Advent of Code 2019, day 2

So day one went fairly smooth. Nothing too difficult to implement, as you can expect from a first challenge. Since I’ve done some of the challenges last year (implemented them in Go), I know that there will be a rapid ramp-up in difficulty and that a number of challenges build “on top of each other”. Perfect opportunities to start exploring how to write reuseable Haskell code.

But we’ll tackle that when the opportunity actually presents itself and not make things more difficult than needed.

The challenge: Build a sort of computer

I will not describe the entire problem again, Advent of Code is way better at that. But to make things simple: read numbers from a file, start at the first number, execute an action based on the number and write the result of the action somewhere.

In the first “note” (I wouldn’t call these ramblings articles) I started out with some boilerplate by setting up the required files for Cabal, but lets not do that this time, since I realised we don’t really need it (just yet).

I’ll just create a directory, create a Main.hs file and run stuff from GHCi to get things working. In the end I’ll try to modify the program to take the input program (intcode program) from the standard input, just as a challenge.

Stubbing out the program

Lets get our environment setup.

jeroen@DESKTOP:~/taoc19$ cd day2
jeroen@DESKTOP:~/taoc19/day2$ touch Main.hs
jeroen@DESKTOP:~/taoc19/day2$ ghci
GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
Prelude> :load Main.hs
[1 of 1] Compiling Main             ( Main.hs, interpreted )
Ok, one module loaded.

Great, that worked. The Main.hs file is still empty, but it works, no Cabal or Stack needed to get something done. Now to open the editor from GHCi (with :edit or :e) and start implementing this intcode machine.

*Main> :e
editor not set, use :set editor
*Main> :set editor vim

Oops, let make a mental note to actually set $EDITOR in my environment, guess I don’t use it as often as thought.

So filling the Main.hs file with the same boilerplate as last time:

module Main where

main :: IO ()
main = do
        raw <- readFile "input.txt"
				        print raw

Running the main function in GHCi does exactly as expected, it outputs the contents of the input.txt file. No big deal.

So after stubbing out the general outline of the program this is what I came up with:

module Main where

main :: IO ()
main = do
        raw <- readFile "input.txt"
        -- split the input up into instructions (split on ,)
        let input = parseInput raw
        -- run the program
        let output = runProgram input
        -- get the value from first position in memory
        let solution = output !! 0
        print solution

-- parseInput takes a string as input and outputs
-- an array of integers
parseInput = id

-- runProgram takes a piece of memory and returns
-- the state of memory after the program has completed
runProgram = id

So we have two high level functions to define, sounds doable.

First challenge is to find a way to split the input string on the comma’s separating the individual memory values. I heard “real Haskell programmers” use Hoogle to find the functions they are looking for based on the type signature they think “should get the job done”.

Since we’re looking to split a string based on a different string, the required type signature should look something like String -> String -> [String]. But after searching Hoogle for it I couldn’t find anything that looks like it might do the job. Of course I could have just searched for a function called split, or some variation of it, but I wanted to do it “the real way"TM. Luckily, after reading an article on Monday Morning Haskell I remembered that Haskell also has a Text type, offering some additional string handling abilities.

💡 I remain blisfully unaware of other benefits of using the `Text` type, please enlighten me if you want to.

Re-running the search with Text -> Text -> [Text] yielded exactly the result I was looking for: splitOn. So feeding the raw data into splitOn and splitting on , gives us a [String] which we only need to convert into a [Int]. The splitOn function is included in the Data.Text package, so we’ll have to import that as well. But then, the readFile we use to load the data gives us a String, so we’ll have to import Data.Text.IO as well to be able to utilize the readFile function from that (all found by using Hoogle).

At this point, let’s reconsider our solution of using the splitOn function as provided by Data.Text and research Hoogle for a different splitOn function. Turns out, there is a splitOn variant in Data.List.Split that is generic (i.e. it accepts anything of the type Eq a => [a] -> [a] -> [[a]]) so will probably accept a String as well. Let’s try it out in GHCi.

GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
Prelude> :m + Data.List.Split
Prelude Data.List.Split> splitOn "," "1,2,3,4,5"
Prelude Data.List.Split> :t splitOn "," "1,2,3,4,5"
splitOn "," "1,2,3,4,5" :: [[Char]]

Awesome, we get something back that looks like a [String] (since a String is a [Char]). So we’ll be good to go to use this.

So let’s write a simple function to do this, iterate (map) over all the individual items and read them into a [Int].

-- parseInput takes a string as input and outputs
-- an array of integers
-- parseInput :: String -> [Int]
parseInput :: String -> [Int]
parseInput x = map read $ splitOn "," x

That takes care of getting our input ready. The second step involves a small nuance in the challenge:

    Once you have a working computer, the first step is to restore the gravity
    assist program (your puzzle input) to the "1202 program alarm" state it had
    just before the last computer caught fire. To do this, before running the
    program, replace position 1 with the value 12 and replace position 2 with the
    value 2. What value is left at position 0 after the program halts?

So we have to set the first value of the program to 12, and the second value to 2. This calls for a function to replace a certain index in a List. At this point we could choose to replace the usage of List with Data.Vector which offers this functionality by default. But for simplicity sake, let’s stay with our current solution and create a replace function that takes an Int (the index), another Int (the new value) and a List, and returns a List. To build this function we use the splitAt function provided by Data.List.Split, which we imported in the previous step anyway.

replace :: Int -> Int -> [Int] -> [Int]
replace i v xs = let (hxs, _:txs) = splitAt i xs in
								   hxs ++ v : txs

which, when tested in GHCi, yields exactly what we want:

[1 of 1] Compiling Main             ( Main.hs, interpreted )
Ok, one module loaded.
*Main> replace 2 99 [1,2,3,4,5]

So we can construct our actual program with replace 1 12 $ replace 2 2 input, store it in a variable and use that to run the actual program.

💡 Turns out, `Data.List.Index` has a function called `setAt` which does EXACTLY the same as our `replace` function. Unfortunately, this is only available as an external library, so I choose not to use it.

Now things get interesting

We have a list of numbers, which somehow translates to instructions to be executed by a virtual computer, mutating memory. Sounds easy right?

IMO, this is actually the easy part, it involves us creating a function that takes 4 numbers from the list, applying a certain mutation to memory based on the values in those four numbers, taking the next four numbers, etc. Untill we find the number 99.

runProgramAt :: Int -> [Int] -> [Int]
runProgramAt pc m = let opcode = m !! pc
												left = m !! (m !! (pc + 1))
												right = m !! (m !! (pc + 2))
												result = m !! (pc + 3)
												next = pc + 4 in
										case opcode of
												-- 99 signals the end of the program, just return
												-- the entire memory
												99 -> m
												-- 1 indicates addition (left + right -> result), continue
												-- with the next operation at pc + 4
												1 -> runProgramAt next $ replace result (left + right) m
												-- 2 indicates multiplication (left * right -> result), continue
												-- with the next operation at pc + 4
												2 -> runProgramAt next $ replace result (left * right) m
												-- and to satisfy the compiler, give it a fallback case
												-- which just returns the entire memory and stops
												otherwise -> m

Now when I change my runProgram function to use this function to run the program starting at position 0 by changing it into runProgram = runProgramAt 0, and running this from GHCi I get my correct answer:

*Main> main

Finding a certain solution

Really typical, part 2 of the challenge involves us finding a set of input that yields a certain output. This reeks like a standard brute-force search. These can be done really efficiently in Haskell by using list comprehensions. So probably we’ll end up with something like:

findSolution :: Int -> [Int] -> Int
findSolution s m = head [noun * 100 + verb | 
                    noun <- [0..99], 
                    verb <- [0..99], 
                    runProgram (replace 1 noun $ replace 2 verb m) !! 0 == s]

When calling this function with the input supplied by the challenge:

-- get the required input to complete part 2
let nounverb = findSolution 19690720 input
print nounverb

it yields the correct solution, right away:

[1 of 1] Compiling Main             ( Main.hs, interpreted )
Ok, one module loaded.
*Main> main

where the second answer is the answer for part 2. Given that I ran this in GHCi I expected it to be a bit slower, so let’s see if that’s the case:

*Main> :set +s
*Main> main
(1.04 secs, 3,337,885,928 bytes)

That seems about right, let’s try compiling and timing this as a standalone binary:

jeroen@DESKTOP:~/taoc19/day2$ ghc Main.hs
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...
jeroen@DESKTOP:~/taoc19/day2$ time ./Main

real    0m0.567s
user    0m0.567s
sys     0m0.000s

That’s actually quite an improvement, and more than acceptable for a brute-force solution ;-)

Todo list

Let’s call it a day for challenge number 2. Since the challenge tells us we’ve got to keep the IntCode computer stored away for later challenges, we’ll look at re-using what’s already there in the next challenge when we need to IntCode computer.