Feed Pigeons (Check iO > Home)

どんな問題？

この問題はかなり手間取った。鳩にエサをやる問題なんだが、なかなか状況を理解できなかった。
まず鳩について。最初(1st minute)は鳩が1匹いる。1分後(2nd minute)には新たに2匹がやってきて合計3匹になる。さらに1分後(3rd minute)には新たに3匹がやってきて合計6匹になる。以後繰り返し。
ここで鳩にエサをやるわけだが、鳩1匹は毎分1個エサを食べる。鳩の数よりエサの数が少なければ、早くきた鳩が優先的にエサを食べる。
例えば、3rd minuteにエサが3つしか無ければ、最初の1匹と2nd minuteにきた2匹がエサを食べるので、3rd minuteに新たにきた3匹はエサを食べられない、ということ。

さて、エサの数がN個のとき、エサを食べることのできる鳩は何匹でしょうか？という問題。ただし、N<100000 とする。

どうやって解く？

うーん、何から手を付けていいか分からない。

とりあえず、m分後の鳩の数を求めることから始めよう。
m=1 なら 1
m=2 なら 1+2 = 3
m=3 なら 1+2+3 = 6

return sum(i for i in range(1, m + 1))

となると、m分後に必要なトータルのエサの数は、
m=1 なら 1
m=2 なら 1+(1+2) = 4
m=3 なら 1+(1+2)+(1+2+3) = 10

return sum(sum(i for i in range(1, n + 1)) for n in range(1, m + 1))

これで、何分後にエサが無くなるかはわかりそうだ。
・・・いや待てよ、「早くきた鳩が優先的にエサを食べる」のあたりは、どうやって処理するんだ？
この方針ではダメな気がしてきた。

毎分エサやりを繰り返すんだから、1分ごとにループさせるべきだろう。
先に古い鳩がエサを食べて、その後に新しい鳩が食べる。エサが無くなったら、その時点でエサを食べた鳩の数を返す。こんな感じでコードを書いてみた。

def checkio(portions):
    fed_pigeons = 0  # エサを食べた鳩の数
    minute = 1
    while True:
        for i in range(fed_pigeons):  # 古い鳩にエサやり
            portions -= 1
            if portions <= 0: 
                return fed_pigeons
        for i in range(minute):  # 新しい鳩にエサやり
            portions -= 1
            fed_pigeons += 1  # エサを食べた鳩をカウント
            if portions <= 0: 
                return fed_pigeons
        minute += 1

おっ、クリアできたぞ。（実際には、あーでもない、こーでもないと、かなり時間がかかってしまった。）
ただ、エサやり部分（portions -= 1 と if porttions <= 0 のあたり）が重複しているのがかっこわるいし、個人的に while True: の無限ループは嫌いだ。

エサやり部分を 関数内の関数(feed)にまとめてみた。

def checkio(portions):
    def feed():
        nonlocal portions
        portions -= 1
        return portions <= 0

    fed_pigeons = 0
    minute = 1
    while True:
        for i in range(fed_pigeons):
            if feed():
                return fed_pigeons
        for i in range(minute):
            fed_pigeons += 1
            if feed():
                return fed_pigeons
        minute += 1
    return fed_pigeons

まず、feed内からは、直接portsion変数を変更できないようだ。こういうときは nonlocal を付けるといいようだ。
そして、エサが無くなったらfeed()でTrueを返す。戻り値がTrueならcheckio()がfed_pigeonsを返す、という2段階処理になった。feed()から、直接メインに return fed_pigeons することはできないんだろうか？
いずれにしても、さっきよりもわかりにくくなってしまった。

考え方を変えて、鳩自体に古い鳩か新しい鳩かのフラグを持たせることにした。鳩クラスを作るほどではないので、単純にboolのリストとする。Falseなら古い鳩、Trueなら新しい鳩である。

def checkio(portions):
    fed_pigeons = 0
    minute = 1
    while True:
        pigeons = [False] * fed_pigeons + [True] * minute
        for p in pigeons:
            if p:
                fed_pigeons += 1
            portions -= 1
            if portions <= 0:
                return fed_pigeons
        minute += 1

おっ、なんか良い感じじゃね？
古い鳩と新しい鳩を1つのリストにまとめることで、エサやり処理を1カ所にまとめることができた。

で、やっぱり while True: があまり好きじゃないので、for ループにしてみた。

def checkio(portions):
    fed_pigeons = 0
    for minute in range(1, 1000):
        pigeons = [False] * fed_pigeons + [True] * minute
        for p in pigeons:
            if p:
                fed_pigeons += 1
            portions -= 1
            if portions <= 0:
                return fed_pigeons
    return fed_pigeons

うーん、エサは最大100,000なので、1000ループもいらないだろうということで、range(1, 1000)としたが、あまりスマートではないな。
もし、クライアントが「あれ、エサは1,000,000って言ってなかったけ？言ったよね。あ、納期明日なんでヨロシク」って言いだしたら困るし。さっきのwhile True: の方がよかったかな。
というか、1から無限に数を返すrangeって無かったっけ？

ググったら、

import sys

for i in range(1, sys.maxsize):
    pass

でいいみたい。それか、自作してもいい。

def range_inf(start=0):
    i = start
    while True:
        yield i
        i += 1

for i in range_inf(1):
    pass

ちなみに、100,000個のエサをやると、83分後になくなるようだ。（だから、ループは range(1, 100) で十分だったことになる。）
エサにありついた鳩は3486匹、なんて近所迷惑な・・・。

他の人の答え（追記）

あまりに手こずったので、他の人の解答を見るのを忘れていた。
みんな、私の答えよりも、はるかにシンプルに解いている。

def checkio(number):
    birds = mins = 0
    while number > birds:
        mins += 1
        birds += min(mins, number - birds)
        number -= birds
    return birds

http://www.checkio.org/mission/feed-pigeons/publications/shreekar/python-3/feeding-pegions/

これなんてシンプル＆わかりやすい。特にこの1行。

birds += min(mins, number - birds)

mins=新しく来た鳩、number=残りのエサ、birds=古くからの鳩
ということだから、number - birds=新しく来てエサを食べた鳩　となる。
エサが無くなったらループを抜けて終了。
すばらしい。