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

[download]
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

[download]
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

[download]
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":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.