Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

Friday, November 23, 2012

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 != 1:
i += 1
print(i,p)
p[:p] = p[:p][::-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 != 1:
i += 1
#print(i,p)
p[:p] = p[:p][::-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:
i += 1
p[:p + 1] = p[:p + 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
while p0:
i  += 1
p0 += 1
p[:p0] = p[:p0][::-1]
p0  = p
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 to p0 and discard p[1:] for the purposes of the assignment into *_. I tried:

```>>> def f1(p):
i, p0 = 0, p
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
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)
```
"