1# Source: https://github.com/python/pyperformance
2# License: MIT
3
4# The Computer Language Benchmarks Game
5# http://benchmarksgame.alioth.debian.org/
6# Contributed by Sokolov Yura, modified by Tupteq.
7
8
9def fannkuch(n):
10    count = list(range(1, n + 1))
11    max_flips = 0
12    m = n - 1
13    r = n
14    check = 0
15    perm1 = list(range(n))
16    perm = list(range(n))
17    perm1_ins = perm1.insert
18    perm1_pop = perm1.pop
19
20    while 1:
21        if check < 30:
22            check += 1
23
24        while r != 1:
25            count[r - 1] = r
26            r -= 1
27
28        if perm1[0] != 0 and perm1[m] != m:
29            perm = perm1[:]
30            flips_count = 0
31            k = perm[0]
32            while k:
33                perm[: k + 1] = perm[k::-1]
34                flips_count += 1
35                k = perm[0]
36
37            if flips_count > max_flips:
38                max_flips = flips_count
39
40        while r != n:
41            perm1_ins(r, perm1_pop(0))
42            count[r] -= 1
43            if count[r] > 0:
44                break
45            r += 1
46        else:
47            return max_flips
48
49
50###########################################################################
51# Benchmark interface
52
53bm_params = {
54    (50, 10): (5,),
55    (100, 10): (6,),
56    (500, 10): (7,),
57    (1000, 10): (8,),
58    (5000, 10): (9,),
59}
60
61
62def bm_setup(params):
63    state = None
64
65    def run():
66        nonlocal state
67        state = fannkuch(params[0])
68
69    def result():
70        return params[0], state
71
72    return run, result
73