Skip to content

Instantly share code, notes, and snippets.

@Engelberg
Created February 19, 2013 18:47
Show Gist options
  • Save Engelberg/4988711 to your computer and use it in GitHub Desktop.
Save Engelberg/4988711 to your computer and use it in GitHub Desktop.
Santa Claus problem in Clojure
;; Ref-based Santa Claus solution, Written by Mark Engelberg
;; (start-simulation) to run
(def *num-elves* 10)
(def *num-reindeer* 9)
;; Santa is a ref containing either {:state :asleep} or {:state :busy, :busy-with <sequence-of-workers>}
(def santa (ref {:state :asleep}))
(defn waiting-room [capacity]
{:capacity capacity, :queue (ref clojure.lang.PersistentQueue/EMPTY)})
(def reindeer-waiting-room (waiting-room 9))
(def elf-waiting-room (waiting-room 3))
;; workers have a state that is either :idle (aka building toys / on holiday), :waiting-for-santa, or :with-santa
(def elves (for [i (range *num-elves*)]
{:room elf-waiting-room, :species :elf, :id i, :state (ref nil)}))
(def reindeer (for [i (range *num-reindeer*)]
{:room reindeer-waiting-room, :species :reindeer, :id i, :state (ref nil)}))
(def workers (concat elves reindeer))
;; Adding a worker to a waiting room entails
;; * putting the worker in the room's queue
;; * setting his state to :waiting-for-santa
;; * checking to see if there are enough workers in the room to warrant waking Santa
(declare wake-santa)
(defn add-to-room [room worker]
(let [{:keys [capacity queue]} room]
(dosync
(alter queue conj worker)
(ref-set (worker :state) :waiting-for-santa)
(when (>= (count @queue) capacity)
(wake-santa)))))
;; A couple helper functions that use threads to handle delaying an action by some length of time
(defn on-thread [f]
(.start (Thread. f)))
(defmacro wait-and-do [n f]
`(on-thread (fn [] (do (Thread/sleep ~n) ~f))))
;; So how does a worker get added to a waiting room?
;; Well, whenever a worker's state is set to :idle, we need to start a timer, after which he will be added back to the waiting room.
(doseq [worker workers] (add-watch (worker :state) :watch-for-idle
(fn [key ref old new]
;(printf "%s %d %s\n" (worker :species) (worker :id) @(worker :state))
(when (= new :idle)
(wait-and-do (rand-int 1000) (add-to-room (worker :room) worker))))))
;; Here's the function that sets a worker's state to :idle
(defn idle "Sets worker's state to :idle"
[worker]
(dosync
(ref-set (worker :state) :idle)))
;; To begin the simulation, we need to set all the workers' states to idle
(defn start-simulation []
(dorun (map idle workers)))
;; So what happens when a meeting room determines that Santa needs to wake up? Well, if he's already awake, nothing.
;; If he's not awake, he needs to go through the process of admitting visitors for a meeting
(declare santa-admits-visitors)
(defn wake-santa []
(when (= (@santa :state) :asleep)
(santa-admits-visitors)))
;; There's a certain process that Santa needs to go through whenever it is time to admit visitors for a meeting.
;; First he checks to see if there are enough reindeers, otherwise he checks whether there are enough elves.
;; If there aren't enough workers gathered in one of those meeting rooms, he just goes back to sleep.
(declare check-waiting-room visit-santa)
(defn santa-admits-visitors []
(cond
(check-waiting-room reindeer-waiting-room)
(visit-santa reindeer-waiting-room)
(check-waiting-room elf-waiting-room)
(visit-santa elf-waiting-room)
:else
(dosync (ref-set santa {:state :asleep}))))
(defn check-waiting-room "Is the waiting room sufficiently filled to warrant waking Santa?"
[room]
(>= (count @(room :queue)) (room :capacity)))
;; When Santa actually has his meeting with the visitors, several things have to happen
;; * Santa's state is set to :busy, and also includes info about who is meeting with.
;; * The various workers' states are set to :with-santa
;; * The workers who go to meet with Santa are popped off the queue from their meeting room.
(defn visit-santa [room]
"A group of workers from room go to visit Santa"
(let [capacity (room :capacity),
queue @(room :queue),
visitors (take capacity queue),
remainder (loop [n capacity, queue queue] (if (zero? n) queue (recur (dec n) (pop queue))))]
(dosync
(ref-set santa {:state :busy, :busy-with (take (room :capacity) @(room :queue))})
(doseq [worker visitors] (ref-set (worker :state) :with-santa))
(ref-set (room :queue) remainder))))
;; When the meeting with Santa is over, several things need to happen
;; * All the workers who were meeting with him return to their idle state
;; * Santa goes through the "admit visitors" process again, to see whether
;; there are enough workers in either room to warrant another meeting (otherwise back to sleep)
(defn end-meeting-with-santa []
(dosync
(doseq [worker (@santa :busy-with)] (ref-set (worker :state) :idle))
(santa-admits-visitors)))
;; When a meeting with Santa happens, this watcher will set a random delay to simulate the length of the meeting.
(add-watch santa :watch-for-meeting
(fn [key ref old new]
; (printf "Santa's state: %s\n" (@santa :state))
(when (= (:state new) :busy)
(printf "Santa is meeting with %ss: %s\n"
(:species (first (@santa :busy-with)))
(str (vec (map :id (@santa :busy-with)))))
(flush)
(wait-and-do (rand-int 10) (end-meeting-with-santa)))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment