Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
weitz.de
weitz.de
Clojure, using core.logic, is also there for good measure.
I also recommend a Mozart/Oz style interactive search tree explorer made by a student [2] .. built on fd.js.
[1] https://github.com/srikumarks/fd.js [2] http://minhtule.github.io/Search-Tree-Visualization/
Some types of constraints force brute-force searches, for example if the MD5 sum of the list needs to match a particular value then there is little that we can do without trying every possible list of permutations. Some constraints allow faster, but still intractable, searches that grow exponentially with the size of the problem (knapsack problems fall into this category). In this riddle, we have 15 simple constraints; some can even be applied to individual permutations (e.g. "The Norwegian lives in the first house."). A straightforward solution thus presents itself to us. Here is the entire solution in Python:
from itertools import permutations as perms
for brit, swede, dane, norwegian, german in perms(range(5)):
if norwegian != 0: continue
for red, green, white, yellow, blue in perms(range(5)):
if brit != red: continue
if green != white - 1: continue
if norwegian not in [blue-1, blue+1]: continue
for tea, coffee, milk, beer, water in perms(range(5)):
if milk != 2: continue
if dane != tea: continue
if green != coffee: continue
for pallmall, dunhill, marlboro, winfield, rothmans in perms(range(5)):
if dunhill != yellow: continue
if winfield != beer: continue
if rothmans != german: continue
if marlboro not in [water-1, water+1]: continue
for dogs, birds, cats, horses, fish in perms(range(5)):
if swede != dogs: continue
if pallmall != birds: continue
if marlboro not in [cats-1, cats+1]: continue
if dunhill not in [horses-1, horses+1]: continue
nation = {brit: "Brit", swede: "Swede", dane: "Dane",
norwegian: "Norwegian", german: "German"}
print "The {} owns the fish".format(nation[fish])
Python is great for simple problems like this. I wrote this program while waiting for my daughter to come downstairs to be driven to school this morning.
It's a really well-constructed puzzle, though: the identity of the fish owner is the very last part of the grid that you get to fill in.
I got the algorithms from the "AI a modern Approach" book by Peter Norvig.
This is a solution to a Sudoku. https://github.com/huherto/aima3/blob/master/src/csp/Sudoku....
This is a solution to the Map Coloring problem. https://github.com/huherto/aima3/blob/master/src/csp/MapColo...
I thought I also have a solution for the Einstein riddle using this framework, but did that with a regular search. http://humbertook.blogspot.com/2010/12/resolucion-algoritmic...
It is a good illustration of code-as-data in Lisp. It's just that in this case, code-as-data doesn't seem to be a particular advantage in solving the problem (it's not a disadvantage either, just a stylistic difference).
So this article could have been 'A C solution to "Einsteins Riddle"' if C had been chosen as the language. Not a criticism, just a clarification, since HN is full of people looking for the true potential of new/different languages.
Problem solving and algorithms exist independent of programming languages.
What's unique to this version here, is the use of a code generator.
http://www.weitz.de/files/einstein-minimize.lisp
> So this article could have been 'A C solution to "Einsteins Riddle"' if C had been chosen as the language.
The code would have looked vastly different.
One issue that I found when solving problems like this is that, to achieve speed, it can become necessary to use many nested lets. That could hurt readability. Nobody wants to see a line of code nested 20 tabs deep!
require :: Bool -> [()]
require True = return ()
require False = []
sample :: [(Int, Int)]
sample = do
x <- [1,2,3,4,5]
y <- [1,2,3,4,5]
require (x == 2 * y)
return (x, y)