Topswops: Difference between revisions
(Go solution) |
|||
Line 144: | Line 144: | ||
{{out}} |
{{out}} |
||
<pre>[0, 1, 2, 4, 7, 10, 16, 22, 30, 38]</pre> |
<pre>[0, 1, 2, 4, 7, 10, 16, 22, 30, 38]</pre> |
||
=={{header|Go}}== |
|||
<lang go>// Adapted from http://www-cs-faculty.stanford.edu/~uno/programs/topswops.w |
|||
// at Donald Knuth's web site. Algorithm credited there to Pepperdine |
|||
// and referenced to Mathematical Gazette 73 (1989), 131-133. |
|||
package main |
|||
import "fmt" |
|||
const ( // array sizes |
|||
maxn = 10 // max number of cards |
|||
maxl = 50 // upper bound for number of steps |
|||
) |
|||
func main() { |
|||
for i := 1; i <= maxn; i++ { |
|||
fmt.Printf("%d: %d\n", i, steps(i)) |
|||
} |
|||
} |
|||
func steps(n int) int { |
|||
var a, b [maxl][maxn + 1]int |
|||
var x [maxl]int |
|||
a[0][0] = 1 |
|||
var m int |
|||
for l := 0; ; { |
|||
x[l]++ |
|||
k := int(x[l]) |
|||
if k >= n { |
|||
if l <= 0 { |
|||
break |
|||
} |
|||
l-- |
|||
continue |
|||
} |
|||
if a[l][k] == 0 { |
|||
if b[l][k+1] != 0 { |
|||
continue |
|||
} |
|||
} else if a[l][k] != k+1 { |
|||
continue |
|||
} |
|||
a[l+1] = a[l] |
|||
for j := 1; j <= k; j++ { |
|||
a[l+1][j] = a[l][k-j] |
|||
} |
|||
b[l+1] = b[l] |
|||
a[l+1][0] = k + 1 |
|||
b[l+1][k+1] = 1 |
|||
if l > m-1 { |
|||
m = l + 1 |
|||
} |
|||
l++ |
|||
x[l] = 0 |
|||
} |
|||
return m |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
1: 0 |
|||
2: 1 |
|||
3: 2 |
|||
4: 4 |
|||
5: 7 |
|||
6: 10 |
|||
7: 16 |
|||
8: 22 |
|||
9: 30 |
|||
10: 38 |
|||
</pre> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
Revision as of 22:32, 23 November 2012
Topswops is a card game created by John Conway in the 1970's.
Assume you have a particular permutation of a set of n cards numbered 1..n on both of their faces, for example the arrangement of four cards given by [2, 4, 1, 3] where the leftmost card is on top. A round is composed of reversing the first m cards where m is the value of the topmost card. rounds are repeated until the topmost card is the number 1 and the number of swaps is recorded. For our example the swaps produce:
[2, 4, 1, 3] # Initial shuffle [4, 2, 1, 3] [3, 1, 2, 4] [2, 1, 3, 4] [1, 2, 3, 4]
For a total of four swaps from the initial ordering to produce the terminating case where 1 is on top.
For a particular number n
of cards, topswops(n)
is the maximum swaps needed for any starting permutation of the n cards.
- Task
The task is to generate and show here a table of n
vs topswops(n)
for n in the range 1..10 inclusive.
- Note
Topswops is also known as Fannkuch from the German Pfannkuchen meaning pancake.
- Cf.
C
I don't remember how this code actually works, being an old posting and all, but the results seem right: <lang c>#include <stdio.h>
typedef unsigned char elem;
elem s[16], t[16]; size_t max_n, maxflips;
int flip() { register int i; register elem *x, *y, c;
for (i = 0; i < max_n; i++) if (s[i] == i) return 0;
for (x = t, y = s; i--;) *x++ = *y++;
i = 1; do { for (x = t, y = t + t[0]; x < y; ) c = *x, *x++ = *y, *y-- = c; i++; } while (t[t[0]]);
return i; }
inline void rotate(int n) { elem c; register int i; c = s[0]; for (i = 1; i <= n; i++) s[i-1] = s[i]; s[n] = c; }
/* Tompkin-Paige iterative perm generation */ void tk(int n) { int i = 0, f; maxflips = 0;
elem c[16] = { 0 };
while (i < n) { rotate(i); if (c[i] >= i) { c[i++] = 0; continue; }
c[i]++; i = 1; if (*s) { f = s[s[0]] ? flip() : 1; if (f > maxflips) maxflips = f; } } }
int main(void) { int i; for (max_n = 1; max_n <= 12; max_n++) { for (i = 0; i < max_n; i++) s[i] = i; tk(max_n); printf("Pfannkuchen(%d) = %d\n", max_n, maxflips); }
return 0; }</lang>
- Output:
Pfannkuchen(1) = 0 Pfannkuchen(2) = 1 Pfannkuchen(3) = 2 Pfannkuchen(4) = 4 Pfannkuchen(5) = 7 Pfannkuchen(6) = 10 Pfannkuchen(7) = 16 Pfannkuchen(8) = 22 Pfannkuchen(9) = 30 Pfannkuchen(10) = 38 Pfannkuchen(11) = 51 Pfannkuchen(12) = 65
D
Permutations generator from: http://rosettacode.org/wiki/Permutations#Faster_Lazy_Version <lang d>import std.stdio, std.algorithm, std.range, permutations2;
uint topswops(in uint n) in {
assert (n > 0 && n < 32);
} body {
static uint flip(uint[] deck) pure nothrow { uint[32] temp = void; temp[0 .. deck.length] = deck[]; uint count = 0; for (auto t0 = temp[0]; t0; t0 = temp[0]) { temp[0 .. t0 + 1].reverse(); // Slow with DMD. count++; } return count; }
return iota(n).array().permutations!0().map!flip().reduce!max();
}
void main() {
iota(1, 11).map!topswops().writeln();
}</lang>
- Output:
[0, 1, 2, 4, 7, 10, 16, 22, 30, 38]
Go
<lang go>// Adapted from http://www-cs-faculty.stanford.edu/~uno/programs/topswops.w // at Donald Knuth's web site. Algorithm credited there to Pepperdine // and referenced to Mathematical Gazette 73 (1989), 131-133. package main
import "fmt"
const ( // array sizes
maxn = 10 // max number of cards maxl = 50 // upper bound for number of steps
)
func main() {
for i := 1; i <= maxn; i++ { fmt.Printf("%d: %d\n", i, steps(i)) }
}
func steps(n int) int {
var a, b [maxl][maxn + 1]int var x [maxl]int a[0][0] = 1 var m int for l := 0; ; { x[l]++ k := int(x[l]) if k >= n { if l <= 0 { break } l-- continue } if a[l][k] == 0 { if b[l][k+1] != 0 { continue } } else if a[l][k] != k+1 { continue } a[l+1] = a[l] for j := 1; j <= k; j++ { a[l+1][j] = a[l][k-j] } b[l+1] = b[l] a[l+1][0] = k + 1 b[l+1][k+1] = 1 if l > m-1 { m = l + 1 } l++ x[l] = 0 } return m
}</lang>
- Output:
1: 0 2: 1 3: 2 4: 4 5: 7 6: 10 7: 16 8: 22 9: 30 10: 38
Perl 6
Straightforward implementation. Very slow. <lang perl6>sub postfix:<!>(@a) {
@a == 1 ?? [@a] !! gather for @a -> $a { take [ $a, @$_ ] for grep(none($a), @a)! }
}
sub swops(@a) {
my $count = 0; until @a[0] == 1 { @a = (@a.shift xx @a[0]).reverse, @a; $count++; } return $count;
} sub topswops($n) { max map &swops, (1 .. $n)! }
say "$_ {topswops $_}" for 1 .. 10;</lang>
Output follows that of Python.
Python
This solution uses cards numbered from 0..n-1 and variable p0 is introduced as a speed optimisation <lang python>>>> from itertools import permutations >>> def f1(p): i, p0 = 0, p[0] while p0: i += 1 p0 += 1 p[:p0] = p[:p0][::-1] p0 = p[0] return i
>>> def fannkuch(n): return max(f1(list(p)) for p in permutations(range(n)))
>>> for n in range(1, 11): print(n,fannkuch(n))
1 0 2 1 3 2 4 4 5 7 6 10 7 16 8 22 9 30 10 38 >>> </lang>