Logic Puzzles With Clojure

July 25, 2015 | clojure coding

In the “strange stuff that comes up in Steam chat” category…

The Templars were all taken out for the day during the second week of their visit, and one Templar, (Antimatter) had the good fortune to be taken out twice. Where did the Templars choose to go (in Antimatter’s case, there were two choices) and when was each outing?

Personnel:

Hexagon

Jasmine

Antimatter

Cygnus

Locations:

Globe Theatre

London Eye

Monument

Tower of London

Buckingham Palace

Days: Monday Tuesday Thursday Friday Saturday

Data:

The Templar taken to the Globe Theatre isn’t Cygnus, who went out the day before Hexagon.

Antimatter’s trip to the London Eye was later in the week than his visit to the Tower of London.

Cygnus isn’t the Templar who visited Buckingham Palace on Monday.

No Templar was taken to see the Monument on Friday.

So, I had always had in the back of my mind that it would be interesting to try solving a logic problem with code. Clojure was on my mind because I had been evaluating it for something at work (much to my regret, since 1.7 was just out and web frameworks are painful sauce after a major version upgrade), so I wrote something up — quick, elegant, written quickly using a combo/cartesian-product over combo/permutations run through some conditions in a for loop, and done!

Done, Except For Testing

Well, so I thought. When I was writing this up and researching a bit, I found the classic Zebra problem and decided to try my stuff on it. Wrote it up, ran it, and waited. And waited. And waited some more while Java spun and garbage collected and both the universe and my tea grew colder.

The thing is, the first logic problem only had 14400 possibilities

$$ (_{5}P_{5})^2 $$

… the zebra problem has many more possibilities, about 24 billion and change

$$ (_{5}P_{5})^5 $$

… which meant that my naive “elegant” solution wasn’t going to work.

The key is to cut off constraints as soon as possible. I instead went with a straightforward approach that allowed constraints to be evaluated before going through successive permutations, and Clojure’s lispiness let me do it in a straightforward way that was fairly readable. I was originally thinking that I needed to write a macro but my first pass without macros was readable enough that I was okay with it.

(defn logic-problem [] (eval-stream :name [:hexagon :jasmine :cygnus :antimatter :antimatter2] :day [1 2 4 5 6] ;; Since Antimatter visits twice, don't permute based on him :when (fn [x] (< (get-> x :antimatter :day) (get-> x :antimatter2 :day))) :location [:globe-theater :london-eye :monument :tower-of-london :buckingham-palace] ;; Antimatter's trip to the London Eye was later in the week than his visit to the Tower of London. :when (fn [x] (= (get-> x :antimatter :location) :tower-of-london)) :when (fn [x] (= (get-> x :antimatter2 :location) :london-eye)) ;; The Templar taken to the Globe Theatre isn't Cygnus, who went out the day before Hexagon :when (fn [x] (not= (get-> x :cygnus :location) :globe-theater)) :when (fn [x] (== (+ 1 (get-> x :cygnus :day)) (get-> x :hexagon :day))) ;; Cygnus isn't the Templar who visited Buckingham Palace on Monday. :when (fn [x] (= (get-> x :buckingham-palace :day) 1)) :when (fn [x] (not= (get-> x :cygnus :day) 1)) ;; No Templar was taken to see the Monument on Friday. :when (fn [x] (not= (get-> x :monument :day) 5)) ) )

Yeah, this is very monadish.

The one non-obvious thing in the code above is the get-> call. When building the dictionary for potential answers, I also add indexes for all unique values added to the dictionary. This allows the dictionary to be accessed by any value – so, assuming that Hexagon visited the Monument in our current candidate, (get-> foo :monument) and (get-> foo :hexagon) will return the same data. This is handy because logic problems often use arbitrary indexes to set constraints.

Anyway, I don’t recommend it as good Clojure — my rustiness is apparent every oxide-encrusted time I have to refer to Clojure documentation to remember something basic — but it is interesting and different enough from the Rosetta Clojure example that I thought it was worth throwing a gist up. There is also a complete solution to the Zebra problem in the gist.

Added 2015-07-27: My friend based this problem on something of unknown provenance in his clip folder. In trying to source the original problem, the best I can come up with is Pocket Posh Logic 3: 100 Puzzles. If there’s a better original cite, please let me know.