Yan Cui
I help clients go faster for less using serverless technologies.
This article is brought to you by
Don’t reinvent the patterns. Catalyst gives you consistent APIs for messaging, data, and workflow with key microservice patterns like circuit-breakers and retries for free.
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:
- saw ‘3’, acc state became [ (1, ‘3’) ]
- saw ‘1’, head of acc state is on ‘3’, so acc sate became [ (1, ‘1’); (1, ‘3’) ]
- saw ‘1’, head of acc state is also on ‘1’, so acc state became [ (2, ‘1’); (1, ‘3’) ]
- 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 3 ways I can help you:
- Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
- I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
- Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.
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 :)
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.
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.
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?
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
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?
Yup, that’s correct, at the end of the recursive function, our accumulator becomes elemN::…::elem2::elem1, so we have to reverse it.
Pingback: Look-and-say: F# | Viral F#