The header for this website says, "Some useful stuff and some examples of how not to do it." This may fall into the latter category.
One of my kids had been playing a computer-based game which used a variety of word puzzles. The question he posed to me was to take a word, apply a small set of rules to it, as many times as necessary, and come up with another word. He would supply the rules and both words, and I would supply the sequence of rule applications which would effect the conversion.
(I'm no guru when it comes to Perl, so if you see something that could be expressed in a more efficient manner, please let me know.)
These are the rules:
1. Remove all 's'
2. Sort the characters of the word into alphabetic order
3. Convert all vowels to 'e'
4. Replace the first letter with 'n'
5. Drop the last letter
6. Replace letter pairs with 'ow'
My son then said that the start word was 'first' (or 'ant') and the stop word was 'now'. After some fiddling, resulting in the code below, I said, "With these rules you can't get from 'first' to 'now'. Not even from 'ant' to 'now'. But from 'gnat', yes."
So here's the code, for what it's worth. It was assumed that this would be run as a command line tool, so I load up the start word (stored in $root) and a recursion management flag (stored in $managed). Recursion management is defaulted to true. The recursion level is marked with $level and there's a hash, called %deadends, to keep track of "solutions" that shouldn't be pushed any further as they have already been proved not to get any closer to the solution.
Everything else happens in the apply function which looks at every possible combination of rules in pursuit of the target word. After getting the word to check from @_ with shift, a couple of variables are declared and a for loop initiated, stepping through the rules.
Each rule is evaluated against the passed in value in $arg, and stored in $res. $reason is cleared and each test applied to $res.
If $res is the same as $arg, $reason is "equal". If the length of $res is less than 3, $reason is set to "too short". If $managed is 1, and $res is already in the %deadends hash, $reason is set to "deadend", and if $res is equal to "now" (the goal, as it happens) then $reason is set to "found".
If $reason is not empty and not "equal" then print a newline, as many spaces as there are levels of recursion, the rule that got us here, the incoming word and the result of the rule application. If $reason is "deadend" then print an exclamation mark to show that a deadend has been reached, otherwise print a full stop.
If we've actually reached "now", indicate that with an asterisk. (We could exit the script at this point, but I left it to show all the possible paths to the stop word.)
If managing recursion, store the value of $res in the deadends hash.
Now, if $reason is, for some reason, empty, print a newline, as many spaces as there are recursion levels, the rule, and the $arg and the $res. Then increase the value of $level and recursively call apply with the contents of $res. When it returns, decrease the value of $level.
Here's the first call to apply, with a newline displayed once processing returns from the call.
Keeping track of dead-ends proved useful. Without it, the 'first' to 'now' attempt generated at 406K file (redirecting the output). With it, I got a 5K file. Similarly, 'ant' to 'now' was 1.8K without, and 457 bytes with. When it came to starting with 'gnat', a managed conversion generated an 8K file. Without management the laptop slowed to a crawl. After about five minutes I got an "Out of memory!" on stderr, so I killed the perl processing resulting in a 902 Megabyte file.
This is the result of a managed attempt with 'ant' as the start word:
Sadly, no asterisks. Next, the log of a managed run starting with 'gnat'. Success came quite quickly: start with 'gnat' and apply rules 2, 3, 4, 2, 4, 5, 6 and 2. An even shorter path appears further down: 3, 4, 2, 5, 6, and 4. The shortest appears to be 4, 2, 5, 6, 4 -- nnat, annt, ann, aow, now.
Writing this makes me wonder if I should have found some way to jump from a successful traversal back to 'gnat' rather than applying the rules to instances of 'now' in search of an extended path to 'now'. I leave that as an exercise to the reader, and if you work out how to do it, please let me know.
© Copyright Bruce M. Axtens, 2008
No comments:
Post a Comment