6
\$\begingroup\$

I'm working on day 3.2 of Advent of Code.

The task for this challenge is to create a number spiral where each element is the sum of all of its neighbors. Using this spiral, we have to find the first element that's bigger than the target number.

Here's an example of the spiral

147  142  133  122   59
304    5    4    2   57
330   10    1    1   54
351   11   23   25   26
362  747  806--->   ...

This is the code I have for it

let inputFiles = "C:\FSharpWorkspace\AdventOfCode\AdventOfCode\InputFiles"
let read() = stdin.ReadLine()
let readInt() = Int32.Parse(read())
let (+/) path1 path2 = Path.Combine(path1, path2)
let readChallengeInput challengeNumber =
    let challenge = challengeNumber.ToString()
    if File.Exists(inputFiles +/ challenge) then File.ReadAllText(inputFiles +/ challenge) else stdin.ReadLine()

let spiralSum position =

    // These edge cases are hard, so we ignore them.
    match position with
    | 0 -> Seq.cast<int> [|0|]
    | 1 -> Seq.cast<int> [|1|]
    | _ ->

    let mutable spiral = Array2D.create position position 0

    // 2 is weird because it's the only size where the center doesn't have at least one element on each side.
    let generateInitialCoord() = match position with | 2 -> 0 | _ -> position / 2
    let mutable y = generateInitialCoord()
    let mutable x = generateInitialCoord()
    let mutable dy = 0
    let mutable dx = -1
    spiral.[y, x] <- 1
    let neighbors = [|
        [|1; 1|]
        [|1; 0|]
        [|1; -1|]
        [|0; 1|]
        [|0; -1|]
        [|-1; 1|]
        [|-1; 0|]
        [|-1; -1|]
    |]

    // Make sure we're in the bounds of the array.
    let isValidCoord c = 0 <= c && c < position
    let isValidCoordPair y x = isValidCoord y && isValidCoord x
    let mutable counter = 0;

    while isValidCoordPair x y && counter <= (position * position) do
        let r = neighbors 
                |> Seq.where (fun n -> isValidCoordPair (y + n.[0]) (x + n.[1]))
                |> Seq.map (fun n -> spiral.[y + n.[0], x + n.[1]]) 
                |> Seq.sum
        spiral.[y, x] <- match r with | 0 -> 1 | _ -> r 
        let turnLeft = 
            match (dy, dx) with
            | (1, 0) -> (0, 1)
            | (0, 1) -> (-1, 0)
            | (-1, 0) -> (0, -1)
            | (0, -1) -> (1, 0)
            | _ -> raise(ArgumentOutOfRangeException())
        let (newDy, newDx) = turnLeft
        let newY = y + newDy
        let newX = x + newDx

        // We can make a left turn if it wouldn't take us outside the bounds of the array
        // and we haven't visited the square before.
        if isValidCoordPair newY newX && spiral.[newY, newX] = 0
        then
            y <- newY
            x <- newX
            dy <- newDy
            dx <- newDx
        // Otherwise we go straight.
        else
            y <- y + dy
            x <- x + dx
        counter <- counter + 1

    // The last iteration of the loop leaves us at an invalid square, so we step back one.
    let adjustCoord c = if isValidCoord c then c else if c >= position then c - 1 else c + 1
    y <- adjustCoord y
    x <- adjustCoord x

    // Flatten our 2d array into a seq<int>
    Seq.cast<int> spiral


let sixthChallenge() =
    let input = Int32.Parse (readChallengeInput 5)
    // 10 iterations is enough to get us close to Int32.MaxValue and way more than high enough for the target.
    Seq.init 10 id 
    |> Seq.map (fun i -> spiralSum i) 
    |> Seq.collect id 
    |> Seq.sortBy id
    |> Seq.find (fun v -> v > input)

[<EntryPoint>]
let main argv = 
    let challenge = readInt()
    let result = match challenge with
                 //| 1 -> firstChallenge()
                 //| 2 -> secondChallenge()
                 //| 3 -> thirdChallenge()
                 //| 4 -> fourthChallenge()
                 //| 5 -> fifthChallenge()
                 | 6 -> sixthChallenge()
                 | _ -> raise (NotSupportedException())
    printfn "%A" result
    System.Console.ReadKey() |> ignore
    0 // return an integer exit code

I'm completely new to both F# and functional programming, so I would appreciate any style tips.

The big things I wanted to know are:

  1. Is there a better way to generate the neighbors array?

  2. Is there a way to lazily pipe such that each element gets evaluated by Seq.find (fun v -> v > input) as it's generated?

  3. Is there a way to not hard-code the loop iterations at 10 without getting an Integer overflow?

  4. I feel like I'm using mutable too much. Is there a way to cut down on the number of usages?

\$\endgroup\$
3
+50
\$\begingroup\$

Alright so there's a lot going on here, but the biggest thing I see is concern 4 you had: way too much mutable.

Here's the thing about mutable: it let's us do really unhealthy things, it lets us define processing that can go up, down, left, right, inside and outside, all without giving us any guarantee of what happened.

I also really don't like the while construct, so we're going to replace both those issues with one really fancy design pattern known as "recursive functions" with tail-call recursion.

Normally, a recursive F# function is easy to write:

let rec fn x =
    if x > 0 then x * ((x - 1) |> fn) else 1

This fn could be called factorial, it does everything required to calculate a factorial.

Here's the problem: this function is not tail-call recursive. It will throw a StackOverflowError at some point. (Guaranteed.)

This is caused by x * ..., this form of recursion requires that we make the recursive call before we finish this call. We can't complete until we get the rest of the data.

Now while the stack is large (this doesn't fail until x = ~1000000 for me), we can fix that, permanently. We do this through an "accumulator".

let fn x =
    let rec innerFn acc x =
        if x > 0 then innerFn (acc * x) (x - 1) else 1
    innerFn 1 x

Now the difference is that we create an innerFn that takes an acc and x, then it calls itself, but it calculates the new acc first, and the new x first, we could rewrite it as:

let fn x =
    let rec innerFn acc x =
        let newAcc = acc * x
        let newX = x - 1
        if x > 0 then
            innerFn newAcc newX
        else 1
    innerFn 1 x

So it proves that nothing else needs to happen, the last thing is the recursion.

Writing like this is called "tail-call recursion", the idea that the "recursive" call is the very last call to happen. If that is the case, then the function can recurse infinitely, and F# will rewrite this as a while loop in the JITter.

I'm telling you all this so that I can demonstrate the purpose of this: if we write this factorial algorithm as a while loop, it would look like the following:

let fn x =
    let mutable x1 = x
    let mutable acc = 1
    while x1 > 0 do
        acc <- x1 * acc
        x1 <- x1 - 1
    acc

So now we should see that the majority of your code can be rewritten as a tail-call recursive function. We see the relationship between mutable state and tail-call recursion, it's easy enough to write for such. I've blogged about this topic before, so I'm not going to go into too much detail, but the idea is to identify the following:

  1. What "state" needs to change for each call?
  2. What is the relationship between each call? How does the state need manipulated?
  3. What is the "sentinel", or terminating factor? (What value(s) / state(s) cause your function to finish recursion?)

Once you identify these, it's easy enough to rewrite for tail-call recursion. You can have as large or small an acc as you like, any state that changes between calls can be part of the acc. My example only has one, but technically the x is also an acc for x - 1, if it helps visualize.

I don't currently have time to write this for tail-call recursion for you, but I might do so tonight (so I wouldn't get disappointed too soon).


Another thing I really don't like, is this match at the beginning:

match position with
| 0 -> Seq.cast<int> [|0|]
| 1 -> Seq.cast<int> [|1|]
| _ ->

You're relying on the fall through case to perform the work. You'll see in a moment (as I now have some time to write for tail-call recursion) that the arrangement of a function should be:

  1. Staging / setup;
  2. Dependencies;
  3. Expression(s);

This is how I arrange my functions, always. You're currently mixing 2+3, and it make things harder to reason about. Ideally, you should have created a let algorithm position = ..., then in your match:

// These edge cases are hard, so we ignore them.
match position with
| 0 -> Seq.cast<int> [|0|]
| 1 -> Seq.cast<int> [|1|]
| v -> alg v

Problem solved, and we kept the match from bleeding anywhere.


Before I write the tail-call recursive example, I want to go over some issues I see with how you do things. Your dx and dy can be far improved, and you can stop relying on that exception to fix your match up in turnLeft:

type Direction = | Up | Left | Down | Right
let leftTurn = function | Up -> Left | Left -> Down | Down -> Right | Right -> Up
let dirOffset direction = 
    match direction with
    | Up -> (-1, 0)
    | Left -> (0, -1)
    | Down -> (1, 0)
    | Right -> (0, 1)

Now things start becoming clear, and you can see how the direction relates to the offset, but you're not relying on the offset itself. Your code becomes:

let turnLeft = direction |> leftTurn
let (newDy, newDx) = turnLeft |> dirOffset

One of the reasons we remove mutable state is because we get to something like this:

// We can make a left turn if it wouldn't take us outside the bounds of the array
// and we haven't visited the square before.
if isValidCoordPair newY newX && spiral.[newY, newX] = 0
then
    y <- newY
    x <- newX
    dy <- newDy
    dx <- newDx
// Otherwise we go straight.
else
    y <- y + dy
    x <- x + dx

Which, with mutable state, I didn't realize that dy and dx are the previous dy and dx, so our rewrite is:

// We can make a left turn if it wouldn't take us outside the bounds of the array
// and we haven't visited the square before.
if isValidCoordPair newY newX && spiral.[newY, newX] = 0
then
    y <- newY
    x <- newX
    direction <- turnLeft
// Otherwise we go straight.
else
    let (dy, dx) = direction |> dirOffset
    y <- y + dy
    x <- x + dx

This was more confusing than it should have been, so we'll correct that as we get to tail-call recursion.


Before I begin tail-call recursion, I want to introduce you to Seq.sumBy, which is a fun little function that does map + sum in one step:

let r = neighbors 
        |> Seq.where (fun n -> isValidCoordPair (y + n.[0]) (x + n.[1]))
        |> Seq.map (fun n -> spiral.[y + n.[0], x + n.[1]]) 
        |> Seq.sum

To:

let r = neighbors 
        |> Seq.where (fun n -> isValidCoordPair (y + n.[0]) (x + n.[1]))
        |> Seq.sumBy (fun n -> spiral.[y + n.[0], x + n.[1]]) 

Easy enough, right?


The final point to cover before tail-call recursion: currying. You don't see it, but you have two opportunities for currying that can remove a couple lambda's (fun ... -> ...):

let sixthChallenge() =
    let input = Int32.Parse (readChallengeInput 5)
    // 10 iterations is enough to get us close to Int32.MaxValue and way more than high enough for the target.
    Seq.init 10 id 
    |> Seq.map (fun i -> spiralSum i) 
    |> Seq.collect id 
    |> Seq.sortBy id
    |> Seq.find (fun v -> v > input)

Here, you do Seq.collect id and Seq.sortBy id, what if I told you that there's nothing different between Seq.map (fun i -> spiralSum i) and Seq.map spiralSum? Because there isn't.

The Seq.find is a little more interesting: because operators in F# can be treated as functions, we can actually create a partially applied function for v > input, by rewriting it as input < v, and then as (<) input, which takes the < operator and applies input as the left-hand argument:

let sixthChallenge() =
    let input = Int32.Parse (readChallengeInput 5)
    // 10 iterations is enough to get us close to Int32.MaxValue and way more than high enough for the target.
    Seq.init 10 id 
    |> Seq.map spiralSum 
    |> Seq.collect id 
    |> Seq.sortBy id
    |> Seq.find ((<) input)

Doesn't that clean things up just a bit? Interestingly, we could actually Seq.collect spiralSum even, because id is just the identity function, and then we can Seq.sort instead of Seq.sortBy id, because it's already numeric:

let sixthChallenge() =
    let input = Int32.Parse (readChallengeInput 5)
    // 10 iterations is enough to get us close to Int32.MaxValue and way more than high enough for the target.
    Seq.init 10 id 
    |> Seq.collect spiralSum 
    |> Seq.sort
    |> Seq.find ((<) input)

Alright, on to the fun stuff: tail-call recursion. We're going to start with the while loop, as it's the biggest kicker, and we'll go from there.

Your while loop depends on a few things, including all of the following:

  1. direction;
  2. spiral;
  3. y;
  4. x;
  5. counter;

These are all the things it has to mutate, so we're going to start rewriting it for tail-call recursion with the mutation first.

let rec algorithm () =
    if isValidCoordPair x y && counter <= (position * position) then
        let r = neighbors 
                |> Seq.where (fun n -> isValidCoordPair (y + n.[0]) (x + n.[1]))
                |> Seq.sumBy (fun n -> spiral.[y + n.[0], x + n.[1]]) 
        spiral.[y, x] <- match r with | 0 -> 1 | _ -> r 
        let turnLeft = direction |> leftTurn
        let (newDy, newDx) = turnLeft |> dirOffset
        let newY = y + newDy
        let newX = x + newDx

        // We can make a left turn if it wouldn't take us outside the bounds of the array
        // and we haven't visited the square before.
        if isValidCoordPair newY newX && spiral.[newY, newX] = 0
        then
            y <- newY
            x <- newX
            direction <- turnLeft
        // Otherwise we go straight.
        else
            let (dy, dx) = direction |> dirOffset
            y <- y + dy
            x <- x + dx
        counter <- counter + 1
        algorithm ()
    else ()
algorithm ()

Technically, that's it. We rewrote for tail-call recursion very easily, but we still use mutable. Now that we see the tail-call recursive example, it's easier to do the next step: integrate counter into the "algorithm" (I'm bad at naming things):

let rec algorithm counter =
    if isValidCoordPair x y && counter <= (position * position) then
        let r = neighbors 
                |> Seq.where (fun n -> isValidCoordPair (y + n.[0]) (x + n.[1]))
                |> Seq.sumBy (fun n -> spiral.[y + n.[0], x + n.[1]]) 
        spiral.[y, x] <- match r with | 0 -> 1 | _ -> r 
        let turnLeft = direction |> leftTurn
        let (newDy, newDx) = turnLeft |> dirOffset
        let newY = y + newDy
        let newX = x + newDx

        // We can make a left turn if it wouldn't take us outside the bounds of the array
        // and we haven't visited the square before.
        if isValidCoordPair newY newX && spiral.[newY, newX] = 0
        then
            y <- newY
            x <- newX
            direction <- turnLeft
        // Otherwise we go straight.
        else
            let (dy, dx) = direction |> dirOffset
            y <- y + dy
            x <- x + dx
        algorithm (counter + 1)
    else ()
algorithm 0  

So that's one mutable gone, and it was easy to do. Next, we want to eliminate direction methinks, because you don't use that after the algorithm runs, it's just state for the algorithm:

let rec algorithm counter direction =
    if isValidCoordPair x y && counter <= (position * position) then
        let r = neighbors 
                |> Seq.where (fun n -> isValidCoordPair (y + n.[0]) (x + n.[1]))
                |> Seq.sumBy (fun n -> spiral.[y + n.[0], x + n.[1]]) 
        spiral.[y, x] <- match r with | 0 -> 1 | _ -> r 
        let turnLeft = direction |> leftTurn
        let (newDy, newDx) = turnLeft |> dirOffset
        let newY = y + newDy
        let newX = x + newDx

        // We can make a left turn if it wouldn't take us outside the bounds of the array
        // and we haven't visited the square before.
        if isValidCoordPair newY newX && spiral.[newY, newX] = 0
        then
            y <- newY
            x <- newX
            algorithm (counter + 1) turnLeft
        // Otherwise we go straight.
        else
            let (dy, dx) = direction |> dirOffset
            y <- y + dy
            x <- x + dx
            algorithm (counter + 1) direction
    else ()
algorithm 0 Up

As you can see, we seed the initial direction as well as count, so things should start becoming more clear.

Here's something I've been wondering for the last 2 hours: why does this bit exist:

// The last iteration of the loop leaves us at an invalid square, so we step back one.
let adjustCoord c = if isValidCoord c then c else if c >= position then c - 1 else c + 1
y <- adjustCoord y
x <- adjustCoord x

It has no effect, because you never use y or x after your loop. You don't even need them after the loop, so we can integrate them like we have the others:

let rec algorithm counter direction y x =
    if isValidCoordPair x y && counter <= (position * position) then
        let r = neighbors 
                |> Seq.where (fun n -> isValidCoordPair (y + n.[0]) (x + n.[1]))
                |> Seq.sumBy (fun n -> spiral.[y + n.[0], x + n.[1]]) 
        spiral.[y, x] <- match r with | 0 -> 1 | _ -> r 
        let turnLeft = direction |> leftTurn
        let (newDy, newDx) = turnLeft |> dirOffset
        let newY = y + newDy
        let newX = x + newDx

        // We can make a left turn if it wouldn't take us outside the bounds of the array
        // and we haven't visited the square before.
        if isValidCoordPair newY newX && spiral.[newY, newX] = 0
        then
            algorithm (counter + 1) turnLeft newY newX
        // Otherwise we go straight.
        else
            let (dy, dx) = direction |> dirOffset
            algorithm (counter + 1) direction (y + dy) (x + dx)
    else ()
algorithm 0 Up y x

Now the only part we need post-loop is spiral, so we'll deal with it last because it's more complicated (but barely).

In regard to spiral, there are two things I need to make blatantly clear:

  1. The array type in F# is, by .NET definition, mutable. So you really don't need mutable on it, it's already mutable.
  2. We try to avoid mutable state, but sometimes it's just not simple. In our case, I'm going to leave it.

If I had more time (going holiday shopping with the GF soon) I would describe how we could eliminate mutating it, but I think this lesson stood to prove it's point: we can almost entirely avoid mutable state in F#, and we also learned a few cool tricks on the way.

\$\endgroup\$
  • \$\begingroup\$ I had no idea acc was a thing. I'm glad to know that I was right to be scared of how much I was using mutable. This gives me a lot to work on, thank you! \$\endgroup\$ – Morgan Thrapp Dec 15 '17 at 21:19
  • \$\begingroup\$ @MorganThrapp Well acc in F# is nothing special, but it has meaning to those of us in the language, much like i in C# is nothing special, but we all see it as an "iterator". We use acc to hold accumulated state for us to continue processing, which is a well-received practice in the community. (You'll see a lot of it, and there's nothing special or unique.) \$\endgroup\$ – 202_accepted Dec 15 '17 at 21:21
  • \$\begingroup\$ @MorganThrapp You may like the edited answer. ;) \$\endgroup\$ – 202_accepted Dec 16 '17 at 15:04
  • \$\begingroup\$ This is awesome. Thank you so much! I started rewriting parts of it, but this gives me even more to work on. \$\endgroup\$ – Morgan Thrapp Dec 17 '17 at 16:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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