Topswops: Difference between revisions
(Updated second D entry according to the updates in C entry) |
(Updated D entries) |
||
Line 189: | Line 189: | ||
void main() { |
void main() { |
||
foreach (i; 1 .. 11) |
foreach (i; 1 .. 11) |
||
writefln("% |
writefln("%2d: %d", i, topswops(i)); |
||
}</lang> |
}</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> 1: 0 |
||
2 |
2: 1 |
||
3 |
3: 2 |
||
4 |
4: 4 |
||
5 |
5: 7 |
||
6 |
6: 10 |
||
7 |
7: 16 |
||
8 |
8: 22 |
||
9 |
9: 30 |
||
10 |
10: 38</pre> |
||
===D: Faster Version=== |
===D: Faster Version=== |
||
{{trans|C}} |
{{trans|C}} |
||
<lang d> |
<lang d>import std.stdio, std.typetuple; |
||
template Range(int start, int stop) { |
|||
static if (stop <= start) |
|||
alias TypeTuple!() Range; |
|||
else |
|||
alias TypeTuple!(Range!(start, stop - 1), stop - 1) Range; |
|||
} |
|||
⚫ | |||
uint topswops(size_t n)() nothrow { |
|||
static assert(n > 0 && n < best.length); |
|||
size_t d = 0; |
size_t d = 0; |
||
⚫ | |||
alias T = byte; |
alias T = byte; |
||
alias Deck = T[ |
alias Deck = T[n]; |
||
void trySwaps(in ref Deck deck, in uint f |
void trySwaps(in ref Deck deck, in uint f) nothrow { |
||
if (d > best[n]) |
if (d > best[n]) |
||
best[n] = d; |
best[n] = d; |
||
foreach_reverse (immutable i; 0 |
foreach_reverse (immutable i; Range!(0, n)) { |
||
if (deck[i] == -1 || deck[i] == i) |
if (deck[i] == -1 || deck[i] == i) |
||
break; |
break; |
||
Line 223: | Line 234: | ||
} |
} |
||
Deck deck2 = |
Deck deck2 = void; |
||
foreach (immutable i; Range!(0, n)) // Copy. |
|||
⚫ | |||
d++; |
d++; |
||
foreach (immutable i; Range!(1, n)) { |
|||
enum uint k = 1U << i; |
|||
⚫ | |||
if (deck2[i] == -1) { |
if (deck2[i] == -1) { |
||
if (f & k) |
if (f & k) |
||
Line 236: | Line 248: | ||
deck2[0] = cast(T)i; |
deck2[0] = cast(T)i; |
||
foreach_reverse (immutable j; 0 |
foreach_reverse (immutable j; Range!(0, i)) |
||
deck2[i - j] = deck[j]; |
deck2[i - j] = deck[j]; // Reverse copy. |
||
trySwaps(deck2, f | k |
trySwaps(deck2, f | k); |
||
} |
} |
||
d--; |
d--; |
||
Line 246: | Line 258: | ||
Deck deck0 = -1; |
Deck deck0 = -1; |
||
deck0[0] = 0; |
deck0[0] = 0; |
||
trySwaps(deck0, |
trySwaps(deck0, 1); |
||
return best[n]; |
return best[n]; |
||
} |
} |
||
import std.stdio; |
|||
void main() { |
void main() { |
||
foreach (i; 1 |
foreach (i; Range!(1, 14)) |
||
writefln("%2d: %d", i, topswops |
writefln("%2d: %d", i, topswops!i()); |
||
}</lang> |
}</lang> |
||
{{out}} |
{{out}} |
||
Line 268: | Line 278: | ||
10: 38 |
10: 38 |
||
11: 51 |
11: 51 |
||
12: 65 |
12: 65 |
||
13: 80</pre> |
|||
This version also uses templates to speed up the computation. The total runtime is about 12 seconds. |
|||
=={{header|Go}}== |
=={{header|Go}}== |
Revision as of 17:50, 27 November 2012
You are encouraged to solve this task according to the task description, using any language you may know.
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
A much faster algorithm that doesn't go through all permutations, per Knuth tAoCP 7.2.1.2 exercise 107 (possible bad implementation on my part notwithstanding): <lang c>#include <stdio.h>
- include <string.h>
typedef struct { char v[16]; } deck;
int n, d, best[16];
void tryswaps(deck *a, int f, int s) { deck b = *a; char*const A = a->v; char*const B = b.v; register int i, j, k;
if (d > best[n]) best[n] = d;
do { if (A[s] == -1 || A[s] == s) break; if (d + best[s] <= best[n]) return; } while (s--);
d++; for (i = 1, k = 2; i <= s; i++, k <<= 1) { if (B[i] == -1) { if (f & k) continue; } else if (B[i] != i) continue;
B[0] = j = i; while (j--) B[i-j] = A[j]; tryswaps(&b, f|k, s); } d--; }
int main(void) { deck x; memset(&x, -1, sizeof(x)); x.v[0] = 0;
for (n = 1; n <= 13; n++) { d = 0; tryswaps(&x, 1, n - 1); printf("%2d: %d\n", n, best[n]); }
return 0; }</lang>
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() {
foreach (i; 1 .. 11) writefln("%2d: %d", i, topswops(i));
}</lang>
- Output:
1: 0 2: 1 3: 2 4: 4 5: 7 6: 10 7: 16 8: 22 9: 30 10: 38
D: Faster Version
<lang d>import std.stdio, std.typetuple;
template Range(int start, int stop) {
static if (stop <= start) alias TypeTuple!() Range; else alias TypeTuple!(Range!(start, stop - 1), stop - 1) Range;
}
__gshared uint[32] best;
uint topswops(size_t n)() nothrow {
static assert(n > 0 && n < best.length); size_t d = 0;
alias T = byte; alias Deck = T[n];
void trySwaps(in ref Deck deck, in uint f) nothrow { if (d > best[n]) best[n] = d;
foreach_reverse (immutable i; Range!(0, n)) { if (deck[i] == -1 || deck[i] == i) break; if (d + best[i] <= best[n]) return; }
Deck deck2 = void; foreach (immutable i; Range!(0, n)) // Copy. deck2[i] = deck[i];
d++; foreach (immutable i; Range!(1, n)) { enum uint k = 1U << i; if (deck2[i] == -1) { if (f & k) continue; } else if (deck2[i] != i) continue;
deck2[0] = cast(T)i; foreach_reverse (immutable j; Range!(0, i)) deck2[i - j] = deck[j]; // Reverse copy. trySwaps(deck2, f | k); } d--; }
best[n] = 0; Deck deck0 = -1; deck0[0] = 0; trySwaps(deck0, 1); return best[n];
}
void main() {
foreach (i; Range!(1, 14)) writefln("%2d: %d", i, topswops!i());
}</lang>
- Output:
1: 0 2: 1 3: 2 4: 4 5: 7 6: 10 7: 16 8: 22 9: 30 10: 38 11: 51 12: 65 13: 80
This version also uses templates to speed up the computation. The total runtime is about 12 seconds.
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
J
Solution:<lang j> swops =: ((|.@:{. , }.)~ {.)^:a:</lang> Example (from task introduction):<lang j> swops 2 4 1 3 2 4 1 3 4 2 1 3 3 1 2 4 2 1 3 4 1 2 3 4</lang> Example (topswops of all permutations of the integers 1..10):<lang j> (,. _1 + ! >./@:(#@swops@A. >:)&i. ])&> 1+i.10
1 0 2 1 3 2 4 4 5 7 6 10 7 16 8 22 9 30
10 38</lang>
Java
Some of this code was copied from Utils.java. It uses a lot of memory and should probably be replaced with something that works better, but it's a start. <lang java5>import java.util.ArrayList; import java.util.Collections;
public class Topswops{ private static <T extends Comparable<? super T>> boolean nextPerm(ArrayList<T> data){ // find the swaps int c = -1, d = data.size(); for(int i = d - 2; i >= 0; i--) if(data.get(i).compareTo(data.get(i + 1)) < 0){ c = i; break; }
if(c < 0) return false;
int s = c + 1; for(int j = c + 2; j < d; j++) if(data.get(j).compareTo(data.get(s)) < 0 && data.get(j).compareTo(data.get(c)) > 0) s = j;
// do the swaps Collections.swap(data, c, s); while (--d > ++c) Collections.swap(data, c, d);
return true; }
private static <T extends Comparable<? super T>> ArrayList<ArrayList<T>> permutations(ArrayList<T> d){ ArrayList<ArrayList<T>> result = new ArrayList<ArrayList<T>>(); Collections.sort(d); do{ result.add(new ArrayList<T>(d)); }while(nextPerm(d)); return result; }
public static int topswops(int n){ int retVal = 0; ArrayList<Integer> orig = new ArrayList<Integer>(n); for(int i = 1; i <= n; i++){ orig.add(i); //build the original list } ArrayList<ArrayList<Integer>> perms = permutations(orig); for(ArrayList<Integer> perm : perms){ int swaps = run(perm); if(swaps > retVal) retVal = swaps; }
return retVal; }
private static int run(ArrayList<Integer> perm){ int count = 0; int first = perm.get(0); while(first != 1){ count++; ArrayList<Integer> swapMe = new ArrayList<Integer>(); for(int i = 0; i < first; i++){ swapMe.add(perm.remove(0)); //grab the section that needs to be reversed } Collections.reverse(swapMe); perm.addAll(0, swapMe); //put it back at the start first = perm.get(0); //get the new first element } return count; }
public static void main(String[] args){ for(int i = 1; i <= 10; i++){ System.out.println(i + ": " + topswops(i)); } }
}</lang> Output:
1: 0 2: 1 3: 2 4: 4 5: 7 6: 10 7: 16 8: 22 9: 30 10: 38
Perl 6
<lang perl6>sub postfix:<!>(@a) {
@a == 1 ?? [@a] !! do for @a -> $a { [ $a, @$_ ] for @a.grep(* != $a)! }
}
sub swops(@a is copy) {
my $count = 0; until @a[0] == 1 { @a[ ^@a[0] ] .= reverse; $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>
Python: Faster Version
<lang python>try:
import psyco psyco.full()
except ImportError:
pass
best = [0] * 16
def try_swaps(deck, f, s, d, n):
if d > best[n]: best[n] = d
i = 0 k = 1 << s while s: k >>= 1 s -= 1 if deck[s] == -1 or deck[s] == s: break i |= k if (i & f) == i and d + best[s] <= best[n]: return d s += 1
deck2 = list(deck) k = 1 for i2 in xrange(1, s): k <<= 1 if deck2[i2] == -1: if f & k: continue elif deck2[i2] != i2: continue
deck[i2] = i2 deck2[0:i2+1] = reversed(deck[0:i2+1]) try_swaps(deck2, f | k, s, 1 + d, n)
def topswops(n):
best[n] = 0 deck0 = [-1] * 16 deck0[0] = 0 try_swaps(deck0, 1, n, 0, n) return best[n]
for i in xrange(1, 13):
print "%2d: %d" % (i, topswops(i))</lang>
- Output:
1: 0 2: 1 3: 2 4: 4 5: 7 6: 10 7: 16 8: 22 9: 30 10: 38 11: 51 12: 65
XPL0
<lang XPL0>code ChOut=8, CrLf=9, IntOut=11; int N, Max, Card1(16), Card2(16);
proc Topswop(D); \Conway's card swopping game int D; \depth of recursion int I, J, C, T; [if D # N then \generate N! permutations of 1..N in Card1
[for I:= 0 to N-1 do [for J:= 0 to D-1 do \check if object (letter) already used if Card1(J) = I+1 then J:=100; if J < 100 then [Card1(D):= I+1; \card number not used so append it Topswop(D+1); \recurse next level deeper ]; ]; ]
else [\determine number of topswops to get card 1 at beginning
for I:= 0 to N-1 do Card2(I):= Card1(I); \make working copy of deck C:= 0; \initialize swop counter while Card2(0) # 1 do [I:= 0; J:= Card2(0)-1; while I < J do [T:= Card2(I); Card2(I):= Card2(J); Card2(J):= T; I:= I+1; J:= J-1; ]; C:= C+1; ]; if C>Max then Max:= C; ];
];
[for N:= 1 to 10 do
[Max:= 0; Topswop(0); IntOut(0, N); ChOut(0, ^ ); IntOut(0, Max); CrLf(0); ];
]</lang>
- Output:
1 0 2 1 3 2 4 4 5 7 6 10 7 16 8 22 9 30 10 38