//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;
}
}
}
|
