/* The Broken Chains - Challenge a chain made of "m" different characters. rule : - never repeating any "n"-long pattern. - Characters are stored, indexed in a list - start the chain with the character's list. - Everytime you need a next character, you start by trying with the next one in the (rotating) list. If it doesn't allow you to to respect the no-repetition rule, then you take the next one in the (rotating) list. At some point, no character will fit the rule. ==> Input: m,n - m = is the number of different characters in the chain - n = is the length of the pattern checked for repetitions. ==> Output: length of the chain when it breaks test cases 2,2 => 4 13,1 => 13 5,7 => 107 7,4 => 136 42,42 => 69824 90,19 => 144288 1000000,6 => 4999992250005 */ /* * * * * * * List device. * * * * * * */ class End{}; templatestruct List{ static const unsigned Head = c; using Tail = T; }; // Length templatestruct Len{ static const unsigned result = 1 + Len::result ; }; template<>struct Len{ static const unsigned result = 0; }; // Contains ( List , List ) templatestruct And{ static const bool result = ( L::Head == J::Head ) && And::result; }; templatestruct And{ static const bool result = true ; }; templatestruct And{ static const bool result = false ; }; template<>struct And{ static const bool result = true ; }; templatestruct Contains{ static const bool result = And::result || Contains::result ; }; templatestruct Contains{ static const bool result = false; }; // GetFirst_n_elements templatestruct GetFirst_n_elements{ using result = List::result>; }; templatestruct GetFirst_n_elements{ using result = End; }; templatestruct GetFirst_n_elements{ using result = End ; }; template<>struct GetFirst_n_elements{ using result = End ; }; /* * * * * * CHAIN device * * * * * */ // Chain initialization templatestruct Chain_List{ using result = List::result>; }; template<>struct Chain_List<0>{ using result = End ; }; // Next elements // - Check pattern /* L::Head 2 m 4 0 1 2 3 =>iterator 2 3 0 1 =>value = i+L%m */ templatestruct Test{ static const bool result = Contains::result>>::result; }; templatestruct Next{ static const unsigned v = (it+L::Head+1)%m; static const unsigned result = Test::result ? Next::result : v; }; templatestruct Next{ static const unsigned result = m; }; templatestruct Ch_Facade{ typedef List step; using result = typename Ch_Facade::result>::result ; }; templatestruct Ch_Facade{ using result = L; }; templatestruct Chain{ typedef typename Chain_List::result L; using result = typename Ch_Facade::result>::result; }; #include using namespace std; template void print(bool i=false){ print(true); std::cout << T::Head ; if(i) std::cout <<","; } template<> void print(bool){} #define BROKEN_CHAIN(m,n) \ typedef Chain::result chain_##m##_##n; \ cout << "Broken chain ( "<< m <<", "<< n << " ) :\n"; \ print(); \ cout << "\nLength : " << Len::result << endl; \ int main() { BROKEN_CHAIN(3,3) cout << "Expected : 17 => 01201011212202001\n\n"; BROKEN_CHAIN(2,2)cout << "Expected : 4 \n\n"; BROKEN_CHAIN(13,1)cout << "Expected : 13 \n\n"; BROKEN_CHAIN(5,7)cout << "Expected : 107 \n\n"; //BROKEN_CHAIN(7,4)cout << "Expected : 136 \n\n"; //BROKEN_CHAIN(42,42) //BROKEN_CHAIN(90,19) //BROKEN_CHAIN(1000000,6) cout << "\n * * * END * * *\n"; return 0; }

[CHALLENGE] THE BROKENCHAIN