Havel-Hakimi algorithm implementation in Clojure not working as expected

Question

I am trying to implement the Havel-Hakimi algorithm using Clojure.

The steps in the algorithm are: 1. Remove zeros and reverse sort a list of values from highest to lowest. 2. Check if the list of values is empty, in which case exit and return a value of true. 3. If not empty, check to see if the first value in the list is greater than the length of the rest of the list. If it is, return false, else remove the first entry in the list and repeat the process.

The following is my implementation in code.

(defn hh [lst]
  (if-let [lst (empty? (remove #{0} (reverse (sort lst))))]
    true
    (if (> (first lst) (count (rest lst)))
        false
        (hh (map dec (rest lst))))))

The following are my test cases.

(deftest hh-test
  (is (= true (hh [])))
  (is (= false (hh [1])))
  (is (= true (hh [1 1])))
  (is (= false (hh [2 2])))
  (is (= false (hh [2 2 0]))) ;;failing and i don't know why
  (is (= false (hh [3 2 1])))
  (is (= true (hh [3 1 2 3 1])))
  (is (= false (hh [5 3 0 2 6 2 0 7 2 5])))) ;;also failing and I don't know why

The fifth test case is particularly troubling me because it should be equivalent to the previous test case (the zero should get immediately dropped from the list and would then be equivalent to the previous test case, but for some reason it isn't).

I'm still new and learning Clojure (and programming in general) and I haven't been able to get debugging in Cider working (I get some strange errors when trying to debug) so I'm a bit stuck. Any help is appreciated.

Answer 1

One thing you can do is require logging (or just use println)

(ns f
  (:require [clojure.tools.logging :as log]))

And then proceed to log the crap (the technical term) out of your function:

(defn hhd [lst iter]
  (log/info "iter:" iter ", lst is" lst)
  (if-let [lst (empty? (remove #{0} (reverse (sort lst))))]
    (do (log/info "returning true; lst = " lst) true)
    (if (> (first lst) (count (rest lst)))
      (do (log/info "returning false; lst =" lst) false)
      (do (log/info "doing recursion; lst =" lst)
          (hhd (map dec (rest lst)) (inc iter))))))

Running this on the problematic [2 2 0] we see:

f> (hhd [2 2 0] 0)
[nREPL-worker-19] 2019-08-06 04:25:41,213 INFO f: iter: 0 , lst is [2 2 0]
[nREPL-worker-19] 2019-08-06 04:25:41,214 INFO f: doing recursion; lst = [2 2 0]
[nREPL-worker-19] 2019-08-06 04:25:41,215 INFO f: iter: 1 , lst is (1 -1)
[nREPL-worker-19] 2019-08-06 04:25:41,215 INFO f: doing recursion; lst = (1 -1)
[nREPL-worker-19] 2019-08-06 04:25:41,215 INFO f: iter: 2 , lst is (-2)
[nREPL-worker-19] 2019-08-06 04:25:41,215 INFO f: doing recursion; lst = (-2)
[nREPL-worker-19] 2019-08-06 04:25:41,216 INFO f: iter: 3 , lst is ()
[nREPL-worker-19] 2019-08-06 04:25:41,216 INFO f: returning true; lst =  true
true

Right off the bat we see that the lst value before the recursive step is the orignal list --- it isn't reverse sorted and it still has zeros!

Since (almost) everything in clojure is immutable, just calling sort and remove on the lst doesn't change the list. Wait? But aren't you setting the result of that to a local lst variable? Well, no, that local lst variable gets the result of calling empty?, which can only be a boolean. However, a quirky thing about if-let is that it only sets the variable if the test is true, otherwise it's like it never existed. And that's why the lst in your "else" clause is the original list (although without that quirk it would be set to "false", which isn't what you wanted, anyway).

The way to turn this around is first, to use seq instead of empty?. seq tests if a sequence is not empty, and if not takes the value of the sequence instead of a boolean, which is what you want here.

Then, second, since this is the opposite of your original test, you need to switch the "if" and "else" clauses:

(defn hh [lst]
  (if-let [lst (seq (remove #{0} (reverse (sort lst))))]
    (if (> (first lst) (count (rest lst)))
      false
      (hh (map dec (rest lst))))
    true))

With that, your failing tests pass. But one of your passing tests fails. I think in that case the test is expecting the wrong value.

Answer 2

Jas has corrected the code you wrote into what you probably intended to write. But even corrected, it is not the Havel-Hakimi algorithm.

The problem is that the recursive call (hh (map dec (rest lst))), decrements all the numbers in (rest lst). It should only decrement (first lst) of them. Modifying Jas's code to do so, we get ...

(defn hh [lst]
  (let [lst (remove #{0} (reverse (sort lst)))]
    (println lst)
    (if (empty? lst)
      true
      (let [n (first lst), ns (rest lst)]
        (if (> n (count ns))
            false
            (let [front (take n ns), back (drop n ns)]
              (hh (concat (map dec front) back))))))))

... where I've added a diagnostic println.

Everything now works as you expected, apart from the new test case:

=> (hh [5 3 0 2 6 2 0 7 2 5])
(7 6 5 5 3 2 2 2)
(5 4 4 2 1 1 1)
(3 3 1 1)
(2)
false

But this too looks right to me.

---

We can tidy the code up a bit:

(defn hh [lst]
  (let [lst (filter pos? (reverse (sort lst)))]
    (or (empty? lst)
        (let [[n & ns] lst]
          (and (<= n (count ns))
               (let [[front back] (split-at n ns)]
                 (recur (concat (map dec front) back))))))))

• (filter pos? ... ) replaces (remove #{0} ... ) as a predicate. This stops negative numbers looping indefinitely.
• The or and and eliminate true and false.
• recur replaces the recursive call of hh, possible since it's in tail position.
• The destructuring is more concise.

---

A final point about the algorithm: it still works if you take out the sorting! This came as a surprise to me.