#!/usr/bin/env python3
#
# Local interaction tool for "Game: Pattern Chase".
#
# This program is provided for contestants who want to run an interactive
# solution on their own machine. It starts the contestant program as a child
# process, sends the same kind of messages that the judge would send, reads the
# contestant's replies, and checks that the local transcript is valid.
#
# This is NOT the official interactor used during judging.
#
# In particular, this tool uses a very simple local jury strategy: whenever the
# jury has to choose a bit, it chooses 0 or 1 uniformly at random from a
# pseudo-random generator controlled by --seed. The official tests may contain
# many different cases and the official judge is the only source of truth. A
# solution that passes this local interaction tool is only known to be valid for
# the local random interaction that was generated here; this does not guarantee
# that the solution will pass the official test data.
#
# Basic usage
# -----------
#
# First compile your solution if needed:
#
#     g++ -std=c++17 -O2 -pipe -static -s -o solution solution.cpp
#
# Then run the local tool and put the contestant command after "--":
#
#     python local_interactive.py -- ./solution
#
# For an interpreted solution, put the interpreter in the command:
#
#     python local_interactive.py -- python solution.py
#
# Useful examples:
#
#     python local_interactive.py --echo -- ./solution
#     python local_interactive.py --case 01:3 --seed 2026 -- ./solution
#     python local_interactive.py --case 01:3 --case 101:5 --echo -- ./solution
#
# The separator "--" is important when the contestant command has its own
# arguments. Everything after it is treated as the command to execute.
#
# Local protocol simulated by this tool
# -------------------------------------
#
# 1. The tool writes one integer T to the contestant program. T is the number of
#    local cases. By default T = 1. Each --case option adds one case.
#
# 2. For each case, the tool writes a line
#
#        S K
#
#    where S is a non-empty binary string and K is the length of the game. The
#    case is supplied as S:K, for example --case 01:3. The tool requires
#    K >= len(S).
#
# 3. The contestant must print exactly one token, either
#
#        Alice
#
#    or
#
#        Bob
#
#    This chooses which player the contestant controls.
#
# 4. The game then constructs a binary string of length K. Alice writes the
#    1st, 3rd, 5th, ... bits. Bob writes the 2nd, 4th, 6th, ... bits.
#
#    If it is the contestant's turn, the contestant must print exactly one
#    token, either 0 or 1.
#
#    If it is the jury's turn, this local tool prints one random bit, 0 or 1.
#    The random sequence is reproducible with --seed.
#
# 5. After K bits have been chosen, Alice wins if S occurs as a substring of the
#    constructed string. Bob wins otherwise. The local tool accepts the case only
#    if the contestant's chosen player wins this locally generated game.
#
# Command-line options
# --------------------
#
# --case S:K
#     Add one local test case. This option may be repeated. S must be a
#     non-empty binary string, and K must be an integer at least len(S). If no
#     case is given, the default case is 01:3.
#
# --seed N
#     Set the random seed used for the jury's bits. This makes local runs
#     reproducible. Changing the seed may produce a different local transcript.
#
# --timeout SECONDS
#     Maximum time to wait for each contestant output. The default is 2 seconds.
#     A timeout usually means the contestant is waiting for input at the wrong
#     time or forgot to flush its output.
#
# --echo
#     Print the full local transcript to stderr. Lines prefixed with "judge ->"
#     are sent by this tool, and lines prefixed with "participant ->" are read
#     from the contestant program.
#
# Output and flushing requirements
# --------------------------------
#
# Interactive programs must flush after every output operation. For example, in
# C++ use "cout << value << endl;" or "cout << value << '\\n' << flush;". In
# Python use "print(value, flush=True)".
#
# This tool reads contestant output line by line and expects exactly one token
# on each required line. Extra tokens on the same line are treated as a protocol
# error.
#
# Exit status
# -----------
#
# The tool exits with status 0 if the contestant program follows the local
# protocol and wins every local case. If the contestant loses one or more local
# generated games but the protocol can still continue, this tool finishes the
# whole local interaction and then exits with a non-zero status. Protocol errors,
# timeouts, unexpected termination, and non-zero contestant exit statuses are
# still reported immediately.
#
import argparse
import queue
import random
import subprocess
import sys
import threading


def parse_case(value):
    if ":" in value:
        s, k = value.split(":", 1)
    elif "," in value:
        s, k = value.split(",", 1)
    else:
        raise argparse.ArgumentTypeError("case must be S:K, for example 01:3")
    if not s or any(c not in "01" for c in s):
        raise argparse.ArgumentTypeError("S must be a non-empty binary string")
    try:
        k = int(k)
    except ValueError as exc:
        raise argparse.ArgumentTypeError("K must be an integer") from exc
    if not (len(s) <= k):
        raise argparse.ArgumentTypeError("K must be at least len(S)")
    return s, k


def fail(proc, message):
    if proc.poll() is None:
        proc.kill()
    print(f"local_interactive: {message}", file=sys.stderr)
    raise SystemExit(1)


def send(proc, line, echo):
    if echo:
        print(f"judge -> {line}", file=sys.stderr)
    try:
        proc.stdin.write(line + "\n")
        proc.stdin.flush()
    except BrokenPipeError:
        fail(proc, "participant terminated while reading judge output")


def start_reader(proc):
    lines = queue.Queue()

    def read_stdout():
        for line in proc.stdout:
            lines.put(line)
        lines.put(None)

    thread = threading.Thread(target=read_stdout, daemon=True)
    thread.start()
    return lines


def read_token(proc, lines, timeout, echo, what):
    try:
        line = lines.get(timeout=timeout)
    except queue.Empty:
        fail(proc, f"timeout while waiting for {what}; did you flush?")
    if line is None:
        fail(proc, f"participant terminated while sending {what}")
    parts = line.strip().split()
    if len(parts) != 1:
        fail(proc, f"expected exactly one token for {what}, got {line.rstrip()!r}")
    if echo:
        print(f"participant -> {parts[0]}", file=sys.stderr)
    return parts[0]


def contains_pattern(text, pattern):
    return pattern in text


def run_case(proc, lines, rng, case_id, s, k, timeout, echo):
    send(proc, f"{s} {k}", echo)

    role = read_token(proc, lines, timeout, echo, f"role in case {case_id}")
    if role not in {"Alice", "Bob"}:
        fail(proc, f"case {case_id}: expected Alice or Bob, got {role!r}")

    participant_is_alice = role == "Alice"
    current = []

    for pos in range(k):
        alice_turn = (pos % 2 == 0)
        participant_turn = participant_is_alice == alice_turn
        if participant_turn:
            bit = read_token(proc, lines, timeout, echo, f"move {pos + 1} in case {case_id}")
            if bit not in {"0", "1"}:
                fail(proc, f"case {case_id}, move {pos + 1}: expected 0 or 1, got {bit!r}")
        else:
            bit = str(rng.randrange(2))
            send(proc, bit, echo)
        current.append(bit)

    final_string = "".join(current)
    alice_won = contains_pattern(final_string, s)
    participant_won = alice_won if participant_is_alice else not alice_won
    if not participant_won:
        message = (
            f"case {case_id}: participant chose {role}, final string {final_string!r}; " +
            "the participant lost this random local game"
        )
        print(message, file=sys.stderr)
        return message
    print(f"case {case_id}: ok ({role}, final string {final_string})", file=sys.stderr)
    return None


def main():
    parser = argparse.ArgumentParser(
        description="Local interactive tester for Game: Pattern Chase."
    )
    parser.add_argument(
        "--case",
        action="append",
        type=parse_case,
        dest="cases",
        help="test case as S:K, for example 01:3; may be repeated",
    )
    parser.add_argument("--seed", type=int, default=1, help="random seed for jury bits")
    parser.add_argument("--timeout", type=float, default=2.0, help="seconds to wait for each participant output")
    parser.add_argument("--echo", action="store_true", help="print the interaction transcript to stderr")
    parser.add_argument("program", nargs=argparse.REMAINDER, help="participant command, usually after --")
    args = parser.parse_args()

    program = args.program
    if program and program[0] == "--":
        program = program[1:]
    if not program:
        parser.error("missing participant command; use: python3 local_interactive.py -- ./solution")

    cases = args.cases or [("01", 3)]
    rng = random.Random(args.seed)
    proc = subprocess.Popen(
        program,
        stdin=subprocess.PIPE,
        stdout=subprocess.PIPE,
        text=True,
        bufsize=1,
    )
    lines = start_reader(proc)

    send(proc, str(len(cases)), args.echo)
    first_wrong_answer = None
    for case_id, (s, k) in enumerate(cases, start=1):
        wrong_answer = run_case(proc, lines, rng, case_id, s, k, args.timeout, args.echo)
        if first_wrong_answer is None and wrong_answer is not None:
            first_wrong_answer = wrong_answer

    proc.stdin.close()
    try:
        code = proc.wait(timeout=args.timeout)
    except subprocess.TimeoutExpired:
        fail(proc, "participant did not terminate after all local cases")
    if code != 0:
        raise SystemExit(code)
    if first_wrong_answer is not None:
        print(
            f"local_interactive: wrong answer after completing all cases: {first_wrong_answer}",
            file=sys.stderr,
        )
        raise SystemExit(1)
    print("local_interactive: accepted on the local random interaction", file=sys.stderr)


if __name__ == "__main__":
    main()