Secret Santa

secret-santa.clj

; Clojure is a dynamic programming language that targets the Java Virtual Machine (and the CLR,
; and JavaScript). It is designed to be a general-purpose language, combining the approachability
; and interactive development of a scripting language with an efficient and robust infrastructure
; for multithreaded programming. Clojure is a compiled language - it compiles directly to JVM bytecode,
; yet remains completely dynamic. Every feature supported by Clojure is supported at runtime.
; Clojure provides easy access to the Java frameworks, with optional type hints and type inference,
; to ensure that calls to Java can avoid reflection.
;
; Clojure is a dialect of Lisp, and shares with Lisp the code-as-data philosophy and a powerful
; macro system. Clojure is predominantly a functional programming language, and features a rich set
; of immutable, persistent data structures. When mutable state is needed, Clojure offers
; a software transactional memory system and reactive Agent system that ensure clean, correct,
; multithreaded designs.
;
; http://clojure.org/

; There's an IRC room about programming in Latvian. Join at #developerslv @freenode.

; Input.
(def people ["Oliver"
             "Jack"
             "Charlie"
             "Harry"
             "Oscar"
             "Thomas"
             "Jacob"
             "Ethan"
             "Noah"
             "James"
             "William"
             "Joshua"
             "George"
             "Leo"
             "Max"])
(def pairs-banned [["Oliver" "Charlie"]
                   ["Charlie" "Harry"]
                   ["Oscar" "Jacob"]])

; Helper.
(defn in? [coll x]
  (not (nil? (some #(= x %) coll))))

; Brute-force solution with side effects. Problem is NP-complete so sorry, but not sorry.
(defn get-pairs! [people pairs-banned]
  (loop []
    (let [pairs (zipmap people (shuffle people))]
      (if (nil? (some (fn [[p1 p2]]
                        (or (= p1 p2)
                            (in? pairs-banned [p1 p2])
                            (in? pairs-banned [p2 p1])))
                      pairs))
        pairs
        (recur)))))

; Output.
(doall
  (map (fn [[p1 p2]] (println (format "%s gives to %s" p1 p2)))
       (get-pairs! people pairs-banned)))

; Not working, but still a solution. Doesn't work because sometimes assigns 2+ gifts to a person.
; At least it doesn't brute-force.
(defn get-pairs [people pairs-banned]
  (loop [people-left people
         pairs []]
    (let [person (first people-left)]
      (if (nil? person)
        pairs
        (recur
          (rest people-left)
          (let [next-person
                (some (fn [pair]
                        (let [[person-a person-b] pair]
                          (if (and (= person-a person)
                                   (not (some #(or (= [person-a person-b] %) (= [person-b person-a] %))
                                              pairs-banned)))
                            pair)))
                      (for [person-a people-left person-b people-left
                            :when (not= person-a person-b)]
                        [person-a person-b]))]
            (conj pairs
                  (if (nil? next-person) [person (first people)] next-person))))))))

; Output.
(doall
  (map (fn [[person-a person-b]] (println (format "%s gives to %s" person-a person-b)))
       (get-pairs (shuffle people) pairs-banned)))

An example output:

➜  Clojure  lein exec secret-santa.clj
Leo gives to Oscar
Oscar gives to Jack
Jack gives to Joshua
Joshua gives to Max
Max gives to George
George gives to Ethan
Ethan gives to Jacob
Jacob gives to Noah
Noah gives to Thomas
Thomas gives to Harry
Harry gives to Oliver
Oliver gives to William
William gives to James
James gives to Charlie
Charlie gives to Leo

Output of the new, working solution:

➜  Clojure  lein exec secret-santa.clj
Max gives to James
Leo gives to Oliver
Noah gives to Jack
Joshua gives to Charlie
Oscar gives to Joshua
James gives to Jacob
Ethan gives to Max
Harry gives to Oscar
Thomas gives to Noah
William gives to Harry
George gives to Ethan
Jacob gives to Thomas
Charlie gives to Leo
Oliver gives to George
Jack gives to William