Posts Tagged ‘puzzle’

Twitter, Puddles and foldlr

Posted in Programming on May 9th, 2015 by Pavel – Be the first to comment

Blue Water DropsAbout 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.


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).


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

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 →

Scala for Project Euler

Posted in Programming, Scala on August 21st, 2010 by Pavel – 46 Comments

Scala logo, e^ipi + 1 = 0Project Euler is a collection of interesting computational problems intended to be solved with computer programs. Most of the problems challenge your skills in algorithm design rather than your knowledge of mathematics.

Thanks to short concrete problems and number-only solutions you don’t have to thinker with IDEs, GUI designers, programming libraries and frameworks, so Project Euler is an excellent tool for learning a new programming language or improving your core programming skills.
Continue reading →