Go back to Richel Bilderbeek's homepage.

Go back to Richel Bilderbeek's C++ page.

 

 

 

 

 

(C++) MU puzzle

 

The MU puzzle is a puzzle originally described in [1] and can be read online at [2]. I wrote a program to search for the solution, before I knew the solution to the puzzle.

 

//From http://www.richelbilderbeek.nl/CppMuPuzzle.htm
#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>


//From http://learningcppisfun.blogspot.com/2008/04/remove-duplicates-from-vector.html
template<typename T>
void RemoveDuplicates(std::vector<T>& v)
{
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
}

const std::vector<std::string> GetNext(const std::string& s)
{
  assert(!s.empty());
  //std::cout << "Getting nexts of " << s << '\n';
  std::vector<std::string> v;
  //Rule 1: if xI -> xIU
  if (s[s.size()-1]=='I')
  {
    const std::string t = s + "U";
    v.push_back(t);
  }
  //Rule 2: x -> xx
  {
    const std::string t = s + s;
    v.push_back(t);
  }
  //Rule 3: III -> U
  if (s.size()>=3)
  {
    const std::size_t max = s.size() - 2;
    const std::size_t sz = s.size();
    for (std::size_t i = 0; i!=max; ++i)
    {
      const std::string sub = s.substr(i,3);
      if (sub == "III")
      {
        const std::string t = s.substr(0,i) + "U" + s.substr(i+3,sz-i-3);
        v.push_back(t);
      }
    }
  }
  //Rule 4: UU -> (nothing)
  if (s.size()>=3)
  {
    const std::size_t max = s.size() - 1;
    const std::size_t sz = s.size();
    for (std::size_t i = 0; i!=max; ++i)
    {
      const std::string sub = s.substr(i,2);
      if (sub == "UU")
      {
        const std::string t = s.substr(0,i) + s.substr(i+2,sz-i-2);
        v.push_back(t);
      }
    }
  }
  //Remove duplicates
  RemoveDuplicates(v);

  //std::copy(v.begin(),v.end(),std::ostream_iterator<std::string>(std::cout,"\t"));
  //std::cout << '\n';
  return v;
}

int main()
{
  std::vector<std::string> v;
  v.push_back("I");
  for (std::size_t round = 0; ; ++round)
  {
    std::cout << "Starting round " << round << '\n';
    //Generate all candidates for next round
    std::vector<std::string> v_next; //Next round
    const std::size_t sz = v.size();
    for (std::size_t i=0; i!=sz; ++i)
    {
      if (v[i].size() > round) continue;
      std::cout << "Checking " << v[i] << '\n';
      const std::vector<std::string> v_temp = GetNext(v[i]);
      std::copy(v_temp.begin(),v_temp.end(),std::back_inserter(v_next));
    }
    //Append v_next
    std::copy(v_next.begin(),v_next.end(),std::back_inserter(v));
    //Remove duplicates
    RemoveDuplicates(v);
    //Check for U
    const std::string target = "U";
    if (std::find(v.begin(),v.end(),target)!=v.end())
    {
      std::cout << "U found!\n";
      break;
    }
  }
}

 

Screen output:

 

Starting round 0
Starting round 1
Checking I
Starting round 2
Checking I
Checking II
Checking IU
Starting round 3
Checking I
Checking II
Checking IIU
Checking IU
Starting round 4
Checking I
Checking II
Checking IIII
Checking IIU
Checking IU
Checking IUIU
Starting round 5
Checking I
Checking II
Checking IIII
Checking IIIIU
Checking IIU
Checking IU
Checking IUIU
Checking UI
Starting round 6
Checking I
Checking II
Checking IIII
Checking IIIIU
Checking IIU
Checking IIUIIU
Checking IU
Checking IUIU
Checking IUU
Checking UI
Checking UIU
Checking UIUI
Starting round 7
Checking I
Checking II
Checking IIII
Checking IIIIU
Checking IIU
Checking IIUIIU
Checking IU
Checking IUIU
Checking IUU
Checking IUUIUU
Checking UI
Checking UIU
Checking UIUI
Checking UIUIU
Checking UIUUIU
Starting round 8
Checking I
Checking II
Checking IIII
Checking IIIIIIII
Checking IIIIU
Checking IIU
Checking IIUIIU
Checking IIUU
Checking IU
Checking IUIU
Checking IUIUIUIU
Checking IUU
Checking IUUI
Checking IUUIUU
Checking UI
Checking UIIU
Checking UIU
Checking UIUI
Checking UIUIU
Checking UIUIUIUI
Checking UIUUIU
Starting round 9
Checking I
Checking II
Checking IIII
Checking IIIIIIII
Checking IIIIIIIIU
Checking IIIIIU
Checking IIIIU
Checking IIIIUI
Checking IIIUII
Checking IIU
Checking IIUIII
Checking IIUIIU
Checking IIUU
Checking IIUUIIUU
Checking IU
Checking IUIIII
Checking IUIU
Checking IUIUIUIU
Checking IUU
Checking IUUI
Checking IUUIIUUI
Checking IUUIU
Checking IUUIUU
Checking UI
Checking UIIIII
Checking UIIU
Checking UIIUUIIU
Checking UIU
Checking UIUI
Checking UIUIU
Checking UIUIUIUI
Checking UIUIUIUIU
Checking UIUUIU
[More screen output]

 

 

 

 

 

References

 

  1. Douglas Hofstadter. Goedel, Escher, Bach: An Eternal Golden Braid. 1999. ISBN: 0465026567.
  2. Wikipedia page about the MU puzzle.

 

 

 

 

 

Go back to Richel Bilderbeek's C++ page.

Go back to Richel Bilderbeek's homepage.

 

Valid XHTML 1.0 Strict