Advent of Code F# – Day 10

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:

day10_01

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.

8 Comments

  1. Horia Toma   •  

    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. Boris Kogan   •  

    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. Yan Cui   •  

    Thanks :-) you should check out Scott Wlaschin’s blog (http://fsharpforfunandprofit.com/) as well, I have taken a lot of inspirations and hints from Scott regarding style and approach.

  4. Bryan Slatner   •  

    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?

  5. Yan Cui   •  

    F# list is a ref type https://msdn.microsoft.com/en-us/library/ee370372.aspx 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 http://blogs.msdn.com/b/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx 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 : https://gist.github.com/theburningmonk/46a4f513f9c87ddd5f10

  6. Bryan Slatner   •  

    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?

  7. Yan Cui   •  

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

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

Leave a Reply

Your email address will not be published.