StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Though this question has a tag of C++, consider this pseudo-code to express the algorithm (which conveniently happens to be written in ruby.)</p> <pre><code># Where the knight can jump to $m = { 0 => [4,6], 1 => [6,8], 2 => [7,9], 3 => [4,8], 4 => [0,3,9], 5 => [], 6 => [0,1,7], 7 => [2,6], 8 => [1,3], 9 => [2,4] } $cache = Hash.new # return count def nseq( k, n, e=0 ) e += 1 if k.even? return 0 if 3 < e return 1 if n == 1 key = "#{k}:#{n}:#{e}" # for the memoization return $cache[key] if $cache.has_key? key # Sum nseq(j,n-1,e) for j in $m[k] return $cache[key] = $m[k].inject(0) { |sum,j| sum + nseq( j, n-1, e ) } end 0.upto(9) do |k| 2.upto(8) do |n| count = nseq(k,n) puts "k=#{k},n=#{n}: #{count}" break if count.zero? end end </code></pre> <p>This outputs</p> <pre><code>k=0,n=2: 2 k=0,n=3: 6 k=0,n=4: 8 k=0,n=5: 16 k=0,n=6: 0 k=1,n=2: 2 k=1,n=3: 5 k=1,n=4: 10 k=1,n=5: 24 k=1,n=6: 32 k=1,n=7: 64 k=1,n=8: 0 k=2,n=2: 2 k=2,n=3: 4 k=2,n=4: 10 k=2,n=5: 16 k=2,n=6: 32 k=2,n=7: 0 k=3,n=2: 2 k=3,n=3: 5 k=3,n=4: 10 k=3,n=5: 24 k=3,n=6: 32 k=3,n=7: 64 k=3,n=8: 0 k=4,n=2: 3 k=4,n=3: 6 k=4,n=4: 14 k=4,n=5: 16 k=4,n=6: 32 k=4,n=7: 0 k=5,n=2: 0 k=6,n=2: 3 k=6,n=3: 6 k=6,n=4: 14 k=6,n=5: 16 k=6,n=6: 32 k=6,n=7: 0 k=7,n=2: 2 k=7,n=3: 5 k=7,n=4: 10 k=7,n=5: 24 k=7,n=6: 32 k=7,n=7: 64 k=7,n=8: 0 k=8,n=2: 2 k=8,n=3: 4 k=8,n=4: 10 k=8,n=5: 16 k=8,n=6: 32 k=8,n=7: 0 k=9,n=2: 2 k=9,n=3: 5 k=9,n=4: 10 k=9,n=5: 24 k=9,n=6: 32 k=9,n=7: 64 k=9,n=8: 0 </code></pre> <p>The result is the number of all <code>n</code>-length sequences starting on key <code>k</code>, which have no more than 3 even digits in them. For example, the last entry is <code>k=9,n=8: 0</code>. This means that all sequences of length 8 starting on key 9 include more than 3 even digits.</p> <p>EDIT: Here it is translated into C++. It produces identical output as above.</p> <pre><code>#include<iostream> #include<map> using namespace std; const int MAX_EVENS = 3; // Assume < 8 // Where the knight can jump to const int jumpto[][3] = { {4,6}, // 0 {6,8}, {7,9}, {4,8}, // 1 2 3 {0,3,9}, {}, {0,1,7}, // 4 5 6 {2,6}, {1,3}, {2,4} }; // 7 8 9 const int jumpto_size[] = { 2, // 0 2, 2, 2, // 1 2 3 3, 0, 3, // 4 5 6 2, 2, 2 }; // 7 8 9 typedef map<unsigned,int> cachetype; cachetype cache; int nseq( int k, int n, int e=0 ) { e += k&1^1; // increment e if k is even. if( MAX_EVENS < e ) return 0; if( n <= 1 ) return 1; unsigned key = (n << 4 | k) << 3 | e; // n is left with 32-7=25 bits cachetype::const_iterator it = cache.find(key); if( it != cache.end() ) return it->second; int sum = 0; for( int i=0 ; i<jumpto_size[k] ; ++i ) sum += nseq( jumpto[k][i], n-1, e ); return cache[key] = sum; } int main() { for( int k=0 ; k<=9 ; ++k ) for( int n=2 ; n<=8 ; ++n ) { int count = nseq(k,n); cout << "k="<<k<<",n="<<n<<": "<<count<<endl; if( count == 0 ) break; } return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload