BerandaComputers and TechnologyAdvent of Code in Haskell Preparation Part 2: Where We Build a...

Advent of Code in Haskell Preparation Part 2: Where We Build a Computer

So day one went fairly smooth. Nothing too difficult to impoement, 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.

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.

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.
*Main>

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
*Main>

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"
["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]
[1,2,99,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.

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:

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
3101844
8478

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
3101844
8478
(1.04 secs, 3,337,885,928 bytes)
*Main>

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
3101844
8478

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

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

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.

Read More

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments