CODEWITHSUNDEEP
algorithmclojurefunctional-programming
Brandon
Brandon

Reputation: 3130

How to solve this programming situation using Clojure in a functional manner?

I have a programming problem that I know how I might tackle in Ruby, but don’t know the best way in Clojure (and figure there may be an elegant way to do this taking a functional mindset).

The problem can be simplified as thus:

I have a 3 litre bucket, filled with water. There is a hole in the bottom of the bucket, that is leaking 10 mL/s (i.e. it will take 300 seconds / 5 minutes to empty). I have a glass of water with a 100 mL capacity that I can use to pour in new water to the bucket.

I can only pour the entire contents of the glass into the bucket, no partial pours. The pour occurs instantaneously.

Project out a set of time steps where I can pour glasses of water into the bucket.

I know there is a pretty obvious way to do this using algebra, but the actual problem involves a “leak rate” that changes with time, and "new glass volumes" that don't always equal 100 mL and as such isn’t simple to solve in a closed form.

The Ruby way to solve this would be to keep track of the bucket volume using a “Bucket instance”, and test at numerous time steps to see if there bucket has 100 mL of room. If so, dump the glass, and add to the water in the “bucket instance”. Continue the time steps, watching the bucket volume.

I hope what I have described is clear.

Upvotes: 3

Views: 288

Answers (2)

noisesmith
noisesmith

Reputation: 20194

One of the most important concepts of functional programming is that any mutation without external side effects can be offloaded onto immutable function parameter bindings.

Here the time of the simulation and the level of the bucket are the primary function parameters, and they are updated for each recursive call. The other parameters are modeled as functions of time. We could picture each of these functions actually being a lazy sequence based on the time deltas just as the fill-times function itself is. Or piecewise linear equations modeled with lookups in a vector, or whathaveyou.

user> 
(defn fill-times
  [time level
   {:keys [sample-rate calc-bucket-size calc-leak-rate calc-glass-size]
    :as params}]
  (loop [t time l level]
    (let [input-capacity (calc-glass-size time)
          bucket-capacity (calc-bucket-size time)
          has-room (> (- bucket-capacity l) input-capacity)
          leak-delta (* (calc-leak-rate) sample-rate -1)]
      (if has-room
        (lazy-seq (cons t (fill-times t (+ l input-capacity)
                                      params)))
        (recur (+ t sample-rate) (+ l leak-delta))))))

#'user/fill-times
user> (take 50 (fill-times 0 0 {:sample-rate 1
                                 :calc-bucket-size (constantly 3000)
                                 :calc-leak-rate (constantly 10)
                                 :calc-glass-size (constantly 100)}))
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 11 21 31 41 51 61 71 81 91 101 111 121 131 141 151 161 171 181 191 201)

When there is sufficient room, the glass is dumped (and of course is filled instantly) and we make a note of the time, calling the function again to get the following times. When there is not room, we recur, updating the time and the bucket level. The result is a (hypothetically infinite) lazy sequence of times at which the glass can be emptied (assuming that the glass is filled instantly, and dumped instantly).

Upvotes: 5

Jerry101
Jerry101

Reputation: 13357

I don't have a lot of experience with Clojure, but one way to think of it is a lazy seq of state values at time steps. Lazily compute each state value from the previous state value.

This is a recurrence equation, also known as a difference equation. It computes new values as a function of previous values without overwriting them.

A state value could be just the bucket level or a tuple holding the (time, bucket_level, pour_in_count).

Upvotes: 3

Related Questions