/* 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) \ cout << " ( "<< m <<", "<< n << " ) => " << Len::result>::result << endl; \ int main() { BROKEN_CHAIN(1,2) // 2 => 2 + (1*2) =4 BROKEN_CHAIN(2,2) // 4. => 4 + (2*2) =8 BROKEN_CHAIN(3,2) // 8. => 8 + (3*2) =14 BROKEN_CHAIN(4,2) // 14 => 14 + (4*2) = 22 BROKEN_CHAIN(5,2) // 22 => 22 + (5*2) =32 // next = p + (n*m) BROKEN_CHAIN(6,2) BROKEN_CHAIN(7,2) BROKEN_CHAIN(8,2) BROKEN_CHAIN(9,2) // next = prev + (m-1)*n + m*(n-2) BROKEN_CHAIN(1,3) // 3 => 3 + (5) = 1*3 + 2 BROKEN_CHAIN(2,3) // 8 => 8 + (9) = 2*3 + 3 // prev + 2*3 +3*1 BROKEN_CHAIN(3,3) // 17 => 17 + (13) 3*3 + 4 // 17 + 3*3 + 4*1 BROKEN_CHAIN(4,3) // 30 => 30 + (17) 4*3 + 5 // 30 + 4*3 + 5*1 BROKEN_CHAIN(5,3) // 47 => 47 + (21) BROKEN_CHAIN(6,3) // 68 => 68 + (25) //BROKEN_CHAIN(7,3) // 93 cout << endl; //BROKEN_CHAIN(8,3) //BROKEN_CHAIN(9,3) // next = p + n*m + i+4 + BROKEN_CHAIN(1,4) // 4 => 4 + (4) 1*4 +0 // next = prev + 1*4 + 2 BROKEN_CHAIN(2,4) // 8 => 8 + (16) 2*4 +8 -0 // 4+ 4 + 2*2 - 2*2(m*n/m) BROKEN_CHAIN(3,4) // 24 => 24 + (13) 3*4 +1 BROKEN_CHAIN(4,4) // 37 => 37 + (31) 4*4 + 15(16-1) BROKEN_CHAIN(5,4) // 68 => 68 + (22) 5*4 +2? // KEN_CHAIN(6,4) // 90 ? => 90 + (46?) 6*4 +22(24 -2) // KEN_CHAIN(7,4) // 136 ? => 136 + 7*4 +3 ?? // KEN_CHAIN(8,4) // 167 ? ? BROKEN_CHAIN(1,5) // 5 => 5 + (9) 1*5 + 4 BROKEN_CHAIN(2,5) // 14 => 14 + (9) 2*5 -1 BROKEN_CHAIN(3,5) // 23 => 23 + (33) 3*5 + 18 //BROKEN_CHAIN(4,5) // 56 // KEN_CHAIN(5,5) /* n= 2 : incr =0 next = prev + incr incr = incr + 2 m. in. res incr ------------------- 1. 2 2 0+2 + 2. 2 4 2+ 2 3. 4 8. 4+ 2 4. 6 14 6+ 2 5. 8 22 8.. 6. 10 32 10 7. 44 8 58 9 74 n= 3 : init 1 prev + incr incr = incr +4 m. in. res incr ------------------- 1. 1 3 1 + 4 2. 5 8 5 + 4 3. 9 17. 9 + 4 4. 13 30 17 5. 47 21 6. 58 25 7. 74 29 8 103 33 9 136 n = 4 : init = 1 j=3 nex = pr + in i = i - ( j) j = j+6 m. res i. a. b. z = z+6 ------------------- init -> 1. 3. 3 1. 4 ] 4. 12. 9 (3+6) 2. 8 ] 16 -3 -15 (9+6) 3 24 ] 13 +18 +21 (15+6) 4. 37 ] 31 -9 -27 5. 68 ] 22.+24 +33 6 90 ] 46 7.136 ] 8 9 n= 5 prev + incr(3) => incr = incr - (-incr ) - 2*incr m. res i. a. b. c. z=z+8 ------------------- init -> 1. 5 ] 9. 0. 0. -16. (16) 2. 14 ] 9 24. +24. +24 (24) 3 23 ] 33. 0. -24. -48 (32) 4. 56 ] 33. -8. -8. +16 (40) 5. 89 ] 25. 40. +48. +56 (48) 6 114 ] 65 -8. -48. -96 (56) 7.179 ] 57.-16. -8. +40 (64) 8 236 ] 41 9 277 ] 1 5 5 1 + 8 2 14 5 + 9 9 -- 0 -> 9 3 23 14 + 9 9 -- 24 -> 33 4 56 23 + 33 33 0 33 89 56 + 33 33 -8 25 114 89 + 25 25 40 65 179 114 + 65 65 -8 57 236. 179 + 57 57 -16 41 277. 236 + 41 */ cout << "\n * * * END * * *\n"; return 0; }

formula?