From time to time a programming problem comes a long and hardcore nerd snipes me. Today was no different when someone in the phillydev slack posted:
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.
Breaking this down, finding all of the possible decodings of a encoded message seemed like a reasonable place to start. I had recently watched this youtube video doing suduko and finding all of the possible solutions recursively.
So my first pass was able to find the first encoded message type, but stopped there.
So here it looks through all of the possible mappings and when it matches, it
recurses on the left. When there is no more data to check, it returns. This
gets the first alphabetically matching message: The given example of
So to not stop after the first, my instinct was to replace
but then I just ended up with a ton of recursive generators and unwinding was a
pain. So I revisited the video so see how he was doing it with Sudoku and it
was through the use of
global. Not a fan, but I got a working solution.
Again not a big fan of using
global but it worked and it established a pattern;
pass the built string into the child stack frame, and if the search is exhausted
for a given branch, append the built string to a global list of results. So using
the rescursion to do the search, but not using the recursive results to try and
return a data structure that has to be parsed to get the final answer.
With the presence of
global, I wasnt quite happy with this solution yet, so I
tried using a different global esq pattern, default parameters.
This solution was a lot cleaner, but ultimately I traded one antipattern for another;
the trick mutable defaults. The problem with mutable defaults immedeiately reared
its head when I went to add some doctests. The
(that is how it shares it across stacks), but that also means it only works for
1 call, then all the rest still have the results of the previous runs included.
I went to fix this first by making the list instantiation outside of the function,
and therefore it would still be passing a reference to the list all the way down,
but then the function basically was a procedure to fill a given list with the
results, and the side effect driven nature of that made me feel dirty. So in
the interest of functional purity, I fell back to the recommeneded workaround
for mutable defaults;
Back to functional purity, and a nice and clean signature and all of my tests are passing. This was a fun little problem and thinking recursively is always a challenge.