Topswops: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 42:
{{trans|Python:_Faster_Version}}
<
F try_swaps(&deck, f, =s, d, n)
Line 83:
L(i) 1..12
print(‘#2: #.’.format(i, topswops(i)))</
{{out}}
Line 103:
=={{header|360 Assembly}}==
The program uses two ASSIST macro (XDECO,XPRNT) to keep the code as short as possible.
<
TOPSWOPS CSECT
USING TOPSWOPS,R13 base register
Line 223:
BR R14 ---------------}-----------------------------------
YREGS
END TOPSWOPS</
{{out}}
<pre>
Line 241:
This is a straightforward approach that counts the number of swaps for each permutation. To generate all permutations over 1 .. N, for each of N in 1 .. 10, the package Generic_Perm from the Permutations task is used [[http://rosettacode.org/wiki/Permutations#The_generic_package_Generic_Perm]].
<
procedure Topswaps is
Line 279:
Ada.Integer_Text_IO.Put(Item => Topswaps(I), Width => 3);
end loop;
end Topswaps;</
{{out}}<pre> 0 1 2 4 7 10 16 22 30 38</pre>
=={{header|AutoHotkey}}==
<
R := []
for i, val in obj{
Line 295:
R[A_Index]:= A_LoopField
return R
}</
Examples:<
Res := Print(Cards)
while (Cards[1]<>1)
Line 309:
Res .= (A_Index=1?"":"`t") val
return Trim(Res,"`n")
}</
Outputs:<pre>2 4 1 3
4 2 1 3
Line 318:
=={{header|C}}==
An algorithm that doesn't go through all permutations, per Knuth tAoCP 7.2.1.2 exercise 107 (possible bad implementation on my part notwithstanding):
<
#include <string.h>
Line 362:
return 0;
}</
The code contains critical small loops, which can be manually unrolled for those with OCD. POSIX thread support is useful if you got more than one CPUs.
<
#include <stdio.h>
#include <string.h>
Line 479:
return 0;
}</
=={{header|C++}}==
<
#include <iostream>
#include <vector>
Line 507:
}
return 0;
}</
{{out}}
Line 525:
http://rosettacode.org/wiki/Permutations#Faster_Lazy_Version
{{trans|Haskell}}
<
int topswops(in int n) pure @safe {
Line 539:
foreach (immutable i; 1 .. 11)
writeln(i, ": ", i.topswops);
}</
{{out}}
<pre>1: 0
Line 554:
===D: Faster Version===
{{trans|C}}
<
__gshared uint[32] best;
Line 605:
foreach (immutable i; staticIota!(1, 14))
writefln("%2d: %d", i, topswops!i());
}</
{{out}}
<pre> 1: 0
Line 623:
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
TOPSWOPS
Line 735:
end
</syntaxhighlight>
Test:
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 759:
end
</syntaxhighlight>
{{out}}
<pre>
Line 776:
=={{header|Elixir}}==
{{trans|Erlang}}
<
def get_1_first( [1 | _t] ), do: 0
def get_1_first( list ), do: 1 + get_1_first( swap(list) )
Line 799:
end
Topswops.task</
{{out}}
Line 818:
=={{header|Erlang}}==
This code is using the [[Permutations | permutation]] code by someone else. Thank you.
<syntaxhighlight lang="erlang">
-module( topswops ).
Line 840:
get_1_first_many( N_permutations ) -> [get_1_first(X) || X <- N_permutations].
</syntaxhighlight>
{{out}}
<pre>
Line 858:
=={{header|Factor}}==
<
math.ranges sequences ;
FROM: sequences.private => exchange-unsafe ;
Line 883:
10 [1,b] [ dup topswops "%2d: %2d\n" printf ] each ;
MAIN: main</
{{out}}
<pre>
Line 899:
=={{header|Fortran}}==
<
implicit none
contains
Line 955:
end do
end program
</syntaxhighlight>
=={{header|Go}}==
<
// at Donald Knuth's web site. Algorithm credited there to Pepperdine
// and referenced to Mathematical Gazette 73 (1989), 131-133.
Line 1,012:
}
return m
}</
{{out}}
<pre>
Line 1,029:
=={{header|Haskell}}==
====Searching permutations====
<
topswops :: Int -> Int
Line 1,040:
main =
mapM_ (putStrLn . ((++) <$> show <*> (":\t" ++) . show . topswops)) [1 .. 10]</
{{out}}
<pre>1: 0
Line 1,056:
'''Alternate version'''
<br>Uses only permutations with all elements out of place.
<
import Control.Arrow (first)
Line 1,075:
main :: IO ()
main = mapM_ print $ take 10 $ topSwops [1 ..]</
'''Output'''
<pre>(1,0)
Line 1,093:
build the original list of 1..n values.
<
every n := 1 to 10 do {
ts := 0
Line 1,113:
if *A <= 1 then return A
suspend [(A[1]<->A[i := 1 to *A])] ||| permute(A[2:0])
end</
Sample run:
Line 1,132:
=={{header|J}}==
'''Solution''':<
'''Example''' (''from task introduction''):<
2 4 1 3
4 2 1 3
3 1 2 4
2 1 3 4
1 2 3 4</
'''Example''' (''topswops of all permutations of the integers 1..10''):<
1 0
2 1
Line 1,149:
8 22
9 30
10 38</
'''Notes''': Readers less familiar with array-oriented programming may find [[Talk:Topswops#Alternate_J_solution|an alternate solution]] written in the structured programming style more accessible.
=={{header|Java}}==
{{trans|D}}
<
static final int maxBest = 32;
static int[] best;
Line 1,200:
System.out.println(i + ": " + topswops(i));
}
}</
{{out}}
<pre>1: 0
Line 1,217:
'''Infrastructure:'''
<
def until(cond; next):
def _until:
Line 1,236:
else
. as $n | ($n-1) | permutations | [$n-1, .] | insert
end;</
'''Topswops:'''
<
def flips:
# state: [i, array]
Line 1,250:
def fannkuch:
reduce permutations as $p
(0; [., ($p|flips) ] | max);</
'''Example:'''
<
{{out}}
<
[1,0]
[2,1]
Line 1,265:
[8,22]
[9,30]
[10,38]</
=={{header|Julia}}==
Fast, efficient version
<
n == 1 && return 0
n == 2 && return 1
Line 1,333:
end
end
end</
{{out}}
<pre>julia> function main()
Line 1,358:
=={{header|Kotlin}}==
{{trans|Java}}
<
val best = IntArray(32)
Line 1,392:
fun main(args: Array<String>) {
for (i in 1..10) println("${"%2d".format(i)} : ${topswops(i)}")
}</
{{out}}
Line 1,409:
=={{header|Lua}}==
<
function permute (list)
local function perm (list, n)
Line 1,451:
-- Main procedure
for i = 1, 10 do print(i, topswops(i)) end</
{{out}}
<pre>1 0
Line 1,466:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
An exhaustive search of all possible permutations is done
<
swaps[a_] := Length@FixedPointList[flip, a] - 2
Print[#, ": ", Max[swaps /@ Permutations[Range@#]]] & /@ Range[10];</
{{out}}
<pre>1: 0
Line 1,483:
=={{header|Nim}}==
{{trans|Java}}
<
const maxBest = 32
Line 1,522:
for i in 1..10:
echo &"{i:2}: {topswops(i):2}"</
{{out}}
<pre>
Line 1,539:
=={{header|PARI/GP}}==
Naive solution:
<
my(t=v[1]+1);
if (t==2, return(0));
Line 1,552:
mx;
}
vector(10,n,topswops(n))</
{{out}}
<pre>%1 = [0, 1, 2, 4, 7, 10, 16, 22, 30, 38]</pre>
Line 1,560:
=={{header|Perl}}==
Recursive backtracking solution, starting with the final state and going backwards.
<
sub next_swop {
my( $max, $level, $p, $d ) = @_;
Line 1,596:
printf "Maximum swops for %2d cards: %2d\n", $_, topswops $_ for 1..10;
</syntaxhighlight>
{{out}}
Line 1,614:
=={{header|Phix}}==
Originally contributed by Jason Gade as part of the Euphoria version of the Great Computer Language Shootout benchmarks.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">fannkuch</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 1,656:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 1,674:
=={{header|Picat}}==
<
member(N,1..10),
Perm = 1..N,
Line 1,725:
S := S + 1
end
end.</
{{out}}
Line 1,741:
=={{header|PicoLisp}}==
<
(let (Lst (range 1 N) L Lst Max)
(recur (L) # Permute
Line 1,755:
(for I 10
(println I (fannkuch I)) )</
Output:
<pre>1 0
Line 1,770:
=={{header|PL/I}}==
{{incorrect|PL/I|Shown output is incorrect at the very least.}}
<syntaxhighlight lang="pl/i">
(subscriptrange):
topswap: procedure options (main); /* 12 November 2013 */
Line 1,803:
end;
end topswap;
</syntaxhighlight>
<pre>
1: 1
Line 1,818:
=={{header|Potion}}==
<
i = 0, l = list(b-a+1)
while (a + i <= b):
Line 1,872:
if (n<1): n=10.
fannkuch(n)
</syntaxhighlight>
Output follows that of Raku and Python, ~2.5x faster than perl5
Line 1,878:
=={{header|Python}}==
This solution uses cards numbered from 0..n-1 and variable p0 is introduced as a speed optimisation
<
>>> def f1(p):
i = 0
Line 1,903:
9 30
10 38
>>> </
===Python: Faster Version===
{{trans|C}}
<
import psyco
psyco.full()
Line 1,952:
for i in xrange(1, 13):
print "%2d: %d" % (i, topswops(i))</
{{out}}
<pre> 1: 0
Line 1,969:
=={{header|R}}==
Using iterpc package for optimization
<syntaxhighlight lang="r">
topswops <- function(x){
i <- 0
Line 1,995:
result <- rbind(result, c(i, max(A$flips)))
}
</syntaxhighlight>
Output:
Line 2,015:
Simple search, only "optimization" is to consider only all-misplaced permutations (as in the alternative Haskell solution), which shaves off around 2 seconds (from ~5).
<syntaxhighlight lang="racket">
#lang racket
Line 2,033:
(for ([i (in-range 1 11)]) (printf "~a\t~a\n" i (topswops i)))
</syntaxhighlight>
Output:
Line 2,051:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
my int $count = 0;
until @a[0] == 1 {
Line 2,062:
sub topswops($n) { max (1..$n).permutations.race.map: &swops }
say "$_ {topswops $_}" for 1 .. 10;</
{{Out}}
<pre>1 0
Line 2,077:
Alternately, using string manipulation instead. Much faster, though honestly, still not very fast.
<syntaxhighlight lang="raku"
my int $count = 0;
while (my \l = $a.ord) > 1 {
Line 2,088:
sub topswops($n) { max (1..$n).permutations.map: { .chrs.join.&swops } }
say "$_ {topswops $_}" for 1 .. 10;</
Same output
Line 2,095:
The '''decks''' function is a modified permSets (permutation sets) subroutine,
<br>and is optimized somewhat to take advantage by eliminating one-swop "decks".
<
parse arg things .; if things=='' then things= 10
Line 2,132:
end /*h*/
z= reverse( subword(z, 1, t) ) subword(z, t + 1)
end /*u*/</
Some older REXXes don't have a '''changestr''' BIF, so one is included here ───► [[CHANGESTR.REX]].
Line 2,151:
=={{header|Ruby}}==
{{trans|Python}}
<
i = 0
while (a0 = a[0]) > 1
Line 2,166:
for n in 1..10
puts "%2d : %d" % [n, fannkuch(n)]
end</
{{out}}
Line 2,184:
'''Faster Version'''
{{trans|Java}}
<
@best[n] = d if d > @best[n]
(n-1).downto(0) do |i|
Line 2,214:
for i in 1..10
puts "%2d : %d" % [i, topswops(i)]
end</
=={{header|Rust}}==
<
use itertools::Itertools;
Line 2,250:
(1_usize..=10).for_each(|x| println!("{}: {}", x, topswops(x)));
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,266:
=={{header|Scala}}==
{{libheader|Scala}}<
def fannkuchen(l: List[Int], n: Int, i: Int, acc: Int): Int = {
Line 2,297:
assert(result == Vector((1, 0), (2, 1), (3, 2), (4, 4), (5, 7), (6, 10), (7, 16), (8, 22), (9, 30), (10, 38)), "Bad results")
println(s"Successfully completed without errors. [total ${scala.compat.Platform.currentTime - executionStart} ms]")
}</
Computing results...
Pfannkuchen(1) = 0
Line 2,315:
=={{header|Tcl}}==
{{tcllib|struct::list}}<!-- Note that struct::list 1.8.1 (and probably earlier too) has a bug which makes this code hang when computing topswops(10). -->Probably an integer overflow at n=10.
<
proc swap {listVar} {
Line 2,348:
}
}
topswopsTo 10</
n topswops(n)
1 0
Line 2,364:
{{trans|Go}}
{{libheader|Wren-fmt}}
<
var maxn = 10
Line 2,413:
}
for (i in 1..maxn) Fmt.print("$2d: $d", i, steps.call(i))</
{{out}}
Line 2,430:
=={{header|XPL0}}==
<
int N, Max, Card1(16), Card2(16);
Line 2,466:
IntOut(0, N); ChOut(0, ^ ); IntOut(0, Max); CrLf(0);
];
]</
{{out}}
Line 2,485:
{{trans|C}}
<
int N, D, Best(16);
Line 2,520:
IntOut(0, N); Text(0, ": "); IntOut(0, Best(N)); CrLf(0);
];
]</
{{out}}
Line 2,542:
{{trans|D}}
Slow version
<
flip:=fcn(xa){
if (not xa[0]) return(0);
Line 2,551:
}
foreach n in ([1 .. 10]){ println(n, ": ", topswops(n)) }</
{{out}}
<pre>
|