ターゲット

• paizaでタイトルの事象に遭遇した人

事象

paizaのスキルチェックのとあるBランク問題で、入力例にすべて成功するがテストケースですべて失敗する事象に遭遇しました。使用した言語はPythonです。

試したこと

paiza では問題に回答してもテストケースの内容は明かされないため、自力で失敗するテストケースを探す必要があります。
可能性0%とは言いませんが、入力例がすべて成功しているのにテストケースはすべて失敗するのはロジック以外の何かがおかしいと踏んで、paizaが公開している情報をもとに言語のバージョン、実行時間、メモリ使用量を調べましたが問題ありませんでした。

参考：

別のロジックを同じくPythonで書いたコードや、同じロジックをJavaScriptで書き直したコードはテストケースまですべて成功しました。結果をよく見ると「ランタイムエラーです」と表示されているので、出力値が間違っているのではなく処理途中でエラーになっていることが伺えます。

他のコードなら動くのに、当該のコードだけすべて失敗するため、さすがに入力例とテストケースになんらかの環境差異があるのか疑いました。 paiza に問い合わせてみましたが、当然ながら、個別の問題についての回答はできない旨の返答がありました。

原因

結論、Pythonのデフォルトの制限回数を超えて再帰的な処理を行っていたのが原因でした。

該当部分を抽象化したコードが下記です。(問題の答えは貼れないので)

class Controller
    ...
    def invoke(self):
        self.process()
        if self.is_finished():
            self.print_result()
        else:
            self.invoke()
    ...

Controller.invoke()

環境にもよりますが、Pythonは再帰回数をデフォルトで1000回に制限しています。
入力例では数回程度の再帰的な処理で済みましたが、テストケースでは再帰的な処理が1000回を超えるためエラーで落ちていました。

入力例の環境でいろいろ調べてたときに表示されたエラーメッセージ

RecursionError: maximum recursion depth exceeded in comparison

参考：

同じロジックでJavaScriptで動いたが、Pythonで動かなかった原因はこの再帰的な処理の上限回数の違いによるものでした。JavaScriptの再帰的な処理の上限回数は環境によりますが、原因を調べているときにタイムアウトを仕込んだりしていたので、推測するに paiza の環境では10,000回以上は再帰的な処理ができると思われます。

解決策

上記の stack overflow では

Python isn't a functional language and tail recursion is not a particularly efficient technique. Rewriting the algorithm iteratively, if possible, is generally a better idea.

とあり、解決策は以下の２つです。
① 再帰回数の上限を上げる（非推奨）
② ループで書き直す
ただし、①はスタック領域を使い潰して落ちるのを防ぐためにある制限なので、外さないほうが無難です。

① 再帰回数の上限を上げる（非推奨）

import sys

# 変更前の上限
print(sys.getrecursionlimit())
# 再帰処理の最大回数より大きい値で上限を再設定
# 厳密には回数ではなく、呼び出しの深さのようなので +α 設定した方が良さそうです
sys.setrecursionlimit(1500 + α)

② ループで書き直す

class Controller
    ...
    def invoke(self):
        while(not self.is_finished()):
            self.process()
        self.print_result()
    ...

Controller.invoke()

原因の調べ方

備忘録も兼ねて、どのように原因を調べたか残しておきます。
今回はランタイムエラーになっていてかつ繰り返し処理されるコードであったため、下記のスリープを仕込むことで原因の行を特定しました。

仕込んだタイムアウト

import time

time.sleep(1)

スリープを仕込む場所によって、実行時間が変わってきます。
正常に動いていれば繰り返しの回数が16回程度になった段階で、実行時間切れのエラーになります。
可能であるならば、コメントアウトで範囲を狭めながら特定しても問題ありません。

学び

• Pythonでは再帰的な処理は最適化されていないため、ループ処理で実装する
• 各言語に再帰的な処理の上限回数があるので、把握していないとある日唐突にエラーになる可能性がある

引用 / 参考

引用
1. What is the maximum recursion depth in Python, and how to increase it?

参考
1. POH! 各言語のバージョン、環境情報
2. オブジェクトの総メモリ使用量をざっくり見積もる
→メモリ使用量を調べるのに使う関数が載っています。
3. Pythonの再帰回数の上限を確認・変更（sys.setrecursionlimitなど）