Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
I was reminded by a recent Reddit thread of the classic "get a goat, wolf, and cabbage across a river" problem (spazzy kittens version, painfully verbose Haskell version). You're on the left side of a river with a cabbage, goat, and wolf, and want to get them to the right side. The wolf will eat the goat, and the goat the cabbage, but only if you leave them alone. You can only fit one of them in your boat at a time.

The problem can be solved by computer with some backtracking, or by hand with some thought. Being a Perl programmer, I naturally thought to golf it, and thought that the best solution would involve a clever regex or substitution. Here's a terse, but un-obfuscated version:

sub wgc { return if $seen{"@_"}++; my%x=@_; if ($x{b} && $x{c} && $x{g} && $x{w}) { print+(sort keys%$_),"\n" for @h; exit; } elsif ((!$x{b} && ($x{c} && $x{g} || $x{g} && $x{w})) || ($x{b} && (!$x{c} && !$x{g} || !$x{g} && !$x{w}))) { return; } else { if ($x{b}) { delete $x{b}; for ('xx', keys %x) { my %y=%x; delete $y{$_}; local @h=(@h, \%y); wgc(%y); } } else { $x{b}=1; { local (@h) = (@h, \%x); wgc(%x); } for my $k (qw(c g w)) { if (!$x{$k}) { my %y=(%x,$k,1); local (@h) = (@h, \%y); wgc(%y); }; } } } } wgc
And here's the output, where "b", "c", "g", and "w" represent the boat, cabbage, goat, and wolf being on the right bank:
bg g bcg c bcw cw bcgw
I wasn't clever enough to come up with the regex solution, but here's a compressed version of the above, weighing in at 382379 strokes:
sub w{return if$s{"@_"}++;my%x=@_;if($x{b}&$x{c}&$x{g}&$x{w}){print+(s +ort keys%$_),"\n"for@h;exit;}elsif(($x{b}||!($x{c}&&$x{g}||$x{g}&&$x{ +w}))&&(!$x{b}||!(!$x{c}&&!$x{g}||!$x{g}&&!$x{w}))){if($x{b}){delete$x +{b};for(A,keys%x){my%y=%x;delete$y{$_};local@h=(@h,\%y);w(%y)}}else{$ +x{b}=1;{local@h=(@h,\%x);w(%x);}for(qw(c g w)){if(!$x{$_}){my%y=(%x,$ +_,1);local@h=(@h,\%y);w(%y)}}}}}w
Have at it!

In reply to Golf: Cabbage, Goat, Wolf by educated_foo

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (3)
As of 2022-01-16 20:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:












    Results (49 votes). Check out past polls.

    Notices?