Advent of Code F# – Day 10

Yan Cui

I help clients go faster for less using serverless technologies.

The source code for this post (both Part 1 and Part 2) is available here and you can click here to see my solutions for the other Advent of Code challenges.

Description for today’s challenge is here.


Day 10 is nice and easy, and the solution I came up with is less than 20 lines of code, so I’m gonna leave it here and walk you through it:


So the bulk of the way happens in the fold inside the read function, which, starting with the empty list as the accumulated state, the following happened:

  1. saw ‘3’, acc state became [ (1, ‘3’) ]
  2. saw ‘1’, head of acc state is on ‘3’, so acc sate became [ (1, ‘1’); (1, ‘3’) ]
  3. saw ‘1’, head of acc state is also on ‘1’, so acc state became [ (2, ‘1’); (1, ‘3’) ]
  4. saw ‘3’, head of acc state is on ‘1’, so acc state became [ (1, ‘3’); (2, ‘1’); (1, ‘3’) ]

After the fold, we still need to reverse the list, and then construct the output string as “132123…”.

To answer the challenge, we just iteratively apply the read function (I used a fold here, but you can equally just write it as a recursive function), and voila!

Part 2 is identical, with the only difference being that read is invoked 50 times instead of 40.


Whenever you’re ready, here are 4 ways I can help you:

  1. If you want a one-stop shop to help you quickly level up your serverless skills, you should check out my Production-Ready Serverless workshop. Over 20 AWS Heroes & Community Builders have passed through this workshop, plus 1000+ students from the likes of AWS, LEGO, Booking, HBO and Siemens.
  2. If you want to learn how to test serverless applications without all the pain and hassle, you should check out my latest course, Testing Serverless Architectures.
  3. If you’re a manager or founder and want to help your team move faster and build better software, then check out my consulting services.
  4. If you just want to hang out, talk serverless, or ask for help, then you should join my FREE Community.


8 thoughts on “Advent of Code F# – Day 10”

  1. nice, I had my solution implemented with fold and builiding temporary strings (instead of just a list of tuples like you did) and it took an hour to compute the result for 50 iterations :)

  2. Really, really nice: a totally “F#-y” solution. Your sense of style in F# is the best I’ve seen so far. I cheated and did it with a .NET List of bytes. :) Runs fast but reeks of C++ sort of self-defeating.

  3. It shows how new I am to F# that it wouldn’t have even occurred to me to use anything other than the sequence type as an accumulator. That’s something I’m going to need to add to my repertoire.

    I wrote the prettiest little recursive function to do it. Unfortunately, after 29 iterations you get a stack overflow. Does F# pass lists by value on the stack?

  4. F# list is a ref type so they’re not passed by value.

    The problem is here:

    > | n::t -> count::lastNum::nextNum n 1 t

    This is not tail recursive (see for details on tail recursion if you’re not familiar with the concept)

    In this case, ‘count’ and ‘lastNum’ has to be kept around until ‘nextNum n 1 t’ returns, so you can’t optimize away the stack frame for each recursion and why you get a SO exception.

    The easiest way to fix this would be to take in an ‘accumulator’ in your recursive function, which in this case could be the (count, number) list you have collected so far. For example, you might write something along this line :

  5. Thanks very much for that explanation. That makes perfect sense.

    I see what you mean by adding an accumulator to the recursive function.In this case, the accumulator basically acts as a private stack and that’s why you have to reverse it at the end. Am I reading that right?

  6. Yup, that’s correct, at the end of the recursive function, our accumulator becomes elemN::…::elem2::elem1, so we have to reverse it.

  7. Pingback: Look-and-say: F# | Viral F#

Leave a Comment

Your email address will not be published. Required fields are marked *