93139


## 実行環境

  * Python 3.10.8
  * PyPy 7.3.11 with MSC v.1929 64 bit (AMD64)

## 質問

[AtCoder Beginner Contest 236
のD問題](https://atcoder.jp/contests/abc236/tasks/abc236_d)に回答している際に，同じスクリプト・標準入力に対してPyPyとPythonで標準出力が異なるという現象に遭遇しました．

PyPyでは再帰が途中で終了しており，これはPythonのような意図する動作ではありません．

これは仕様ですか．またPyPyでPythonと同じような出力を得るために，何をすべきですか．

## 問題のスクリプト

[code]

    # script.py
    
    import operator
    import functools
    
    # input -----
    
    n = int(input())
    a = [[0] * n * 2 for _ in range(n * 2)]
    
    for i in range(2 * n - 1):
        for j, e in enumerate(map(int, input().split()), i + 1):
            a[i][j] = a[j][i] = e
    
    # -----------
    
    
    def rec(i):
        global ans
    
        if not __debug__:
            print(f"called rec({i = })\n  {pairs = }\n  {not_selected = }\n  {ans = }\n")
    
        if i == 2 * n:
            ans = max(
                ans,
                functools.reduce(
                    operator.xor,
                    (a[e1 - 1][e2 - 1] for e1, e2 in zip(*[iter(pairs)] * 2)),
                    0,
                ),
            )
            return
    
        if i % 2 == 0:
            e = min(not_selected)
            pairs.append(e)
            not_selected.discard(e)
            rec(i + 1)
            pairs.pop()
            not_selected.add(e)
        else:
            for e in not_selected:
                pairs.append(e)
                not_selected.discard(e)
                rec(i + 1)
                pairs.pop()
                not_selected.add(e)
    
    
    pairs = []
    not_selected = set(range(2 * n))
    ans = 0
    
    rec(0)
    print(ans)
    
    
[/code]

## 標準入力

[code]

    2
    4 0 1
    5 3
    2
    
[/code]

## Pythonでの実行結果

[code]

    $ python -O script.py
    
     ~ console input ~
    
    called rec(i = 0)
      pairs = []
      not_selected = {0, 1, 2, 3}
      ans = 0
    
    called rec(i = 1)
      pairs = [0]
      not_selected = {1, 2, 3}
      ans = 0
    
    called rec(i = 2)
      pairs = [0, 1]
      not_selected = {2, 3}
      ans = 0
    
    called rec(i = 3)
      pairs = [0, 1, 2]
      not_selected = {3}
      ans = 0
    
    called rec(i = 4)
      pairs = [0, 1, 2, 3]
      not_selected = set()
      ans = 0
    
    called rec(i = 2)
      pairs = [0, 2]
      not_selected = {1, 3}
      ans = 4
    
    called rec(i = 3)
      pairs = [0, 2, 1]
      not_selected = {3}
      ans = 4
    
    called rec(i = 4)
      pairs = [0, 2, 1, 3]
      not_selected = set()
      ans = 4
    
    called rec(i = 2)
      pairs = [0, 3]
      not_selected = {1, 2}
      ans = 4
    
    called rec(i = 3)
      pairs = [0, 3, 1]
      not_selected = {2}
      ans = 4
    
    called rec(i = 4)
      pairs = [0, 3, 1, 2]
      not_selected = set()
      ans = 4
    
    called rec(i = 2)
      pairs = [0, 2]
      not_selected = {1, 3}
      ans = 6
    
    called rec(i = 3)
      pairs = [0, 2, 1]
      not_selected = {3}
      ans = 6
    
    called rec(i = 4)
      pairs = [0, 2, 1, 3]
      not_selected = set()
      ans = 6
    
    called rec(i = 2)
      pairs = [0, 3]
      not_selected = {2, 1}
      ans = 6
    
    called rec(i = 3)
      pairs = [0, 3, 1]
      not_selected = {2}
      ans = 6
    
    called rec(i = 4)
      pairs = [0, 3, 1, 2]
      not_selected = set()
      ans = 6
    
    called rec(i = 4)
      pairs = [0, 3, 1, 2]
      not_selected = set()
      ans = 6
    
    6
    
[/code]

## PyPyでの実行結果

[code]

    $ pypy -O test.py
    
     ~ console input ~
    
    called rec(i = 0)
      pairs = []
      not_selected = {0, 1, 2, 3}
      ans = 0
    
    called rec(i = 1)
      pairs = [0]
      not_selected = {1, 2, 3}
      ans = 0
    
    called rec(i = 2)
      pairs = [0, 1]
      not_selected = {2, 3}
      ans = 0
    
    called rec(i = 3)
      pairs = [0, 1, 2]
      not_selected = {3}
      ans = 0
    
    called rec(i = 4)
      pairs = [0, 1, 2, 3]
      not_selected = set()
      ans = 0
    
    4
    
    
[/code]


CC BY-SA 4.0
2023-01-01T06:54:33.157
93137
2023-01-01T10:44:19.413
2023-01-01T07:22:13.197
51374
51374
question
python python3
PyPyの再帰関数の仕様はPythonのものと異なるか

[code]

            for e in not_selected:
    
[/code]

`not_selected`の要素についてループしている最中に、`not_selected`を書き換えているのが原因です。  
書き換える予定のコンテナは、以下のように、いったんコピーを取ってからループに使用するようにしましょう。

[code]

            for e in tuple(not_selected):
    
[/code]

(修正後の実行結果と比較すると分かりますが、実はPythonでの実行結果も、`pairs = [0, 2]`が2回現れるなど異常な動作をしています)


CC BY-SA 4.0
2023-01-01T10:33:26.450
93139
2023-01-01T10:44:19.413
2023-01-01T10:44:19.413
43506
43506
93137
answer