Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
(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)))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.