Volt
bab4431884
The module had no cell in any gate, and read two ways: its docstring promised
ValueError for 'no duplicate present' while its self-test said it does not
promise detection at all. Measured at 95e4962: every array of length n+1 over
1..n for n=1..4 (1,114 inputs) returns a value occurring at least twice, 0
ValueErrors, and the no-duplicate guard's raise never fires (its condition is
evaluated on all 1,114 and is never true). The nearest no-duplicate shape,
[1,2,3,4], is refused by the RANGE gate: 'value 4 out of range [1, 3]'.
- find_duplicate.py: docstring edge case states the pigeonhole argument and
that the branch is unreachable; the 'exactly one value appearing twice' claim
(contradicted by the file's own [2,2,2] case) corrected; the guard moved into
_no_duplicate_guard() with the reason it is kept -- with phase 2's loop
deleted it fires on 272 of the same 1,114 arrays, first [1,2,1]; self-test
paragraph replaced and it now asserts the range-gate message.
- test_find_duplicate.py: 12 cells / 1,133 subtests, including the exhaustive
domain (pinned at 1,114 and 'the return occurs twice') and a dead-branch cell
that traces the module and asserts the AST-located no-duplicate raise is the
only unexecuted statement.
- Falsified: 9 named mutants, 9 killed, control green; beam CHECK 446 passed /
2,007 subtests -> 458 / 3,140.
125 lines
4.6 KiB
Python
125 lines
4.6 KiB
Python
"""Find a duplicate in an array of n+1 integers each in [1, n].
|
|
|
|
Classic Floyd's tortoise-and-hare on the implicit linked list defined by
|
|
f(i) = nums[i]. Guarantees O(n) time, O(1) extra space, and does not
|
|
mutate the input. Returns a duplicated value; when several values repeat,
|
|
returns one of them (the entry point of the cycle reachable from index 0).
|
|
|
|
Edge cases handled:
|
|
- len(nums) < 2 -> ValueError
|
|
- values out of [1, n], or not a plain int (bool and float included)
|
|
-> ValueError
|
|
- no duplicate present -> unreachable, and therefore never raised:
|
|
a no-duplicate array cannot satisfy both preconditions at once. With
|
|
len(nums) = n + 1 values drawn from 1..n, pigeonhole forces a repeat;
|
|
the only arrays that avoid one are shorter than n + 1 or carry a value
|
|
outside 1..n, and both are refused by the gates above before Floyd
|
|
runs (see `_no_duplicate_guard()`). The count check after phase 2 is
|
|
kept as an invariant, not as a handler: an entry node has two distinct
|
|
predecessors by definition, so its value occurs at least twice.
|
|
"""
|
|
from typing import List
|
|
|
|
|
|
def _no_duplicate_guard(candidate: int, nums: List[int]) -> int:
|
|
"""Invariant: the phase-2 entrance value is duplicated, or raise.
|
|
|
|
Unreachable on validated input (see the module docstring). It is here so
|
|
that an edit which widens the gates above -- or shortens phase 2, the other
|
|
half of the argument -- fails loudly instead of returning a value as if it
|
|
were a duplicate. Measured: the raise fires 0 times over every validated
|
|
input for n = 1..4, and it *does* fire when phase 2's loop is deleted, which
|
|
is the edit it exists for. `test_find_duplicate.py` pins that this is the
|
|
module's only unexecuted line, so removing it, or growing new dead code
|
|
beside it, moves a cell.
|
|
"""
|
|
if nums.count(candidate) < 2:
|
|
raise ValueError("no duplicate present in nums")
|
|
return candidate
|
|
|
|
|
|
def find_duplicate(nums: List[int]) -> int:
|
|
n = len(nums) - 1
|
|
if n < 1:
|
|
raise ValueError("nums must contain at least 2 elements")
|
|
for v in nums:
|
|
if not isinstance(v, int) or isinstance(v, bool) or v < 1 or v > n:
|
|
raise ValueError(f"value {v!r} out of range [1, {n}]")
|
|
|
|
# Phase 1: find meeting point inside the cycle.
|
|
slow = nums[0]
|
|
fast = nums[nums[0]]
|
|
while slow != fast:
|
|
slow = nums[slow]
|
|
fast = nums[nums[fast]]
|
|
|
|
# Phase 2: find cycle entrance = duplicate.
|
|
slow2 = 0
|
|
while slow2 != slow:
|
|
slow2 = nums[slow2]
|
|
slow = nums[slow]
|
|
# Floyd alone would return an entrance value even for a permutation; the
|
|
# guard below states the invariant that the range gates make that
|
|
# impossible. It is a proof checkpoint, not a scenario handler.
|
|
return _no_duplicate_guard(slow, nums)
|
|
|
|
|
|
def _self_test() -> None:
|
|
import random
|
|
|
|
# Known duplicates.
|
|
cases = [
|
|
([1, 3, 4, 2, 2], 2),
|
|
([3, 1, 3, 4, 2], 3),
|
|
([1, 1], 1),
|
|
([2, 2, 2], 2), # value appearing 3x still reports 2
|
|
([1, 2, 3, 4, 5, 5], 5),
|
|
]
|
|
for nums, expected in cases:
|
|
got = find_duplicate(nums)
|
|
assert got == expected, (nums, got, expected)
|
|
|
|
# Randomized: inject one duplicate into a permutation.
|
|
rng = random.Random(42)
|
|
for trial in range(200):
|
|
n = rng.randint(1, 40)
|
|
base = list(range(1, n + 1))
|
|
dup = rng.randint(1, n)
|
|
base.append(dup)
|
|
rng.shuffle(base)
|
|
assert find_duplicate(base) == dup, (base, dup)
|
|
|
|
# Input must not be mutated.
|
|
original = [1, 3, 4, 2, 2]
|
|
snapshot = list(original)
|
|
find_duplicate(original)
|
|
assert original == snapshot
|
|
|
|
# Error cases.
|
|
for bad in ([], [1], [0, 1], [1, 3], [1, 2, 3, 4], [True, 1]):
|
|
try:
|
|
find_duplicate(bad)
|
|
except ValueError:
|
|
pass
|
|
else:
|
|
raise AssertionError(f"expected ValueError for {bad!r}")
|
|
|
|
# The no-duplicate case never reaches Floyd: a permutation of 1..n has
|
|
# length n, which is one short of a valid input, so the range gate
|
|
# refuses it with an out-of-range message. The `no duplicate present`
|
|
# branch cannot fire on any validated input -- pinned as the module's
|
|
# only unexecuted line in test_find_duplicate.py.
|
|
for permutation in ([1, 2, 3, 4], [2, 1], [1, 2, 3]):
|
|
try:
|
|
find_duplicate(list(permutation))
|
|
except ValueError as exc:
|
|
assert "out of range" in str(exc), (permutation, exc)
|
|
else:
|
|
raise AssertionError(f"expected ValueError for {permutation!r}")
|
|
|
|
print("ALL TESTS PASSED")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
_self_test()
|