Advent of Code 2019 day 2 in F#

Question

I sped through the 5hr F# pluralsight course this week-end and thought I'd sement my learning by going through as many Advent of Code puzzles I could with this new learning. However, already on day 2 I'm starting to question whether I'm too biased from C syntax and imperative coding to do it "right".

I really really miss being able to break from for loops for the second solution here. Sure I could make a while loop and have a mutable i and j, but it seems wrong either way. Also, I'd like function pointers for the "ops", but that's just a matter of doing some more work I guess.

In any case, some pointers on things to improve and make more declarative in the code would be super appreciated. Would really like to get going on the right foot before running off to day 3.

open System
open System.IO
let parse = fun (x:String) -> x.Split ',' |> Array.map int
let run (ops:int[]) = 
 let mutable i = 0
 while i < ops.Length do
 match ops.[i] with
 | 1 ->
 let a = ops.[ops.[i+1]]
 let b = ops.[ops.[i+2]]
 ops.[ops.[i+3]] <- a + b
 i <- i + 4
 | 2 ->
 let a = ops.[ops.[i+1]]
 let b = ops.[ops.[i+2]]
 ops.[ops.[i+3]] <- a * b
 i <- i + 4
 | 99 ->
 i <- ops.Length
 | _ ->
 printfn "doh %A" i
 ops
let test = parse >> run
let test1 = test "1,0,0,0,99"
let test2 = test "2,3,0,3,99"
let test3 = test "2,4,4,5,99,0"
let test4 = test "1,1,1,4,99,5,6,0,99"
let input = parse <| File.ReadAllText (Path.Combine [|__SOURCE_DIRECTORY__;@"input.txt"|])
let prog1 = Array.copy input
prog1.[1..2] <- [|12;2|]
run prog1 |> ignore
let exp = 19690720
let mutable solNounVerb = (0, 0)
for i = 0 to 100 do
 for j = 0 to 100 do
 let prg = Array.copy input
 prg.[1..2] <- [|i;j|]
 run prg |> ignore
 if prg.[0] = exp then
 solNounVerb <- (i, j)
let sol2 = (fun (i, j) -> i * 100 + j) solNounVerb

• Aaron Powell: Here is the exercise you're referring to, for others looking for it

Answer 1

Possibly not the best solution, but here's one that uses F# more extensively:

let rec processProgram (i: int) (ops: int list) =
 match ops with
 | opCode :: aPos :: bPos :: outPos :: rest when opCode = 1 -> // add op code
 let a = ops |> List.item aPos
 let b = ops |> List.item bPos
 let complete = [opCode; aPos; bPos; outPos] @ processProgram (i + 4) rest
 let (left, right) = complete |> List.splitAt outPos
 left @ [a + b] @ (right |> List.skip 1)
 | opCode :: aPos :: bPos :: outPos :: rest when opCode = 2 -> // multiple op code
 let a = ops |> List.item aPos
 let b = ops |> List.item bPos
 let complete = [opCode; aPos; bPos; outPos] @ processProgram (i + 4) rest
 let (left, right) = complete |> List.splitAt outPos
 left @ [a * b] @ (right |> List.skip 1)
 | head :: rest when head = 99 -> // terminate
 ops
 | _ ->
 failwith "Unsported opcode"

I've turned the function into a recursive function with let rec so that it can be called from within itself, I'll generally use this rather than a loop.

Next I'm using list rather than array so that I can pattern match on the operations. Let's look at that:

match ops with
| opCode :: aPos :: bPos :: outPos :: rest when opCode = 1 -> // add op cod

This expects the list to have at least 4 elements, and I'm destructing it into the pieces we care about, opCode (what we're doing), aPos and bPos (where in the instruction set the values we want are) and outPos (where to put the output in the instruction list). It's then got a when test on the end to check the value of the opCode so we can hit the right op code branch.

When the match is hit we grab the values from their current pos and then process the rest of the instruction set, generating a new list with:

let complete = [opCode; aPos; bPos; outPos] @ processProgram (i + 4) rest

The @ operator concats two list's together.

Then we'll split it on the outPos:

let (left, right) = complete |> List.splitAt outPos

This gives us a tuple of int list * int list that we deconstruct into two variables and lastly we rebuild the list through concatinations:

left @ [a + b] @ (right |> List.skip 1)

We use the left part to start with, as it is all up until the outPos, then insert the result of the op-code (add in this place) and then concat-ing the right but skipping outPos which is the head of the list.

Side note: it's not stated in the requirements that you can update positions beyond the current op stack, so I didn't implement that, it'll only do reverse-updates.

• Lars-Erik: Lots of useful info here. Thanks! Think I'll also look into using sequences.

Answer 2

A first simple clean up could be made here:

 | 1 ->
 let a = ops.[ops.[i+1]]
 let b = ops.[ops.[i+2]]
 ops.[ops.[i+3]] <- a + b
 i <- i + 4
 | 2 ->
 let a = ops.[ops.[i+1]]
 let b = ops.[ops.[i+2]]
 ops.[ops.[i+3]] <- a * b
 i <- i + 4

The two entries are equal except from the operators (+ and *). So you could define a function that takes an operator as argument and return the next i:

let operation i oper (ops: int[]) = 
 let a = ops.[ops.[i+1]]
 let b = ops.[ops.[i+2]]
 ops.[ops.[i+3]] <- oper a b
 i + 4

This will clean up the main loop to:

let run (ops:int[]) = 
 let mutable i = 0
 while i < ops.Length do
 match ops.[i] with
 | 1 -> i <- operation i (+) ops
 | 2 -> i <- operation i (*) ops
 | 99 -> i <- ops.Length
 | _ -> printfn "doh %A" i
 ops

---

The answer in F# to loops updating mutable variables is often (if not always) recursion (optimally with tail calls). Changing your run function to use recursion could be like this:

let run (ops:int[]) = 
 let rec runner i =
 match ops.[i] with
 | 1 -> runner (operation i (+) ops)
 | 2 -> runner (operation i (*) ops)
 | 99 -> ops
 | _ -> failwith (sprintf "Invalid value at index %d" i)
 runner 0

• Lars-Erik: Thanks, that was really useful! That's what I meant by function pointers. +1
• Lars-Erik: Not to mention tail calls. The Advent of Code puzzles will definitely exhaust the stack.