Hardest Problem Solver

(defpackage :hardest-problem
  (:nicknames :hard)
  (:use :clamp :experimental :iter)
  (:shadowing-import-from :experimental
     :def :mac :fn :defmemo :coerce
     :while :until :repeat :summing :with :in))

(in-package :hard)

(def know (possibilities)
  "Is the number of blue-eyed people known from the given
   possibilities?"
  (single possibilities))

(defmemo possibilities (see day)
  "Returns a list containing all of the possible total number of
   blue-eyed people given that a person sees SEE blue-eyed people on
   day DAY."
  (if (is day 1)
      (keep [> _ 0] (list see (inc see)))
      (hofeach #'keep pos (possibilities see (dec day))
        (~know (possibilities (dec pos) (dec day))))))

(def solve (see)
  "Returns the day that a blue-eyed person who sees SEE blue-eyed
   people would figure out they are blue-eyed."
  (iter (for day from 1)
        (finding day such-that (know (possibilities see day)))))