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:

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

Replies are listed 'Best First'.
Re: (Golf) Gödel, Escher, and Bach, Oh My!
by japhy (Canon) on Jul 03, 2001 at 18:37 UTC
    My very first attempt. (Note, Masem, your first example should be "MUUUU" => "M".) 
    sub mu {
# 43*5 + 15 = 230 chars
# 123456789_123456789_123456789_123456789_123
  my($f,$t,$s)=@_;return 0if$f eq$t;@_=$f;for
  my$i(1..$s){@_=map{(my$A=$_)=~s/I$/IU/;(my$
  B=$_)=~s/^M(.*)/M$1$1/;(my$C=$_)=~s/III/U/;
  (my$D=$_)=~s/UU//;grep{$_ ne$t||return$i}$A
  ,$B,$C,$D}@_;}0
}

    [download]


    japhy -- Perl and Regex Hacker
[reply]
[d/l]
      (my$C=$_)=~s/III/U/;

      [download]
      Rule 3 is the trickiest to implement. As I've noted in the update (it hasn't changed the problem, just addendum), MUIIIIU can go to both MUUIU and MUIUU. Needless to say, the regex above won't cut it (at least, it won't return the shortest transformation route).

      Also note that similar concerns apply to Rule 4; MIUUIUUI can go to MIIUUI and MIUUII, both which can go on to different strings.

      Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain
[reply]
[d/l]
Re: (Golf) Gödel, Escher, and Bach, Oh My!
by VSarkiss (Monsignor) on Jul 03, 2001 at 18:51 UTC
    I don't think this is right:
    mu( "MUUUU", "MU", 20 ); # returns 2
    According to the rules, a string with no I's always transforms into a string with an even number of U's (if it has an M at the beginning): rule 2 doubles the number of U's, rule 4 removes an even number, rules 1 and 3 never apply if there are no I's, and no rule can add an I if one isn't there to start with.

    Masem, were you able to make this derivation or is "MU" a typo for "M"?

    BTW, I agree with your assessment of GEB. A rare combination of fun and enlightening. My favorites are the dialogues, especially "Contracrostipunctus" and the "Crab Canon". Had you noticed the former is a self-referential double acrostic?

    Update: Man, by the time I analyze the first example, japhy already has a solution....

[reply]
      Had you noticed the former is a self-referential double acrostic?

      :-)

      The whole book is a self-reference full of self-references and recursions.
      I read it twice cover to cover. Once you reach the end, you might as well think you are back at the beginning.

      It's like a 'Möbiusband', an 'Eternal Golden Braid'.
      That's another self reference, EGB <-> GEB

[reply]
        Heh. Only twice? ;-) You've almost certainly missed some of the games.

        I took a seminar with Hofstadter in the early 80's about the book. I thought I'd read it thoroughly, and I was stunned at how much I'd missed.

        I don't have my copy with me, but a couple I remember:

        • A reference in the bibliography to "Copper, Silver, Gold: An Indestructible Metallic Alloy" by Gebstadter, Egbert B. The book is described as "a turgid, confused mess" (something like that), which is an actual quote from one of the first reviews of GEB (pre-Pulitzer, of course).
        • A lot of people miss the second level of "Contracrostipunctus". If you line up the acrostic, it reads: 
          Hofstadter's
Contracrostipunctus
Acrostically
Backwards
Spells
'J. S. Bach'
          And it does, down to the punctuation!
        For more fun, read Le Ton Beau de Marot for some of what they went through to translate GEB into other languages.
[reply]
Re: (Golf) Gödel, Escher, and Bach, Oh My!
by blakem (Monsignor) on Jul 03, 2001 at 23:56 UTC
    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.

    I couldn't agree more. The GEB is a great read and takes you down some wonderfully twisty thought trails. The amazing thing is that its still relevant over 20 years later.

    -Blake
    p.s. I haven't ever made it through the last 100 pages or so either ;-)

    Update I finally read the last part of GEB. What a great book!

[reply]
Re: (Golf) Gödel, Escher, and Bach, Oh My!
by chipmunk (Parson) on Jul 06, 2001 at 00:13 UTC
    Here's my solution. It's 184 characters: 
    sub mu {
for(@s=($_[0],$c=0);$c<$_[2];){($_=shift@s or$c++,$s[@s]=0,next
)eq$_[1]&&return$c;$s[@s]="$_$1"if/^M/;/I$/and$s[@s]=$_.U;$s[
@s]="$`$'"while/UU/g;$s[@s]=$`.U.substr$',2while/I(?=II)/g}0
}

    [download]
    I believe it handles all the cases correctly. Here are the tests I used: 
    print mu( "MUUUU", "M", 20 );   # returns 2
print mu( "MI", "MU", 7 );      # returns 0
print mu( "MI", "MI", 20 );     # returns 0
print mu( "MI", "MUIUI", 20);   # returns 4
print mu( "MI", "MUIUI", 3 );   # returns 0
print mu( "MIIII", "MIU", 4);   # returns 1
print mu( "MI", "MIIU", 4);     # returns 2

    [download]
    The second to last line tests rule 3 where there are four Is in a row, and the last line tests rule 1.

    I switched the limit on the second test from 20 to 7 because I didn't have the patience to wait for the sub to run through all the possibilities to 20 steps. :)

[reply]
[d/l]
[select]

Back to Meditations