python リファクタリングをお願いします。

Question

water1 = 100
water2 = 150

limit = 300  #水が入る容量

count = 0
judge1, judge2 = False, False

l = [0]
while 1:
    if (l[count] + water1) <= 300:
        l.append(l[count] + water1)
    else:
        judge1 = True

    if (l[count] + water2) <= 300:
        l.append(l[count] + water2)
    else:
        judge2 = True

    if judge1 and judge2:
        break
    else:
        count += 1

del l[0]
print(sorted(set(l)))

結果

[100, 150, 200, 250, 300]

上のコードは水が300[ml]入る容器にwater1[ml]とwater2[ml]を入れていき、水の容量をできるだけ細かく刻んで入れた場合の総数を求めるコードです。
例えば、最初は300[ml]の容量のコップは水が入っていないので、0[ml]です。次にwater1の容器で100[ml]コップに移すのでコップには100[ml]の水が入ります。これがパターン１です。
次に、コップを空にして、water2の容器で150[ml]の水をコップに入れるとコップの水は150mlになります。これがパターン２です。
パターン３はwater1の容器を使い100[ml]を2回注いで200[ml]にないます。これを300[ml]からこぼれないように繰り返した時、できるだけ多くのパターンをつくり、その時のコップの中身を出力します。

もっとスッキリまとまる気がするのですが、リファクタリングするとしたらどのようになるでしょうか？
よろしくお願いいたします。

Comments

[toast-uz]

学校の課題か何かでしょうか？少し不自然な質問に感じました。
「学校の課題を解いてほしい等の質問は、具体的にプログラミングで困っている質問ではないと考え、推奨していません。」by teratail

[sfdust]

基本的なところについて質問します。

「水の容量をできるだけ細かく刻んで入れた場合の総数を求めるコードです。」という問題なのに、答えが質問文に記載されているようになる意味が分かりません。
「できるだけ」「細かく刻んで」という文面を素直にとらえるならば、「与えられた２つのコップのいずれかまたは両方を使って、そのコップに満杯の水を入れ、与えられた容器に、容器の総計量（問題文の場合は３００ミリリットル）まで水を注ぐとき（コップを容器に注ぐときに「１回」とする）、なるべくその回数が多くなるようにせよ」というような意味になるのではないでしょうか。
この場合、答えとしては「water1 = 100　を３回使う」すなわち、「３」または[100,100,100]となるのではないでしょうか？

一方、もし「[100, 150, 200, 250, 300]」という答えがあっているならば、問題文は「与えられた容量の異なる２つのコップがある。このコップにそれぞれ満杯に水をいれ、与えられた容器が満杯になるまで注いでいった場合の各回における容器に入っている水の容量のパターンをすべて列挙せよ。ただし、何も注がない（０ミリリットル）パターンは答えから除外する」というような問題となるはずです。

そもそも、質問者さんは問題をきちんと理解しているのでしょうか？
質問文に書かれた答えは、あっているのでしょうか？

[hentaiman]

「リファクタリング」は金を出せばクラウドソーシングでアルバイトしている質問者よりも（恐らくちょっと上）初心者がやってくれると思いますよ。探してみては？

[hogeee]

まず、皆様に誤解を与えるような質問を投稿してしまい大変申し訳ございませんでした。
初めに断っておきますと学校の課題ではありません。
もともとこれは、Atcoderというサイトの問題を細かく考えようとして作り出した私のオリジナルです。

https://atcoder.jp/contests/abc074/tasks/arc083_a?lang=ja
↑元の問題

上の問題がレベルの低い私にとって難しく、一筋縄ではいかなかったので、write upを探しました。

https://scrapbox.io/pocala-kyopro/C_-_Sugar_Water
↑その時読んだ記事

上の記事を読んで、「水を先に全部作るプログラミング」ってどうやって書くんだろう。と思い、試行錯誤しながら一生懸命つくりました。でも、自分のコードに自信がないので、「もっと綺麗に書けるのでは？」と思いました。しかし、私は学生でもないですし、職業もプログラマーとまったく関係ありません。身の回りにプログラマーは一人もいません。なので、私よりもたくさん優れたプログラマーがたくさんいるteratailに質問してみれば何かヒントを得られるかもしれない。ということで、作ったコードを質問しました。
学生が課題を面倒くさがって、teratailに問題を丸投げしているならそれは怠惰であり、プログラマーとして成長しにくいと思います。
しかし、私は自分のコードをより良くしたい、私はこのアプローチで問題に取り組んでみたけど、もっと違うの視点からの良いアプローチがあるのではないか、という動機で質問させていただきました。

[toast-uz]

hogeee様、状況理解しました。そのような背景を記述いただくと、ありがたいです。

Answer 1

tiitoi さんの find_pattern の引数 water は不要に見えますね。
重箱の隅をつつくような話で恐縮ですが、リファクタリングの質問なので良いと思うコードを提示しておきます。

def find_pattern(waters, limit, lst=None, ptns=None):
    """waters: 追加可能な水の容量の種類
       limit: 容量の上限
       lst: 入れた水の履歴
       ptns: パターン記録用
    """
    if not lst: lst=[]
    if not ptns: ptns = set()
    if sum(lst) > limit:
        # 上限を超えた場合は再帰関数を終了する。
        return ptns
    else:
        ptns.add(tuple(lst))
    for water in waters:
        find_pattern(waters, limit, lst + [water], ptns)
    return ptns


waters = [100, 150]  # 追加可能な水の容量の種類
limit = 300  # 容量の上限
patterns = find_pattern(waters, limit)
print(set(sum(x) for x in patterns))  # {0, 100, 200, 300, 150, 250}

waters = [100, 180]  # 追加可能な水の容量の種類
patterns = find_pattern(waters, limit)
print(set(sum(x) for x in patterns))  # {0, 100, 200, 300, 180, 280}

Comments

[hogeee]

特定の処理は関数にまとめる癖を私はつけた方が良さそうです。やっぱり出来る人がリファクタリングするとすごくカッコイイコードになりますね！私は読むだけで精一杯でこのレベルで実装出来るようになるにはとても努力しなくてはいけないと思いました。
ありがとうございます！

[hentaiman]

> 特定の処理は関数にまとめる癖を私はつけた方が良さそうです
いや、それはプログラムを作っていれば自然と身に付くものです。
具体的には、同じ処理を何度も書いている、似たような処理を何度も書いているなど、冗長で面倒臭さいとか読みにくいとかが理由となって改善した結果です。
なので、まとめる事を目的にしてしまっては無駄に処理が分散するなどして可読性の低下にもつながるので、まずは不便に感じるまでは冗長に書く事を薦めます。慣れて勘所が分かれば最初から関数化クラス化してもいいでしょうが。

[tiitoi]

To: lehshell さん

> tiitoi さんの find_pattern の引数 water は不要に見えますね。

コメントありがとうございます。修正途中のコードが残っていたので修正しました。
また、lehshell さんのコードはパターン記録用の変数もグローバル変数でなくなるので、関数の副作用がなくなってよいですね。参考になります。

[hogeee]

変態マンさん。
なるほど、確かに目的になってしまってはだめですよね。私は繰り返し処理をfor文とwhile文でやっつけてしまう癖があるので、再帰をマスターするためになるべく再帰処理が使えそうなところは再帰処理を実装してみようと思います。
ところで、再帰処理をしようと思ったら必ず関数を使用するという認識で大丈夫すかね？

[hentaiman]

そうね
再帰の学習が目的ならついでに末尾再帰でも調べておくといいと思いますよ

> for文とwhile文でやっつけてしまう癖があるので
勉強目的なので再帰優先で問題無いですが、実用するなら再帰使わずに済ませる方法が優先です

[hogeee]

末尾再帰について少し調べてみましたが、スタックオーバーフローを回避するための処理？で結構奥が深そうですね！

実用では再帰は極力使わないほうがいいんですね！おそらくメモリを使いすぎてスタックオーバーフローにならないように、ということですよね。
ありがとうございました！

Answer 2

バックトラッキング法 を再帰関数で実装して解けばいいと思います。

水を再帰的に追加していき、総容量が上限を超えたら再帰関数を終了します。
以下のようにすれば、入れられる水の種類が増えても対応できます。

waters = [100, 150]  # 入れられる水の容量
limit = 300  # 容量の上限
patterns = []  # パターン記録用


def find_pattern(lst=tuple()):
    """lst: 入れた水の履歴
    """
    if sum(lst) > limit:
        return  # 上限を超えた場合は再帰を終了する。

    patterns.append(lst)

    for water in waters:
        find_pattern(lst + (water,))


find_pattern()

print(patterns)  # 手順のパターン
# {(150,), (150, 100), (100, 100), (100, 150), (100,), (150, 150), (100, 100, 100), ()}
print(set(sum(x) for x in patterns))  # 容量のパターン
# {0, 100, 200, 300, 150, 250}

不要な処理を削りました。

Comments

[hogeee]

バックトラキング法というのを知らなかったので、調べていこうと思います。
コードも私のコードとは違う方法でアプローチ？されていますし、洗練されていて勉強になります。
ありがとうございました！

[tiitoi]

バックトラッキング法という名前での解説記事はあまりありませんが、ベースとなるのは「深さ優先探索」です。こちらのキーワードで調べたほうが情報が得られるかもしれません。
例えば、オセロや将棋ゲームのAIをつくるときに将来の指し手を列挙するのに使われます。

[hogeee]

調べたらバックトラック法というのは深さ優先探索だと解説が載っていました。深さ優先探索と幅優先探索は参考書で勉強したのですがこういう時に使うのですね！
なかなか意識していないと冗長的なコードを書いてしまうと思いますが、早く再帰をマスターしたいです。頑張ります。将棋作ってみたいです！ありがとうございます！