Topswop and a convoluted multiple assignments warning

I was messing around with John Conways Topswop problem:

Given a starting permutation of 1..n items, consider the leftmost value and call it L:

• If L is not 1 then reverse the leftmost L values in the sequence.
• Repeat, counting the number of reversions required until L becomes 1

Repeat the process for all permutations of 1..n items and report the maximum number of reversions required amongst all the permutations.

I initially came up with this doodle:

>>> def f1(p):
    i = 0
    while p[0] != 1:
        i += 1
        print(i,p)
        p[:p[0]] = p[:p[0]][::-1]
    return i

>>> f1([4,2,1,5,3])
1 [4, 2, 1, 5, 3]
2 [5, 1, 2, 4, 3]
3 [3, 4, 2, 1, 5]
4 [2, 4, 3, 1, 5]
5 [4, 2, 3, 1, 5]
5
>>> def f1(p):
    i = 0
    while p[0] != 1:
        i += 1
        #print(i,p)
        p[:p[0]] = p[:p[0]][::-1]
    return i

>>> f1([4,2,1,5,3])
5
>>> from itertools import permutations
>>> def fannkuch(n):
    return max(f1(list(p)) for p in permutations(range(1, n+1)))

>>> 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
>>>

Range

Python usually uses ranges 0..n-1 so I made that modification:

>>> def f1(p):
    i = 0
    while p[0]:
        i += 1
        p[:p[0] + 1] = p[:p[0] + 1][::-1]
    return i

>>> def fannkuch(n):
    return max(f1(list(p)) for p in permutations(range(n)))

Speed

I had to wait for fannkuch(10) so decided to do some quick optimization and created name p0 to mop up some array lookups:

>>> def f1(p):
    i, p0 = 0, p[0]
    while p0:
        i  += 1
        p0 += 1
        p[:p0] = p[:p0][::-1]
        p0  = p[0]
    return i

Those assignments

It was at this stage that I thought "Ooh, I haven't used that new assignment in Python 3 where you can use *name on the left hand side of an assignment", plus, I could add it in to an already complex assignment  just for the hell of it.

I am creating p, so I should be able to assign p[0] to p0 and discard p[1:] for the purposes of the assignment into *_. I tried:

>>> def f1(p):
    i, p0 = 0, p[0]
    while p0:
        i  += 1
        p0 += 1
        p0, *_ = p[:p0] = p[:p0][::-1]
    return i

>>> for n in range(1, 11): print(n,fannkuch(n))

1 0
2 1
3 2
Traceback (most recent call last):
  File "", line 1, in 
    for n in range(1, 11): print(n,fannkuch(n))
  File "", line 2, in fannkuch
    return max(f1(list(p)) for p in permutations(range(n)))
  File "", line 2, in 
    return max(f1(list(p)) for p in permutations(range(n)))
  File "", line 6, in f1
    p0, *_ = p[:p0] = p[:p0][::-1]
KeyboardInterrupt
>>>

I had to interrupt it as it failed to return. Something was wrong!

I thought it might be the order of assignment and tried:

>>> def f1(p):
    i, p0 = 0, p[0]
    while p0:
        i  += 1
        p0 += 1
        p[:p0] = p0, *_ = p[:p0][::-1]
    return i

>>> 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
>>>

Yay Success!!

But I did this so you don't have to :-)

It is a few optimizations too far, and, when you look in the docs they state:

"
WARNING: Although the definition of assignment implies that overlaps between the left-hand side and the right-hand side are ‘safe’ (for example a, b= b, a swaps two variables), overlaps within the collection of assigned-to variables are not safe! For instance, the following program prints [0, 2]:

x = [0, 1]
i = 0
i, x[i] = 1, 2
print(x)

"