sasaharayuugo.net

プログラミングでジュニア算数オリンピック『1997年度トライアル問題1問目』その3

筆者:昨日の続きです(最初)。ゆっくりやっていきたいです。どんな時も少しだけは書きたい。



問題文:
『ぼくのお兄さんは、西暦ABDC年の生れです。
1997年の今年、ぼくのお兄さんの年令は、A+B+C+Dになりました。
ぼくのお兄さんは何才になったのでしょうか。』



昨日は値の答えへの近づき方のルールを探るということで、第一歩という感じでした。

def discoverySameChanged(changedList, ruleList):
        baseList = changedList[:len(changedList)//2]
        otherList = changedList[len(changedList)//2:]

        for i in range(len(otherList)):
            if otherList == baseList[:len(otherList)]:
                return baseList
            else:
                target = otherList.pop(0)
                baseList.append(target)
        
        copyList = baseList.copy()
        ruleList.append(copyList)
        baseList.pop()
        return baseList
    
ruleList = []
    listList = []
    baseList = discoverySameChanged(changedList, ruleList)

    while baseList != []:
        listList.append(baseList)
        baseList = discoverySameChanged(baseList, ruleList)

    printLists(ruleList)
    
2  |2  |2  |2  |
    2  |2  |2  |   |
    2  |2  |2  |   |
    2  |2  |2  |   |
    2  |2  |2  |   |
    2  |2  |2  |   |
    2  |2  |2  |   |
    -7 |-7 |-7 |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    -7 |-7 |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    -7 |-7 |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    -7 |-7 |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    -7 |-7 |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    -7 |-7 |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    -7 |-7 |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    -7 |-7 |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    -7 |-7 |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    2  |2  |   |   |
    -16|-16|   |   |
    2  |   |   |   |
    2  |   |   |   |
    2  |   |   |   |
    (略)
    2  |   |   |   |
    2  |   |   |   |
    2  |   |   |   |
    -25|   |   |   |

 


結局このアルゴリズム(まあ定義的にアルゴリズムだと思います)は、どこかで周期が合うはずだ、という仮説を元に作られていて、でまあ今回は一応機能しているわけですが、例えばリストの最初の方に「-16」だとか、リストの一番最初に「-7」だとかが来ると、おそらく一気に苦しくなる(「-7」は一度周期に合えば何とかなるか?)。
otherListの一番末端である先っぽの方はしっかり切り落とす操作があって何とかなるのだけど、baseListの根本の方をどのタイミングで切り落として、それから仕切りなおすか、あるいはそのまま継続してruleListに入れていくか。
仕組みというか発想は簡単だし、根本の方を切り落としてその後どうするかみたいなのもそんなに難しい話じゃないはずなのだけど、これで良いのかと何となく考えてしまっている。



例えば周期を持ったリストでも、こういう風なパターンがあり得る。
A「1111211112111131111211112」→[111121111211113]→[11112] わりかしオーソドックス
B「111121111211112111121」→[11112] 一番根本と同じで、根本はその後連続している可能性があるから当てにならないが、しかし他を見ると確かにパターン。
C「121111311112」→[1211113]→[12] 
D「11113111121111211112」→[同じパターンがそのまま検出]→[111131111211112]→[1111311112]→[11113]
E「2111131111」 これはもう全部引っかかる。
F(おまけ)「111121111211111111112」



「検出されたオリジナルなパターン - 検出されたオリジナルなパターン = オリジナルなパターン?」という具合で、例えば一番小さな根本のパターンをその次のパターンから引いて、更に同じように検出すれば、例えばその次の一番根本のパターンは中途半端じゃないのでしっかり使えるはずで、もしかしたらBにも対応できるかもしれない。
しかしそもそも一番根本のパターンは、最初の連続する数字とその次の1つの数字でしか無いはずで、何かそもそも本当にこの仕組みで良いのだろうか?



まあこのルールつまり動きにおける同一性を検出するというのは、そもそもかなり主要なテーマなはずで、ゆっくり消化すれば良いし、別に駄目なら後回しにして次の問題に進んでも良い。パターン認識はともかく、基本的には必要条件を見切るだとか、小学生の思考を再現するだとかぐらいなはずで、焦る必要も気負う必要も無い。
例外処理を後に回して、前回のruleListを活かしてそのまま考えても良いかもしれない。ここまで良い結果が出ているのだから、基本的な所を作って、それから例外を考えたほうが、むしろ分かりやすくなるかもしれない。



追記:これも書いたほうが良いかもしれない。検出されたパターンから検出されたパターンを引いて差分を見つけ出すという戦略は、A・一番小さな(1文字じゃない)パターンをその次に小さいパターンから引く、B・一番大きなパターンからその次に大きいパターンを引く、C・全部でやる、D・無加工な大元から一番小さなのを引く、というのをとりあえず今は思いついている。でも例えば定期的に「み、か、ん」というのがリストに混入していたらどうしよう、それを考えるとCしか無いような気もする。分からん、ちょっとしたパニックだ。