Python インタラクティブ問題のデバッグプログラム







# はじめに

競技プログラミングでは「インタラクティブ問題」という、ジャッジとの対話形式の問題が存在します。  
この形式はローカルテストがしにくくデバッグが難航しがちだったので、デバッグ補助プログラムを書いてみました。  

# しくみ

`yield`関数を使ってジャッジプログラムを書き、`next()`で値を取り出します。  
さらに`input()`と`print()`の関数名を上書きすることで、答案の出力先を強引にジャッジとの対話に向かわせます。  

# コード全文

コメントは適宜削除してください。  

~~~python: デバッグプログラム
#インタラクティブ ローカルテスト
'''
【使い方】
答案・ジャッジプログラムを書き、実行テストの関数に渡してください。
直前の入出力ログは get_log() で出力できます。

【注意点】
・input, print関数を書き換えます。
  本提出時はコメントアウトするか、 del input, print で初期状態に戻してください。
・ジャッジにはテストケースを受け取る機能か、自動生成する機能をつけてください。
・答案 → ジャッジ の入力は judge_input というリストに一時保存されています。
  [0, 1, 2, ･･･]の順で、(前回のyield ～ 今)の答案からの出力が保存されています。
  yieldで答案に出力するたび、 judge_input の中身を空にするので注意してください。
・答案 ← ジャッジ の出力は yield (出力したい値) としてください。
  出力値はstr型が望ましいです。 一応自動str変換機能はつけていますが、気休めです。
・ジャッジはassert文でWAの判定を行ってください。
  AC判定を終えた場合、returnでジャッジプログラムを終了してください。

【内部仕様】
・_judge_program_funcにジャッジプログラムを入れ、next関数で出力を順に取り出します。
・入出力ログは judge_log に保存されます。
  答案 ← ジャッジ の出力は末尾に <judge> がついています。
・テストケースの情報(隠された文字列)は各自で確認してください。
・_judge_textは print( end = ) に対応するための仮保存スペースです。
  改行文字が来るまで文字列を結合し、改行が来たら judge_input にappendします。
'''

#内部関数
judge_input, judge_log, _judge_text = [], [], []
_exec_print = print
def print(*value, sep = ' ', end = '\n', file = None, flush = False):  #答案 → ジャッジ
    global judge_input, judge_log, _judge_program_func, _judge_text
    value = sep.join([ str(Vi) for Vi in value ])  #*value(tuple型)をアンパッキング
    _judge_text.append(value)
    if end == '\n':  #改行文字が来た場合、ここまでの文字列を judge_input と _log に送信
        judge_input.append( txt := ''.join( _judge_text ) )
        judge_log.append( txt )
        _judge_text.clear()
    else:
        _judge_text.append( end )

def input():  #答案 ← ジャッジ
    global judge_input, judge_log, _judge_program_func
    if type( value := next( _judge_program_func ) ) != str:  #入力をstrに変換
        if type(value) == list or type(value) == tuple:
            value = ' '.join([str(Vi) for Vi in value])
        else: value = str(value)
    judge_input.clear()  #ジャッジへの入力履歴を初期化
    judge_log.append( f'{value} <judge>' )
    return value


#実行テスト1. 連続テスト
def test_program( solve_program, judge_program, test_time = 1000 ):
    '''
    ジャッジが自力でランダムテストを生成できることを前提に、連続テストを行います。
    (答案プログラム, ジャッジプログラム, テスト回数)を入力してください。
    '''
    global judge_input, judge_log, _judge_program_func

    for counter in range(1, test_time + 1):
        #ジャッジログ・ジャッジ入力履歴を初期化
        judge_log.clear()
        judge_input.clear()

        #ジャッジプログラムを登録し実行
        _judge_program_func = judge_program()
        solve_program()
        try: next( _judge_program_func )
        except StopIteration: continue

#実行テスト2. 特定ケースでのチャレンジ
#関数後半にはジャッジに渡したいテストケースを入力してください
def test_corner( solve_program, judge_program, *value ):
    '''
    ジャッジプログラムがテストケース用の引数を受け取れることを前提とします。
    ジャッジプログラムの引数を順に *value に入力してください。
    たとえば judge(N: int, array: list) と N, array の順に引数指定がなされている場合、
    test_corner( solve_program, judge, 3, [3, 1, 4] ) のように順に渡してください。
    '''
    global judge_input, judge_log, _judge_program_func
    judge_log.clear()
    judge_input.clear()
    _judge_program_func = judge_program( *value )
    solve_program()
    try: next( _judge_program_func )
    except StopIteration: pass

#ジャッジ入出力ログを順に出力
def get_log(): _exec_print(*judge_log, sep = '\n')

'''
ここからジャッジプログラムを書いてください。
ジャッジへの入力はjudge_input(list型)に、出力はyieldでお願いします。
プログラム終了前にAC判定をお願いします。WAの判定にはassertが便利です。
'''

~~~


# 使い方

ローカルテストの下に答案とジャッジプログラムを書き、実行テストの関数に入れてください。  
答案プログラムは関数化し、`exit()`を使わないようにしてください。    
ジャッジプログラムは以下の形式に則って書いてください。  

- 答案 → ジャッジ の入力  
`judge_input`のリストから順に文字列を受け取ってください。  
- 答案 ← ジャッジ の出力
`yield (出力したい文字列)`としてください。
- ジャッジ機能
WAの検知は`assert`文で行ってください。
ACの判定を終えたら`return`でジャッジプログラムを終了してください。


# 使用例

### 自作問題

> ジャッジは長さ$N$の整数列$A = [A_1, ･･･, A_N]$を隠し持っています。  
> $N$回以下の質問で、隠し持っている整数列$A$の全要素を特定してください。  
>
> はじめに、ジャッジは$N$を出力します。  
> 次に、以下の形式で$N$回以下の質問を行ってください。  
>   `? i`: $A_i$($1 \leq i \leq N$)の値を尋ねる。ジャッジは$A_i$を返す。
> 最後に、`! A_1 ･･･ A_N`の形式で回答し、プログラムを終了してください。  

$A$の全要素を順に尋ねる問題です。  

<details><summary>答案例</summary>

~~~python: 答案例
def solve():
    N = int(input())
    A = [None] * (N + 1)  #1-indexedにしたい
    for i in range(1, N + 1):
        print('?', i)
        A[i] = int( input() )
    print('!', *A[1:])  #A[0]の出力をしないよう注意
    return
~~~
これを`solve()`で実行すればよいです。(終)

</details>
  

これのジャッジプログラムを書いて、実際にテストしてみましょう。  
関数名は`judge`にします。  

__隠し持つ$N$と$A$の決定__
コーナーケースへの対処のため、$N, A$を引数に設定することをおすすめします。  
ランダムテスト時は、`random.randint`で適当に決めればよいです。  
~~~python: 隠し持つ値の決定
import random
def judge(N = None, A = None):
    if N == None:
        N = random.randint(1, 10)  #1以上10以下の整数
    if A == None or len(A) != N:
        A = [random.randint(-100, 100) for _ in range(N)]
~~~

__$N$の出力__
値を出力したいときは `yield` を使います。  
~~~python: 値の出力例
yield str(N)
~~~
一応自動で`str`型に変換する機能はつけてあります。  
なので下記の出力法でも大丈夫なのですが、変なバグを避けるため、可能なら文字列型での出力をお願いします。  
~~~python: 出力例(おすすめしない)
yield N
~~~

__$N$回以下の質問__
`!`形式の回答が来るまで入力を受け取ればよいです。  
下記では$N + 1$回質問クエリの受付を行い、`!`クエリが来たら`break`としました。  

入力は`judge_input`の配列に文字列型で格納されています。  
たとえば、$A_1$の要素を尋ねるクエリが来る場合は`judge_input = ['? 1']` となっています。  
~~~python: 質問と応答
for time in range(N + 1):
    q, *i = judge_input[0].split()
    if q == '!':  #回答クエリ
        break

    assert q == '?'
    assert time < N, f'質問回数が{N = }回を超えました。'  #エラーメッセージ
    i = int( i[0] )  #特殊な受け取り方をしていたので修正
    assert 1 <= i <= N  #iの条件を確認
    
    #回答
    yield str( A[i - 1] )  #0-indexedなので注意
~~~

__回答の突き合わせ__
この時点で答案プログラムは終了していますが、ジャッジプログラムにはまだACチェックが残っています。  
隠し持っていた数列との一致を判定し、問題なければ`return`してください。
~~~python: 最終確認
assert q == '!'
B = [int(x) for x in i]  #値をintに変換
assert A == B, f'wrong output: {A = }, {B = }'
return  #問題なければジャッジプログラムも終了
~~~

__ランダムテスト__
実際に答案の`solve()`とジャッジの`judge()`を比較させます。  
ランダムテストを10000回行わせるときはこのようにします。
~~~python: ランダムテスト
test_program( solve, judge, test_time = 10000 )
~~~

これらを全てまとめると、以下のようになります。
長いので折りたたみにしてあります。

<details><summary>使用例</summary>

~~~python: 使用例
#インタラクティブ ローカルテスト
'''
【使い方】
答案・ジャッジプログラムを書き、実行テストの関数に渡してください。
直前の入出力ログは get_log() で出力できます。

【注意点】
・input, print関数を書き換えます。
  本提出時はコメントアウトするか、 del input, print で初期状態に戻してください。
・ジャッジにはテストケースを受け取る機能か、自動生成する機能をつけてください。
・答案 → ジャッジ の入力は judge_input というリストに一時保存されています。
  [0, 1, 2, ･･･]の順で、(前回のyield ～ 今)の答案からの出力が保存されています。
  yieldで答案に出力するたび、 judge_input の中身を空にするので注意してください。
・答案 ← ジャッジ の出力は yield (出力したい値) としてください。
  出力値はstr型が望ましいです。 一応自動str変換機能はつけていますが、気休めです。
・ジャッジはassert文でWAの判定を行ってください。
  AC判定を終えた場合、returnでジャッジプログラムを終了してください。

【内部仕様】
・_judge_program_funcにジャッジプログラムを入れ、next関数で出力を順に取り出します。
・入出力ログは judge_log に保存されます。
  答案 ← ジャッジ の出力は末尾に <judge> がついています。
・テストケースの情報(隠された文字列)は各自で確認してください。
・_judge_textは print( end = ) に対応するための仮保存スペースです。
  改行文字が来るまで文字列を結合し、改行が来たら judge_input にappendします。
'''

#内部関数
judge_input, judge_log, _judge_text = [], [], []
_exec_print = print
def print(*value, sep = ' ', end = '\n', file = None, flush = False):  #答案 → ジャッジ
    global judge_input, judge_log, _judge_program_func, _judge_text
    value = sep.join([ str(Vi) for Vi in value ])  #*value(tuple型)をアンパッキング
    _judge_text.append(value)
    if end == '\n':  #改行文字が来た場合、ここまでの文字列を judge_input と _log に送信
        judge_input.append( txt := ''.join( _judge_text ) )
        judge_log.append( txt )
        _judge_text.clear()
    else:
        _judge_text.append( end )

def input():  #答案 ← ジャッジ
    global judge_input, judge_log, _judge_program_func
    if type( value := next( _judge_program_func ) ) != str:  #入力をstrに変換
        if type(value) == list or type(value) == tuple:
            value = ' '.join([str(Vi) for Vi in value])
        else: value = str(value)
    judge_input.clear()  #ジャッジへの入力履歴を初期化
    judge_log.append( f'{value} <judge>' )
    return value


#実行テスト1. 連続テスト
def test_program( solve_program, judge_program, test_time = 1000 ):
    '''
    ジャッジが自力でランダムテストを生成できることを前提に、連続テストを行います。
    (答案プログラム, ジャッジプログラム, テスト回数)を入力してください。
    '''
    global judge_input, judge_log, _judge_program_func

    for counter in range(1, test_time + 1):
        #ジャッジログ・ジャッジ入力履歴を初期化
        judge_log.clear()
        judge_input.clear()

        #ジャッジプログラムを登録し実行
        _judge_program_func = judge_program()
        solve_program()
        try: next( _judge_program_func )
        except StopIteration: continue

#実行テスト2. 特定ケースでのチャレンジ
#関数後半にはジャッジに渡したいテストケースを入力してください
def test_corner( solve_program, judge_program, *value ):
    '''
    ジャッジプログラムがテストケース用の引数を受け取れることを前提とします。
    ジャッジプログラムの引数を順に *value に入力してください。
    たとえば judge(N: int, array: list) と N, array の順に引数指定がなされている場合、
    test_corner( solve_program, judge, 3, [3, 1, 4] ) のように順に渡してください。
    '''
    global judge_input, judge_log, _judge_program_func
    judge_log.clear()
    judge_input.clear()
    _judge_program_func = judge_program( *value )
    solve_program()
    try: next( _judge_program_func )
    except StopIteration: pass

#ジャッジ入出力ログを順に出力
def get_log(): _exec_print(*judge_log, sep = '\n')

'''
ここからジャッジプログラムを書いてください。
ジャッジへの入力はjudge_input(list型)に、出力はyieldでお願いします。
プログラム終了前にAC判定をお願いします。WAの判定にはassertが便利です。
'''




#ジャッジプログラムを書く
import random
def judge(N = None, A = None):
    if N == None:
        N = random.randint(1, 10)  #1以上10以下の整数
    if A == None or len(A) != N:
        A = [random.randint(-100, 100) for _ in range(N)]

    #Nの出力
    yield str(N)

    #N回以下の質問
    for time in range(N + 1):
        q, *i = judge_input[0].split()
        if q == '!':  #回答クエリ
            break

        assert q == '?'
        assert time < N, f'質問回数が{N = }回を超えました。'  #エラーメッセージ
        i = int( i[0] )  #特殊な受け取り方をしていたので修正
        assert 1 <= i <= N  #iの条件を確認
        
        #回答
        yield str( A[i - 1] )  #0-indexedなので注意

    #最終確認
    assert q == '!'
    B = [int(x) for x in i]  #値をintに変換
    assert A == B, f'wrong output: {A = }, {B = }'
    return  #問題なければジャッジプログラムも終了





#答案を書く
def solve():
    N = int(input())
    A = [None] * (N + 1)  #1-indexedにしたい
    for i in range(1, N + 1):
        print('?', i)
        A[i] = int( input() )
    print('!', *A[1:])  #A[0]の出力をしないよう注意
    return





#ランダムテストを実行
test_program( solve, judge, test_time = 10000 )
~~~

</details>

実行してみるとエラーメッセージが出ず、問題なくテストができました。  
なので`solve()`部分だけ抜き出して提出してください。  



### ABC299D Find by Query

[問題文はこちら](https://atcoder.jp/contests/abc299/tasks/abc299_d)
長さ$N$の01列$S$の中にある、$S_p ≠ S_{p + 1}$なる整数$p$を$20$質問以内に特定してください。  

[実行例(ジャッジ・答案あり)](https://atcoder.jp/contests/abc299/submissions/58175769)
ジャッジプログラムは先述の自作問題に似ているので、上記の実行例リンクからご確認ください。  

ここではコーナーケースの作成について説明します。  
明らかに間違った回答として、$N - 1$から降順に$0$が出るまで探すという方法があります。  
~~~python: 誤答例
def solve_WA():  #S[N - 1]から順に、0が出るまでO(N)回探す
    N = int( input() )
    for i in range(N - 1, 0, -1):
        print('?', i)
        Si = int( input() )
        if Si == 1: continue
        if Si == 0:  #S[i] == 0, S[i + 1] == 1 となるのでp = iとして出力
            print('!', i)
            return
~~~
$S = [0, 1, 1, ･･･, 1, 1, 1]$のような場合に$N - 1$回の探索を要するので誤答なのですが、ランダムテストでこれを落とすのは難しいです。  
この答案を落とすには右から最低でも$21$連続で$1$が続いていないといけないのですが、ランダムテストでそうなる確率は$1 / 2^{20}$と極めて低いからです。  
なので、`test_corner()`というコーナーケースを自分で作ってチャレンジする機能を使います。  
今回であれば`$N = 22, A = [0] + [1] * 21`のケースを試せばよさそうなので、このように実行してみます。  
__`test_corner()`に渡す引数の入力順は `judge()`関数に渡す引数の順にしてください。__
~~~python: 特定ケースのチャレンジ
def solve_WA():
    #中略

def judge(N = None, A = None):
    #中略

#N = 22, A = [0] + [1] * 21 のケースでチャレンジする
test_corner( solve_WA, judge, 22, [0] + [1] * 21 )
~~~
`AssertionError: too many question`と`assert`文でWAの検知ができました。  



### ABC305F Dungeon Explore

[問題文はこちら](https://atcoder.jp/contests/abc305/tasks/abc305_f)
$N$頂点$M$辺の単純連結無向グラフをなるはやで抜けてください。  

[実行例](https://atcoder.jp/contests/abc305/submissions/58176180)

グラフの生成は折りたたみのように行います。

<details><summary>単純連結無向グラフの生成</summary>

~~~python: グラフ作成
#N頂点の木を作成し、隣接リストとして返す(Prufer列使用)  O(NlogN)
import random, heapq
def make_wood(N: int):
    assert N > 0
    if N == 1: return [ [] ]

    G = [[] for _ in range(N)]
    P = [random.randint(0, N - 1) for _ in range(N - 2)]  #Prufer列
    D = [1] * N  #次数
    for Pi in P:
        D[Pi] += 1
    heapq.heapify( Q := [i for i in range(N) if D[i] == 1] )
    for Pi in P:  #Prufer列を順に当てる
        assert D[ Vi := heapq.heappop(Q) ] == 1
        G[Vi].append(Pi)
        G[Pi].append(Vi)
        D[Vi] -= 1
        D[Pi] -= 1
        assert D[Vi] == 0 and D[Pi] > 0
        if D[Pi] == 1:
            heapq.heappush(Q, Pi)
    assert len(Q) == 2
    Ui, Vi = Q[0], Q[1]
    G[Ui].append(Vi)
    G[Vi].append(Ui)
    D[Ui] -= 1
    D[Vi] -= 1
    for i in range(N):
        assert D[i] == 0
        G[i].sort()
    return G

    
#N頂点M辺の単純連結無向グラフを作成  expect O(NlogN + M)
def make_graph(N: int, M: int):
    assert 0 < N < 1 << 31 and N - 1 <= M <= N * (N - 1) // 2
    if N == 1 and M == 0: return [ [] ]

    G = make_wood(N)
    randb = random.getrandbits(32)
    #M / 総辺数 が高いなら、残辺を全列挙して乱択する  ここでは50%をカットオフとする
    if 2 * M > (N * (N - 1) // 2):
        S = {(i << 31 | j) ^ randb for i in range(N) for j in range(i + 1, N)}
        for i in range(N):
            for j in G[i]:
                if i < j: S.discard( (i << 31 | j) ^ randb )
        random.shuffle( S := list(S) )
        for x in range( M - (N - 1) ):
            G[ Ui := (S[x] ^ randb) >> 31 ].append( Vi := (S[x] ^ randb) & 0x7fffffff )
            G[Vi].append(Ui)
    else:  #木で使った辺をsetに登録し、乱択で辺を追加する
        S = {(i << 31 | j) ^ randb for i in range(N) for j in G[i] if i < j}
        while len(S) < M:
            Ui, Vi = random.randint(0, N - 1), random.randint(0, N - 1)
            if Ui == Vi: continue
            if Ui > Vi: Ui, Vi = Vi, Ui
            if (Ui << 31 | Vi) ^ randb not in S:
                S.add( (Ui << 31 | Vi) ^ randb )
                G[Ui].append(Vi)
                G[Vi].append(Ui)
    for i in range(N):
        G[i].sort()
    return G
~~~

プリューファー列から木を生成し、そこに辺をランダムに足す方法をとっています。(終)

</details>

さて、実装例の`solve_WA`を手元で実行すると以下のエラーが出てしまいました。
~~~python:
assert False, 'too many movement'
AssertionError: too many movement
~~~
これは移動回数が$2N$回を超えたときのエラーです。  
どのような移動をしていたのか、ログを確認してみましょう。  
入出力ログは`get_log()`で確認できます。  
~~~python: get_log() 実行結果
8 10 <judge>
3 3 4 5 <judge>
5
3 1 2 7 <judge>
7
3 2 5 6 <judge>
6
3 2 4 7 <judge>
4
2 1 6 <judge>
6
3 2 4 7 <judge>
2
3 5 6 7 <judge>
6
3 2 4 7 <judge>
7
3 2 5 6 <judge>
2
3 5 6 7 <judge>
7
3 2 5 6 <judge>
5
3 1 2 7 <judge>
2
3 5 6 7 <judge>
5
3 1 2 7 <judge>
1
3 3 4 5 <judge>
4
2 1 6 <judge>
1
~~~
ジャッジ側からの返答は末尾に`<judge>`がついています。  
移動経路を辿ると `(1→)5→7→6→4→6→2→6→7→2→7→5→2→5→1→4→1→･･･`となっており、どうも頂点$6$や頂点$7$に複数回入る無駄がありそうですね。  
このように、入出力ログはデバッグの助けになることがあります。   
ぜひご利用ください。


# おわりに

おわりです。  
おもいだしたら追記します。