Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Solving riddles with Perl

by Limbic~Region (Chancellor)
on Sep 17, 2002 at 22:31 UTC ( #198675=perlmeditation: print w/ replies, xml ) Need Help??

I love problem solving. I love riddles. I love programming. These things are not unique, but I haven't found too many resources that depict methodologies on how to combine all three. Consider the following riddle from one of the Die Hard (I think) movies.

You have a 5 gallon bucket and a 3 gallon bucket with as much water as you need, but no other measuring devices. Fill the 5 gallon bucket with exactly 4 gallons of water. The solution is fairly simple:

  • Fill the 5 gallon bucket all the way up
  • Pour it into the 3 gallon bucket until it is full
  • Empty the 3 gallon bucket
  • Pour the remaining 2 gallons into the 3 gallon bucket
  • Fill the 5 gallon bucket all the way up
  • Finish filling the 3 gallon bucket

    or

  • Fill the 3 gallon bucket all the way up
  • Pour all of the 3 gallons into the 5 gallon bucket
  • Fill the 3 gallon bucket all the way up
  • Finish filling the 5 gallon bucket
  • Empty the 5 gallon bucket
  • Pour the 1 gallon in the 3 gallon bucket into 5 gallon
  • Fill up the 3 gallon bucket
  • Pour it into the 5 gallon bucket

    To write this as a program, you need to be able to be able to create a decision tree. You need to be able to define a desired state. You need to be able to pipe the results of the decision back into the tree until you attain the desired state. A bonus would be to do this in the least number of iterations.

    It is easy to describe these with words.

  • I want to have 4 gallons in the 5 gallon bucket.
  • I can fill a bucket until it is full
  • I can empty a bucket
  • I can pour one bucket into another

    Of course there are some limitations on that last one

  • If the first bucket isn't empty to begin with
  • Until the first bucket is empty
  • or until the second bucket is full

    Is this type of programming practical with Perl? Would this program be too complex to generalize? If I were adept enough to write a program to solve the above riddle, it shouldn't be difficult to modify it to solve the following:

    A farmer has a chicken, grain, and a fox. He needs to cross a river and can only take one item with him at a time. He can cross as many times as he needs to, but he can not leave the chicken and the fox together or the chicken and grain.

    Solution available upon request. Better yet, write the program to solve it!

    I have always been fascinated with AI and "stateful" programming, but always felt that languages like C were just too cumbersome to casually dabble with. Is Perl the same?

    Limbic~Region

    PS

    This post was for open discussion, I didn't expect someone to write the code. I am more interested in open discussion about this type of programming. With that said, I am VERY interested to see if anyone is capable of writing the code described above in the general sense

  • Comment on Solving riddles with Perl
    Re: Solving riddles with Perl
    by mdillon (Priest) on Sep 17, 2002 at 22:44 UTC
      I don't know much about this sort of thing, but I do know there have been related discussions in the past, often involving AI::Perlog by Ovid or things otherwise related to Prolog. A search or Super Search may prove to be insightful.
    Re: Solving riddles with Perl
    by Helter (Chaplain) on Sep 19, 2002 at 13:29 UTC
      If you stretch your imagination enough (and Perl is good at letting that happen) you can solve these puzzles using Genetic algorithms.
      You could assign each character in a string a task:
      5 - fill 5 gallon bucket
      3 - fill 3 gallon bucket
      P - pour 5 into 3
      p - pour 3 into 5
      E - empty 5
      e - empty 3

      I don't think I'm missing anything. Your population would be strings of different lengths, maybe 3-10? I'm guessing here.

      Then your fitness function takes the string, and just follows the instructions like a recipie. This does mean that some semi-impossible things could happen, empty an empty bucket, fill a full bucket etc.

      Crossing is just taking random points in the string and swapping them.

      Once you have a good GA engine it is easy to replace the fitness function and the population generation functions, and in a few cases the crossing function (mutation too!).

      If I get bored sometime today maybe I'll code up an example.

      Doing a search on "Genetic Algorithms" turns up a few really good nodes.
      Helter

    Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Node Status?
    node history
    Node Type: perlmeditation [id://198675]
    Approved by myocom
    help
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others cooling their heels in the Monastery: (9)
    As of 2014-11-29 01:16 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      My preferred Perl binaries come from:














      Results (200 votes), past polls