Mainly Tech projects on Python and Electronic Design Automation.

Saturday, April 26, 2008

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

5 comments:

  1. Excellent catch!
    This reminds me of winmine's behavior. It makes sure that your first click is never on a mine.
    (However, in some cases, your first click might solve the game.)

    ReplyDelete
  2. @lorg: sure? I can remember blowing up several times on my first click in winmine.

    Paddy: in the interest of finickity, it would be "Work pays me to be this finicky...".

    Nice post. Keep it up.

    ReplyDelete
  3. moranar:
    yes, at least starting from some version.

    ReplyDelete
  4. I don't get it... what's the error exactly? If the list is sorted, it should require 0 tries, and it does. 0 is a number.

    ReplyDelete
    Replies
    1. The idea is to play the game. If a randomised sort produces the items in order then the while loop is not taken , depriving you of playing the game. If the test was a do-while loop with the test at the end then the player would always be presented with something but the while loop can give you no game to play.

      Delete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive