"""
$ cat ./AGENTS.md
# Instruction

Heuristic Contest の問題を解くためのプログラムを作るリポジトリです。

## ディレクトリ構成

- 今回のコンテストの問題文は ./problem_statement.html です。
- ./main.py に解法を実装します。
  - 使用して良いライブラリは、 Python 3.13 の標準ライブラリと、 NumPy 2.2.1, SciPy 1.14.1 のみです。

## コーディング規約

- 解答は Python で作成する。 main.py に全てを実装する
- 乱数の初期 seed は定数として埋め込んで、複数回の実行で再現性を担保する
- 問題を解く関数を実装する。
  - 関数の引数に、ジャッジとのやり取りを行うコールバック関数を与える。これにより、ローカル実行と、実際の提出による実行の両方に利用できるようにする。
- 仮想的なジャッジも main.py に実装する。適当なコマンドライン引数とともに手元で実行すると、ランダム生成したデータを元に解法を実行し、どの程度のスコアが取れるのか確認できる

## 注意点

以下を厳守する。

- Chat は日本語で回答してください
- 指示・意図・仕様に関して不明な点があれば、実装に移る前に質問する

## アルゴリズムの方針

STRATEGY.md に詳細に記載されています。この方針に従ってください

$ cat STRATEGY.md
# 戦略

- 最初の 20 回は、これまでに与えたことのないランダムなクエリを与える。
- それ以降は、
  - scipy.optimize.linprog を用いて以下の混合整数線形計画問題を考える（これが解を 1 個だけ持つならば、隠された文字列が全てわかったことになる）。
    - 候補となる全ての文字列のうち、過去のクエリ結果から存在し得ないものを除いたもの s それぞれについて、 0 以上 1 以下の変数 x_s を生やす（これは、ジャッジがこの文字列を隠し持っているかどうかに相当する）。
    - 過去のクエリ結果のうち、 t 回目のクエリに含まれる各 (h, b) についてその出現頻度を数え、その個数が s に対するクエリ結果が (h, b) となるような s 全てに対する x_s の総和と一致する、という等式制約を課す。
    - なお、このとき、既に発見済みの文字列は適切に除外して考慮する。
  - まずは上記の問題を、 x に対する整数制約を課さずに解く。
  - 次に、いったん解いた結果の解について、 x_s の値が 0.9999 以上のものと 0.0001 未満のものしか存在しない場合、 x_s の値が 0.9999 以上の s の個数を k として、「これらの s に対する x_s の総和が k - 1 以下」という制約をさらに追加してもう一度 LP を解く。これで解なしになった場合、これら全ての s が隠された文字列であることが確定するので、これらを回答して終了する。
  - x_s の値が 1e-5 以上のもののうち、最も値が大きい s を次のクエリとする。
- なお、既に判明した文字列に関しては (h, b) が (5, 0) で固定になるという仕様があるので、この点に気をつけて注意深く実装すること。
"""
import argparse
import itertools
import random
import sys
from typing import Callable, List, Sequence, Tuple

import numpy as np
from scipy.optimize import linprog
from scipy.sparse import csr_matrix

SEED = 12345
RNG = random.Random(SEED)
QUERY_LEN = 5
NUM_SECRETS = 30


def generate_all_strings() -> List[str]:
    digits = "0123456789"
    return ["".join(p) for p in itertools.permutations(digits, QUERY_LEN)]


def all_hb_pairs() -> List[Tuple[int, int]]:
    pairs: List[Tuple[int, int]] = []
    for h in range(QUERY_LEN + 1):
        for b in range(QUERY_LEN - h + 1):
            pairs.append((h, b))
    return pairs


def hb_pair(s: str, q: str, q_set: set[str]) -> Tuple[int, int]:
    hit = sum(1 for a, b in zip(s, q) if a == b)
    blow = len(set(s) & q_set) - hit
    return hit, blow


class QueryRecord:
    def __init__(self, q: str, counts: List[int]) -> None:
        self.q = q
        self.q_set = set(q)
        self.counts = counts


def pick_random_unasked(candidates: Sequence[str], asked: set[str]) -> str | None:
    if len(asked) >= len(candidates):
        return None
    while True:
        q = RNG.choice(candidates)
        if q not in asked:
            return q


def build_lp(
    history: Sequence[QueryRecord],
    candidates: Sequence[str],
    candidate_sets: Sequence[set[str]],
    found_set: set[str],
    found_at: dict[str, int],
    confirmed_not_secret: set[str],
    pair_index: dict[Tuple[int, int], int],
    pairs: Sequence[Tuple[int, int]],
) -> Tuple[csr_matrix, np.ndarray, List[int]] | None:
    def is_feasible(i: int) -> bool:
        s = candidates[i]
        if s in found_set or s in confirmed_not_secret:
            return False
        for record in history:
            hit = sum(1 for a, b in zip(s, record.q) if a == b)
            blow = len(candidate_sets[i] & record.q_set) - hit
            if record.counts[pair_index[(hit, blow)]] == 0:
                return False
        return True

    unknown_indices = [i for i in range(len(candidates)) if is_feasible(i)]
    if not unknown_indices:
        return None
    pair_count = len(pairs)
    row_count = len(history) * pair_count + 1
    data: List[int] = []
    rows: List[int] = []
    cols: List[int] = []
    for qi, record in enumerate(history):
        q = record.q
        q_set = record.q_set
        for col_idx, cand_idx in enumerate(unknown_indices):
            s = candidates[cand_idx]
            hit = sum(1 for a, b in zip(s, q) if a == b)
            blow = len(candidate_sets[cand_idx] & q_set) - hit
            hb_idx = pair_index[(hit, blow)]
            rows.append(qi * pair_count + hb_idx)
            cols.append(col_idx)
            data.append(1)
    sum_row = row_count - 1
    for col_idx in range(len(unknown_indices)):
        rows.append(sum_row)
        cols.append(col_idx)
        data.append(1)
    a_eq = csr_matrix((data, (rows, cols)), shape=(row_count, len(unknown_indices)))
    b_eq_list: List[int] = []
    for qi, record in enumerate(history):
        fixed_counts = [0] * pair_count
        for s in found_set:
            found_time = found_at[s]
            if found_time <= qi:
                pair = (5, 0)
            else:
                pair = hb_pair(s, record.q, record.q_set)
            fixed_counts[pair_index[pair]] += 1
        for pi in range(pair_count):
            value = record.counts[pi] - fixed_counts[pi]
            if value < 0:
                return None
            b_eq_list.append(value)
    b_eq_list.append(NUM_SECRETS - len(found_set))
    b_eq = np.array(b_eq_list, dtype=float)
    return a_eq, b_eq, unknown_indices


def solve_strategy2(ask: Callable[[str], Sequence[Tuple[int, int]]]) -> None:
    candidates = generate_all_strings()
    candidate_sets = [set(s) for s in candidates]
    pairs = all_hb_pairs()
    pair_index = {pair: i for i, pair in enumerate(pairs)}
    asked: set[str] = set()
    found_set: set[str] = set()
    found_at: dict[str, int] = {}
    confirmed_not_secret: set[str] = set()
    history: List[QueryRecord] = []
    query_count = 0

    def process_response(q: str, response: Sequence[Tuple[int, int]]) -> bool:
        if not response:
            return False
        if response[0] == (-1, -1):
            return False
        counts = [0] * len(pairs)
        for h, b in response:
            counts[pair_index[(h, b)]] += 1
        found_before = len(found_set)
        if counts[pair_index[(5, 0)]] > found_before:
            found_set.add(q)
            found_at[q] = len(history)
        else:
            confirmed_not_secret.add(q)
        history.append(QueryRecord(q, counts))
        asked.add(q)
        if response[0] == (5, 0):
            return False
        return True

    for _ in range(25):
        q = pick_random_unasked(candidates, asked)
        if q is None:
            return
        query_count += 1
        print(f"[query {query_count}] strategy2 random-initial q={q}", file=sys.stderr, flush=True)
        if not process_response(q, ask(q)):
            return

    while True:
        if len(found_set) >= NUM_SECRETS:
            return
        lp = build_lp(
            history,
            candidates,
            candidate_sets,
            found_set,
            found_at,
            confirmed_not_secret,
            pair_index,
            pairs,
        )
        if lp is None:
            q = pick_random_unasked(candidates, asked)
            if q is None:
                return
            query_count += 1
            print(f"[query {query_count}] strategy2 random-no-lp q={q}", file=sys.stderr, flush=True)
            if not process_response(q, ask(q)):
                return
            continue
        a_eq, b_eq, unknown_indices = lp
        bounds = [(0.0, 1.0)] * len(unknown_indices)
        result = linprog(c=np.zeros(len(unknown_indices)), A_eq=a_eq, b_eq=b_eq, bounds=bounds, method="highs")
        if not result.success or result.x is None:
            q = pick_random_unasked(candidates, asked)
            if q is None:
                return
            query_count += 1
            print(f"[query {query_count}] strategy2 random-lp-fail q={q}", file=sys.stderr, flush=True)
            if not process_response(q, ask(q)):
                return
            continue
        x = result.x
        near_one_cols: List[int] = []
        binary_solution = True
        for col_idx, value in enumerate(x):
            if value >= 0.9999:
                near_one_cols.append(col_idx)
            elif value < 0.0001:
                continue
            else:
                binary_solution = False
                break
        if binary_solution and near_one_cols:
            a_ub = np.zeros((1, len(unknown_indices)))
            for col_idx in near_one_cols:
                a_ub[0, col_idx] = 1.0
            b_ub = np.array([len(near_one_cols) - 1], dtype=float)
            test = linprog(
                c=np.zeros(len(unknown_indices)),
                A_eq=a_eq,
                b_eq=b_eq,
                A_ub=a_ub,
                b_ub=b_ub,
                bounds=bounds,
                method="highs",
            )
            if not test.success:
                for col_idx in near_one_cols:
                    s = candidates[unknown_indices[col_idx]]
                    if s in asked:
                        continue
                    query_count += 1
                    print(f"[query {query_count}] strategy2 deduced-final q={s}", file=sys.stderr, flush=True)
                    if not process_response(s, ask(s)):
                        return
                return
        scored: List[Tuple[float, str]] = []
        for col_idx, cand_idx in enumerate(unknown_indices):
            if x[col_idx] < 1e-5:
                continue
            s = candidates[cand_idx]
            if s in asked:
                continue
            scored.append((x[col_idx], s))
        if scored:
            q = max(scored)[1]
            query_count += 1
            print(f"[query {query_count}] strategy2 lp-top q={q}", file=sys.stderr, flush=True)
            if not process_response(q, ask(q)):
                return
            continue
        q = pick_random_unasked(candidates, asked)
        if q is None:
            return
        query_count += 1
        print(f"[query {query_count}] strategy2 random-fallback q={q}", file=sys.stderr, flush=True)
        if not process_response(q, ask(q)):
            return


class LocalJudge:
    def __init__(self, secrets: Sequence[str]) -> None:
        self.secrets = list(secrets)
        self.found = set()
        self.query_count = 0

    def ask(self, q: str) -> List[Tuple[int, int]]:
        self.query_count += 1
        q_set = set(q)
        response: List[Tuple[int, int]] = []
        for s in self.secrets:
            if s in self.found or s == q:
                response.append((5, 0))
                self.found.add(s)
                continue
            hit = sum(1 for a, b in zip(s, q) if a == b)
            blow = len(set(s) & q_set) - hit
            response.append((hit, blow))
        response.sort()
        return response

    def is_solved(self) -> bool:
        return len(self.found) == len(self.secrets)

    def verify_solution(self) -> Tuple[bool, List[str], List[str]]:
        secret_set = set(self.secrets)
        missing = sorted(secret_set - self.found)
        extra = sorted(self.found - secret_set)
        return not missing and not extra, missing, extra


def interactive_ask(q: str) -> List[Tuple[int, int]]:
    print(q)
    sys.stdout.flush()
    pairs: List[Tuple[int, int]] = []
    for _ in range(NUM_SECRETS):
        line = sys.stdin.readline()
        if not line:
            return []
        h_str, b_str = line.split()
        pairs.append((int(h_str), int(b_str)))
    return pairs


def run_local() -> None:
    candidates = generate_all_strings()
    RNG.shuffle(candidates)
    secrets = candidates[:NUM_SECRETS]
    judge = LocalJudge(secrets)
    solve_strategy2(judge.ask)
    solved = judge.is_solved()
    verified, missing, extra = judge.verify_solution()
    if not solved:
        print("warning: not all secrets were found", file=sys.stderr, flush=True)
    if not verified:
        if missing:
            print(f"missing={missing}", file=sys.stderr, flush=True)
        if extra:
            print(f"extra={extra}", file=sys.stderr, flush=True)
    score = 100000 - judge.query_count
    print(f"queries={judge.query_count} score={score} solved={solved} verified={verified}", file=sys.stderr, flush=True)


def main() -> None:
    parser = argparse.ArgumentParser()
    parser.add_argument("--local", action="store_true",default=False)
    args = parser.parse_args()
    if args.local:
        run_local()
    else:
        solve_strategy2(interactive_ask)


if __name__ == "__main__":
    main()