#!/usr/bin/env python3 # # Local interaction tool for "Game: Cursor Minimum". # # This program is provided for contestants who want to test an interactive # solution locally. It starts the contestant program as a child process, plays # the role of the judge, and verifies that the contestant follows the protocol # on one chosen hidden permutation. # # This is NOT the official interactor used during judging. # # The official tests may contain many different hidden permutations and the # official judge is the only source of truth. This local tool only checks the # single permutation that you give it with --perm or --input-file, or the default # sample-like permutation if no permutation is supplied. Passing this tool means # that the solution worked for that local permutation and query limit; it 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 --perm 3,1,4,2 --limit 5 -- ./solution # python local_interactive.py --input-file local_case.txt --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 # ------------------------------------- # # The hidden data is a permutation p[1], p[2], ..., p[n]. The contestant does # not receive the permutation. The goal is to output the position of the minimum # value in the permutation. # # 1. The tool writes one line to the contestant program: # # n q # # Here n is the permutation length and q is the query limit. If --limit is # not supplied, q is floor(1.4 * n). # # 2. The contestant may ask a query by printing # # ? j # # where 1 <= j <= n. The tool keeps a cursor at the previous queried # position. For the first query, or if j is the same as the previous query, # the answer is "=". Otherwise, if the previous position was i, the answer is # based on comparing p[i] and p[j]: # # "<" if p[i] < p[j] # ">" if p[i] > p[j] # # After answering, the cursor moves to j. # # 3. The contestant may finish by printing # # ! a # # where a is the claimed position of the minimum value. The tool accepts only # if a is the true minimum position of the local hidden permutation. # # 4. If the contestant asks more than q queries, gives an invalid query, or # violates the protocol, this local tool sends -1 when appropriate and exits # with a non-zero status. # # Choosing local data # ------------------- # # --perm P # Use P as the hidden permutation. The values may be separated by commas or # spaces. For example, --perm 3,1,4,2 sets n = 4 and the minimum position to # 2. If neither --perm nor --input-file is given, the default permutation is # 3,1,4,2. # # --input-file PATH # Read the local data from a file. The file must contain n followed by n # integers forming a permutation of 1..n. For example: # # 4 # 3 1 4 2 # # --limit Q # Override the query limit q sent to the contestant. The default is # floor(1.4 * n). # # --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. It accepts blank lines by # ignoring them, but every non-empty command line must be either "? j" or "! a" # with exactly two tokens and a valid integer index. # # Exit status # ----------- # # The tool exits with status 0 if the contestant program follows the local # protocol, stays within the local query limit, and prints the correct minimum # position. It exits with a non-zero status if the contestant gives an invalid # command, exceeds the query limit, times out, terminates unexpectedly, prints a # wrong answer, or exits with a non-zero status itself. # import argparse import queue import subprocess import sys import threading def parse_perm(value): try: perm = [int(x) for x in value.replace(",", " ").split()] except ValueError as exc: raise argparse.ArgumentTypeError("permutation must contain integers") from exc if not perm: raise argparse.ArgumentTypeError("permutation must be non-empty") n = len(perm) if sorted(perm) != list(range(1, n + 1)): raise argparse.ArgumentTypeError("permutation must contain each value from 1 to n exactly once") return perm def read_input_file(path): data = open(path, encoding="utf-8").read().split() if not data: raise SystemExit("local_interactive: input file is empty") n = int(data[0]) perm = [int(x) for x in data[1:]] if len(perm) != n: raise SystemExit(f"local_interactive: expected {n} permutation values, got {len(perm)}") if sorted(perm) != list(range(1, n + 1)): raise SystemExit("local_interactive: input file does not contain a permutation") return perm def fail(proc, message, send_minus_one=False): if send_minus_one and proc.poll() is None: try: proc.stdin.write("-1\n") proc.stdin.flush() except BrokenPipeError: pass 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_line(proc, lines, timeout, echo): try: line = lines.get(timeout=timeout) except queue.Empty: fail(proc, "timeout while waiting for participant output; did you flush?") if line is None: fail(proc, "participant terminated before answering") if echo: print(f"participant -> {line.rstrip()}", file=sys.stderr) return line.strip().split() def main(): parser = argparse.ArgumentParser( description="Local interactive tester for Game: Cursor Minimum." ) parser.add_argument("--perm", type=parse_perm, help="hidden permutation, for example 3,1,4,2") parser.add_argument("--input-file", help="file containing n followed by a permutation") parser.add_argument("--limit", type=int, help="query limit; default is floor(1.4*n)") 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") if args.input_file and args.perm: parser.error("use only one of --perm and --input-file") perm = read_input_file(args.input_file) if args.input_file else (args.perm or [3, 1, 4, 2]) n = len(perm) limit = args.limit if args.limit is not None else (14 * n) // 10 if limit < 1: parser.error("--limit must be positive") min_pos = min(range(1, n + 1), key=lambda i: perm[i - 1]) proc = subprocess.Popen( program, stdin=subprocess.PIPE, stdout=subprocess.PIPE, text=True, bufsize=1, ) lines = start_reader(proc) send(proc, f"{n} {limit}", args.echo) queries = 0 prev = None while True: parts = read_line(proc, lines, args.timeout, args.echo) if not parts: continue if parts[0] == "?": if len(parts) != 2: fail(proc, "query must have format '? j'", send_minus_one=True) try: j = int(parts[1]) except ValueError: fail(proc, "query index must be an integer", send_minus_one=True) if not (1 <= j <= n): fail(proc, f"query index {j} is out of range", send_minus_one=True) queries += 1 if queries > limit: fail(proc, f"too many queries: {queries} > {limit}", send_minus_one=True) if prev is None or prev == j: reply = "=" elif perm[prev - 1] < perm[j - 1]: reply = "<" else: reply = ">" prev = j send(proc, reply, args.echo) elif parts[0] == "!": if len(parts) != 2: fail(proc, "answer must have format '! a'") try: answer = int(parts[1]) except ValueError: fail(proc, "answer index must be an integer") if answer != min_pos: fail(proc, f"wrong answer: got {answer}, expected {min_pos}") proc.stdin.close() try: code = proc.wait(timeout=args.timeout) except subprocess.TimeoutExpired: fail(proc, "participant did not terminate after the final answer") if code != 0: raise SystemExit(code) print(f"local_interactive: accepted in {queries} queries", file=sys.stderr) return else: fail(proc, f"expected '?' or '!', got {parts[0]!r}", send_minus_one=True) if __name__ == "__main__": main()