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.
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
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
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
0000 -G- 1010 -E- 0010 1101 -E- 0101 -G- 1111
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:
Then combine them to get the final answer:
There are certainly more elegant approaches, but I enjoyed this, and I hope you enjoyed reading it.