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
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
: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
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
💡 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
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
-- 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
offers this functionality by default. But for simplicity sake, let’s stay with our current solution and create a
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
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