Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)

weitz.de

Post reply on HN
Print view View original

11–20 of 23 posts

Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)

#11

Post by tonetheman »

japr59 wrote: post #9
Crito wrote: post #7

Hmm, seems like this could potentially be solved in a cool way using the amb operator. Might have to give that a shot later today.

Definitely. For anybody interested, 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 let s. That could hurt readability. Nobody wants to see a line of code nested 20 tabs deep!

Oh node programmers love that... :)

Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)

#13

Post by aufreak3 »

If 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 [2] http://minhtule.github.io/Search-Tree-Visualization/

Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)

#15

Post by blahedo »

Presented 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.

Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)

#16

Post by andolanra »

twfarland wrote: post #14
Crito wrote: post #7

Hmm, seems like this could potentially be solved in a cool way using the amb operator. Might have to give that a shot later today.

Haskell lists also work nicely for nondeterministic computation.

Indeed, 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
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.)

Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)

#17

Post by FatalError »

In 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.

Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)

#18

Post by zaph0d »

These 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/sr...

Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)

#19

Post by lispm »

FatalError wrote: post #17

In 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 eith…

> 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

> 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.

Post reply on HN