# Search a sequence for its minimum and stop as soon as the lowest possible value is found

Peter Otten __peter__ at web.de
Mon Jan 9 12:30:30 EST 2017

```Antonio Caminero Garcia wrote:

> On Friday, January 6, 2017 at 6:04:33 AM UTC-8, Peter Otten wrote:
>> Example: you are looking for the minimum absolute value in a series of
>> integers. As soon as you encounter the first 0 it's unnecessary extra
>> work to check the remaining values, but the builtin min() will continue.
>>
>> The solution is a minimum function that allows the user to specify a stop
>> value:
>>
>> >>> from itertools import count, chain
>> >>> stopmin(chain(reversed(range(10)), count()), key=abs, stop=0)
>> 0
>>
>> How would you implement stopmin()?
>>
>> Currently I raise an exception in the key function:
>>
>> class Stop(Exception):
>>     pass
>>
>> def stopmin(items, key, stop):
>>     """
>>     >>> def g():
>>     ...     for i in reversed(range(10)):
>>     ...         print(10*i)
>>     ...         yield str(i)
>>     >>> stopmin(g(), key=int, stop=5)
>>     90
>>     80
>>     70
>>     60
>>     50
>>     '5'
>>     """
>>     def key2(value):
>>         result = key(value)
>>         if result <= stop:
>>             raise Stop(value)
>>         return result
>>     try:
>>         return min(items, key=key2)
>>     except Stop as stop:
>>         return stop.args[0]
>
> This is the simplest version I could come up with. I also like the classic
> 100% imperative, but it seems that is not trendy between the solutions
> given :D.
>
> you can test it here https://repl.it/FD5A/0
> source code:
>
> from itertools import accumulate
>
> # stopmin calculates the greatest lower bound (infimum).
> #
>
> def takeuntil(pred, seq):
>   for item in seq:
>     yield item
>     if not pred(item):

The "not": one of those decisions that can drive programmers into madness ;)

>       break
>
> def stopmin(seq, stop=0):
>   drop_ltstop = (item for item in seq if item >= stop)
>   min_gen = (min_ for min_ in accumulate(drop_ltstop, func=min))

You don't need the genexp here; just accumulate() will do.
Using accumulate() is a nice suggestion, by the way.

>   return list(takeuntil(lambda x: x!= stop, min_gen))[-1]

> seq = [1, 4, 7, -8, 0, 7, -8, 9] # 0 just until zero is generated
> seq = [1, 4, 7, -8, 7, -8, 9] # 1 the entire sequence is generated
>
> print(stopmin(seq, stop=0))

Once it passes my doctests your code isn't quite as simple, but still

from itertools import accumulate
from operator import itemgetter
from collections import deque

firstitem = itemgetter(0)

def takeuntil(pred, items):
for item in items:
yield item
if pred(item):
break

def last(items):
tail = deque(items, maxlen=1)
if tail:
return tail.pop()
else:
raise ValueError

def minkey(a, b):
return min(a, b, key=firstitem)

def stopmin(items, *, key, stop):
"""
>>> def g():
...     for i in reversed(range(10)):
...         print(10*i)
...         yield str(i)
>>> stopmin(g(), key=int, stop=5)
90
80
70
60
50
'5'
>>> stopmin(g(), key=int, stop=8.5)
90
80
'8'
>>> stopmin(g(), key=int, stop=9)
90
'9'
>>> stopmin([10, 9, -11, 7, -12], key=abs, stop=0)
7
>>> try: stopmin([], key=abs, stop=0)
... except ValueError: print('OK')
OK
>>> stopmin("a", key=lambda x: print(x) or "c", stop="b")
a
'a'
>>> class A:
...    def __init__(self, key):
...        self.key = key
>>> stopmin([A(2), A(2), A(1), A(0)], key=lambda a: a.key, stop=1.1).key
1
"""
pairs = ((key(item), item) for item in items)
descending_pairs = accumulate(pairs, func=minkey)
return last(takeuntil(lambda p: p[0] <= stop, descending_pairs))[1]

```