Reprise: [2,3,4,7] --> "2-4,7"
Peter Hansen
peter at engcorp.com
Tue Jun 17 22:59:20 EDT 2003
I followed the original thread with great interest, as I thought
of using the problem as the focus of a workshop in Test-Driven
Development which I was planning to hold at work with my group.
(Yes, those of you sick of TDD in general, or especially my comments
about it and the value of unit testing, might like to hit "k" at this
point. Or stay on board and perhaps find something of interest. :-)
I saved the original messages, but studiously avoided looking at
any of the solutions: I wanted the chance to develop a solution on
my own, using TDD, and to explore any differences which might be
attributable to the use of that approach.
(Note here: I don't yet consider myself extremely proficient at TDD,
but even so I am much better with it than without. I wanted the practice,
sure, but also a chance to compare my results objectively with what
others produced.)
(Another note: I probably spent substantially longer on this than
any of the others. For the record, it took me much of a tedious
Sunday to get my code working.)
I ended up writing 19 unit tests to drive my design, and worked from
a set of four (initially, then five) acceptance tests based on
the two initial uses cases (the thread's title, and the example
within), plus a special case (the example reversed), plus the one
failure pointed out by M.Garcia (foo, foo1). Later, after I finished,
I added another case after noticing a likely failure mode in M.Fletcher's
code. (Sorry Mike! :-)
Here's the summary of the results. NOTE: some of the failures are
based solely on the programmer's perfectly valid interpretation of
ambiguous requirements, but I might have chosen to interpret them
differently in my acceptance tests. See the explanatory notes.
Programmer Results (of 5 tests) Notes
--------------- -------------------- --------------------
ACooke 2 failures, 1 error [3] [4]
Alex 1 error [3]
ASchmolk 1 failure [6]
CezaryB no failures
GYoung no failures
MFletcher 2 failures [1] [2]
MGarcia#1 1 failure [1]
PHansen no failures
RHettinger 4 failures, 1 error [3] [4] [5]
SDaniels 1 error [3]
[1] When an item with a leading zero (e.g. mx09) is not part of a "span"
it is unclear whether it should be left as-is or returned as an
integer with the zero stripped (e.g. mx9) as would happen if it
forms a span's endpoint. The choice is arbitrary: I happened to
choose "stripped" initially, then changed my mind once I ran
GYoung's code, treating the OP's own code as the requirement.
It's unfair to call this one a real failure.
[2] The "foo0,foo1" case is treated as "foo,foo1".
[3] Raises ValueError when comparing "foo" and "foo1".
[4] Merges non-adjacent spans, contrary to the requirement that the
"original order of names be preserved".
[5] Returns "2-6" from input of "2,3,4,7". Returns "foo0-2" from input
of "foo0,foo1". Probably an off-by-one error?
[6] Returns "2-4" from input of "2,3,4,7". Another off-by-one?
Here's some informal data on the sizes of the programs from PyCount,
purely for the curious. I've marked with (*) those which had no
failures other than item [1] above.
lines code doc comment blank file
28 22 1 0 5 .\ranges_acooke.py
14 10 1 0 3 .\ranges_alex.py
24 21 1 0 2 .\ranges_aschmolk.py
42 36 1 0 5 .\ranges_cezaryb.py (*)
29 23 1 0 5 .\ranges_gyoung.py (*)
50 39 3 3 5 .\ranges_mfletcher.py
46 42 1 0 3 .\ranges_mgarcia1.py (*)
64 48 1 7 8 .\ranges_phansen.py (*)
29 21 1 2 5 .\ranges_rhettinger.py
32 26 1 0 5 .\ranges_sdaniels.py
One should not, of course, expect much in the way of doc/comment lines
for code posted to the newsgroup. Speaking empirically, anyway. :-)
This is an early result, from an evening's work wrapping my acceptance
tests around each programmer's code. I have not yet attempted to
compare more subjective aspects, such as how readable the code is,
nor how amenable to refactoring.
For the record, since the others have all posted their code for
public viewing and, unwittingly, this dissection, here is mine:
----------------------------------------------------
from __future__ import generators
def areConsecutive(left, right):
try:
return left[0] == right[0] and int(left[1]) + 1 == int(right[1])
except (TypeError, ValueError):
return False
def endpoints(items):
if items:
items = iter(items)
left = items.next()
try:
while 1:
# have at least one item, try finding a next
test = items.next()
if areConsecutive(left, test):
try:
# we've found a span of at least two, continue checking
while 1:
right = test
test = items.next()
if areConsecutive(right, test):
# still have a span, continue
right = test
else:
# span has ended: yield it and continue
yield left, right
left = test
break
except StopIteration:
# ran out during span: yield it and we're done
yield left, right
return
else:
# yield non-span and try again
yield left,
left = test
# handle final case where we have a left but no right
except StopIteration:
yield left,
def formatRange(items):
if len(items) == 2:
return '%s%s-%s' % (tuple(items[0]) + (items[1][1],))
else:
return '%s%s' % tuple(items[0])
def split(item):
import re
prefix, val = re.match('(\D*)(\d*)', item).groups()
return prefix, val
def collapse(items):
items = [split(x) for x in items]
result = []
for span in endpoints(items):
result.append(formatRange(span))
return result
-----------------------------------------------------
I would really have liked to simplify endpoints(), but I didn't
seem to have any of the inspiration that led some of the more
brilliant among us to such short answers as they produced! :-(
Here are the acceptance test cases. If there's any interest
at all, I can post the unit tests which drove my design above.
---------------------------------------------------
'''Acceptance tests for TDD seminar problem.'''
# Run as "python accept.py programmer" where programmer is, e.g. "phansen".
# Modules under test are stored as "ranges_phansen.py" and so on.
import unittest
# module under test
import sys
try:
name = 'ranges_' + sys.argv[1]
sys.argv[1:] = sys.argv[2:]
except:
name = 'ranges'
moduleUnderTest = __import__(name)
collapse = moduleUnderTest.collapse
class TestCase(unittest.TestCase):
def test01(self):
'''simple numbers, from title of posting'''
self.assertEqual(collapse(['2','3','4','7']), ['2-4','7'])
def test02(self):
'''include prefixes, contiguous ranges separated by other elements, non-numeric items'''
self.assertEqual(collapse(['6','7','mx8','mx09','mx10','8','9','10','foo']),
['6-7','mx8-10','8-10','foo'])
def test03(self):
'''reversed example: don't form any ranges, don't munge leading zeros either'''
self.assertEqual(collapse(['foo','10','9','8','mx10','mx09','mx8']),
['foo','10','9','8','mx10','mx09','mx8'])
def test04(self):
'''case from newsgroup that wasn't handled by one solution'''
self.assertEqual(collapse(['foo','foo1']),
['foo','foo1'])
def test05(self):
'''test for handling 0 as a valid integer: Mike's code appears flawed in this respect'''
self.assertEqual(collapse(['foo0','foo1']),
['foo0-1'])
if __name__ == '__main__':
unittest.main()
---------------------------------------------------
-with-apologies-to-anyone-feeling-over-scrutinized-ly y'rs,
Peter Hansen
More information about the Python-list
mailing list