僕のコードにはフローチャートが書けない

NBUゆるゆるかれんだー Advent Calendar 2021 https://adventar.org/calendars/6491

9日目の記事

昨今の私はプログラム系の担当科目も外れて、ゲームプログラミング担当というものの殆どUnity入門講座でC#は少しだけだし、メディアアートはMax8やTouchDesignerでノード型、アルゴリズムの解説はSNAP!でブロックプログラミングとテキストのコードを書く機会がめっきり減った。

ゼミでは流行りの機械学習でPythonを使う機会も有るが既存のライブラリをpipしてコードを切り貼りして書いているだけ。

たまには1からコードを書いてみようとPythonの勉強も兼ねてTwitterで見かけた問題を解いてみた。

問題:

1)も2)も即答かなと思ったけど、なんと1)にはリプライで別解が54個あると指摘されていて驚く。

別解をロジカルに導こうとしたけど思い浮かばなかったのでコードで検索することにした。

ちなみに54個の別解を指摘した人もコードで検索してた。

実行環境:

ideone(あいでぃいーわん。イデオンではないらしい。)上のPython3

https://ideone.com/ オンラインで幾つかのプログラム言語をコンパイル&実行&コード共有ができるサービス。

同様のサービスに、codepad.org、repl.it、paiza.ioなど。JavaScriptなら CodePenなど。

問題を解いている様子の実況Tweet

Ver.1

[1,2,3,4,5,6,7]を用意するのに range(1,8)は嫌な書き方だなとか、リスト内包表記で初期化はなんかダサいなとか思いながら

[1,2,3,4,5,6,7,8,9]も同様に用意する。

[7,6,5,4,3,2,1]に逆順に並べ替え、ちょっとした効率化を図る。分子の大きな数から足していく方が目標値の7を早く超えて検索を打ち切れるので(大した効果はない)。

解の個数をカウントするのに変数 i を用意して初期化。

1~9から7個取り出す順列組み合わせを作るのは面倒だしどうせやることは同じなのでitertoolsパッケージのpermutationsを使う。楽ちん。

1/a + 2/b + 3/c + 4/d + 5/e + 6/f + 7/g を計算するために(1,a)~(7,g)の組のリストを作るのは

[1,2,3,4,5,6,7] と [a,b,c,d,e,f,g] をzip すればいい。

(分子,分母)のリストを合計して  7 に一致するか判定する。集計中に7を超えたら集計のforループは打ち切る。

7個目の分数まで合計して結果が7に一致するかチェックして番号を付けて出力。


結果 44 個

計算誤差を考慮していなかったので、10個も別解を見落とした。

Ver.2

誤差の許容範囲を色々変えて試す。


7±0.0004以内に収まるという条件は十分正確そうに見える。

しかし、出力は 65個で 11個も 0.0004の誤差に収まる誤答が含まれていた。

結果参照:https://ideone.com/oTvU30


誤差を±0.0001以内に絞ったら、54個の回答に辿り着いた。

結果参照:https://ideone.com/JWjypu

計算打ち切り無くしてコードシンプルにしたVer.

分数型で計算したら計算誤差考えなくていいよねVer.

分数型は分子分母の組(既約分数)で数を扱い、四則演算は通分して計算します。よって誤差は分子分母が整数に収まる範囲(通分の過程でオーバーフローしそう)であれば発生しない※。
※fractionsパッケージのコードやリファレンス見てないのではっきりしたことは分からず。Lispとかなら多倍長整数でやるので誤差無しなんだけど。

fractionsパッケージをインポートして、 x/yを計算するところを Fraction(x,y)に置き換えるだけ。

Fractionクラスのオブジェクトに対する演算は自動的にFractionに対する演算で処理される。ので、sumするだけ。

*でイテレータからリスト展開したら内包表記による初期化要らないよねVer.

横に長くなり始めます。

番号付け処理は連番のリストとZIPしたリストでやるんだけど専用のenumerateがあるから使えばいいよねVer.

enumerateの初期値は分かりにくいところに書くことになるね。処理を一時変数に置けばいいんだけど。

解のリストを改行して表示するのにfor使わずにリストを文字列化して改行で区切って出力してprint1行のコードにしてインポートした関数の名前を付け替えて短くしたけどやっぱり横に長いよねVer.

ついにimportを除けば1行になった。

pprintパッケージ使えばリストを整列して表示できるし解の検索と出力は分けて書いた方が見やすいよねVer.

まとめ

何某「Python知ってる?」

僕「知らないですね。」

2023.3.17追記

filter map lambda enumerare で書いてみたけど長くなった。

リスト内包表記に戻した。