Professional Web Applications Themes

eistein's riddle - Ruby

this will keep you busy Einstein wrote the following riddle. He said that 98% of the world could not solve it. There are 5 houses in 5 different colors in a row. In each house lives a person with a different nationality. The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet. No owners have the same pet, smoke the same brand of cigar, or drink the same beverage. Other facts: 1. The Brit lives in the red house. 2. The Swede keeps dogs as pets. 3. The Dane drinks ...

  1. #1

    Default eistein's riddle



    this will keep you busy

    Einstein wrote the following riddle. He said that 98% of the world could not
    solve it.

    There are 5 houses in 5 different colors in a row. In each house lives a
    person with a different nationality. The 5 owners drink a certain type of
    beverage, smoke a certain brand of cigar, and keep a certain pet. No owners
    have the same pet, smoke the same brand of cigar, or drink the same
    beverage. Other facts:

    1. The Brit lives in the red house.
    2. The Swede keeps dogs as pets.
    3. The Dane drinks tea.
    4. The green house is on the immediate left of the white house.
    5. The green house`s owner drinks coffee.
    6. The owner who smokes Pall Mall rears birds.
    7. The owner of the yellow house smokes Dunhill.
    8. The owner living in the center house drinks milk.
    9. The Norwegian lives in the first house.
    10. The owner who smokes Blends lives next to the one who keeps cats.
    11. The owner who keeps the horse lives next to the one who smokes Dunhill.
    12. The owner who smokes Bluemasters drinks beer.
    13. The German smokes Prince.
    14. The Norwegian lives next to the blue house.
    15. The owner who smokes Blends lives next to the one who drinks water.


    The question is : WHO OWNS THE FISH?


    -a
    --

    ATTN: please update your address books with address below!

    ================================================== =============================
    | EMAIL :: Ara [dot] T [dot] Howard [at] noaa [dot] gov
    | PHONE :: 303.497.6469
    | ADDRESS :: E/GC2 325 Broadway, Boulder, CO 80305-3328
    | STP :: http://www.ngdc.noaa.gov/stp/
    | NGDC :: http://www.ngdc.noaa.gov/
    | NESDIS :: http://www.nesdis.noaa.gov/
    | NOAA :: http://www.noaa.gov/
    | US DOC :: http://www.commerce.gov/
    |
    | The difference between art and science is that science is what we
    | understand well enough to explain to a computer.
    | Art is everything else.
    | -- Donald Knuth, "Discover"
    |
    | /bin/sh -c 'for l in ruby perl;do $l -e "print \"\x3a\x2d\x29\x0a\"";done'
    ================================================== =============================

    Ara.T.Howard Guest

  2. #2

    Default Re: eistein's riddle [SPOILER!]

    * Ara.T.Howard <gov> [Feb, 03 2004 22:50]: 

    [conditions]
     

    Sorry to spoil it, but it's the German. Hooray, I'm one of the 2% who
    can solve it. Thank god I have such a high IQ that this doesn't inflate
    my self-esteem any further ;-)
    nikolai

    P.S.
    This can be solved using finite-state transducers, see
    http://www.xrce.xerox.com/competencies/content-ysis/fsCompiler/famples.html#Einstein1
    for a solution. I'm not saying that I had actually read this article
    before trying out the puzzle, but I have, so that's why I know ;-)
    D.S.

    --
    ::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::
    ::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::
    ::: page: www.pcppopper.org :: fun atm: gf,lps,ruby,lisp,war3 :::
    main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}


    Nikolai Guest

  3. #3

    Default Re: eistein's riddle (solution)

    Here's the output of a Ruby program I wrote a couple of months ago to solve
    puzzles like this:

    cr cg cw cy cb nb ns nd nn ng bt bc bm bb bw zp zd zb zm zc pd pb pc ph pf
    +== == == == ==+== == == == ==+== == == == ==+== == == == ==+== == == == ==+
    i1|-- -- -- ++ --|-- -- -- ++ --|-- -- -- -- ++|-- ++ -- -- --|-- -- ++ -- --|
    i2|-- -- -- -- ++|-- -- ++ -- --|++ -- -- -- --|-- -- ++ -- --|-- -- -- ++ --|
    i3|++ -- -- -- --|++ -- -- -- --|-- -- ++ -- --|++ -- -- -- --|-- ++ -- -- --|
    i4|-- ++ -- -- --|-- -- -- -- ++|-- ++ -- -- --|-- -- -- -- ++|-- -- -- -- ++|
    i5|-- -- ++ -- --|-- ++ -- -- --|-- -- -- ++ --|-- -- -- ++ --|++ -- -- -- --|
    +== == == == ==+== == == == ==+== == == == ==+== == == == ==+== == == == ==+
    pd|-- -- ++ -- --|-- ++ -- -- --|-- -- -- ++ --|-- -- -- ++ --|
    pb|++ -- -- -- --|++ -- -- -- --|-- -- ++ -- --|++ -- -- -- --|
    pc|-- -- -- ++ --|-- -- -- ++ --|-- -- -- -- ++|-- ++ -- -- --|
    ph|-- -- -- -- ++|-- -- ++ -- --|++ -- -- -- --|-- -- ++ -- --|
    pf|-- ++ -- -- --|-- -- -- -- ++|-- ++ -- -- --|-- -- -- -- ++|
    +== == == == ==+== == == == ==+== == == == ==+== == == == ==+
    zp|++ -- -- -- --|++ -- -- -- --|-- -- ++ -- --|
    zd|-- -- -- ++ --|-- -- -- ++ --|-- -- -- -- ++|
    zb|-- -- -- -- ++|-- -- ++ -- --|++ -- -- -- --|
    zm|-- -- ++ -- --|-- ++ -- -- --|-- -- -- ++ --|
    zc|-- ++ -- -- --|-- -- -- -- ++|-- ++ -- -- --|
    +== == == == ==+== == == == ==+== == == == ==+
    bt|-- -- -- -- ++|-- -- ++ -- --|
    bc|-- ++ -- -- --|-- -- -- -- ++|
    bm|++ -- -- -- --|++ -- -- -- --|
    bb|-- -- ++ -- --|-- ++ -- -- --|
    bw|-- -- -- ++ --|-- -- -- ++ --|
    +== == == == ==+== == == == ==+
    nb|++ -- -- -- --|
    ns|-- -- ++ -- --|
    nd|-- -- -- -- ++|
    nn|-- -- -- ++ --|
    ng|-- ++ -- -- --|
    +== == == == ==+

    Legend:
    i1 house 1 cr red nb Brit bt tea zp Pall Mall pd dogs
    i2 house 2 cg green ns Swede bc coffee zd Dunhill pb birds
    i3 house 3 cw white nd Dane bm milk zb Blends pc cats
    i4 house 4 cy yellow nn Norwegian bb beer zm Bluemasters ph horse
    i5 house 5 cb blue ng German bw water zc Prince pf fish

    Regards,
    Pit


    Pit Guest

  4. #4

    Default Re: eistein's riddle

    Hardly efficient (in fact I haven't yet run it through to completion),
    but since we were recently talking about amb:
    ---
    $colors = ["red", "white", "yellow", "blue", "green"]
    $nationalities = ["Brit", "Swede", "Dane", "Norwegian", "German"]
    $beverages = ["tea", "coffee", "milk", "beer", "water"]
    $cigars = ["Pall Mall", "Blends", "Dunhill", "Prince", "Bluemasters"]
    $pets = ["dogs", "birds", "cats", "horse", "fish"]

    class House
    attr_reader :color, :nationality, :beverage, :cigar, :pet

    def initialize
    color = $amb.one_of($colors)
    nationality = $amb.one_of($nationalities)
    beverage = $amb.one_of($beverages)
    cigar = $amb.one_of($cigars)
    pet = $amb.one_of($pets)
    end
    end

    def find(property, value)
    $houses.detect{|h| h.send(property) == value} || $amb.fail
    end

    def color(s) find(:color, s) end
    def nationality(s) find(:nationality, s) end
    def beverage(s) find(:beverage, s) end
    def cigar(s) find(:cigar, s) end
    def pet(s) find(:pet, s) end

    def next_door(h1, h2)
    ($houses.index(h1) - $houses.index(h2)).abs == 1
    end

    $amb = Amb.new
    $houses = (1..5).collect{House.new}

    #fact 1
    $amb.assert(nationality("Brit").color == "red")
    #fact 2
    $amb.assert(nationality("Swede").pet == "dogs")
    #fact 3
    $amb.assert(nationality("Dane").beverage == "tea")
    #fact 4
    $amb.assert(houses.index(color("white")) -
    houses.index(color("green")) == 1)
    #fact 5
    $amb.assert(color("green").beverage == "coffee")
    #fact 6
    $amb.assert(cigar("Pall Mall").pet == "birds")
    #fact 7
    $amb.assert(color("yellow").cigar == "Dunhill")
    #fact 8
    $amb.assert(houses[2].beverage == "milk")
    #fact 9
    $amb.assert(houses[0].nationality == "Norwegian")
    #fact 10
    $amb.assert(next_door(cigar("Blends"), pet("cats")))
    #fact 11
    $amb.assert(next_door(cigar("Dunhill"), pet("horse")))
    #fact 12
    $amb.assert(cigar("Bluemasters").beverage == "beer")
    #fact 13
    $amb.assert(nationality("German").cigar == "Prince")
    #fact 14
    $amb.assert(next_door(nationality("Norwegian"), color("blue")))
    #fact 15
    $amb.assert(next_door(cigar("Blends"), beverage("water")))

    #No owners have the same pet, smoke the same brand of cigar
    #or drink the same beverage.
    $amb.assert(houses.collect{|h| h.color}.uniq.size == 5)
    $amb.assert(houses.collect{|h| h.nationality}.uniq.size == 5)
    $amb.assert(houses.collect{|h| h.beverage}.uniq.size == 5)
    $amb.assert(houses.collect{|h| h.cigar}.uniq.size == 5)
    $amb.assert(houses.collect{|h| h.pet}.uniq.size == 5)

    puts "The " + pet("fish").nationality + " owns the fish"
    Avi Guest

  5. #5

    Default Re: eistein's riddle

    > Einstein wrote the following riddle. He said that 98% of the world could not 

    [... riddle snipped]

    For an interesting way of solving this problem, try this -- draw the
    five lots on a piece of paper. Get a set of differently colored lego
    bricks. Use a different color for each property (e.g. red for
    nationality, blue for house color, white for beverage, ...) and mark the
    bricks "brit", "swede", "red, "dog", etc...

    For each fact in the list -- try to express it with the bricks, for example:

    1. The Brit lives in the red house.

    => Snap together the bricks for "brit" and "red"

    4. The green house is on the immediate left of the white house.

    => Put the brick for "green" to the left of the brick for "white".

    8. The owner living in the center house drinks milk.

    => Put the brick for "milk" on the center lot that you have drawn.

    This demonstrates how amazingly much simpler a problem can become when
    you have the right cognitive tools. Kind of like programming in ruby.
    (To get back on topic ;)

    // Niklas
    Niklas Guest

  6. #6

    Default Re: eistein's riddle

    Excuse my ignorance, but what is amb?

    Guillaume.

    On Tue, 2004-02-03 at 21:55, Avi Bryant wrote: 




    Guillaume Guest

  7. #7

    Default Re: eistein's riddle

    Sorry to respond to myself. You posted earlier a description and
    implementation of amb in ruby-talk:91075.



    On Wed, 2004-02-04 at 14:56, Guillaume Marcais wrote: 
    >
    >
    >[/ref]




    Guillaume Guest

  8. #8

    Default Re: eistein's riddle

    Very interesting code... but hangup forever...

    /einstein.rb:24:in `find': Interrupt from ./einstein.rb:24:in
    `detect'
    from ./einstein.rb:24:in `each'
    from ./einstein.rb:24:in `detect'
    from ./einstein.rb:24:in `find'
    from ./einstein.rb:28:in `nationality'
    from ./einstein.rb:40

    If i runnit with irb:


    einstein.rb(main):061:0> puts "The " + pet("fish").nationality + " owns
    the fish"
    The Brit owns the fish
    => nil

    But seems wrong answer...

    I think in 'detect' line is the bug...


    ----------- CODE ---------------------------------------

    #!/usr/local/bin/ruby

    class Amb
    def initialize
    failureContinuation = proc{raise "Amb goal tree exhausted"}
    end

    def fail
    failureContinuation.call(nil)
    end

    def assert(bool)
    fail unless bool
    end

    def choose(procArray)
    kPrev = failureContinuation
    callcc do |kEntry|
    procArray.each do |p|
    callcc do |kNext|
    failureContinuation = proc do |v|
    failureContinuation = kPrev
    kNext.call(v)
    end
    kEntry.call(p.call)
    end
    end
    kPrev.call(nil)
    end
    end

    def one_of(enumerable)
    choose(enumerable.collect{|ea| proc{ea}})
    end

    def maybe
    one_of([true, false])
    end
    end

    $colors = ["red", "white", "yellow", "blue", "green"]
    $nationalities = ["Brit", "Swede", "Dane", "Norwegian", "German"]
    $beverages = ["tea", "coffee", "milk", "beer", "water"]
    $cigars = ["Pall Mall", "Blends", "Dunhill", "Prince", "Bluemasters"]
    $pets = ["dogs", "birds", "cats", "horse", "fish"]

    class House
    attr_reader :color, :nationality, :beverage, :cigar, :pet

    def initialize
    color = $amb.one_of($colors)
    nationality = $amb.one_of($nationalities)
    beverage = $amb.one_of($beverages)
    cigar = $amb.one_of($cigars)
    pet = $amb.one_of($pets)
    end
    end

    def find(property, value)
    $houses.detect{|h| h.send(property) == value} || $amb.fail
    end

    def color(s) find(:color, s) end
    def nationality(s) find(:nationality, s) end
    def beverage(s) find(:beverage, s) end
    def cigar(s) find(:cigar, s) end
    def pet(s) find(:pet, s) end

    def next_door(h1, h2)
    ($houses.index(h1) - $houses.index(h2)).abs == 1
    end

    $amb = Amb.new
    $houses = (1..5).collect{House.new}
    puts "Finding.... red..\n"
    $amb.assert(nationality("Brit").color == "red")
    #fact 2
    puts "Finding.... dogs..\n"
    $amb.assert(nationality("Swede").pet == "dogs")
    #fact 3
    $amb.assert(nationality("Dane").beverage == "tea")
    #fact 4
    $amb.assert(houses.index(color("white")) -
    houses.index(color("green")) == 1)
    #fact 5
    $amb.assert(color("green").beverage == "coffee")
    #fact 6
    $amb.assert(cigar("Pall Mall").pet == "birds")
    #fact 7
    $amb.assert(color("yellow").cigar == "Dunhill")
    #fact 8
    $amb.assert(houses[2].beverage == "milk")
    #fact 9
    $amb.assert(houses[0].nationality == "Norwegian")
    #fact 10
    $amb.assert(next_door(cigar("Blends"), pet("cats")))
    #fact 11
    $amb.assert(next_door(cigar("Dunhill"), pet("horse")))
    #fact 12
    $amb.assert(cigar("Bluemasters").beverage == "beer")
    #fact 13
    $amb.assert(nationality("German").cigar == "Prince")
    #fact 14
    $amb.assert(next_door(nationality("Norwegian"), color("blue")))
    #fact 15
    $amb.assert(next_door(cigar("Blends"), beverage("water")))
    puts "All 15 facts...\n"

    Regards,
    --
    Enrique Meza <com>


    Enrique Guest

  9. #9

    Default Re: eistein's riddle

    I ran it and it crashed on me after 4 days of hard computation (on a
    double PII 400Mhz)!

    But I love the method though.

    Guillaume.

    % time ruby amb-test2.rb
    amb-test2.rb:45: undefined local variable or method `houses' for
    main:Object (NameError)
    Command exited with non-zero status 1
    352198.51user 252.87system 98:25:05elapsed 2%CPU (0avgtext+0avgdata
    0maxresident)k
    0inputs+0outputs (273major+54916minor)pagefaults 0swaps

    On Sun, 2004-02-08 at 20:17, Avi Bryant wrote: 




    Guillaume Guest

  10. #10

    Default Re: eistein's riddle

    On Wed, Feb 11, 2004 at 09:08:52AM +0900, Guillaume Marcais wrote: 

    Wouldn't it be faster to do it with a pencil and paper? It took me less
    than 10 minutes.


    --
    Daniel Carrera | No trees were harmed in the generation of this e-mail.
    PhD student. | A significant number of electrons were, however, severely
    Math Dept. UMD | inconvenienced.



    Daniel Guest

  11. #11

    Default Re: eistein's riddle

    Agreed. On that particular example I was more interested by the amb
    class and how it works. I thought it led to an elegant way to express
    and solve problems. But way too slow to be of any use for not so big
    problems.

    Guillaume.

    Le 10 févr. 04, à 19:20, Daniel Carrera a écrit :
     
    >
    > Wouldn't it be faster to do it with a pencil and paper? It took me
    > less
    > than 10 minutes.
    >
    >
    > --
    > Daniel Carrera | No trees were harmed in the generation of this
    > e-mail.
    > PhD student. | A significant number of electrons were, however,
    > severely
    > Math Dept. UMD | inconvenienced.
    >
    >[/ref]




    Guillaume Guest

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139