Waterfall challenge

I just finished preparing slides for my new computational thinking class, and since I don’t want to start on anything new half an hour before I leave the office, I went on twitter and saw this interesting post. It’s a programming challenge described here, with an imperative solution, and with a functional solution described in the first post.

The imperative solution is rather involved and looks like this:

The functional solution is more elegant but also a bit slower. Broken into three functions, as it is in the blog post referenced above, it looks like this:

Well, if you want to write fast code, your first thought should be: can I come up with a simple algorithm. Later, you can worry about implementing it.

Here, we have a problem that involves figuring out if a wall at any given position has higher walls to the left and the right, and if so, what the smallest wall to the left or right are. So, very easily, we can break it down into collecting a list of the tallest wall seen to the left and to the right of each position. This is something we can compute with the accumulate and accumulate_right functions from purrr. After that, we can solve the problem by mapping over these two vectors and the vector of wall heights, and we have a three line solution to the challenge.

Not only is this solution much simpler, it is also a lot faster.

 

Update: Ok, if I had been smarter half an hour ago I would have seen that the pmap expression was overkill. A vector expression will work just fine and be faster.

 

Looking for collaborators

There are a few R packages I just wrote to have examples for my books, but I now think they might be generally useful. I just haven’t taken them to the point where they are. I know I am lazy enough to just leave them as they are, but if I could get collaborators who would like to work on them with me, I think we can make something out of them.

There is the bindr package that makes it just a tad easier to work with functions that return more than a single value.

Then there is the dfdr package that computes the derivative of a function with a bit of meta programming, that I can see greatly helping in numerical optimisation.

And, of course, there is the ralgo package I am working on right now for efficient data structures in R; I implement data structures in it as I write my next R book.

If anyone out there would like to be involved in a little bit of R programming with me, I would love to collaborate.

Amazon search

Uhoo! I managed to figure out how to embed a search on Amazon for my books on my books page. It looks like this:

Cool, right?