Menu

Subscribe

Functional puzzles (part 1)

As I've mentioned before, I have found the Advent of Code puzzles to be very useful in learning a new language.

I'd like to show how I wrote my first functional-style program (with immutable data structures and recursion) when trying to solve the first puzzle of AoC 2015. Spoilers ahead!

The language used doesn't really matter — I first did this in Elixir, and then again in Clojure, so I will stay in the domain of dynamically-typed functional languages. That is, I'll model my data as a combination of basic data structures and won't create type definitions for everything.

The puzzle

AoC puzzles are given in two parts; you solve the first, then the requirements change slightly. The first part of our puzzle is:

Santa is trying to deliver presents in a large apartment building, but he can't find the right floor - the directions he got are a little confusing. He starts on the ground floor (floor 0) and then follows the instructions one character at a time.

An opening parenthesis, (, means he should go up one floor, and a closing parenthesis, ), means he should go down one floor.

The apartment building is very tall, and the basement is very deep; he will never find the top or bottom floors.

For example:

  • (()) and ()() both result in floor 0.
  • ((( and (()(()( both result in floor 3.
  • ))((((( also results in floor 3.
  • ()) and ))( both result in floor -1 (the first basement level).
  • ))) and )())()) both result in floor -3.

To what floor do the instructions take Santa?

Let's start with some plain, imperative Javascript:

function santa(instructions) {  
  let floor = 0;
  for (let i of instructions) {
    if (i == '(') {
      floor += 1;
    } else {
      floor -= 1;
    }
  }
  return floor;
}

console.log(santa("(())")) // 0

(Let's assume that we won't get any weird characters in there.)

Keeping the same mindset, let's jump into Elixir. Try as you might, you won't find any loop construct in Elixir — no while, no goto, and the for construct is not what you might think.

The only tool we have to implement a loop is recursion, and we'll use that:

defmodule Santa do  
  defp santa([], floor) do
    floor
  end

  defp santa([h | t], floor) do
    if h == "(" do
      santa(t, floor + 1)
    else
      santa(t, floor - 1)
    end
  end

  def santa(instructions) do
    l = String.codepoints(instructions)
    santa(l, 0)
  end
end

IO.inspect Santa.santa("(())") # 0

Notice how we have 2 + 1 versions of the function. The first two are private and take two arguments, while the third one is public, takes one argument, and only converts the string into a list. This is all perfectly fine in Elixir.

Then, we use Elixir's pattern matching in function definitions to effectively say:

  • If the list is empty, we are done, here's the floor. This is the "stop clause" of our recursive function.
  • If the list has elements, get the first one, check what kind is it, then continue with the rest of the elements and the updated floor. This is the "work clause".

Note how floor is initialized in the 1-arity function, then updated and eventually returned by the other two functions. In functional programming, this kind of pattern is usually called "accumulator passing", and is used to ensure that our recursive calls can be optimized by the compiler so we don't suffer a stack overflow (good luck googling for that).

A slightly more idiomatic Elixir code would look like this:

defmodule Santa do  
  defp santa([], floor), do: floor

  defp santa(["(" | t], floor) do
    santa(t, floor + 1)
  end

  defp santa([")" | t], floor) do
    santa(t, floor - 1)
  end

  def santa(instructions) do
    l = String.codepoints(instructions)
    santa(l, 0)
  end
end

This more specific pattern matching — we are not only getting the first element of the list, but we also check what it is and do the right thing without a conditional. Plus, if we pass something that's not a ( or a ), our process will promptly crash.

The code above represents pretty much the first Elixir code I've ever written. Today I would probably write something like this:

defmodule Santa do  
  def santa(instructions) do
    instructions
    |> String.codepoints
    |> Enum.map(fn("(") -> 1
                  (")") -> -1 end)
    |> Enum.reduce(fn(x, acc) -> x + acc end)
  end
end

The |> is called the "pipe operator" and allows you to "pipe" the return of a function as the first argument to the next function etc.

We are using the map and reduce functions to go at a higher abstraction level where we reason about the whole problem in one go.

This approach allows you to start thinking about the code in terms of plain language:

  • Take the instructions...
  • convert them to individual characters...
  • replace "(" with 1 and ")" with -1...
  • add everything together.

Note that we never even mention the "floor" by any name — the function should probably be named floor. If the computation was more complex, I'd break it into smaller pieces just to name a few variables for clarity.

For fun, here is the same approaches in Clojure:

Recursive version: 

(defn santa
  ([instructions]
   (santa instructions 0))
  ([instructions n]
   (if (nil? (seq instructions)) n 
      (if (= (first instructions) \( )
        (recur (rest instructions) (+ n 1))
        (recur (rest instructions) (- n 1))))))

(println (santa "(())"))
;; UPDATE: Added nil? to (seq instructions), thanks /u/nogridbag

That is dense! (and not idiomatic at all, BTW). First, we are using a multi-arity function definition, same as in Elixir. Then we are checking if the instructions are empty; Clojure's Sequence abstraction allows us to do that without caring what the actual data type is (could be a list, a vector, a Java array...). Then we just get the first character, and recurse with the rest of the instructions. (Instead of (+ n 1) I would have used (inc n), but I left it as-is for clarity.)

Notice since the JVM doesn't support Tail Call Optimization, we have to use the special keyword recur, compared to Elixir, where we just call the function by name. The compiler puts some restrictions on where you can put the recur to ensure you are always recursing from the tail position.

Here is the more idiomatic map/reduce version:

(defn santa [instructions]
  (let [conv {\( 1, \) -1}]
    (->> instructions
         (map conv)
         (reduce +))))

Since Clojure doesn't have a build-in pattern matching, we create a lookup-map named conv from \( and \) (Java Character instances) to the elevator directions.

Clojure has literal support for maps, and they can contain any key or value, e.g. {1 "a"} or {"b" true}. No colons, and commas are optional. You can get the value out of a map by either using get or by just pretending the map is a function and calling it — (get {"a" 1} "a") and ({"a" 1} "a") are equivalent.

Note that Clojure has very explicit scoping rules — we have to use let to define that map, and it's only accessible within its body.

The ->> is equivalent to Elixir's |> only it pipes the values as the last argument, which is what map/reduce expect. Contrary to Elixir, Clojure supports map over a String — it converts into a sequence of Java Characters. Finally, + is just a plain function so we can use it as-is without having to define a wrapper function as we did in Elixir.

This is mostly equivalent with the Elixir version, with the notable difference that if you pass in something unexpected, you will silently get a nil in your sequence and eventually a NullPointerException when you try to add a nil and a number together. This can be cryptic if you are new to Clojure.

How about some map-reduce Javascript? 

function santa(instructions) {  
    let conv = {'(': 1, ')': -1}; 
    return [...instructions]
             .map((i) => conv[i])
             .reduce((acc, v) => acc + v);
}

Not half bad! We do have to convert the string to an Array since map is not a first-class function, which is annoying. At least the ... spread operator makes it a bit straightforward.

Note how it suffers the same problem with Clojure — this time, we'll get undefined in our mapped Array, and our returned value will be NaN. Which is arguably worse than just blowing up.

I won't show a recursive Javascript version; Javascript doesn't have support for tail-recursive calls, meaning that while it would work for a few characters, when we'd try this with the actual puzzle input it might result in a stack overflow error.

This is enough for Part 1 — we've solved the problem in 3 different styles, two of them functional. In Part 2 we'll see how each approach adapts to the different requirements.

Clojure Bonus Round — an imperative version, with mutable state:

(defn santa [instructions]
  (let [floor (atom 0)]
    (doseq [i instructions]
      (if (= i \( )
        (swap! floor inc)
        (swap! floor dec)))
    @floor))

Here we are using an atom, which is one of Clojure's primitives for state. We iterate over the instructions, and either increase or decrease the "mutable" floor value. When we're done, we're "dereferencing" the value contained in the atom and return it.

Note that this atom is by default thread-safe; if we wanted, we could spin up multiple threads to work on this collection in parallel, and at their core they would just call (swap! floor inc) without needing to lock the value.

This is a very unsuitable way to solve this problem, but it is worth pointing out that if your algorithm is better expressed with local mutable state, Clojure allows you to do that, whereas Elixir will make it really hard.