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

That history meme, in Python!

It seemsed that everyone was joining in the 'history meme', and finding out what was in their history:

http://blogs.gnome.org/newren/2008/04/11/that-history-meme/
http://jaysonrowe.wordpress.com/2008/04/11/command-history-meme/
http://jjesse.wordpress.com/2008/04/11/joining-the-history-meme/
http://fengshaun.wordpress.com/2008/04/11/shell-history-meme/
(You get the idea, ... more here).

They were all using unix command line tools, piped together to show the most frequent commands they had used.:

history|awk '{a[$2]++ } END{for(i in a){print a[i] " " i}}'|sort -rn|head

This being a Python blog, and knowing before-hand that Python is really awful at one-liners, I nevertheless decided that it would be of some use to try and pipe history to a Python one-liner that performed a similar task .

I came up with:

bash$ history | python  -c 'import sys,itertools,pprint; 
    pprint.pprint(sorted([
        (len(list(g)),k) for k,g in itertools.groupby(sorted([
            x.split()[1]for x in sys.stdin if len(x.split())>1])
            , lambda x:x)
        ])
        [-10:][::-1])' 
[(63, 'echo'),
 (41, 'history'),
 (30, './tst1.sh'),
 (28, 'declare'),
 (21, 'python'),
 (18, 'perl'),
 (18, 'cat'),
 (16, 'ls'),
 (15, 'xterm'),
 (15, 'history|python')]
bash$ 

I decided to break the command into multiple lines for readability above; it was developed, painfully, all on one line.

So readers, the above is something that Python stinks at - one-liners. (Unless you know a better way in Python ...)

- Paddy.