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.