2
\$\begingroup\$

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
\$\endgroup\$
1

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Lots of useful info here. Thanks! Think I'll also look into using sequences. \$\endgroup\$
    – Lars-Erik
    Mar 24, 2020 at 13:22
1
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thanks, that was really useful! That's what I meant by function pointers. +1 \$\endgroup\$
    – Lars-Erik
    Mar 24, 2020 at 13:20
  • 1
    \$\begingroup\$ Not to mention tail calls. The Advent of Code puzzles will definitely exhaust the stack. \$\endgroup\$
    – Lars-Erik
    Mar 24, 2020 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.