Perl Script To Help Solve the "M I U" puzzle on Linux or Unix

Updated 6/02 - Blogspot bracket interpretation was showing the script incorrectly.

Hey There,

For this "Lazy Sunday" post, as promised, we're going to be taking a look, again, at formal systems and the "MI to MU" puzzle presented by Douglas R. Hofstadter in his book "Godel, Escher, Bach: An Eternal Golden Braid." And, also as promised, I've put together a Perl script to walk you through it, that should run on most Linux and Unix flavours (including Cygwin for Windows).

At the end of today's post, I've attached a simple Perl program that will let you attack this puzzle and solve it, while being certain that you're adhering to "the rules." I'm not a big fan of following the rules, in general (you can get a lot more done, and make significant breakthroughs, by ignoring convention ;), but a "formal system" can't exist without them.

Many of you may have already solved this puzzle on your own. If you'll permit me the opportunity to throw you a hint (assuming you haven't solved it yet), the answer is all in the way you perceive your boundaries, as laid out by the rules. The first time I tried to solve this I ended up with a few pieces of paper describing a decision-tree that I could barely comprehend (even though I'd written it ;). The third time I tried it, I realized that I was making assumptions, based on the "rules" presented, that were completely incorrect. In fact, by following the rules exactly (and removing any thought-prejudice I had with regards to what the rules made possible) I was able to solve it in the minimum number of steps.

Needless to say, this script isn't "perfect." For instance, I didn't bother to include extra code to do case-insensitive input matching and settled with creating a simple menu that only accepts the number of your selection as input (So, for instance, when you're presented with your options, you'll have to type 4 - rather than the first letter of the option - and if you're asked for string input, you'll need to enter "I" rather than "i", etc).

I spent most of my time writing this script trying to figure out how many different ways the puzzle could permutate and stray from the rules (and, of course, fixing those holes) rather than making it aesthetically pleasing. It will probably offend Perl purists, as well, since I wrote it as quickly as possible, with little regard for efficiency and elegance of the code ;)

For a refresher on the rules of this puzzle, and examples of valid rule applications, check out yesterday's post regarding formal systems.

Here's hoping you enjoy a little brain-teaser as much as I do, and that this simple Perl script helps break you out of any "strange loops" you might have in your subconscious that prevent you from reaching the solution!

Cheers





This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License

#!/usr/bin/perl

#
# mimu.pl - Solve the M I U formal system MI to MU puzzle by the rules
#
# 2008 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#

$start = "MI";
print "\nYour string is $start\n\n";

until ( $start eq "MU" ) {
 if ( $start eq "M" ) {
  print "\nYou Cannot Solve This\n";
  print "Puzzle Within This Formal\n";
  print "System From This Point On\n";
  print "Try Again!\n\n";
  exit;
 }
 print "Which rule to you want to apply?\n";
 print "1.  Add a U to end of string if string ends in I\n";
 print "2.  Duplicate a pattern following an M - Mx = Mxx\n";
 print "3.  Convert III to U\n";
 print "4.  Remove UU\n";
 print "5.  Quit\n";
 print "?> ";
 $response = <STDIN>;
 if ( $response == 1 ) {
  $test = $start;
  $test =~ s/^.*(I)$/$1/;
  if ( $test eq "I" ) {
   $start = $start . "U";
   print "\nYour string is now $start\n\n";
  } else {
   print "\nLast letter is not an I, cannot add U\n\n";
   print "Your string is still $start\n\n";
  }
   
 } elsif ( $response == 2 ) {
  print "\nWhat string do you want to duplicate?\n\n";
  $response = <STDIN>;
  chomp($response);
  if ( $response =~ /^ * *$/ ) {
   print "\nNo Input Received\n\n";
   print "Your string is still $start\n\n";
   next;
  }
  if ( $start =~ /^M$response.*$/ ) {
   print "\nDuplicating $response\n\n";
   $start =~ s/^(M)($response)(.*)$/$1$2$2$3/;
   print "Your string is now $start\n\n";
  } else {
   print "\nThe string $response does not follow your M\n\n";
   print "Your string is still $start\n\n";
  }
 } elsif ( $response == 3 ) {
  undef @tripIs;
  $string = $start;
  $char = 'III';
  $offset = 0;

  $result = index($string, $char, $offset);
  if ( $result == -1 ) {
   print "\nCannot Find III in your string\n\n";
   print "\nYour string is still $start\n\n";
   next;
  }

  while ($result != -1) {
   push(@tripIs, "$result");
   $offset = $result + 1;
   $result = index($string, $char, $offset);
  }
  print "\nFrom left to right, which offset\n";
  print "of III would you like to replace?\n\n";
  if ( defined @tripIs ) {
   foreach $triplet (@tripIs) {
    print "${triplet}: III\n";
    $count++;
   }
  }
  print "\n";
  chomp($response = <STDIN>);
  $temp = substr($string, $response, 3);
  if ( $temp ne "III" ) {
   print "\nCannot Find III At Index $response\n\n";
   print "\nYour string is still $start\n\n";
  } else {
   substr($string, $response, 3) = 'U';
   $start = $string;
   print "\nYour string is now $start\n\n";
  }
 } elsif ( $response == 4 ) {
  undef @doubleUs;
  $string = $start;
  $char = 'UU';
  $offset = 0;

  $result = index($string, $char, $offset);
  if ( $result == -1 ) {
   print "\nCannot Find UU in your string\n\n";
   print "\nYour string is still $start\n\n";
   next;
  }

  while ($result != -1) {
   push(@doubleUs, "$result");
   $offset = $result + 1;
   $result = index($string, $char, $offset);
  }
  print "\nFrom left to right, which offset\n";
  print "of UU would you like to remove?\n\n";
  if ( defined @doubleUs ) {
   foreach $doubleu (@doubleUs) {
    print "${doubleu}: UU\n";
    $count++;
   }
  }
  print "\n";
  chomp($response = <STDIN>);
  $temp = substr($string, $response, 2);
  if ( $temp ne "UU" ) {
   print "\nCannot Find UU At Index $response\n\n";
   print "\nYour string is still $start\n\n";
  } else {
   substr($string, $response, 2) = '';
   $start = $string;
   print "\nYour string is now $start\n\n";
  }
 } elsif ( $response ==5 ) {
  print "\nYou quit with your string at $start\n\n";
  exit;
 } else {
  print "WTF?\n";
  print "\nYour string is still $start\n\n";
 }
}
print "\nYour string is $start\n\n";
print "Puzzle Solved!  Congrats\n\n";
exit;

, Mike