(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 #include #include #include #include #include //From http://learningcppisfun.blogspot.com/2008/04/remove-duplicates-from-vector.html template void RemoveDuplicates(std::vector& v) {   std::sort(v.begin(), v.end());   v.erase(std::unique(v.begin(), v.end()), v.end()); } const std::vector GetNext(const std::string& s) {   assert(!s.empty());   //std::cout << "Getting nexts of " << s << '\n';   std::vector 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::cout,"\t"));   //std::cout << '\n';   return v; } int main() {   std::vector 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 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 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.