Functional Programming for Coding Challenges#

In this post I want to introduce you to solving coding puzzles with functional programming. Personally, I love doing coding puzzles. Especially in programming languages that I’m not using at work. At least functional programming is getting more and more mainstream in the last few years (hottake: imo it’s the superior paradigm in comparison to imperative OOP) but work-related code is often just data transformation without any real challenging algorithm work in between. And thinking about and implementing algorithms is arguably the most fun part of programming. So why not combine functional programming and fun algorithms into a little hobby (it can’t be a coincidence that fun is in functional). And that’s exactly what I want to write about.

Just a small heads-up about me. I’m not a good competitive programmer, I’m not fast in solving those puzzles and sometimes I can’t solve them at all because they can get really hard. But the fun is tinkering around and learning new stuff, if you try to solve coding challenges by pasting the problem description into an LLM, I’d reckon you use your time for different things because that’s not the spirit of those challenges.

What is a Coding Puzzle?#

A coding puzzle is basically what you get as homework in algorithms and data structures classes at school. You get one or multiple inputs and a problem description and your task is to write an implementation that solves the problem for the given inputs. One of the most famous challenges is Advent of Code but there are other ones like Everybody Codes and Codingame. That’s basically it and in this blog we’ll go through the tools that help you solve those things in a functional style.

What is Functional Programming?#

It’s a huge topic and far too broad to write about it in detail, but the two most important parts are that we compose our programs as functions and that we don’t write imperative code where we tell the program what to do like int i = 1; i++; but declarative code where we tell the program what we want like List.reverse [1;2;3;4]. This sounds a bit like magic, because how does the program know how to reverse a list in the first place?

let rec reverse(list) =
    match list with
    | [] -> []
    | x :: xs -> reverse(xs) @ [x]

This is an example implementation for the reverse function in OCaml. The main reason we can use a declarative style is that in functional programming we use recursion instead of loops to solve problems. But you probably wonder now if you have to write funky recursive functions for every problem. And the answer is no. Another very important part of functional programming languages is that you can pass functions as parameters to other functions. Functions that take other functions as arguments are called higher-order functions. These functions are implemented, as you probably guessed, recursively. But you won’t see any recursion at all when using them. There are 3 basic ones that are really common and useful.

The filter Function#

Often, we have a list and want to remove stuff from it that’s not important for us. For example, we have a list from 1 to 5 and we only want the even numbers. We could write it like this

List.filter (fun x -> x mod 2 = 0) [1;2;3;4;5]

This filter function takes another function, in this case anonymous, and evaluates it for every element in the list. If the anonymous function returns true, the element is contained in the resulting list.

The map Function#

Another very common use case is to apply something to every element in a list. For example, we want to add 1 to every element in a list. This could be implemented like this

List.map (fun x -> x + 1) [1;2;3;4;5]

Like filter, the map function takes a function and a list and applies the function to every element in the list and returns a new list with the new values.

The fold/reduce Function#

The probably most difficult to understand of the basic functions is the fold, sometimes also called the reduce function. This function takes a list and transforms it into another value; it does not have to be a list anymore, it can be any value you like. For example, we want to add every number in a list. This can be done with fold like this:

    List.fold_left (fun a x -> a + x) 0 [1;2;3;4;5]
    (* or even shorter *)
    List.fold_left (+) 0 [1;2;3;4;5]

The fold function takes more than just a function and a list as input. It takes a function with 2 arguments, an initial argument, and a list as input. A fold works as follows: it takes the supplied initial value (the 0 in the example above) and passes it into the anonymous function (the a parameter of the anonymous function). Additionally, the x parameter is passed into the function, which is the current element of the list. Then the anonymous function is evaluated, and for the next item in the list, the a value of the anonymous function is the value the function returned the previous iteration. That’s why a is also called the accumulator, because it accumulates the result of the computations. This result is returned at the end.

Don’t be confused by the _left after the fold. In many languages there is no distinction and it’s basically just about which direction the list is traversed. This matters for non-commutative operations like division if you don’t pass in an anonymous function but a named one like in the shorter example above.

Combining the Functions#

After you’ve played around with those functions you can start building really complex stuff already by combining these functions. For example, let’s assume we have a list of numbers and we want to sum up the squares of all numbers that are divisible by 3.

[1;2;3;4;5;6;7;8;9;10]
|> List.filter (fun x -> x mod 3 = 0)
|> List.map (fun x -> x * x) 
|> List.fold_left (+) 0

The |> operator is something many functional programming languages offer (even PHP 8.5 has it now). It takes the output of the left side and passes it into the right side. When combining these functions, an algorithm looks more like a data pipeline than a bunch of loops doing stuff. This makes it incredibly readable and maintainable (which is not very necessary for coding challenges, but it helps a lot when debugging). Nobody prevents you from declaring your own higher-order functions, so you can go wild with them.

There are a few other higher-order functions that are useful:

  • zip takes two lists and combines them into a single list by tuple-ing up the ith element of each list.
  • flatten takes a nested list and un-nests it.
  • append takes two lists and appends them.
  • sort takes a list and sorts it.

Understanding the Problem#

The most important part is understanding the problem. A good competitive programmer (which is basically the sport where you try to solve (very hard) challenges as fast as possible) can read the examples in a problem description and go from there. But mere mortals, like me, have to read all the text to know what’s going on. And it’s important to understand exactly what the actual problem is. I have lost countless hours solving the wrong problems. :D It’s also really important to look at the given examples. They give the most insight into the problem. If the examples are well written, you can test your understanding by going through the examples step by step and seeing for yourself if your expected outcome is what’s actually written in the example.

Parsing the Input#

Most inputs in coding challenges are pretty simple. It may be a grid with special characters like

##.###
.#.#..
.#.#..
##.###

where each # could be a wall and you have to find a corridor from top to bottom (this would be trivial here). Or the input could just be a list of numbers like "1,2,3,-3,4.2,54,1337,42,69" and you have to manipulate them in some way. But they can get really convoluted, like multiple lines of "Card 01 | A=1 B=4 C=22 D=19". The best thing about coding challenges is that we don’t care about broken input. It’s the task of the task setter to give you correct input. For simple inputs you can get away with combinations of split, filter, and map. For more complex inputs you can use regex, but if you want to do it true functional style you probably want to build something called a parser with a parser combinator library. In OCaml there is Angstrom, in Haskell there is Parsec, in F# there is FParsec, and in your functional programming language of choice there is probably one as well. Computerphile made a good video about them a few years ago. Regardless of the way you parse input, it’s important to get it into a data structure that’s helpful to solve the problem. Often it’s helpful to not discard data when reading input, because even if you don’t need the input for the first part of a problem most of the time the upcoming parts of a problem need them. Good input does not contain unnecessary information. For example, when I solve grid-based problems I most of the time read the input into a hash map because even if a 2-dimensional list would look closer to the input, it’s harder to do bound checks on the lists. Something you don’t need to worry about at all with hash maps.

Solving a Problem#

Now that we know that we want to solve problems with (recursive) functions and know how to get the input in a nice format into our program, we want to solve a little problem to fit everything together. Let’s go with part 1 of everybody.codes Q1 2025. I don’t want to spoil too much, so we only do part 1.

There is a list of names "Vyrdax,Drakzyph,Fyrryn,Elarzris" and a sequence like "R3,L2,R3,L1" as input and we have to modify a pointer to the correct name in the list by shifting it to the right or left based on the instructions. R3 means 3 to the right, L2 means 2 to the left. If we hit 0 or 3 (the maximum index of the list) we don’t move further, we just stay there.

So first, we parse the input. The names are pretty easy:

let names = String.split_on_char ',' "Vyrdax,Drakzyph,Fyrryn,Elarzris"

but the instructions could be a bit tricky, based on how we want to handle them. But let’s go with a parser just to show it off.

let is_digit = function '0' .. '9' -> true | _ -> false

let number = take_while1 is_digit

let sign = char 'R' *> return 1 <|> char 'L' *> return (-1)

let instruction =
  let* s = sign in
  let* n = number in
  return (s * int_of_string n)

let parser = sep_by (char ',') instruction

This parser parses our input list and transforms values with the R prefix to positive numbers and the L numbers get transformed into negative numbers.

  • is_digit is a function that returns true if a character is a digit, otherwise false.
  • number is a parser that reads at least 1 digit.
  • sign reads an R and returns 1 or reads an L and returns -1.
  • instruction combines the sign parser and the number parser and returns sign * number.
  • parser is the complete parser that reads the instruction parser separated by ','.

This looks a bit more complicated than a simple regex, but it’s MUCH easier to debug and to maintain. And it’s fun to write.

So after we’ve parsed the input, we just need a function that modifies a pointer to the correct element in the list starting at 0.

We can do this by building a recursive function ourselves or by using fold. Let’s do it both ways.

(* recursive function *)
let solve_rec input = 
    let rec aux i r =
        match i with
        | [] -> r
        | x :: xs -> aux xs (max 0 (min (r + x) ((List.length input) - 1))) in
    aux input 0
    
(* fold *)
let solve_fold input = List.fold_left 
    (fun a x -> (max 0 (min (a + x) ((List.length input) - 1)))) 
    0 input

You see, whatever a for loop achieves in the imperative paradigm is easily achieved with a little recursion here. Basically, we take the input, destructure it into the head of the list and the rest of the list, do our little calculation with the head of the list and call the function again with the rest of the list. The value r is used as the accumulator for the final result. And that’s what allows us to easily rewrite the function as a fold, the function that uses an accumulator.

The hardest part in functional programming, especially when you come from the imperative paradigm, is imo that you have to know beforehand what you want to achieve. In imperative programming you build your program by thinking “the next step my program has to do is increment this variable by 1” and so on. But in functional programming you basically tell the program to do complete operations like “filter all odd numbers from this list”. So your building blocks are much bigger and more powerful but it’s a bit harder (at least in the beginning) to fit them together all at once. But that’s where practice makes perfect. And I hope this primer helps you a bit getting started. If you need a programming language to start solving problems in a functional style I recommend OCaml, its type system makes it basically impossible to write bugs (at the cost that your program won’t compile most of the time when it’s wrong lol), or if you are hardcore you can try out Haskell which is a very pure form of functional programming. But you can also just use JavaScript or Java or C++ to do this. Most languages support functional programming by now.

Have a good one!