4 ms·
Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
- bentcorner 13y agoAfter having spent time doing these puzzles as a child, it strikes me just now that they have a large similarity to Sudoku puzzles.
- huherto 13y agoInteresting, they are very similar. Both are constraint satisfaction problems. 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.java 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/MapColoring.java 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-algoritmica-del-problema-de.html http://humbertook.blogspot.com/2010/12/resolucion-algoritmic...
- taeric 13y agoSeems perfectly crafted for prolog. So... I'd love to see how this compares to a solution in http://docs.racket-lang.org/racklog/ http://docs.racket-lang.org/racklog/
- lispm 13y agoProlog solution in Lisp, here LispWorks: http://lispm.de/source/misc/kw-zebra.lisp http://lispm.de/source/misc/kw-zebra.lisp
- MrRoger 13y agohttp://rosettacode.org/wiki/Zebra_puzzle#Racket http://rosettacode.org/wiki/Zebra_puzzle#Racket Clojure, using core.logic, is also there for good measure.
- pge 13y agoFor an elegant and efficient solution method for this class of problems (which includes sudoku), check out donald knuths dancing links algorithm.
- Crito 13y agoHmm, seems like this could potentially be solved in a cool way using the amb operator. Might have to give that a shot later today.
- japr59 13y agoDefinitely. For anybody interested, http://mitpress.mit.edu/sicp/full-text/sicp/book/node90.html http://mitpress.mit.edu/sicp/full-text/sicp/book/node90.html offers a nice introduction to the amb operator. 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!
- tonetheman 13y agoOh node programmers love that... :)
- twfarland 13y agoHaskell lists also work nicely for nondeterministic computation.
- andolanra 13y agoIndeed, we can use Haskell lists as the amb operator and implement require as require :: Bool -> [()] require True = return () require False = [] and then express amb-like computations in effectively the same way: sample :: [(Int, Int)] sample = do x <- [1,2,3,4,5] y <- [1,2,3,4,5] require (x == 2 * y) return (x, y) after which the value of sample is [(2,1),(4,2)]. (Also, my require is effectively the same as the guard function found in Control.Monad, specialized for lists.)
- vukk 13y agoOne way to elegantly describe and solve such a problem would be Answer Set Programming.
- scast 13y agoAlso, checkout potassco ASP solver. Beautiful work and superb performance. YMMV.
- aufreak3 13y agoIf any of you actually need such constraint satisfaction in javascript, checkout my fd.js library [1]. You'll find einstein, sudoku and other puzzles in the tests.js file. 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 https://github.com/srikumarks/fd.js [2] http://minhtule.github.io/Search-Tree-Visualization/ http://minhtule.github.io/Search-Tree-Visualization/
- blahedo 13y agoPresented with a page like this, obviously I sat down to solve the puzzle. :) For others who do the same, CRUCIAL CLARIFICATION: The constraint that "The green house is on the left of the white house" must be read as saying that the green house is immediately to the left of the white house, not merely that it is somewhere to the left (otherwise you don't have quite enough information to continue). 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.
- FatalError 13y agoIn case anyone else misunderstood the title, this article doesn't demonstrate the unique ability of Lisp to solve this problem. The method they use is constraint solving using backtracking. This could be implemented in any language. 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.
- lispm 13y ago> the unique ability of Lisp to solve this problem 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 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.
- zaph0d 13y agoThese kind of problems are more elegantly solved in logic (aka relational) programming languages like Prolog and similar logic programming implementations like miniKanren & Clojure's core.logic. Here's the same problem solved using Clojure's core.logic library https://github.com/swannodette/logic-tutorial/blob/master/src/logic_tutorial/tut3.clj https://github.com/swannodette/logic-tutorial/blob/master/sr...
- Theyeard 13y agoA different version of this riddle in Prolog/JavaScript: https://curiosity-driven.org/prolog-interpreter#puzzle https://curiosity-driven.org/prolog-interpreter#puzzle
- todd8 13y agoIn this riddle, the search space is a list of five permutations, the first being a permutation of the five nationalities (Brit, Swede, etc.), the next being a permutation of the five house colors and so on. A brute-force search would need to search (5!)^5 possibilities because there are 5! (equal to 120) permutations of 5 elements. 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]) On my old laptop this solution runs in 0.023 seconds of real time using Python 2.7. I haven't tried it using Pypy. Notice that in order to cut off branches of the search space as soon as possible, I introduce the tests for the constraints as soon as possible while generating the permutations. This is standard Python and only needs one function (permutations) from the standard library.
- mumrah 13y agoVery cool solution. Out of curiosity, how many iterations complete before finding the solution?