[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