Prefix: If you haven't yet had a chance to read Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas Hofstadter, you really really should try; this is a wonderful book on meta-mathematics and patterns and AI and .... well, lots of ideas. I've always been able to read it up to the last few chapters at which point my mind explodes. It's a fascinatingly deep book.

Now, one of the first puzzles is called the MU puzzle. It's rather simple:

• A 'string' is made up of characters 'M', 'I', and 'U'.
• A string can be transformed into another string using any of the 4 following rules:
  1. If the string ends in I, you can create a new string by adding a U. (MUI -> MUIU)
  2. If your string starts with M (and thus represented by Mx), you can create a new string that is Mxx (MUI -> MUIUI)
  3. If your string contains III, you can create a new string by replacing that with a U (MUIII -> MUU)
  4. If your string contains UU, you can create a new string by dropping that entirely. (MUUI -> MI)
• The rules above are optional.

Now, the puzzle that is in the book is to try to transform MI to MU. Much of the book shows that this is impossible. This golf isn't going to go that far.

Given the above rules for the MU-puzzle, and two strings, the starting and target strings (only made up of M, I, or U), and a number that is the maximum number of steps.

Find the perl golf solution that either returns the shortest number of steps it takes to get from the starting string to the target string, or zero if no such transformation is possible within the maximum number of steps. Zero should also be returned if the target string equals the starting string.

Note that each step is *1* application of any rule above; that is, "MUUUU" to "M" requires 2 steps. (MUUUU->MUU->M).

Example usages is as below:

# call as mu ( $start, $targer, $max );
mu( "MUUUU", "M", 20 );   # returns 2 UPDATED!!!!!! (thanks japhy)
mu( "MI", "MU", 20 );     # returns 0
mu( "MI", "MI", 20 );     # returns 0
mu( "MI", "MUIUI", 20);   # returns 4
mu( "MI", "MUIUI", 3 );   # returns 0
[download]

And as a hint, double maps are possibly your friends.

Update : fixed the problem in the example above. And as another hint (based on japhys first go), be aware that MUIIIIU can go to both MUIUU and MUUIU.

---

Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

---

In reply to (Golf) Gödel, Escher, and Bach, Oh My! by Masem

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! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

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:
	&		&
	<		&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.