#!/usr/bin/env python3
"""Checker for Better Data Transfer.

Usage: check.py <points> <input> <reference_output> <contestant_output>
"""
import sys

def fail(msg, code=1):
    print(msg)
    sys.exit(code)

def verbose(msg):
    pass
    #print(msg, file=sys.stderr)

def code_check(tokens, s, h, weights, target):
    """Return None if tokens form a prefix-free code of total cost target, or a short description of the problem."""
    if len(tokens) != s:
        return f"expected {s} codewords, got {len(tokens)}"
    total = 0
    for w, tok in zip(weights, tokens):
        if not tok:
            return "empty codeword"
        cost = 0
        for ch in tok:
            if ch == "*":
                cost += h
            elif ch == "0" or ch == "1":
                cost += 1
            else:
                return f"invalid character {ch!r} in codeword"
        total += w * cost
    st = sorted(tokens)
    for x, y in zip(st, st[1:]):
        if y.startswith(x):
            return f"not prefix-free ({x!r} is a prefix of {y!r})"
    if total != target:
        return f"code needs {total} ns, not {target} ns"
    return None

def read_lines(path):
    with open(path) as f:
        lines = [ln.rstrip("\r\n") for ln in f]
    return lines

def main():
    if len(sys.argv) != 5:
        fail(f"usage: {sys.argv[0]} points input reference_output contestant_output", 2)
    try:
        points = float(sys.argv[1])
        assert points > 0
    except (ValueError, AssertionError):
        fail(f"invalid points argument {sys.argv[1]!r}", 2)

    # ---- input ----
    try:
        toks = open(sys.argv[2]).read().split()
        pos = 0
        t = int(toks[pos]); pos += 1
        tests = []
        for _ in range(t):
            s, h = int(toks[pos]), int(toks[pos + 1]); pos += 2
            a = [int(x) for x in toks[pos:pos + s]]; pos += s
            assert len(a) == s
            tests.append((s, h, a))
        assert pos == len(toks)
    except (OSError, ValueError, IndexError, AssertionError):
        fail("INTERNAL ERROR: cannot parse the input file", 2)

    # ---- reference output (and its self-consistency) ----
    try:
        reflines = read_lines(sys.argv[3])
    except:
        fail('INTERNAL ERROR: Could not parse the reference output (not an ASCII text?)')
    if len(reflines) != 2 * t:
        fail("INTERNAL ERROR: reference output has the wrong number of lines", 2)
    opt = []
    for i, (s, h, a) in enumerate(tests):
        try:
            (val,) = reflines[2 * i].split()
            val = int(val)
        except ValueError:
            fail(f"INTERNAL ERROR: cannot parse reference time of test {i + 1}", 2)
        problem = code_check(reflines[2 * i + 1].split(), s, h, a, val)
        if problem is not None:
            fail(f"INTERNAL ERROR: reference code of test {i + 1}: {problem}", 2)
        opt.append(val)

    # ---- contestant output ----
    try:
        lines = read_lines(sys.argv[4])
    except:
        fail('Could not parse the submission (not an ASCII text?)')
    if len(lines) != 2 * t:
        fail(f"wrong number of lines: expected {2 * t}, got {len(lines)}")

    code_problem = None  # (test number, description)
    for i, (s, h, a) in enumerate(tests):
        parts = lines[2 * i].split()
        if len(parts) != 1:
            fail(f"test {i + 1}: expected a single number on the time line, got {len(parts)} tokens")
        try:
            got = int(parts[0])
        except ValueError:
            fail(f"test {i + 1}: cannot parse the transmission time")
        if got != opt[i]:
            if got < opt[i] and code_check(lines[2 * i + 1].split(), s, h, a, got) is None:
                fail(f"INTERNAL ERROR: test {i + 1}: contestant proves time {got} ns, "
                     f"beating the reference ({opt[i]} ns) -- fix the reference output!", 2)
            fail(f"wrong optimal time for some test case")
        if code_problem is None:
            problem = code_check(lines[2 * i + 1].split(), s, h, a, opt[i])
            if problem is not None:
                code_problem = (i + 1, problem)
                verbose(f"test {i + 1}: code not accepted: {problem}")

    if code_problem is None:
        score, msg = points, f"OK: optimal times and valid optimal codes for all {t} tests"
    else:
        score = points // 2
        msg = "Partially OK: all times optimal but some codes are incorrect"
    print(f"{score:g}")
    print(msg)
    sys.exit(0)

if __name__ == "__main__":
    main()