Skip to content

Instantly share code, notes, and snippets.

@malisper
Created April 25, 2015 12:19
Show Gist options
  • Save malisper/80625bcda75c66780f81 to your computer and use it in GitHub Desktop.
Save malisper/80625bcda75c66780f81 to your computer and use it in GitHub Desktop.
(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