Pavel Fatin

About a year ago I happen to devise a solution (spoiler!) to a puzzle latter known as “Twitter’s waterflow problem”. Despite the number of alternative solutions, my original approach still stand out in its own way, and can be used to demonstrate a few peculiar things about recursion and list folding.

The puzzle probably existed before Twitter itself, yet it received great popularity after Michael Kozakov’s post about his interview at Twitter. As Reddit commenter noticed, “luxury of time and hindsight are wonderful things indeed”, so here goes the problem specification.

Specification

We are given a list of numbers, representing walls of different height. The goal is to determine how much rain water can be accumulated between the walls.

Here’s a visual representation of [2,5,1,2,3,4,7,7,6]:

In this case, the amount of accumulated water is 10 (note that there are no implicit side walls).

Requirements

Because of the puzzle popularity, many solutions, in different programming languages, were posted:

• Comments to Michael’s Gist (spoiler!)
• Comments on Reddit (spoiler!)

Approach, conciseness, performance and even correctness of those solutions vary greatly. What kind of solution do we want? It must be:

• efficient (O(n)time complexity),
• concise (1-5 lines of code),
• compatible with linear-access sequences (like list),
• preferably “functional”.

Now you may take your time and try to solve this problem by yourself before reading any further. In this way, you will not only enjoy a rather cute puzzle, but be able to comprehend with greater clarity what I’m going to show next.
Continue reading →

The famous Ninety-Nine Prolog problems (by Werner Hett) transcended their original purpose and became a popular set of exercises for languages other than Prolog.

Solving these puzzles (and comparing your solutions with solutions of others) is a good way to “get a feel” for programing language and to explore idiomatic approaches to particular kind of problems.

Today we can easily find solutions to the problems in almost any wide-spread programming language. However most of the attempts use a single programing language and provide only one solution to each problem.

By providing multiple types of solutions we can enrich our programming “toolbox” and learn pros and cons of various methods. By using several programming languages simultaneously we can easily correlate different programming paradigms and explore limits of language expressive power.

Here goes my take on Ninety-Nine Problems in:

• Scala,
• Java,
• Clojure,
• Haskell.

All the code is available as a GitHub repository.
Continue reading →