gistfile1.txt

The Challenge
-------------
Given the following riddle, write a regular expression describing all possible answers,
assuming you never make a move which simply undoes the last one you made.

The Riddle
----------
You are on your way somewhere, taking with you your cabbage, goat, and wolf, as always.
You come upon a river and are compelled to cross it, but you can only carry one of the
three companions at a time. None of them can swim because this isn't THAT kind of riddle.
Further, if you should ever leave the goat alone with the cabbage, or the wolf alone
with the goat, one will devour the other and this riddle will take a dark turn. How do
get yourself and all three of your faithful companions to the other side of the river
in one piece?

Let C,G,W, and E indicate trips across the river carrying the cabbage, goat, wolf, or
nothing, respectively.

A Brute Force Solution
----------------------
This may not be elegant, but by god it'll get us there. This riddle is a system with
four binary bits of state, side of the river on which the three companions and you
currently reside. Lets call the starting side 0 and the goal side 1. We can represent
any state as a 4 bit number, with the high order bit representing you, then the cabbage,
goat, and wolf. We can then represent all possible states by counting:

0000  0001  0010  0011

0100  0101  0110  0111

1000  1001  1010  1011

1100  1101  1110  1111

Next, we can eliminate all the illegal states, that is, states where the goat and cabbage
or goat and wolf are on one side of the river, but we're on the other:

0000  0001  0010

0100  0101

            1010  1011

      1101  1110  1111

Now, build a graph of states which are one move apart. This is a bit tricksy, because
every legal move will flip the state of the high order bit, and at most one other bit,
where the other bit must have started in the same state as the high order bit.
We'll also label each edge with the move that produced it

                        1110 -G- 0100
                       /             \
                      C               W
                     /                 \
0000 -G- 1010 -E- 0010                  1101 -E- 0101 -G- 1111
                     \                 /
                      W               C
                       \             /
                        1011 -G- 0001

We can translate that pretty directly into a regex with the intuition that each solution
starts and ends the same, but could contain some number of times around the loop in
one direction or the other before getting there. Our restriction against taking back
a move just made means once you've gone one direction around the loop, you can only
go that direction. We start by writing two regexes, one for each direction:

Clockwise: GE(CGWCGW)*CGWEG

Counterclockwise: GE(WGCWGC)*WGCEG


Then combine them to get the final answer:

GE[(CGWCGW)*CGW|(WGCWGC)*WGC]EG


There are certainly more elegant approaches, but I enjoyed this, and I hope you enjoyed reading it.