Bug in simple code after 2+ years and 133 comments

I was just reading this blog entry about a simple game of presenting a scrambled list of numbers and you having to reverse the leftmost N numbers until all numbers are in ascending order.

The game is implemented in various languages, including PHP Ruby and Python and most seem to be structured as:

1. create a randomized list of numbers
2. while the list is not sorted:
1. ask for and input the number to be reversed
2. reverse that portion of the list.

Ignoring any checks on input, it seemed odd that the programs did not check that the initial randomization did not produce a sorted list at step 1 that would cause the inner while loop to be skipped altogether!

Here is proof for Python:

>>> n = 10
>>> sortlist = range(n)
>>> randlist = range(n)
>>> random.shuffle(randlist)
>>> x = 0
>>> while randlist != sortlist:
...     x += 1
...     random.shuffle(randlist)
...
>>> print x
714418
>>>

If you were testing an implementation or otherwise running it, every once in a while it would just exit. Run it again and it would most likely work for a long time. It is not something I would like to use the normal xUnit type tests/continuous testing regime to uncover as although a transient fail would be noted, those test regimes rely heavily on easy reproducibility of the failure.

I guess what would be needed is knowledge of corner cases. For shuffle, corner cases to think of would include returning the input order, reverse input order, sorted, and reverse sorted order.





- Paddy.






P.S. Work pays me to be this finickity when testing ASICs