#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <deque> #include <unordered_map> #pragma GCC target ("abm,bmi,bmi2,popcnt") #define NDEBUG //////////////////////////////////////////// // // // Program: // // Compute a[1..n] = A338024 // // b[1..n] = A292764 // // c[1..n] = A338099 // // // // Usage: // // a.out <<< <n> // // // // Example: // // a.out <<< 4 // // // // Output: // // a[ 1]= 1 (...) // // b[ 1]= 2 (...) // // c[ 1]= 3 (...) // // a[ 2]= 6 (...) // // b[ 2]= 8 (...) // // c[ 2]= 10 (...) // // a[ 3]= 15 (...) // // b[ 3]= 18 (...) // // c[ 3]= 21 (...) // // a[ 4]= 28 (...) // // b[ 4]= 36 (...) // // c[ 4]= 40 (...) // // // // Note: // // Pipe output to grep 'a[' // // to get terms of A338024 // // // //////////////////////////////////////////// // Pegs are numbered from 0 to 3. // Disks are numbered from 0 (smallest) to N (largest). // A configuration of disks on the pegs is represented // by an unsigned integer, the two least significant bits // representing the peg the smallest disk is on; // the next two bits representing the peg the second smallest // disk is on, etc. // Search is breadth first, starting from the initial configuration // c0=0 (that is all disks on peg 0 // towards target configurations target[0], target[1] and target[2], // all disks on peg 0, on peg 1, or on peg 2, respectively. // Whenever a target is reached another disk is added on, until // the target includes all disks and is voided. // All configurations for the current move are held in a queue q, // followed by a marker (ULONG_MAX), followed by the configurations // for the next move. The queue dynamically changes as a move is processed. // The history of previously reached configurations is held in a bit set. // As this bit set takes an huge amount of memory, it is compressed: // Bits are grouped into words, which are stored in the following fashion: // If a word is all ones, the corresponding bit in the meta bit vector V is set. // If a word is all zeros, the corresponding bit in V is cleared. // If a word has some ones and some zeros, the corresponding bit // in V is also cleared, and the actual word is stored in map v. // Note that history is cumulative, so bits only change from 0 to 1, // consequently words progress from 0 to some bits set, to all bits set, // respectively meta bit clear, in map v, to meta bit set. typedef unsigned long Configuration; typedef unsigned Word; #define One 1u #define WordSiz (sizeof(Word)*CHAR_BIT) #define BIGMAX (((1ul<<(2u*N))+WordSiz*WordSiz-1u)/(WordSiz*WordSiz)) int main() { unsigned N; assert(1==scanf("%u", &N)); assert(N && N<=32u); std::deque<Configuration> q; Configuration target[4u]; for(Configuration i=0; i<4u; i++) target[i]=i; #ifndef NDEBUG fprintf(stderr, "Looking for %lx\n", target); #endif Word *V=(Word *)calloc(BIGMAX, sizeof(Word)); std::unordered_map<Configuration, Word> v; Configuration c0=0; v[0]=1; //V[0]=0 already q.push_back(c0); for(unsigned move=1u; target[1]|target[2]|target[3]; move++) { #ifndef NDEBUG fprintf(stderr, "MOVE %u:\n", move); #endif q.push_back(ULONG_MAX); for(Configuration c; ~(c=q.front()); ) { q.pop_front(); #ifndef NDEBUG fprintf(stderr, "Config %lx:\n", c); #endif unsigned uncovered=0xf; for(unsigned disk=0; disk<N; disk++) { unsigned peg=c>>(disk*2u)&3u; if(!(uncovered&1u<<peg)) continue; if(!(uncovered&=~(1u<<peg))) break; for(unsigned possible=uncovered; possible; ) { unsigned newpeg=__builtin_ctz(possible); if(uncovered&1u<<newpeg && newpeg==(peg+1u&3u)) { Configuration newc=(c&~(3ul<<disk*2u))|(Configuration)newpeg<<(disk*2u); if(!(V[newc/WordSiz/WordSiz]&One<<newc/WordSiz%WordSiz)) { Word word=v[newc/WordSiz]; if(!(word&One<<newc%WordSiz)) { word|=One<<newc%WordSiz; if(~word) v[newc/WordSiz]=word; else { v.erase(newc/WordSiz); V[newc/WordSiz/WordSiz]|=One<<newc/WordSiz%WordSiz; } q.push_back(newc); #ifndef NDEBUG fprintf(stderr, "Generating %u->%u new config: %lx\n", peg, newpeg, newc); #endif } } } possible&=~(1u<<newpeg); } } } q.pop_front(); //ULONG_MAX for(Configuration c : q) for(unsigned i=1u; i<4u; i++) if(c==target[i]) { unsigned diskcount=__builtin_popcountl(target[i])/__builtin_popcount(i); printf("%c[%2d]= %7u (queue length= %9lu uncompressed= %9lu)\n", " abc"[i], diskcount, move, q.size()-1, v.size()); fflush(stdout); target[i] = diskcount<N ? target[i]|target[i]<<2u : 0; } } }