/* Great Tits Puzzle Solution -- Guy Jacobson */ #include #include #include /* Known constants about Tits Group */ #define N 1600 #define NELTS 17971200 typedef unsigned long long hashval; /* Variables copied from the Javascript */ int pLeft[N] = {1,-1,1,-1,1,-1,2,2,-2,-2,3,3,4,-3,-3,5,-4,5,5,6,-5,7,-5,-5,8,-6,8,8,-7,9,9,10,-8,10,-8,-8,10,10,-9,-9,11,-10,11,-10,12,12,-10,-10,13,13,14,-11,15,-11,16,16,-12,-12,17,17,18,-13,-13,19,-14,19,19,-15,20,20,-16,-16,21,21,22,-17,-17,23,-18,22,22,23,-19,24,-19,-19,25,25,-20,-20,26,26,27,-21,-21,28,-22,28,11,28,-23,-22,-22,29,-23,29,29,-24,30,-11,30,-25,-25,31,31,32,-26,-26,33,-27,33,33,34,-28,35,-28,36,-28,36,36,36,37,-29,38,-29,-29,39,39,-30,40,-30,40,40,41,-31,-31,42,-32,10,24,41,-33,42,-33,-33,43,-34,43,-10,-35,43,43,-36,44,-36,-36,-36,45,-37,45,45,-38,46,-24,46,-39,-39,47,47,-40,48,-40,-40,49,-41,49,49,50,-42,50,51,-41,51,51,-42,52,52,53,-43,53,-43,54,54,-43,-43,55,55,-44,56,45,56,57,-45,58,-45,-45,59,59,-46,60,-46,60,60,61,-47,-47,62,62,-48,63,43,63,-49,64,-49,-49,64,-50,63,-50,64,-51,64,-51,-51,1,-1,-52,-52,63,-53,63,-53,64,-45,-54,-54,64,64,65,-55,-55,65,65,-56,66,-56,66,-57,66,66,-58,67,-43,67,-59,-59,68,68,-60,69,-60,-60,70,-61,70,70,70,-62,-62,71,71,-63,72,-63,72,72,-64,73,73,-64,-63,74,74,-64,75,-64,76,76,77,77,78,-63,79,-63,80,80,-64,81,81,82,-64,-64,83,-65,83,83,-65,-65,83,83,-66,84,-66,85,-66,-66,86,86,-67,3,-67,86,-3,86,-68,-68,87,87,-69,88,70,88,-70,89,-70,-70,-70,90,90,90,-71,-71,91,91,-72,91,-72,-72,1,-1,-73,-73,90,90,90,-74,-74,12,90,-75,91,91,-76,-76,92,-77,-77,91,-78,-12,90,-79,91,91,-80,-80,92,92,-81,-81,67,-82,91,91,92,-83,92,-83,-83,93,93,-83,-83,94,94,-84,95,83,-85,95,-70,95,-86,-86,96,96,97,-86,97,-86,97,97,98,-87,-87,46,98,-88,68,-88,98,98,-89,99,99,100,101,-90,-90,-90,102,102,103,-91,-91,44,-91,92,103,104,104,105,-90,-90,-90,105,105,-67,-90,105,105,-91,-91,106,106,16,-92,106,-91,107,-90,-46,106,-91,-91,106,106,107,-92,-92,108,-16,108,-91,-91,108,-92,108,-92,-44,-83,83,-93,-93,107,107,-68,-94,-94,108,108,-95,109,109,-95,110,-95,97,109,110,-96,-96,111,-97,96,-97,111,-97,-97,112,-98,111,84,111,-98,112,112,112,-98,-98,1,-1,-99,-99,82,-100,110,-101,110,-92,110,111,-102,-102,112,-103,112,112,113,114,97,-103,114,-104,-104,114,-105,114,114,115,-105,-105,10,115,-105,-105,116,116,117,-106,-106,118,-10,-106,-83,117,-107,118,-106,118,118,-106,-106,118,-107,118,118,119,-108,120,-108,120,120,-108,120,-108,121,12,121,117,121,-107,-107,122,-97,70,-84,-108,-108,-12,-96,-109,-109,119,119,-110,-82,-109,120,-110,120,120,121,-111,121,122,122,-111,123,123,124,-112,-111,124,-111,124,124,-112,-112,-112,125,115,125,126,118,126,-110,-97,-110,126,-110,126,-111,126,119,126,-112,126,-112,-112,126,-113,126,-114,125,125,-114,126,126,-114,100,-114,-114,127,-115,-70,122,126,-115,127,127,128,-116,-116,129,-117,129,129,130,-118,131,131,-117,132,132,-118,132,-118,-118,133,133,-118,134,-118,-118,135,-119,135,135,-120,136,-120,-120,137,-120,137,-117,-121,137,-121,137,-121,62,135,136,-122,137,137,138,139,139,140,-119,-119,140,140,140,140,-120,141,-120,-120,142,-121,142,-121,143,-122,-122,1,-1,-123,-123,142,-124,142,-115,-124,142,-124,-124,142,-118,142,143,-125,144,-125,144,-126,-100,-126,142,-119,141,-126,142,-126,135,-126,142,-126,142,-126,-62,98,-126,122,-126,-125,-125,142,138,-126,-126,142,142,122,-122,142,-127,143,144,-126,144,144,-127,-127,145,-128,145,140,145,-129,145,-129,-129,146,-130,145,145,-131,-131,144,66,-132,-132,144,-132,144,144,145,-133,-133,128,145,-134,146,146,147,-135,147,-135,-135,147,147,-136,105,142,146,-137,147,-137,147,147,-137,147,-137,-135,146,-136,146,66,-137,-137,145,-138,24,-139,-139,143,-140,143,59,-140,-140,-140,-140,142,142,-141,143,143,-98,-142,144,-142,125,144,-143,-66,-24,143,143,144,-142,144,-142,145,145,-142,133,140,-142,143,-142,143,-143,142,-122,-144,142,-144,-135,-142,-141,142,142,-142,-122,143,143,-142,144,-142,1,-1,75,-66,143,-138,143,-59,-142,143,143,143,-142,-142,143,143,-142,143,138,-143,142,-144,142,-144,-144,141,-140,-105,-145,140,-145,141,-145,140,-145,141,141,-128,-146,-145,-145,141,-144,141,141,142,-144,74,-144,-144,143,-145,142,142,143,-145,1,-1,-146,-146,139,-147,139,-147,138,-142,-147,-147,138,138,-146,138,21,-147,137,-147,-147,-75,-147,135,-146,135,-146,135,136,-145,136,-125,-143,136,-143,14,52,-21,137,-142,-142,1,-1,-143,-143,134,134,134,-144,-14,134,-144,134,-133,-143,-143,133,-144,74,-144,132,-140,-145,-145,132,-74,-143,131,-143,-142,131,131,-142,131,125,17,129,-142,-142,129,129,76,-143,-143,90,127,-144,128,-52,128,128,-143,-17,-143,125,125,-143,-143,-143,126,-138,-143,-143,126,-143,126,-142,125,-142,124,-141,22,124,-140,125,125,-141,-140,1,-1,-141,-141,123,123,123,124,-141,124,-141,-141,123,-142,-74,-22,122,122,122,-143,-142,-142,120,-143,119,-139,111,-139,-138,96,117,118,-138,-138,119,-138,119,-137,119,-76,-135,119,-135,119,-135,119,-136,118,-136,117,117,-136,118,118,119,48,-90,-137,116,116,117,-134,-134,-134,116,116,-134,116,-134,116,116,-133,116,116,-132,79,83,114,-132,115,-131,-125,115,-131,-131,116,-131,-129,115,115,-129,-129,116,117,-127,117,117,-128,118,-128,-128,-125,-125,-48,117,118,118,-126,118,118,101,-126,118,-126,-125,-124,116,116,-124,117,117,-125,-125,108,116,-96,115,-123,-123,-123,114,-124,113,-124,45,-123,112,-111,-122,-122,-122,111,-120,-119,111,111,111,-117,111,-118,111,111,82,-119,-79,-119,109,-119,109,-83,-119,108,-119,108,-119,-118,-117,-117,1,-1,-118,-118,104,-119,-116,-116,104,-117,40,-45,-116,-116,103,-116,104,-116,-116,102,-116,-116,102,-114,101,101,-115,101,101,-115,102,87,102,-116,102,-115,-115,101,101,102,-116,102,-117,-101,-117,-117,101,101,-118,101,-40,41,100,-117,99,-118,-118,99,-118,-118,89,98,-118,-108,-116,-116,-82,94,-117,-117,93,93,-116,-115,68,91,-114,-113,76,91,-112,90,85,90,-111,91,91,-111,-111,-111,90,-111,-41,-111,-111,67,90,-109,89,-109,90,-108,90,-108,80,89,8,89,-104,88,88,88,-104,2,-8,-2,79,-103,-87,32,-104,-102,81,81,-102,-101,-101,80,-101,-101,81,81,-102,67,-102,80,-102,81,-101,-101,80,-102,-68,-102,65,77,78,-101,-101,-89,-101,-32,-100,-99,-76,19,-99,73,74,-98,75,-94,-67,-93,-93,26,-91,-85,72,72,-91,-90,71,-90,-19,69,-91,-91,56,66,-90,58,65,65,-80,51,-90,-89,61,61,-90,-26,-90,61,-89,-79,-89,-88,-88,-88,-67,1,-1,-81,-81,53,53,-80,52,-65,52,-81,-81,10,13,-80,30,49,-81,49,-80,49,-77,-10,-78,47,47,-13,5,45,-73,45,-74,-5,-56,-75,-51,40,40,-58,-72,-72,37,-71,-69,-66,-30,-65,-65,-61,-61,16,9,31,-61,31,31,31,-53,-53,-52,-9,-52,18,25,25,-49,-16,-49,25,-49,25,-47,-47,-45,25,-45,-40,-40,-37,3,-18,3,-3,-31,-3,-31,-31,-31,-25,-25,17,17,17,-25,16,-25,16,16,13,-25,1,-1,14,11,2,12,-2,-17,-17,-17,-16,-13,-16,-16,-11,4,-14,-12,2,-4,-2}; int pRight[N] = {2,-1,-1,1,2,2,-3,3,3,3,-5,4,5,5,5,-7,5,-8,6,7,7,8,8,8,-11,8,-12,9,9,-13,10,3,10,11,-11,10,-16,11,11,11,-18,11,12,12,-19,13,13,13,-20,14,15,15,16,16,-22,17,17,17,-23,18,19,19,19,-25,19,-26,20,20,-27,21,21,21,-29,22,23,23,23,-31,22,-32,23,24,24,25,25,25,-35,26,26,26,-37,27,28,28,28,-39,28,-40,28,29,29,29,29,-42,29,-43,30,30,-44,30,31,31,31,-46,32,33,33,33,-48,33,-49,34,35,35,36,36,-51,36,-52,-51,37,38,38,39,39,39,-54,40,40,-55,40,-56,41,42,42,42,-58,42,-59,41,42,42,43,43,43,-62,43,-63,43,43,-64,44,44,45,45,45,45,-66,45,-67,46,46,-68,46,47,47,47,-70,48,48,49,49,49,-72,49,-73,50,48,50,51,-74,51,-75,52,52,-76,53,40,53,54,54,-78,55,55,55,-80,56,56,-81,56,57,58,58,59,59,59,-84,60,60,-85,60,-86,61,62,62,62,-88,63,63,-89,63,64,64,65,65,-90,-92,-83,64,64,-93,64,65,57,64,-94,63,63,63,-96,63,64,64,-97,64,64,64,-98,65,66,32,65,-100,66,66,-101,66,-102,66,-103,67,67,-104,67,68,68,68,-106,69,69,70,70,70,-108,70,-109,41,71,71,71,-111,72,72,-112,72,-113,73,73,-114,74,74,74,-114,75,75,76,76,-116,77,-115,78,79,79,80,80,-117,81,81,-118,82,83,83,83,-120,83,-121,84,-103,83,-122,84,84,85,85,86,86,86,-125,87,87,-126,86,-127,86,87,87,87,-129,88,88,-130,88,89,89,90,90,90,90,-133,28,91,91,91,-135,-104,91,40,91,91,-137,90,90,90,-139,-131,91,91,91,-139,91,91,-140,92,92,92,-141,92,-99,-141,91,-142,91,91,-143,92,92,92,-145,93,93,93,-146,-26,-147,92,93,-112,93,93,93,-149,94,94,94,-150,95,95,-151,95,95,-152,95,96,96,96,-154,97,54,97,-154,97,-155,98,99,99,99,-157,99,99,-158,98,-159,99,99,-160,100,101,102,102,102,102,-162,103,104,104,104,104,104,73,104,-163,105,106,-25,105,105,-165,-65,105,105,-166,106,106,106,-168,10,106,106,107,107,108,-140,-170,107,107,-102,-172,107,108,108,108,-174,108,109,70,108,-175,108,-176,108,-176,107,107,107,107,-177,108,108,108,108,-179,109,109,-180,110,110,-181,110,-182,110,111,111,111,-184,111,111,111,112,112,112,-185,-164,-186,111,112,112,-187,-74,113,113,113,-188,112,11,111,-190,110,-191,110,-192,110,111,112,112,112,-194,112,-195,113,114,-195,114,114,-195,114,114,-195,114,-196,115,116,116,116,-196,116,116,116,-197,117,118,118,118,-198,118,118,-199,118,118,-199,118,-198,119,69,118,-199,118,-200,119,120,120,-201,120,-202,66,120,121,121,122,-200,-200,121,122,122,122,-202,-202,121,108,120,120,-204,119,119,119,-205,120,120,120,120,-206,120,-207,121,41,121,122,-208,123,123,-209,124,125,101,124,-210,124,-211,125,125,125,125,-211,125,126,-211,126,127,127,86,126,-212,126,-213,126,-214,126,-123,126,127,-174,126,-217,126,-218,-152,-218,126,126,-184,127,127,127,127,127,-220,127,-221,126,127,127,-221,128,129,129,129,-223,129,-224,130,131,131,-224,132,132,-225,133,-12,133,133,133,-226,134,134,135,135,135,-227,135,-228,136,136,137,137,137,138,-216,-229,137,137,-230,137,-228,-75,-229,136,137,137,-229,138,139,-228,140,141,141,-196,-230,36,-230,141,141,142,142,142,-232,142,143,143,-233,143,143,-234,142,142,142,-236,142,-237,142,142,143,143,129,-237,142,143,144,144,-238,144,-239,144,-237,-156,-237,-52,142,142,-195,142,142,142,-238,142,143,143,-239,142,142,142,142,142,142,-240,142,142,142,-241,143,-241,142,143,143,144,-242,144,-243,145,145,145,-244,145,-245,145,-117,145,146,146,146,-248,87,-249,48,-117,144,-250,144,144,144,-251,144,-251,145,146,146,146,-252,146,146,-253,147,-18,147,148,148,133,-256,55,147,-257,146,147,147,-258,147,-258,148,14,108,147,54,-258,146,-259,45,145,145,-258,145,-259,-179,143,-259,143,-260,-242,142,142,142,142,-261,143,143,-262,144,144,144,145,145,-264,79,144,142,143,-265,144,116,144,145,145,-266,146,-191,-267,144,-110,-267,143,-268,-182,-269,142,142,143,143,143,143,80,-268,143,143,143,-268,144,144,145,145,-269,144,-268,143,-268,143,89,143,143,-268,-32,144,144,-135,-270,-269,143,-270,143,105,-271,142,-9,26,141,-272,32,140,140,141,141,-274,-117,141,141,-275,142,142,142,-245,141,142,-222,-276,142,143,143,143,143,143,-278,77,-279,143,5,143,-280,119,-177,-151,-282,139,-30,109,-283,138,138,138,47,-283,138,-284,138,-25,8,137,-124,-285,135,70,135,136,-155,136,137,-258,137,-157,136,137,137,137,137,137,-18,-231,124,-284,134,134,134,-286,-286,135,135,-287,135,-285,-273,-286,133,133,-286,133,133,-194,-287,132,132,132,-288,-287,131,-230,131,131,-286,132,-210,-287,-197,-287,130,78,129,-285,26,-285,128,128,-286,128,128,-287,128,-287,-285,-43,-285,-217,-285,126,126,126,126,-286,126,126,126,89,126,-286,-169,98,112,125,125,-285,125,125,-286,126,126,26,-286,124,-265,123,-288,-288,124,3,124,-286,-144,123,-286,123,-287,122,-287,-118,-169,122,108,97,-289,63,120,104,119,119,99,-286,118,119,119,119,-218,119,-285,119,120,75,119,81,119,-282,119,-281,93,-282,-109,-282,118,118,-280,119,-279,-279,-279,116,-277,117,118,118,-126,70,-279,-92,116,-280,116,-7,100,116,-24,-277,-232,-277,114,115,115,116,116,-236,116,116,116,-274,116,-240,-273,116,116,116,117,118,-10,-272,118,118,-273,118,118,118,118,-269,118,59,119,0,-270,46,118,118,119,-12,-210,0,-266,117,117,-265,118,118,-216,-267,-235,-265,116,116,102,-130,-266,92,114,114,19,-67,113,-265,112,-217,111,112,112,97,-263,-258,86,111,-256,111,-257,112,112,-142,32,-172,-197,109,-257,109,84,109,-65,40,-185,107,107,107,-254,106,-233,-5,-256,104,104,104,-251,104,-252,103,103,103,104,104,-49,-11,-151,103,101,102,-246,68,-247,44,101,-247,102,102,-247,102,-106,102,-179,-159,101,-245,102,103,-109,-245,102,-246,101,101,-246,-53,101,-9,101,-106,-230,-46,-244,99,99,-245,99,99,-244,99,-210,-245,-205,94,-242,-214,94,-159,-243,94,94,94,-239,-215,92,92,-238,-184,40,-236,90,91,91,-234,92,42,-67,90,91,91,91,91,91,-231,-231,53,90,90,-228,90,-228,90,57,-102,89,-224,-31,-220,-93,-58,-92,87,-221,81,78,84,-220,83,78,-9,-219,-35,81,14,80,81,81,81,-218,82,-87,-218,80,81,81,75,59,80,-218,-57,-219,-19,77,78,-14,-11,77,77,77,-219,4,37,-191,73,73,74,75,75,-217,-164,74,74,74,-212,-191,72,-176,-61,-17,71,-202,0,-202,-34,44,-14,-204,7,66,-202,-159,-202,15,18,-97,43,-199,62,-20,61,61,62,-181,-196,-184,53,-118,-106,-191,55,-187,-109,53,-62,43,-15,-182,52,-123,52,-176,-184,50,50,-183,-70,49,-94,49,-179,49,-179,-6,33,-178,-130,-172,-77,45,-173,36,-174,-169,42,-168,-60,24,-166,-18,-37,18,37,37,0,36,-12,35,-123,-112,-152,-151,-46,31,-152,-139,-16,-110,15,-89,-133,-98,13,-130,26,26,-43,25,-93,25,-31,25,25,25,-88,-65,-30,-30,22,22,22,-102,-5,-12,19,19,19,19,19,-4,-76,4,-61,6,17,-30,-13,17,-40,9,15,-59,-59,-50,-15,13,13,5,-15,1,3,-42,-24,-4,-42,-37,0,0,-32,-32,0}; char *scrambledMessage = "TITS IDSHYNVNTRIEVSSLNSEETYEEHIR MTLBNDMDH S ISN VDENINDIEINX SIR BRI IINXLNH IFDHUODEHNNRIMWRUNHLET DI RIEID NLNULRFOEMEMFNLFIVUNYR YR INNTEFUINBINRNNDGRVFSERIIE GEFLNR INOIGULYT HDDCLUB I U WEMELF ISLFE IN YIHLXENNNI NEE YUNOEDROEUDDV NHNT E D DHULO NDEENI OI IELELLEE RINETHDCLT DLTENO UNFBSTFNDLUN ETIEDVTEENOITETDR TRGNYSEABDEIEE DTOIOUEHVDEWE TNNIIDLTYUIIVV T HIO RUURE IHTDHGSDNOUNI NR NTHUDTXNB D LOLDV YIM N EN UXN IRHEREEIONFNONN NXTNO UNOEO EQRRS UOEHNVU UHDUUEOI EF E HR MRIGB I NIHIH ITTLEELNIHT I CLEU LELOTATHLD OULQ RLYPWDEESSNER RHAENNFET TU HUERRTYUDFDNNEXFFF EXUMNRNUE TIT C TEINE ID HEN OD BR E ELNLINTNT OO LNTHDFNIN TLSTRHDN HLOEX FDUGDLE NYLUE NTEIUDEIYEIEIOILFLT O VHOUL FUE TEESTRMVNYEDOB DSUELDRDRO TIBS TEFLTIFLEE EYTV UNTIL DIDMYN UE YU SNWISYDHIRC AQIDYINLDUOLH THHOO E ROIN YNVEHFTNNEETE DR EED RTITHAD TOUORCAUXS LYUTE SR CNNHUHIFRHDHDLUO EEYI OURNUUENSRTEE HNESTERIIQSE MMETONNINLFHOFSUEINDIEIOFCLENULBR EELEHREOGNE HIYOLDEHHOON RTIWENNUHH IRUDDT LDBSIVENTUUELSHDRRRNVNFOOYNIINR RYHEIUI NISHVNIRTEIDUOU IADNV DN LOG DIIL VGLO UEI OYLNEUI H BIO IE NQSE IEH RCEHTTGTL U Y NIQEENL YRTNQEH N LUUNNIRIILORB DOIH IEEHRFBSHENNFLOHEVHONIISR EBH RYM ANTRSETWNINIULDE DXRGTVTI RODNEXRRTEDESRDININHDYN WLRENIDINTNMRDELYEIUUNFOEIFY EDWUONEUEAFDTTVLH STHI SOOEVX EUENEUI LTNNUVNSD UNERONNE AISVT E H EHEDDT YHX TEDDVOETMEEHO L V IVFE ARMRNDIO XFTTNHUR DNED RONEOENN LIUEEITNRNNNBNOI NTOSDEDNSU SBORRDESEOWNVNRRNS RS OR T MEATWDO PUN DSRHOED TN ARLENDNOTUTENISR UWAVNSV IIQDNLL H SHEENTTVEDUOD DR MNDEHTIINS ULTGTNTF FINNRU YENI F TFBHH ODRBOLR EIYLRD"; /* How many elements have we found so far */ int count = 0; /* Stack of visited positions in DFS */ char stack[NELTS]; /* Heuristic function to check if the element looks like English text. Simplest and fastest version (shown below) just checks whether it contains adjacent space characters. Could also compute statistics, look for patterns (Q always followed by U) or look for likely words. */ int checkEnglish(const char *e) { int i; for (i = 0; i < N - 1; i++) if (e[i] == ' ' && e[i+1] == ' ') return 0; return 1; } /* Simple linear probling hash table for found elements. Only keep the 64-bit hash value; can't afford to store the whole 1600 byte value. */ hashval *hashtab; int hsize; /* Return the least prime number >= i */ int biggerPrime(int i) { int j, k; for (j = i; ; j++) { for (k = 2; k * k < j; k++) if (j % k == 0) continue; if (j % k != 0) return j; } } /* Table is allocated to have load factor 1/2 at the end */ void initHash() { hsize = biggerPrime(2 * NELTS); hashtab = (hashval *) calloc(hsize, sizeof(hashval)); } /* Insert elt into hash table if it's not already present. Return 1 if the element was inserted, 0 if already there. We assume that you will never hash a position to zero, which is used for empty slots */ int insertElt(hashval k) { int i = k % hsize; hashval h; while ((h = hashtab[i])) { if (h == k) return 0; if (++i == hsize) i = 0; } hashtab[i] = k; return 1; } /* Fast 64-bit hash function stolen from the Interwebs */ hashval murmurHash64(const char *e) { const hashval m = 0xc6a4a7935bd1e995UL; const int r = 47; const int len = N / sizeof(hashval); const hashval *data = (hashval *) e; const hashval *end = data + len; hashval h = m; while(data != end) { hashval k = *data++; k *= m; k ^= k >> r; k *= m; h ^= k; h *= m; } h ^= h >> r; h *= m; h ^= h >> r; return h; } /* Enter an element into the hash table if it's not already there; print a message every so often, and check for English. */ int newElt(char *e) { const hashval key = murmurHash64(e); if (insertElt(key)) { if (++count % 100000 == 0) printf ("Count = %d\n", count); if (checkEnglish(e)) printf("%.*s\n",N,e); return 1; } return 0; } /* Apply a permutation to a string. Returns a pointer to a static buffer. Strategy is to alternate to avoid recopying. */ char *apply(const int *p, char *e) { int i; static char e1[N], e2[N]; char *ee; ee = (e == e1)? e2 : e1; for (i = 0; i < N; i++) ee[i] = e[p[i]]; return ee; } /* Generate all elements in lexicographic order by L, R. Uses depth-first search, but is non-recursive, using an explicit stack, because I'm not sure how deep it will get and I don't want to blow out the stack segment of the process. We keep just a single copy of the current permuted message string, applying inverse permutations to backtrack. Could be made faster by taking advantage of knowledge of the group structure (LL = RRR = I) */ int main(int argc, const char *argv[]) { char *e = scrambledMessage; char *st = stack; int n; int pl[N], pr[N], plInv[N], prInv[N]; /* Generate actual permutations for L and R and their inverses */ for (n = 0; n < N; n++) { pl[n] = pLeft[n] + n; plInv[pl[n]] = n; pr[n] = pRight[n] + n; prInv[pr[n]] = n; } initHash(); while (1) { if (newElt(e)) { /* Found a new element */ e = apply(pl, e); /* Push L */ *st++ = 'L'; } else { while (st[-1] == 'R') { /* Backtracking: pop all trailing Rs (if any) */ e = apply (prInv, e); --st; } /* Stack is either empty now or ends in L */ if (st == stack) break; /* Stack empty: search done */ e = apply(pr, apply(plInv, e)); /* Pop L; push R */ st[-1] = 'R'; } } printf("Final count = %d\n", count); return 0; }