This article illustrates the usage of some of Clojure‘s remarkable features, such as specs, atoms, and maps. We hope this can be of some help to illustrate functional programming techniques in a non-trivial context, as well as a more general algorithm design pattern known as memoization.

## 1. Problem definition

A detailed definition of the referred problem can be found here.

## 2. Our approach

We divide our approach to this problem into two parts. First, we describe our problem domain aided by a superb Clojure library. Second, our plans to obtain the solution are devised.

### 2.1. Problem domain

When wrapping our heads around a problem, one good first step is to describe the problem domain. To do that, Clojure offers an amazing library feature called `spec`

. This way, our Clojure source file starts with:

(ns problem.core (:require [clojure.spec.alpha :as s]))

This allows us to assign meaning to the problem entities using `s/def`

. For instance, our problem at hand deals with discrete-time instants and bus stations. Both entities can be abstracted as integer values, so we can write:

(s/def ::station int?) (s/def ::time int?)

This code defines two specs, binding them to the namespace-qualified keywords `:problem.core/station`

and `:problem.core/time`

. Now, both `::station`

and `::time`

can be used to build other specs.

(s/def ::origin ::station) (s/def ::destination ::station) (s/def ::leaves-at ::time) (s/def ::arrives-at ::time)

We see that `::origin`

and `::destination`

are both `::station`

. Also, `::leaves-at`

and `::arrives-at`

have some `::time`

meaning.

At this point, it seems that specs are good enough to convey dimensional meaning to keywords. But that’s not the whole story. Recall that we have used the predicate `int?`

to tell that `::time`

and `::station`

must be of a certain type. In fact, we can provide any predicate we want, even predicate conjunctions.

(s/def ::success-chance (s/and double? #(<= 0.0 % 1.0)))

The last spec not only tells that `::success-chance`

is related to a floating-point value but also that such value must be a number between `0.0`

and `1.0`

. The latter is not achievable within a static type system. Such an observation provides the following remark about specs: they are checked at runtime.

Now we have enough dimensional specs to define our first entity-related spec. According to the problem description, a bus has the following attributes: origin and destination stations, leaving and arrival times, and also a chance with which the bus will meet its schedule. Based on that, it is natural to devise such an entity as a map.

(s/def ::bus (s/keys :req-un [::origin ::destination ::leaves-at ::arrives-at ::success-chance]))

This definition tells that `::bus`

is related to a map containing keys `:origin`

, `:destination`

, `:leaves-at`

, `:arrives-at`

and `:success-chance`

, each having its value in conformance with the associated spec. Notice that, despite our previous specs being bound to qualified keywords, `::bus`

only needs to contain their unqualified counterparts. That is due to the `:req-un`

signaling that such keywords are required but in their unqualified form.

Our problem instances will not deal with only one bus, so we need to attach to some keywords the meaning of a collection of `::bus`

.

(s/def ::buses (s/coll-of ::bus))

Finally, we must define an entity to represent an instance of our problem. We can make use of something like this.

(s/def ::problem (s/keys :req-un [::start-time ::end-time ::origin ::destination ::buses]))

At this point, we are able to tell that our problem consists of, given a set of `::buses`

each with a certain schedule and the chance of actually fulfilling it, determining the highest chance we have to part from `::origin`

and arrive at `::destination`

within the time window defined by `::start-time`

and `::end-time`

.

### 2.2. Our solution

Here we describe the technique we used to tackle this problem.

(defn optimal-route [problem] (let [{:keys [start-time end-time origin destination buses]} problem cache (atom {})] (letfn [(solve [params] ;; ... )] (solve [start-time origin]))))

The function `optimal-route`

starts by extracting the problem’s arguments and defining a cache that consists of a map stored inside an atom. All the actual work is delegated to its nested function `solve`

.

Our approach consists of solving subproblems with varying `origin`

and `start-time`

parameters. As such, those are enough to characterize each subproblem, thus only those need to be passed to `solve`

.

(solve [params] (if (contains? @cache params) (get @cache params) (let [[current-instant current-station] params solution ;; ... ] (swap! cache assoc params solution) solution)))

Notice that, before performing any calculation, `solve`

verifies whether `cache`

contains a value associated with `params`

. In case it does, such a value is treated as a solution, which is returned immediately. Otherwise, no such a solution has been calculated previously, and `solve`

destructures its parameters in order to calculate `solution`

, which is associated to `params`

in `cache`

before being returned.

solution (if (= current-station destination) 1.0 ;; ...

In order to calculate `solution`

, that is, the chance we get to the destination in time, we first verify whether we already are at the destination: in case we are, such a chance is `1.0`

; otherwise, we need to calculate it.

(let [parting-buses ;; ... decreasing-leaving-instants ;; ... grouped-parting-buses ;; ... subproblems ;; ... ] (apply max 0.0 (vals subproblems)))

To accomplish such a calculation, we need to determine four smaller pieces:

- the list of buses parting from our
`current-station`

that we can safely take; - the list of instants in which we can leave
`current-station`

taking one of the`parting-buses`

; - the
`parting-buses`

grouped by the instants they leave`current-station`

; - at last, each subproblem chance of arriving at destination in time.

Once we get all the subproblems solutions, we return the one with maximum value.

parting-buses (filter (fn [bus] (and (= current-station (get bus :origin)) (< current-instant (:leaves-at bus)) (>= end-time (:arrives-at bus)))) buses)

In order to determine `parting-buses`

, we use `filter`

to select the buses that satisfy three criteria:

- the bus is parting from
`current-station`

; - the bus has not parted yet;
- the bus arrives at its destination within our time window.

decreasing-leaving-instants (->> parting-buses (map :leaves-at) (sort >=) dedupe)

For `decreasing-leaving-instants`

, we take the instant each bus is parting at, sort them in non-increasing order, and finally remove duplicate instants. This calculation is important because, in order to obtain the chance of reaching `destination`

in time if we leave `current-station`

in a certain instant, we need to consider the chances associated with each upcoming instant.

grouped-parting-buses (group-by :leaves-at parting-buses)

As of `grouped-parting-buses`

, Clojure provides the handy `group-by`

function, which helps us to group the `parting-buses`

by their parting instant.

subproblems (reduce (fn [current-calculation leaving-instant] (assoc current-calculation leaving-instant (let [buses (get grouped-parting-buses leaving-instant) optimal-bus (->> buses (map (fn [bus] (assoc bus :subproblem-solution (solve [(:arrives-at bus) (:destination bus)])))) (map (fn [bus] (assoc bus :overall-chance (* (:subproblem-solution bus) (:success-chance bus))))) (apply max-key :overall-chance))] (+ (:overall-chance optimal-bus) (* (- 1.0 (:success-chance optimal-bus)) (apply max 0.0 (vals current-calculation))))))) {} decreasing-leaving-instants)

Now we take `subproblems`

into account. For a certain instant:

- we get the
`parting-buses`

parting at such an instant; - associate the solution of the subproblem that relates to each of them;
- calculate the overall chance of each bus delivering us to the destination in time, that is, the chance we can accomplish our schedule once the bus leaves us at its destination multiplied by the chance the bus is actually meeting its own schedule.
- with each bus overall chance calculated, we consider the
`optimal-bus`

to be the one with maximum overall chance. - once
`optimal-bus`

is defined, we calculate the chance associated with the leaving instant at hand, that is, either`optimal-bus`

meets its schedule or we wait to leave`current-station`

in the optimal instant among the upcoming ones, which had their chances calculated beforehand.

## 3. Conclusion

Clojure enforces a functional approach to programming. In turn, this encourages the programmer to devise declarative solutions to their problems, be them of a mathematical nature or a more practical one.

As such, we were led towards a more descriptive than procedural manner of tackling the problem we had in hand. Because of that, it felt less that we were planning an algorithm and more that we were simply stating some of the problem intrinsics.