# __student_code_runs_here__ import copy import hashlib import json import sys import time # Runtime for DSA questions whose tests live in problem.json. buildTestHarness # (processes/ide-content/build-test-harness.ts) puts this text in front of the generated test file, and data/app_data/13-dsa-sheet/_tools/dsa_tool.py # imports it to check the reference solution, so both run the same code. # # Inputs are plain JSON. A large input is not stored: it is a {"$gen": {...}} spec that every # language can rebuild from a seed with the same tiny PRNG (mulberry32), so C++ and JS later get # the identical arrays. # Set when a performance case runs over its limit: the remaining performance cases are skipped, so # a slow solution gets one clear "Time limit exceeded" and not a 20 second hard stop. STATE = {"slow": False} # Running the student's code in another language. Python stays the referee: it makes every input # (external_prepare), the other language only calls the student's function on them, and the answers come # back here to be judged by the same check_case below, so every language gets the same cases, the same # comparison and the same messages. EXTERNAL["outputs"] is None for a normal Python run. For an external run it # maps ":" to what the other language reported for that call: # {"out": , "ms": , "reads": } # {"error": ""} {"skip": true} (no record at all: the program never got there) # Notes for the student (something that could not be checked in that language) collect in "notes". EXTERNAL = {"outputs": None, "stopped": False, "notes": [], "returns": ""} class Skipped(AssertionError): """A case that cannot run in this language (a number too big for it). It does not count against the student. A test that was not run because an earlier one hung or was too slow is not this: it still fails.""" skipped = True def _mulberry32(seed): state = [seed & 0xFFFFFFFF] def next_u32(): state[0] = (state[0] + 0x6D2B79F5) & 0xFFFFFFFF t = state[0] t = ((t ^ (t >> 15)) * (t | 1)) & 0xFFFFFFFF t ^= (t + (((t ^ (t >> 7)) * (t | 61)) & 0xFFFFFFFF)) & 0xFFFFFFFF return (t ^ (t >> 14)) & 0xFFFFFFFF return next_u32 def _shuffle(items, rnd): for i in range(len(items) - 1, 0, -1): j = rnd() % (i + 1) items[i], items[j] = items[j], items[i] return items class TreeNode: """The node class used when the student's file does not define its own `TreeNode`.""" def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def _build_tree(node_class, items): """A binary tree from a level-order list with None for a missing child.""" if not items or items[0] is None: return None root = node_class(items[0]) queue = [root] i = 1 for node in queue: if i < len(items): if items[i] is not None: node.left = node_class(items[i]) queue.append(node.left) i += 1 if i < len(items): if items[i] is not None: node.right = node_class(items[i]) queue.append(node.right) i += 1 return root def _tree_list(root): """The tree as a level-order list with None for a missing child (trailing Nones removed).""" out = [] queue = [root] seen = set() for node in queue: if node is None: out.append(None) continue if id(node) in seen: raise AssertionError( "Your answer is not a tree: the same node appears twice." ) seen.add(id(node)) out.append(node.val) queue.append(node.left) queue.append(node.right) while out and out[-1] is None: out.pop() return out def _ser(vals, left, right): """Level-order list of the tree stored in arrays (node 0 is the root, -1 = no child).""" if not vals: return [] out = [] queue = [0] for i in queue: if i < 0: out.append(None) continue out.append(vals[i]) queue.append(left[i]) queue.append(right[i]) while out and out[-1] is None: out.pop() return out def _shape(n, rnd): """A random binary tree shape with n nodes: each new node takes a random free child slot.""" left, right = [-1] * n, [-1] * n slots = [(0, 0), (0, 1)] if n else [] for i in range(1, n): j = rnd() % len(slots) parent, side = slots[j] slots[j] = slots[-1] slots.pop() if side == 0: left[parent] = i else: right[parent] = i slots.append((i, 0)) slots.append((i, 1)) return left, right def _random_bst(n, step, rnd): """Arrays of a random BST with the values 0, step, 2*step, ...: the root is a random value of the range, and each side is built the same way (the shape of inserting a random order).""" vals, left, right = [], [], [] todo = [(0, n - 1, -1, 0)] if n else [] while todo: lo, hi, parent, side = todo.pop() mid = lo + rnd() % (hi - lo + 1) index = len(vals) vals.append(mid * step) left.append(-1) right.append(-1) if parent >= 0: if side == 0: left[parent] = index else: right[parent] = index if mid + 1 <= hi: todo.append((mid + 1, hi, index, 1)) if lo <= mid - 1: todo.append((lo, mid - 1, index, 0)) return vals, left, right def _preorder(vals, left, right): out = [] stack = [0] if vals else [] while stack: i = stack.pop() out.append(vals[i]) if right[i] >= 0: stack.append(right[i]) if left[i] >= 0: stack.append(left[i]) return out def _inorder(vals, left, right): out = [] stack = [] i = 0 if vals else -1 while i >= 0 or stack: while i >= 0: stack.append(i) i = left[i] i = stack.pop() out.append(vals[i]) i = right[i] return out def _gen_tree(kind, spec, rnd): n = spec.get("n", 0) lo, hi = spec.get("lo", 0), spec.get("hi", 0) if kind == "tree_level": left, right = _shape(n, rnd) return _ser([lo + rnd() % (hi - lo + 1) for _ in range(n)], left, right) if kind == "tree_level_distinct": left, right = _shape(n, rnd) return _ser(_shuffle(list(range(n)), rnd), left, right) if kind in ("tree_preorder", "tree_inorder"): left, right = _shape(n, rnd) vals = _shuffle(list(range(n)), rnd) walk = _preorder if kind == "tree_preorder" else _inorder return walk(vals, left, right) if kind == "skew_tree": # a chain of n nodes, each the left child of the one above out = [rnd() % 10] for _ in range(n - 1): out.extend([rnd() % 10, None]) return out if kind == "skew_bst": # a chain of n nodes, each the right child of the one above, values 0, step, 2*step, ... out = [] for i in range(n): out.append(i * spec["step"]) out.append(None) return out[:-1] if kind == "skew_preorder": return [i * spec["step"] for i in range(n)] if kind == "symmetric_tree": # a root whose left side is a random tree with n nodes and whose right side is its mirror; # sometimes one value of the mirror is changed left, right = _shape(n, rnd) small = [lo + rnd() % (hi - lo + 1) for _ in range(n)] vals = [lo + rnd() % (hi - lo + 1)] + small + small lefts, rights = [-1] * (2 * n + 1), [-1] * (2 * n + 1) for i in range(n): lefts[1 + i] = 1 + left[i] if left[i] >= 0 else -1 rights[1 + i] = 1 + right[i] if right[i] >= 0 else -1 lefts[1 + n + i] = 1 + n + right[i] if right[i] >= 0 else -1 rights[1 + n + i] = 1 + n + left[i] if left[i] >= 0 else -1 if n: lefts[0], rights[0] = 1, 1 + n if rnd() % 3 == 0: vals[1 + n + rnd() % n] += 1 return _ser(vals, lefts, rights) vals, left, right = _random_bst(n, spec.get("step", 2), rnd) if kind == "bst_preorder": return _preorder(vals, left, right) if kind in ("bst_or_not", "bst_swapped") and n >= 2: if kind == "bst_swapped" or rnd() % 2 == 0: i = rnd() % n j = (i + 1 + rnd() % (n - 1)) % n vals[i], vals[j] = vals[j], vals[i] return _ser(vals, left, right) def _gen_design_ops(spec, rnd): """n operations (as text) for the "design a data structure" questions. `kind` picks the structure: lru, point (set / sum / min on a list of `size` values), range_add, kv, snapshot, browser, hits, uf.""" kind, n = spec["kind"], spec["n"] size = spec.get("size", 1) ops = [] if kind == "lru": for _ in range(n): key = rnd() % size if rnd() % 2 == 0: ops.append("put " + str(key) + " " + str(rnd() % 100)) else: ops.append("get " + str(key)) elif kind == "point": verb = spec["verb"] for _ in range(n): if rnd() % 2 == 0: ops.append("set " + str(rnd() % size) + " " + str(rnd() % 2001 - 1000)) else: a, b = rnd() % size, rnd() % size ops.append(verb + " " + str(min(a, b)) + " " + str(max(a, b))) elif kind == "range_add": for _ in range(n): if rnd() % 2 == 0: a, b = rnd() % size, rnd() % size ops.append( "add " + str(min(a, b)) + " " + str(max(a, b)) + " " + str(rnd() % 21 - 10) ) else: ops.append("get " + str(rnd() % size)) elif kind == "kv": time = 0 for _ in range(n): key = "k" + str(rnd() % spec.get("keys", 3)) if rnd() % 2 == 0: time += 1 + rnd() % 3 ops.append("set " + key + " v" + str(rnd() % 50) + " " + str(time)) else: ops.append("get " + key + " " + str(rnd() % (time + 3))) elif kind == "snapshot": snaps = 0 for _ in range(n): r = rnd() % 4 if r < 2: ops.append("set " + str(rnd() % size) + " " + str(rnd() % 100)) elif r == 2 or snaps == 0: ops.append("snap") snaps += 1 else: ops.append("get " + str(rnd() % size) + " " + str(rnd() % snaps)) elif kind == "browser": for _ in range(n): r = rnd() % 3 if r == 0: ops.append("visit site" + str(rnd() % 1000)) elif r == 1: ops.append("back " + str(1 + rnd() % 4)) else: ops.append("forward " + str(1 + rnd() % 4)) elif kind == "hits": time = 1 for _ in range(n): time += rnd() % 40 ops.append(("hit " if rnd() % 2 == 0 else "count ") + str(time)) elif kind == "uf": for _ in range(n): r = rnd() % 3 if r == 0: ops.append("union " + str(rnd() % size) + " " + str(rnd() % size)) elif r == 1: ops.append("connected " + str(rnd() % size) + " " + str(rnd() % size)) else: ops.append("size " + str(rnd() % size)) return ops def _gen(spec): rnd = _mulberry32(spec.get("seed", 1)) kind = spec["type"] n = spec.get("n", 0) lo, hi = spec.get("lo", 0), spec.get("hi", 0) if kind == "int_array": return [lo + rnd() % (hi - lo + 1) for _ in range(n)] if kind == "sorted_int_array": return sorted(lo + rnd() % (hi - lo + 1) for _ in range(n)) if kind == "sorted_desc_int_array": return sorted((lo + rnd() % (hi - lo + 1) for _ in range(n)), reverse=True) if kind == "string": alphabet = spec["alphabet"] return "".join(alphabet[rnd() % len(alphabet)] for _ in range(n)) if kind == "permutation": # a shuffle of 0..n-1 (Fisher-Yates driven by the portable PRNG) return _shuffle(list(range(n)), rnd) if kind == "permutation_missing": # a shuffle of 0..n with one random value left out (n values) items = list(range(n + 1)) items.pop(rnd() % (n + 1)) return _shuffle(items, rnd) if kind == "twice_but_one": # n + 1 different values 0..n: one appears once, the other n appear twice (2n + 1 values) values = _shuffle(list(range(n + 1)), rnd) return _shuffle(values + values[1:], rnd) if kind == "repeat_missing": # a shuffle of 1..n where one value was overwritten by a copy of another (needs n >= 2) items = _shuffle(list(range(1, n + 1)), rnd) i = rnd() % n j = rnd() % n if i == j: j = (j + 1) % n items[i] = items[j] return items if kind == "int_matrix": return [ [lo + rnd() % (hi - lo + 1) for _ in range(spec["cols"])] for _ in range(spec["rows"]) ] if kind == "string_words": # n words, each 1..max_len letters from `alphabet` (max_len defaults to 3) alphabet = spec["alphabet"] max_len = spec.get("max_len", 3) words = [] for _ in range(n): length = 1 + rnd() % max_len words.append( "".join(alphabet[rnd() % len(alphabet)] for _ in range(length)) ) return words if kind == "cyclic_words": # ["w0", "w1", ..., "w", "w0", ...] with n words return ["w" + str(i % spec["period"]) for i in range(n)] if kind == "sudoku_board": # a 9x9 board (0 = empty) with `count` random digits 1..9 at random cells cells = _shuffle(list(range(81)), rnd) board = [[0] * 9 for _ in range(9)] for cell in cells[: spec["count"]]: board[cell // 9][cell % 9] = 1 + rnd() % 9 return board if ( kind in ("sorted_unique_int_array", "rotated_sorted_unique", "mountain") and n == 0 ): return [] if kind == "rotated_sorted_int_array": # a sorted_int_array (repeats allowed) rotated left by a random amount items = sorted(lo + rnd() % (hi - lo + 1) for _ in range(n)) if n == 0: return items k = rnd() % n return items[k:] + items[:k] if kind == "sorted_matrix_flat": # rows x cols whose values increase along each row and continue in the next row total = spec["rows"] * spec["cols"] step = (hi - lo + 1) // total flat = [lo + i * step + rnd() % step for i in range(total)] return [ flat[r * spec["cols"] : (r + 1) * spec["cols"]] for r in range(spec["rows"]) ] if kind == "binary_rows": # each row: some 0s then some 1s (the number of 0s is random from 0 to cols) rows = [] for _ in range(spec["rows"]): zeros = rnd() % (spec["cols"] + 1) rows.append([0] * zeros + [1] * (spec["cols"] - zeros)) return rows if kind == "sorted_unique_int_array": # n different values, increasing, spread over lo..hi (hi - lo + 1 >= n; equal means lo..hi) step = (hi - lo + 1) // n return [lo + i * step + rnd() % step for i in range(n)] if kind == "rotated_sorted_unique": # a sorted_unique_int_array rotated left by a random amount step = (hi - lo + 1) // n items = [lo + i * step + rnd() % step for i in range(n)] k = rnd() % n return items[k:] + items[:k] if kind == "mountain": # strictly increasing up to the largest value, then strictly decreasing (n values) step = (hi - lo + 1) // n items = [lo + i * step + rnd() % step for i in range(n)] top = items.pop() left, right = [], [] for value in items: (left if rnd() % 2 == 0 else right).append(value) return left + [top] + right[::-1] if kind == "twice_sorted_but_one": # a sorted list where every value appears twice except one (2n + 1 values) values = [lo + i * ((hi - lo + 1) // (n + 1)) for i in range(n + 1)] single = rnd() % (n + 1) out = [] for i, value in enumerate(values): out.extend([value] if i == single else [value, value]) return out if kind == "sorted_grid": # rows x cols, strictly increasing along every row and every column k = spec.get("k", 1000) return [ [(i + j) * k + rnd() % k for j in range(spec["cols"])] for i in range(spec["rows"]) ] if kind == "balanced_parens": # a random balanced string of n pairs of parentheses (2n characters) out = [] opens = closes = 0 for _ in range(2 * n): if opens < n and (closes >= opens or rnd() % 2 == 0): out.append("(") opens += 1 else: out.append(")") closes += 1 return "".join(out) if kind == "binary_string": # n bits starting with 1 (a single bit may be 0) if n == 0: return "" bits = ["1" if n > 1 else str(rnd() % 2)] bits.extend(str(rnd() % 2) for _ in range(n - 1)) return "".join(bits) if kind == "cyclic_string_of": # `pattern` repeated and cut to n characters pattern = spec["pattern"] return (pattern * (n // len(pattern) + 1))[:n] if kind == "roman": # the Roman numeral for the number n (1..3999) out = [] for value, symbol in ( (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I"), ): while n >= value: out.append(symbol) n -= value return "".join(out) if kind == "digit_string": # n decimal digits with no leading zero (a single digit may be 0) if n == 0: return "" first = 1 + rnd() % 9 if n > 1 else rnd() % 10 return str(first) + "".join(str(rnd() % 10) for _ in range(n - 1)) if kind == "cyclic_string": # s[i] is chr(base + i % period): n characters with the longest all-different run = period return "".join(chr(spec.get("base", 97) + i % spec["period"]) for i in range(n)) if kind == "int_pairs": # n pairs [a, b] with lo <= a <= b <= hi pairs = [] for _ in range(n): a = lo + rnd() % (hi - lo + 1) b = lo + rnd() % (hi - lo + 1) pairs.append([min(a, b), max(a, b)]) return pairs if kind == "letter_grid": # `rows` strings of `cols` letters from `alphabet` alphabet = spec["alphabet"] return [ "".join(alphabet[rnd() % len(alphabet)] for _ in range(spec["cols"])) for _ in range(spec["rows"]) ] if kind == "edge_list": # n edges [a, b] between different nodes in lo..hi (needs hi > lo) edges = [] for _ in range(n): a = lo + rnd() % (hi - lo + 1) b = lo + rnd() % (hi - lo) edges.append([a, b + 1 if b >= a else b]) return edges if kind == "cyclic_list": # {"values": n ints, "cycle": -1 or the position the last node points back to} values = [lo + rnd() % (hi - lo + 1) for _ in range(n)] return {"values": values, "cycle": rnd() % (n + 1) - 1} if kind == "joined_list": # {"values": n ints, "join": {...}}: the last node points at node `index` (-1 = none) of # the list for parameter `param`, which has `size` nodes values = [lo + rnd() % (hi - lo + 1) for _ in range(n)] index = rnd() % (spec["size"] + 1) - 1 return {"values": values, "join": {"param": spec["param"], "index": index}} if kind == "repeat_but_one": # n + 1 different values: one appears once, the other n appear `times` times (shuffled) step = (hi - lo + 1) // (n + 1) values = [lo + i * step + rnd() % step for i in range(n + 1)] return _shuffle(values[:1] + values[1:] * spec["times"], rnd) if kind == "two_singles": # n + 2 different values: two appear once, the other n appear twice (shuffled) step = (hi - lo + 1) // (n + 2) values = [lo + i * step + rnd() % step for i in range(n + 2)] return _shuffle(values[:2] + values[2:] * 2, rnd) if kind == "nonzero_int_array": out = [] for _ in range(n): v = lo + rnd() % (hi - lo + 1) out.append(v if v else hi) return out if kind == "choice_array": values = spec["values"] return [values[rnd() % len(values)] for _ in range(n)] if kind == "int_pairs_free": # n pairs [a, b], each of a and b in lo..hi pairs = [] for _ in range(n): a = lo + rnd() % (hi - lo + 1) b = lo + rnd() % (hi - lo + 1) pairs.append([a, b]) return pairs if kind == "int_pairs_pos": # n pairs [a, b] with lo <= a < b <= hi pairs = [] for _ in range(n): a = lo + rnd() % (hi - lo) b = a + 1 + rnd() % (hi - a) pairs.append([a, b]) return pairs if kind == "staircase": # n - 2, n - 3, ..., 1, 0, 0: every value jumps to just before the last index return [max(0, n - 2 - i) for i in range(n)] if kind == "spike_array": return [spec["value"] if i == spec["at"] else spec["base"] for i in range(n)] if kind == "jobs": # n jobs [deadline, profit] jobs = [] for _ in range(n): deadline = 1 + rnd() % spec["max_deadline"] profit = 1 + rnd() % spec["max_profit"] jobs.append([deadline, profit]) return jobs if kind == "k_sorted": # a sorted list where every value is at most k places from its sorted position items = sorted(lo + rnd() % (hi - lo + 1) for _ in range(n)) size = spec["k"] + 1 for start in range(0, n, size): items[start : start + size] = _shuffle(items[start : start + size], rnd) return items if kind == "stations": # n gas stations [position, fuel] with increasing positions below `target` step = max(1, spec["target"] // (n + 1)) out = [] for i in range(n): position = 1 + i * step + rnd() % step out.append([position, 1 + rnd() % (3 * step)]) return out if kind == "straights": # n groups of `group` consecutive numbers, shuffled; sometimes one card is changed cards = [] for _ in range(n): start = rnd() % 1000 cards.extend(range(start, start + spec["group"])) if cards and rnd() % 3 == 0: cards[rnd() % len(cards)] += 1 return _shuffle(cards, rnd) if kind == "duplicate_array": # n + 1 values from 1..n: a shuffle of 1..n plus one extra copy return _shuffle(list(range(1, n + 1)) + [1 + rnd() % n], rnd) if kind == "car_list": # n cars [position, speed]: different positions (multiples of `step`), speed in lo..hi positions = _shuffle(list(range(n)), rnd) return [[p * spec["step"], lo + rnd() % (hi - lo + 1)] for p in positions] if kind == "rpn": # a valid reverse Polish expression with n operands (values -9..9), never dividing by zero tokens, values, left = [], [], n while left > 0 or len(values) > 1: if len(values) < 2 or (left > 0 and rnd() % 2 == 0): v = rnd() % 19 - 9 tokens.append(str(v)) values.append(v) left -= 1 else: op = "+-*/"[rnd() % 4] b, a = values.pop(), values.pop() if op == "/" and b == 0: op = "+" if op == "*" and abs(a * b) > 10**9: op = "+" if op == "+": r = a + b elif op == "-": r = a - b elif op == "*": r = a * b else: q = abs(a) // abs(b) r = q if (a < 0) == (b < 0) else -q tokens.append(op) values.append(r) return tokens if kind == "path_string": # an absolute Unix path with n names, some of them . or .., maybe a trailing slash names = ["a", "b", "c", "d", ".", "..", ".", "..", "..."] path = "" for _ in range(n): path += "/" * (1 + rnd() % 2) + names[rnd() % len(names)] if not path: path = "/" if rnd() % 4 == 0: path += "/" return path if kind == "nested_encoding": # a valid k[text] string with n top-level items, nested up to 4 levels, counts 1..3 def seq(items, depth): out = [] for _ in range(items): if depth < 4 and rnd() % 3 == 0: count = 1 + rnd() % 3 out.append(str(count) + "[" + seq(1 + rnd() % 3, depth + 1) + "]") else: out.append("".join("abc"[rnd() % 3] for _ in range(1 + rnd() % 2))) return "".join(out) return seq(n, 0) if kind == "stack_ops": # a valid list of operations for a stack with minimum ("min_stack") or a queue ("queue") ops, size = [], 0 for _ in range(n): if spec["kind"] == "min_stack": if size == 0 or rnd() % 5 < 2: ops.append("push " + str(rnd() % 21 - 10)) size += 1 else: r = rnd() % 3 if r == 0: ops.append("pop") size -= 1 else: ops.append("top" if r == 1 else "get_min") else: if size == 0: if rnd() % 2 == 0: ops.append("push " + str(rnd() % 21 - 10)) size += 1 else: ops.append("empty") else: r = rnd() % 5 if r < 2: ops.append("push " + str(rnd() % 21 - 10)) size += 1 elif r == 2: ops.append("pop") size -= 1 else: ops.append("peek" if r == 3 else "empty") return ops if kind == "arith_expr": # n operands 1..hi joined by random operators from `ops`, no spaces parts = [str(1 + rnd() % hi)] for _ in range(n - 1): parts.append(spec["ops"][rnd() % len(spec["ops"])]) parts.append(str(1 + rnd() % hi)) return "".join(parts) if kind == "calc_expr": # n operands 1..hi with + and -, brackets, and minus signs after "(" or at the start def build(k): if k == 1: return str(1 + rnd() % hi) a = 1 + rnd() % (k - 1) left, right = build(a), build(k - a) op = "+" if rnd() % 2 == 0 else "-" if a > 1 and rnd() % 2 == 0: left = "(" + ("-" if rnd() % 6 == 0 else "") + left + ")" if k - a > 1 and (op == "-" or rnd() % 2 == 0): right = "(" + ("-" if rnd() % 6 == 0 else "") + right + ")" return left + op + right text = build(n) return "-" + text if rnd() % 8 == 0 else text if kind in ( "tree_level", "tree_level_distinct", "symmetric_tree", "skew_tree", "tree_preorder", "tree_inorder", "bst_level", "bst_or_not", "bst_swapped", "bst_preorder", "skew_bst", "skew_preorder", ): return _gen_tree(kind, spec, rnd) if kind == "word_list": alphabet = spec["alphabet"] words = [ "".join(alphabet[rnd() % len(alphabet)] for _ in range(spec["length"])) for _ in range(n) ] return words + spec.get("extra", []) if kind == "sparse_blocks": # rows x cols grid of 0 and 1 where `percent` percent of the cells are 1 return [ [1 if rnd() % 100 < spec["percent"] else 0 for _ in range(spec["cols"])] for _ in range(spec["rows"]) ] if kind == "one_zero_matrix": # rows x cols grid of 0 and 1 where `percent` percent are 0 and at least one cell is 0 rows, cols = spec["rows"], spec["cols"] grid = [ [0 if rnd() % 100 < spec["percent"] else 1 for _ in range(cols)] for _ in range(rows) ] if rows and cols: grid[rnd() % rows][rnd() % cols] = 0 return grid if kind == "permutation_grid": rows, cols = spec["rows"], spec["cols"] flat = _shuffle(list(range(rows * cols)), rnd) return [flat[r * cols : (r + 1) * cols] for r in range(rows)] if kind in ("weighted_edges", "positive_edges", "signed_edges"): # n edges [a, b, w] between different nodes of 0..nodes-1: w in 0..max_w, 1..max_w or # -max_w..max_w nodes, max_w = spec["nodes"], spec["max_w"] edges = [] for _ in range(n): a = rnd() % nodes b = rnd() % (nodes - 1) if b >= a: b += 1 if kind == "weighted_edges": w = rnd() % (max_w + 1) elif kind == "positive_edges": w = 1 + rnd() % max_w else: w = rnd() % (2 * max_w + 1) - max_w edges.append([a, b, w]) return edges if kind == "forest_edges": # n edges forming a tree on the nodes 0..n return [[i, rnd() % i] for i in range(1, n + 1)] if kind == "dag_edges": # n directed edges between different nodes that all follow one hidden order, plus (with # probability cycle_chance percent) one reversed copy of a random edge, which makes a cycle nodes = spec["nodes"] rank = _shuffle(list(range(nodes)), rnd) edges = [] for _ in range(n): a = rnd() % nodes b = rnd() % (nodes - 1) if b >= a: b += 1 edges.append([a, b] if rank[a] < rank[b] else [b, a]) if edges and rnd() % 100 < spec["cycle_chance"]: a, b = edges[rnd() % len(edges)] edges.append([b, a]) return edges if kind == "bipartite_edges": # n edges between the even nodes and the odd nodes of 0..nodes-1 half = spec["nodes"] // 2 return [[2 * (rnd() % half), 2 * (rnd() % half) + 1] for _ in range(n)] if kind == "alien_words": # n words sorted by a hidden random alphabet order (sometimes shuffled instead) alphabet = spec["alphabet"] order = _shuffle(list(alphabet), rnd) rank = {ch: i for i, ch in enumerate(order)} words = [ "".join( alphabet[rnd() % len(alphabet)] for _ in range(1 + rnd() % spec["max_len"]) ) for _ in range(n) ] words.sort(key=lambda w: [rank[ch] for ch in w]) if rnd() % 4 == 0: _shuffle(words, rnd) return words if kind == "tree_plus_edge": # a tree on the nodes 1..n plus one more edge, in shuffled order edges = [[1 + rnd() % (i - 1), i] for i in range(2, n + 1)] a = 1 + rnd() % n b = 1 + rnd() % (n - 1) if b >= a: b += 1 edges.append([a, b]) return _shuffle(edges, rnd) if kind == "distinct_cells": # n different cells [x, y] with 0 <= x, y <= limit seen, cells = set(), [] while len(cells) < n: cell = (rnd() % (spec["limit"] + 1), rnd() % (spec["limit"] + 1)) if cell not in seen: seen.add(cell) cells.append([cell[0], cell[1]]) return cells if kind == "equation_list": # n equations such as "a==b" or "c!=d" over the letters of `alphabet` alphabet = spec["alphabet"] out = [] for _ in range(n): a = alphabet[rnd() % len(alphabet)] op = "==" if rnd() % 2 == 0 else "!=" b = alphabet[rnd() % len(alphabet)] out.append(a + op + b) return out if kind == "connected_edges": # a connected weighted graph on 0..nodes-1 (node 0 reaches every node): a random tree with arrows # away from node 0, plus extra edges, up to n edges nodes, max_w = spec["nodes"], spec["max_w"] edges = [[rnd() % i, i, 1 + rnd() % max_w] for i in range(1, nodes)] while len(edges) < n: a = rnd() % nodes b = rnd() % (nodes - 1) if b >= a: b += 1 edges.append([a, b, 1 + rnd() % max_w]) return _shuffle(edges, rnd) if kind == "connected_simple_edges": # a random tree on n nodes plus `extra` more different edges (no repeats), shuffled edges = [[rnd() % i, i] for i in range(1, n)] have = {(a, b) for a, b in edges} for _ in range(spec["extra"]): for _ in range(20): a = rnd() % n b = rnd() % (n - 1) if b >= a: b += 1 low, high = min(a, b), max(a, b) if (low, high) not in have: have.add((low, high)) edges.append([low, high]) break return _shuffle(edges, rnd) if kind == "path_edges": return [[i, i + 1] for i in range(n - 1)] if kind == "triangle": # a triangle of n rows: row i has i + 1 values in lo..hi return [[lo + rnd() % (hi - lo + 1) for _ in range(i + 1)] for i in range(n)] if kind == "jobs3": # n jobs [start, end, profit] with 1 <= start < end <= max_t jobs = [] for _ in range(n): start = 1 + rnd() % (spec["max_t"] - 1) end = start + 1 + rnd() % (spec["max_t"] - start) jobs.append([start, end, 1 + rnd() % spec["max_profit"]]) return jobs if kind == "square_matrix": return [[lo + rnd() % (hi - lo + 1) for _ in range(n)] for _ in range(n)] if kind == "regex_pattern": # n pattern items from `alphabet` (which may contain "."), each followed by "*" 40% of the time out = [] for _ in range(n): out.append(spec["alphabet"][rnd() % len(spec["alphabet"])]) if rnd() % 5 < 2: out.append("*") return "".join(out) if kind == "word_ops": # n operations on a word dictionary: "insert/search/starts w" (kind "trie") or # "add w" and "search pattern" with "." wildcards (kind "dict") ops = [] for _ in range(n): word = "".join( spec["alphabet"][rnd() % len(spec["alphabet"])] for _ in range(1 + rnd() % spec["max_len"]) ) r = rnd() % 3 if spec["kind"] == "trie": ops.append(["insert", "search", "starts"][r] + " " + word) elif r == 0: ops.append("add " + word) else: word = "".join("." if rnd() % 4 == 0 else ch for ch in word) ops.append("search " + word) return ops if kind == "sentence": # n words joined by single spaces words = [ "".join( spec["alphabet"][rnd() % len(spec["alphabet"])] for _ in range(1 + rnd() % spec["max_len"]) ) for _ in range(n) ] return " ".join(words) if kind == "digit_array": # n decimal digits (0-9), the first one not 0 unless there is only one digit out = [rnd() % 10 for _ in range(n)] if n > 1 and out[0] == 0: out[0] = 1 + rnd() % 9 return out if kind == "sorted_int_arrays": # `count` sorted arrays of `n` ints each return [ sorted(lo + rnd() % (hi - lo + 1) for _ in range(n)) for _ in range(spec["count"]) ] if kind == "records": # n [name, score] records: names from `names`, score in [lo, hi] names = spec["names"] return [ [names[rnd() % len(names)], lo + rnd() % (hi - lo + 1)] for _ in range(n) ] if kind == "design_ops": return _gen_design_ops(spec, rnd) raise ValueError("unknown generator: " + kind) def sample_input(spec, rnd): """One random value for a stress/batch spec: an int, a choice, or a generator whose size fields may be {min, max}. Fields are visited in alphabetical order so every language that uses the same PRNG draws the same numbers.""" kind = spec["type"] if kind == "int": return spec["lo"] + rnd() % (spec["hi"] - spec["lo"] + 1) if kind == "choice": return spec["values"][rnd() % len(spec["values"])] gen = dict(spec) for key in sorted(spec): value = spec[key] if isinstance(value, dict) and set(value) == {"min", "max"}: gen[key] = value["min"] + rnd() % (value["max"] - value["min"] + 1) gen["seed"] = rnd() return _gen(gen) def batch_args(problem, batch, index): """The arguments of random case `index` (0-based) in a batch: the same on every run.""" inputs = batch.get("inputs") or problem["stress"]["inputs"] rnd = _mulberry32((batch["seed"] * 100003 + index) & 0xFFFFFFFF) order = [p["name"] for p in problem["function"]["params"]] return {name: sample_input(inputs[name], rnd) for name in order} class _Reads: def __init__(self): self.count = 0 class _CountedList(list): """A list that counts how many values the code reads from it, for cases with maxReads. Reading by index, iterating, slicing, `in`, `.index` and `.count` all count.""" def __init__(self, items, reads): super().__init__(items) self._reads = reads def __getitem__(self, index): if isinstance(index, slice): self._reads.count += len(range(*index.indices(len(self)))) else: self._reads.count += 1 return list.__getitem__(self, index) def __iter__(self): for value in list.__iter__(self): self._reads.count += 1 yield value def __reversed__(self): for value in list.__reversed__(self): self._reads.count += 1 yield value def __contains__(self, value): self._reads.count += len(self) return list.__contains__(self, value) def index(self, *args): self._reads.count += len(self) return list.index(self, *args) def count(self, value): self._reads.count += len(self) return list.count(self, value) def _counted(value, reads): if not isinstance(value, list): return value if value and isinstance(value[0], list): value = [_counted(row, reads) for row in value] return _CountedList(value, reads) def _materialize(value): if isinstance(value, dict) and "$gen" in value: return _gen(value["$gen"]) return copy.deepcopy(value) class ListNode: """The node class used when the student's file does not define its own `ListNode`.""" def __init__(self, val=0, next=None): self.val = val self.next = next def _build_list(node_class, spec, built): """A linked list from JSON: a list of values, or {"values": [...], "cycle": k} (the tail points back at node k) or {"values": [...], "join": {"param": "a", "index": k}} (the tail points at node k of the list already built for parameter "a"; with no values of its own, the head is that node). Returns (head, nodes it made).""" values = _materialize(spec["values"] if isinstance(spec, dict) else spec) nodes = [node_class(value) for value in values] for left, right in zip(nodes, nodes[1:]): left.next = right tail = None if isinstance(spec, dict): if nodes and spec.get("cycle", -1) >= 0: nodes[-1].next = nodes[spec["cycle"]] join = spec.get("join") if join and join["index"] >= 0: tail = built[join["param"]][join["index"]] if nodes: nodes[-1].next = tail return (nodes[0] if nodes else tail), nodes def _prepare(problem, fn, raw): """The arguments to call fn with. Parameters of type ListNode or TreeNode become linked lists and trees made from the student's own ListNode or TreeNode class (or the ones above). Returns (arguments, nodes), where nodes maps each ListNode parameter to its list of nodes.""" params = problem["function"]["params"] kinds = ("ListNode", "list[ListNode]", "TreeNode") if not any(p["type"] in kinds for p in params): return raw, None scope = getattr(fn, "__globals__", {}) args, built = dict(raw), {} for p in params: if p["type"] == "ListNode": args[p["name"]], built[p["name"]] = _build_list( scope.get("ListNode", ListNode), raw[p["name"]], built ) elif p["type"] == "list[ListNode]": node_class = scope.get("ListNode", ListNode) lists = [_build_list(node_class, spec, built) for spec in raw[p["name"]]] args[p["name"]] = [head for head, _ in lists] elif p["type"] == "TreeNode": args[p["name"]] = _build_tree( scope.get("TreeNode", TreeNode), raw[p["name"]] ) return args, built def _list_values(head): values, seen = [], set() while head is not None: if id(head) in seen: raise AssertionError( "Your answer is a list that loops back on itself. Check the last next pointer." ) seen.add(id(head)) values.append(head.val) head = head.next return values def _finish(problem, actual, built): """The answer as plain JSON: a returned ListNode becomes its list of values, and a returned ListNodeRef becomes its position in the first list parameter (-1 for None).""" kind = problem["function"]["returns"] if kind == "TreeNode": return _tree_list(actual) if kind == "TreeNodeVal": return None if actual is None else actual.val if kind == "ListNode": return _list_values(actual) if kind == "ListNodeRef": if actual is None: return -1 first = next(iter(built.values())) for index, node in enumerate(first): if node is actual: return index raise AssertionError( "The node you returned is not a node of the list you were given." ) return actual def call_fn(problem, fn, raw): """Run fn on JSON inputs and return the answer as JSON (used by the authoring tools).""" args, built = _prepare(problem, fn, raw) order = [p["name"] for p in problem["function"]["params"]] return _finish(problem, fn(*[args[name] for name in order]), built) def _without_digit_limit(call): # Python 3.11+ refuses to turn an int with more than 4300 digits into text, or text into # one. Answers like fibonacci(50000) are bigger, so lift the limit just for this call. old = sys.get_int_max_str_digits() sys.set_int_max_str_digits(0) try: return call() finally: sys.set_int_max_str_digits(old) def _dumps(x, **kwargs): return _without_digit_limit(lambda: json.dumps(x, **kwargs)) def _canon(x): return _without_digit_limit(lambda: json.loads(json.dumps(x))) def _digest(x): return hashlib.sha256( _dumps(_canon(x), separators=(",", ":")).encode() ).hexdigest()[:16] def _short(x, limit=160): text = _dumps(_canon(x)) return ( text if len(text) <= limit else text[:limit] + "... (" + str(len(text)) + " chars)" ) def _same(actual, expected, compare, tolerance): actual, expected = _canon(actual), _canon(expected) if compare == "float": if isinstance(expected, list): return len(actual) == len(expected) and all( abs(a - e) <= tolerance for a, e in zip(actual, expected) ) return abs(actual - expected) <= tolerance if compare == "unordered": def key(v): return _dumps(v, sort_keys=True) return sorted(actual, key=key) == sorted(expected, key=key) return actual == expected def _as_type(value, kind): """A whole number printed by another language (2) is the float the question returns (2.0). Python keeps the two apart when it hashes an answer, so the type the question declares decides.""" if kind == "float": return float(value) if isinstance(value, int) and not isinstance(value, bool) else value if kind.startswith("list[") and isinstance(value, list): return [_as_type(v, kind[5:-1]) for v in value] return value def _external_answer(case, index): """What the other language answered for one call: (answer, milliseconds, reads or None).""" record = EXTERNAL["outputs"].get(case["id"] + ":" + str(index)) if record is None: if EXTERNAL["stopped"]: raise AssertionError("Skipped: an earlier test did not finish, so this one was not run.") EXTERNAL["stopped"] = True raise AssertionError( "Time limit exceeded: your program did not finish this test, so it was stopped. " "Look for an infinite loop, or a much faster approach." ) if record.get("unsupported"): raise Skipped("Skipped: " + record["unsupported"]) if record.get("skip"): raise AssertionError("Skipped: an earlier performance test was already too slow.") if "error" in record: if record.get("fatal"): EXTERNAL["stopped"] = True raise AssertionError("Runtime error: " + str(record["error"])) kind = EXTERNAL["returns"] # A language with 64-bit integers sends the answer as JSON text, because a number bigger than 2^53 does # not survive being a JavaScript number on the way here. out = json.loads(record["outJson"]) if "outJson" in record else record["out"] return _as_type(out, kind), float(record.get("ms", 0)), record.get("reads") def external_note(text): if text not in EXTERNAL["notes"]: EXTERNAL["notes"].append(text) def _check_batch(problem, case, fn): """Many small seeded random cases in one test. Each answer is checked against a short digest stored in the file, so hundreds of cases cost about 1 KB.""" batch = case["batch"] order = [p["name"] for p in problem["function"]["params"]] limit_ms = case.get("limitMs", problem.get("limits", {}).get("timeMs", 2000)) elapsed_ms = 0.0 for index, expected in enumerate(case["digests"]): args = batch_args(problem, batch, index) if EXTERNAL["outputs"] is not None: actual, took, _ = _external_answer(case, index) elapsed_ms += took else: call_args, built = _prepare(problem, fn, copy.deepcopy(args)) started = time.perf_counter() actual = fn(*[call_args[name] for name in order]) elapsed_ms += (time.perf_counter() - started) * 1000.0 actual = _finish(problem, actual, built) if _digest(actual)[: len(expected)] != expected: raise AssertionError( "Wrong answer on random case " + str(index + 1) + " of " + str(len(case["digests"])) + ".\nInput: " + ", ".join(name + " = " + _short(args[name]) for name in order) + "\nGot: " + _short(actual) ) if elapsed_ms > limit_ms: raise AssertionError( "Time limit exceeded: the random cases took " + str(int(elapsed_ms)) + " ms, the limit is " + str(int(limit_ms)) + " ms." ) return elapsed_ms def check_case(problem, case, fn): """Run one case. Raises AssertionError with a student-facing message on failure.""" if "batch" in case: return _check_batch(problem, case, fn) args = {name: _materialize(value) for name, value in case["input"].items()} order = [p["name"] for p in problem["function"]["params"]] limit_ms = case.get("limitMs", problem.get("limits", {}).get("timeMs", 2000)) show = case.get("visible", False) perf = case.get("perf", False) if perf and STATE["slow"]: raise AssertionError( "Skipped: an earlier performance test was already too slow." ) external = EXTERNAL["outputs"] is not None reads = _Reads() if "maxReads" in case and not external else None if reads: args = {name: _counted(value, reads) for name, value in args.items()} if external: actual, elapsed_ms, external_reads = _external_answer(case, 0) else: call_args, built = _prepare(problem, fn, args) started = time.perf_counter() actual = fn(*[call_args[name] for name in order]) elapsed_ms = (time.perf_counter() - started) * 1000.0 actual = _finish(problem, actual, built) if "digest" in case: ok = _digest(actual) == case["digest"] expected_text = "(large output, not shown)" else: ok = _same( actual, case["expected"], problem.get("compare", "exact"), problem.get("tolerance", 1e-9), ) expected_text = _short(case["expected"]) if not ok: if show: raise AssertionError( "Wrong answer.\nInput: " + ", ".join(name + " = " + _short(args[name]) for name in order) + "\nExpected: " + expected_text + "\nGot: " + _short(actual) ) raise AssertionError("Wrong answer on a hidden test case.") read_count = external_reads if external else (reads.count if reads else None) if external and "maxReads" in case and read_count is None: external_note( "This language cannot count how many values your code reads, so the tests with a read limit " "only checked that the answer is right. Python and JavaScript check the limit too." ) if read_count is not None and "maxReads" in case and read_count > case["maxReads"]: raise AssertionError( "Right answer, but too many reads: your code read the list " + str(read_count) + " times and the limit is " + str(case["maxReads"]) + ". Reading every value is not allowed here: halve the search range each step (binary search)." ) if elapsed_ms > limit_ms: if perf: STATE["slow"] = True raise AssertionError( "Time limit exceeded: took " + str(int(elapsed_ms)) + " ms, the limit is " + str(int(limit_ms)) + " ms. The answer is right but too slow: look for a faster approach." ) return elapsed_ms def load_problem(text): return json.loads(text) def _wire_list(spec, built): """A ListNode argument in the one shape every language reads: its values, where the tail loops back to (-1 for nowhere), and where it joins another parameter's list (or None).""" values = _wire_value(_materialize(spec["values"] if isinstance(spec, dict) else spec)) spec = spec if isinstance(spec, dict) else {} return {"values": values, "cycle": spec.get("cycle", -1), "join": spec.get("join")} _SAFE_INT = 2**53 - 1 def _wire_value(value): """JSON for another language: an integer a JavaScript number cannot hold exactly is sent as {"$int": "digits"}.""" if isinstance(value, bool): return value if isinstance(value, int): return {"$int": str(value)} if abs(value) > _SAFE_INT else value if isinstance(value, list): return [_wire_value(v) for v in value] return value def _wire_args(problem, args): """The arguments of one call as plain JSON, in parameter order. Everything is already plain JSON except linked lists (see _wire_list). Trees are level-order lists with None for a missing child.""" out = [] for p in problem["function"]["params"]: value = args[p["name"]] if p["type"] == "ListNode": value = _wire_list(value, None) elif p["type"] == "list[ListNode]": value = [_wire_list(spec, None) for spec in value] out.append(_wire_value(value) if p["type"] not in ("ListNode", "list[ListNode]") else value) return out def _largest_int(value): """The biggest absolute integer anywhere inside a JSON value (0 if there are none).""" if isinstance(value, bool): return 0 if isinstance(value, int): return abs(value) if isinstance(value, list): return max((_largest_int(v) for v in value), default=0) if isinstance(value, dict): return max((_largest_int(v) for v in value.values()), default=0) return 0 def external_prepare(problem, limit=None, max_int=None): """Every call the tests make, in the order the tests run, for a language that is not Python. `limit` is the number of tests to prepare (Run uses the first few), and `max_int` the largest integer that language can hold exactly: a call that needs a bigger one is marked unsupported, not wrong.""" params = problem["function"]["params"] cases = problem["cases"][:limit] if limit else problem["cases"] calls = [] for case in cases: limit_ms = case.get("limitMs", problem.get("limits", {}).get("timeMs", 2000)) if "batch" in case: sources = [ (index, batch_args(problem, case["batch"], index)) for index in range(len(case["digests"])) ] else: sources = [(0, {name: _materialize(value) for name, value in case["input"].items()})] # A digest has no expected answer to look at; an ordinary case does, and it can need a big integer too. expected_big = _largest_int(case["expected"]) if "expected" in case else 0 for index, args in sources: call = { "key": case["id"] + ":" + str(index), "case": case["id"], "index": index, "args": _wire_args(problem, args), "limitMs": limit_ms, "perf": bool(case.get("perf", False)), "reads": "maxReads" in case, "batch": "batch" in case, } biggest = max(expected_big, max((_largest_int(v) for v in args.values()), default=0)) if max_int is not None and biggest > max_int: call["unsupported"] = ( "this test uses numbers bigger than this language can hold exactly, so it was not run." ) calls.append(call) return { "function": problem["function"], "compare": problem.get("compare", "exact"), "calls": calls, } _PROBLEM = load_problem("{\n \"schema\": 1,\n \"function\": {\n \"name\": \"count_halving_steps\",\n \"params\": [\n {\n \"name\": \"n\",\n \"type\": \"int\"\n }\n ],\n \"returns\": \"int\"\n },\n \"limits\": {\n \"timeMs\": 1000\n },\n \"hints\": [\n \"Write `n` in binary. What does `n // 2` do to it?\",\n \"Each halving removes one binary digit. The loop stops at a single digit.\",\n \"Python has `int.bit_length()`.\"\n ],\n \"cases\": [\n {\"id\": \"example_1\", \"visible\": true, \"input\": {\"n\": 8}, \"expected\": 3},\n {\"id\": \"example_2\", \"visible\": true, \"input\": {\"n\": 1000}, \"expected\": 9},\n {\"id\": \"case_1\", \"input\": {\"n\": 1}, \"expected\": 0},\n {\"id\": \"case_2\", \"input\": {\"n\": 2}, \"expected\": 1},\n {\"id\": \"case_3\", \"input\": {\"n\": 3}, \"expected\": 1},\n {\"id\": \"case_4\", \"input\": {\"n\": 7}, \"expected\": 2},\n {\"id\": \"case_5\", \"input\": {\"n\": 15}, \"expected\": 3},\n {\"id\": \"case_6\", \"input\": {\"n\": 16}, \"expected\": 4},\n {\"id\": \"case_7\", \"input\": {\"n\": 17}, \"expected\": 4},\n {\"id\": \"case_8\", \"input\": {\"n\": 1099511627776}, \"expected\": 40},\n {\"id\": \"case_9\", \"input\": {\"n\": 1099511627775}, \"expected\": 39},\n {\"id\": \"random_batch\", \"batch\": {\"count\": 300, \"seed\": 1}, \"digests\": [\"19581e\", \"4fc82b\", \"2c6242\", \"790269\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"6b51d4\", \"2c6242\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4a44dc\", \"4fc82b\", \"6b51d4\", \"19581e\", \"4fc82b\", \"6b51d4\", \"2c6242\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"19581e\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"6b51d4\", \"4a44dc\", \"6b51d4\", \"4a44dc\", \"4a44dc\", \"790269\", \"6b51d4\", \"4fc82b\", \"6b51d4\", \"6b51d4\", \"4fc82b\", \"19581e\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"4a44dc\", \"e7f6c0\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"6b51d4\", \"4fc82b\", \"6b51d4\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"19581e\", \"790269\", \"6b51d4\", \"4fc82b\", \"790269\", \"4fc82b\", \"4a44dc\", \"19581e\", \"4a44dc\", \"2c6242\", \"19581e\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"19581e\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"6b51d4\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4fc82b\", \"6b51d4\", \"6b51d4\", \"19581e\", \"4a44dc\", \"6b51d4\", \"4a44dc\", \"4a44dc\", \"4fc82b\", \"2c6242\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"19581e\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"790269\", \"19581e\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4fc82b\", \"6b51d4\", \"6b51d4\", \"4a44dc\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"2c6242\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"6b51d4\", \"4a44dc\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"790269\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"4a44dc\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"4a44dc\", \"2c6242\", \"4fc82b\", \"6b51d4\", \"19581e\", \"4a44dc\", \"790269\", \"e7f6c0\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4fc82b\", \"4a44dc\", \"6b51d4\", \"4fc82b\", \"19581e\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"2c6242\", \"4fc82b\", \"4a44dc\", \"4a44dc\", \"2c6242\", \"4a44dc\", \"4b2277\", \"6b51d4\", \"4fc82b\", \"2c6242\", \"2c6242\", \"4fc82b\", \"4a44dc\", \"4a44dc\", \"19581e\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"ef2d12\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"2c6242\", \"4a44dc\", \"790269\", \"4fc82b\", \"e7f6c0\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"19581e\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"19581e\", \"4fc82b\", \"2c6242\", \"6b51d4\", \"4fc82b\", \"4a44dc\", \"6b51d4\", \"4fc82b\", \"2c6242\", \"6b51d4\", \"6b51d4\", \"19581e\", \"4fc82b\", \"19581e\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"2c6242\", \"4fc82b\", \"4a44dc\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"19581e\", \"6b51d4\", \"4a44dc\", \"790269\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"19581e\", \"19581e\", \"6b51d4\", \"4a44dc\", \"6b51d4\", \"6b51d4\", \"6b51d4\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"2c6242\", \"6b51d4\", \"4fc82b\", \"4a44dc\", \"2c6242\", \"19581e\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"6b51d4\", \"4fc82b\", \"4a44dc\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"6b51d4\", \"4fc82b\", \"4fc82b\", \"6b51d4\", \"4fc82b\", \"ef2d12\", \"19581e\", \"4fc82b\", \"4fc82b\", \"19581e\", \"4a44dc\"]},\n {\"id\": \"perf_1\", \"perf\": true, \"input\": {\"n\": 1000000000000000000}, \"expected\": 59},\n {\"id\": \"perf_2\", \"perf\": true, \"input\": {\"n\": 576460752303423488}, \"expected\": 59}\n ],\n \"stress\": {\"runs\": 200, \"inputs\": {\"n\": {\"type\": \"int\", \"lo\": 1, \"hi\": 5000}}}\n}\n") _FUNCTION_NAME = _PROBLEM["function"]["name"] def _make_test(index): def run(): fn = globals().get(_FUNCTION_NAME) if not callable(fn): raise AssertionError("Define a function named " + _FUNCTION_NAME + ".") check_case(_PROBLEM, _PROBLEM["cases"][index], fn) return run test_01_example_1 = _make_test(0) test_02_example_2 = _make_test(1) test_03_case_1 = _make_test(2) test_04_case_2 = _make_test(3) test_05_case_3 = _make_test(4) test_06_case_4 = _make_test(5) test_07_case_5 = _make_test(6) test_08_case_6 = _make_test(7) test_09_case_7 = _make_test(8) test_10_case_8 = _make_test(9) test_11_case_9 = _make_test(10) test_12_random_batch = _make_test(11) test_13_perf_1 = _make_test(12) test_14_perf_2 = _make_test(13) def _call_test(fn): import inspect parameters = list(inspect.signature(fn).parameters) if not parameters: return fn() unsupported = [name for name in parameters if name != "tmp_path"] if unsupported: raise TypeError( "pytest fixture " + repr(unsupported[0]) + " is not available in the in-browser test runner" ) import shutil import tempfile from pathlib import Path directory = tempfile.mkdtemp() try: return fn(Path(directory)) finally: shutil.rmtree(directory, ignore_errors=True) def run_tests(limit=None): _test_fns = sorted( (name, fn) for name, fn in globals().items() if name.startswith("test_") and callable(fn) ) if limit is not None: _test_fns = _test_fns[:limit] tests = [] for name, fn in _test_fns: try: _call_test(fn) tests.append({"name": name, "passed": True, "error": None}) except Exception as e: if getattr(e, "skipped", False): tests.append({"name": name, "passed": True, "skipped": True, "error": str(e).strip()}) continue import linecache import traceback detail = str(e).strip() if isinstance(e, AssertionError): reason = "Assertion failed: " + detail if detail else "Assertion failed; the expected condition was false." else: reason = type(e).__name__ + (": " + detail if detail else "") frames = traceback.extract_tb(e.__traceback__) frame = next((item for item in reversed(frames) if item.name == name), None) if frame: source = linecache.getline(frame.filename, frame.lineno).strip() if source: reason += "\nLine " + str(frame.lineno) + ": " + source tests.append({"name": name, "passed": False, "error": reason}) return tests

Halving Steps

Examples

Constraints

Theory

Keywords