[Baypiggies] a python puzzle

Brent Pedersen bpederse at gmail.com
Wed Apr 14 18:41:09 CEST 2010


On Wed, Apr 14, 2010 at 9:32 AM, Damon McCormick <damonmc at gmail.com> wrote:
> Sorry about the cut-and-paste error.  Corrected below.  Also, I believe my
> code is equivalent to Thomas'.
>
> -Damon
>
>
> On Wed, Apr 14, 2010 at 9:29 AM, Damon McCormick <damonmc at gmail.com> wrote:
>>
>> Keeping your original approach, you could define a function like this:
>>
>> def next_or_none_pair (itr):
>>     def result_func ():
>>         try:
>>             return itr.next()
>>         except StopIteration:
>>             return (None, None)
>>     return result_func
>>
>> and then replace your current definitions of xnext and ynext by the
>> following:
>>
>>     xnext = next_or_none_pair(itertools.groupby(xs, grouper))
>>     ynext = next_or_none_pair(itertools.groupby(ys, grouper))
>>
>> The condition of your while loop is already set up to exit when either x
>> or y is None (a condition which, I believe, is currently never True, since
>> the loop ends when StopIteration is thrown).
>>
>> So the only other modification you'd need is that your comparisions
>> between x and y need to handle None:
>>
>>         elif y is None or x < y:
>>             yield list(xgroup), None
>>             x, xgroup = xnext()
>>         elif x is None or x > y:
>>             yield (None, list(ygroup))
>>             y, ygroup = ynext()
>>
>> So the entire thing would look like this:
>>
>
>>
>> import itertools
>>
>>
>> def next_or_none_pair (itr):
>>     def result_func ():
>>     try:
>>             return itr.next()
>>     except StopIteration:
>>             return (None, None)
>>     return result_func
>>
>> def as_pairs (xs, ys, grouper=lambda _: _):
>>
>> """
>>     >>> aordered = [1, 1, 2, 4, 6, 8,
>> 9]
>>     >>> bordered = [1, 3, 4, 5, 6, 7,
>> 8]
>>     >>> for a, b in as_pairs(aordered,
>> bordered):
>>     ... a,
>> b
>>     ([1, 1],
>> [1])
>>     ([2],
>> None)
>>     (None,
>> [3])
>>     ([4],
>> [4])
>>     (None,
>> [5])
>>     ([6],
>> [6])
>>     (None,
>> [7])
>>     ([8],
>> [8])
>>     ([9],
>> None)
>>     """
>>     # assume xs and ys are
>> sorted.
>>     xnext = next_or_none_pair(itertools.groupby(xs, grouper))
>>     ynext = next_or_none_pair(itertools.groupby(ys, grouper))
>>     x, xgroup = xnext()
>>     y, ygroup = ynext()
>>     while x or y:
>>         if x == y:
>>             yield list(xgroup), list(ygroup)
>>             x, xgroup = xnext()
>>             y, ygroup = ynext()
>>         elif y is None or x < y:
>>             yield list(xgroup), None
>>             x, xgroup = xnext()
>>         elif x is None or x > y:
>>             yield (None, list(ygroup))
>>             y, ygroup = ynext()
>>         else:
>>             assert False
>>
>> if __name__ == "__main__":
>>     import doctest
>>     doctest.testmod()
>>
>>
>>
>>
>> On Wed, Apr 14, 2010 at 9:04 AM, Brent Pedersen <bpederse at gmail.com>
>> wrote:
>>>
>>> On Wed, Apr 14, 2010 at 8:20 AM, Brent Pedersen <bpederse at gmail.com>
>>> wrote:
>>> > hi, in trying to write a func that does a kind of merging of 2 sorted
>>> > lists,
>>> > i've come up with a fairly simple implementation that "almost works":
>>> > http://gist.github.com/365485
>>> >
>>> > but it hits StopIteration before returning the last value ([9], None)
>>> > i can wrap the whole thing in a bunch more if statements, i've tried
>>> > heapq.merge, but cant find a nice solution.
>>> >
>>> > any ideas? i think it's an interesting problem.
>>> > -brent
>>> >
>>>
>>> i should add the for my real use-case, the iterables going in will not
>>> be lists, they'll be lazily generated, and very large, so
>>> i dont want to read them into memory to get the last element or slice
>>> them.
>>> ______________________________
>
>

i'm glad to see you guys are hitting the same problems i did. yours
now works, but try setting bordered = xrange(15)
then it has a problem. but your approach is pretty close, i'll see
where i can get from there.
thanks.


More information about the Baypiggies mailing list