public
Last active

  • Download Gist
gistfile1.txt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
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.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.