import Mathlib /-! # Most Stones Removed With Same Row Or Column On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed. Given an array stones of length n where stones[i] = [x_i, y_i] represents the location of the ith stone, return the largest possible number of stones that can be removed. ## Constraints - 1 <= stones.length <= 1000 - 0 <= x_i, y_i <= 10^4 - No two stones are at the same coordinate point. ## Provided examples - `stones = [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]` → `3` - `stones = [[0, 0]]` → `0` - `stones = [[1, 2], [2, 3], [3, 4]]` → `0` ## Synthesized negative examples - invalid input: `stones = []` ([structural] a predicate that admits 1 <= stones.length <= 1000. empty where at least one stone is required.) - invalid input: `stones = [[10001, 0]]` ([structural] a predicate that admits 0 <= xi, yi <= 10^4. x one past stated maximum; a predicate checking only nonnegativity accepts it.) - invalid input: `stones = [[0, 0], [0, 0]]` ([structural] a predicate that admits No two stones are at the same coordinate point.. a predicate that checks bounds but not uniqueness accepts it.) - `stones = [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]` → `4` is wrong ([structural] removed stones are allowed to count as the other stone. Four in one component removed; isolated stone remains) - `stones = [[0, 0]]` → `1` is wrong ([structural] allows a stone to count itself as the other stone in the same row or column. Dropping 'another' makes the single stone removable) - `stones = [[1, 2], [2, 3], [3, 4]]` → `1` is wrong ([structural] no removal is possible, so any positive answer is unreachable. no stone shares a row or column) -/ namespace PMostStonesRemovedWithSameRowOrColumn abbrev Input := List (Nat × Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- Maps each serialized row `[xi, yi]` to a coordinate pair; malformed rows map to the origin. -/ def stonesBridge (rows : List (List Nat)) : List (Nat × Nat) := rows.map fun | [x, y] => (x, y) | _ => (0, 0) /-- `order` is a valid removal order for `stones`: each removed stone belongs to `stones`, was not removed earlier, and shares its row or column with a different stone of `stones` not yet removed. -/ def IsRemovalOrder (stones order : List (Nat × Nat)) : Prop := ∀ i : Nat, ∀ h : i < order.length, order[i]'h ∈ stones ∧ order[i]'h ∉ order.take i ∧ ∃ other : Nat × Nat, other ∈ stones ∧ other ∉ order.take i ∧ other ≠ order[i]'h ∧ (other.1 = (order[i]'h).1 ∨ other.2 = (order[i]'h).2) /-! ### Validity predicate (V) -/ /-- Valid input: between 1 and 1000 stones, all coordinates at most 10^4, and no two stones at the same point. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 1000 && input.all (fun p => p.1 ≤ 10000 && p.2 ≤ 10000) && decide input.Nodup /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest number of stones removable by any valid removal order for `input`: some order removes `result` stones and no order removes more. -/ def maxRemovableStones_spec (input : Input) (result : Output) : Prop := IsGreatest {n : Nat | ∃ order : List (Nat × Nat), IsRemovalOrder input order ∧ order.length = n} result /-! ### Decidable specification (P_check) -/ /-- Decidable form of `IsRemovalOrder` for a concrete order: each position's conditions mirror the specification, with the witness `other` searched within `stones`. -/ def isRemovalOrderB (stones order : List (Nat × Nat)) : Bool := (List.finRange order.length).all fun i => decide (order.get i ∈ stones) && decide (order.get i ∉ order.take i.val) && stones.any fun other => decide (other ∉ order.take i.val) && decide (other ≠ order.get i) && decide (other.1 = (order.get i).1 ∨ other.2 = (order.get i).2) /-- Some permutation of `stones` has a valid prefix of length `k`; valid orders, being injective lists over the stones, arise exactly as such prefixes. -/ def hasValidOrderOfLen (stones : List (Nat × Nat)) (k : Nat) : Bool := decide (k ≤ stones.length) && stones.permutations.any fun perm => isRemovalOrderB stones (perm.take k) /-- Executable checker for `maxRemovableStones_spec`: `result` is achievable and no achievable length up to `input.length` exceeds it. -/ def maxRemovableStones_check (input : Input) (result : Output) : Bool := hasValidOrderOfLen input result && !(List.range (input.length + 1)).any fun n => decide (result < n) && hasValidOrderOfLen input n theorem root_of_bridges (bridge : ∀ (s : Input) (k : Nat), hasValidOrderOfLen s k = true ↔ ∃ o, IsRemovalOrder s o ∧ o.length = k) (input : Input) (result : Output) : maxRemovableStones_check input result ↔ maxRemovableStones_spec input result := by have bound (o : Input) (ho : IsRemovalOrder input o) : o.length ≤ input.length := by have hb := (bridge input o.length).mpr ⟨o, ho, rfl⟩ simp only [hasValidOrderOfLen, Bool.and_eq_true, decide_eq_true_eq] at hb exact hb.1 simp only [maxRemovableStones_check, Bool.and_eq_true, Bool.not_eq_true', Bool.eq_false_iff, ne_eq, List.any_eq_true, List.mem_range, decide_eq_true_eq, bridge, maxRemovableStones_spec, IsGreatest, upperBounds, Set.mem_setOf_eq] constructor · rintro ⟨hr, hmax⟩ refine ⟨hr, ?_⟩ rintro n ⟨o, ho, hn⟩ have hb := bound o ho by_contra hle apply hmax exact ⟨n, Nat.lt_succ_of_le (hn ▸ hb), Nat.lt_of_not_ge hle, o, ho, hn⟩ · rintro ⟨hr, hmax⟩ refine ⟨hr, ?_⟩ rintro ⟨n, hn, hlt, o, ho, hl⟩ exact Nat.not_lt_of_ge (hmax ⟨o, ho, hl⟩) hlt theorem removal_bool (s o : Input) : isRemovalOrderB s o = true ↔ IsRemovalOrder s o := by simp only [isRemovalOrderB, List.all_eq_true, List.mem_finRange, forall_true_left, Bool.and_eq_true, decide_eq_true_eq, List.any_eq_true, List.get_eq_getElem, IsRemovalOrder] constructor · intro h i hi have hh := h ⟨i, hi⟩ simpa only [and_assoc] using hh · intro h i simpa only [and_assoc] using h i.val i.isLt theorem removal_subperm (s o : Input) (h : IsRemovalOrder s o) : List.Subperm o s := by have hn : o.Nodup := by rw [List.nodup_iff_pairwise_ne, List.pairwise_iff_getElem] intro i j hi hj hij heq apply (h j hj).2.1 apply List.mem_take_iff_getElem.mpr exact ⟨i, by omega, heq⟩ apply hn.subperm intro a ha obtain ⟨i, hi, rfl⟩ := List.mem_iff_getElem.mp ha exact (h i hi).1 theorem orders_bridge (s : Input) (k : Nat) : hasValidOrderOfLen s k = true ↔ ∃ o, IsRemovalOrder s o ∧ o.length = k := by simp only [hasValidOrderOfLen, Bool.and_eq_true, decide_eq_true_eq, List.any_eq_true, List.mem_permutations, removal_bool] constructor · rintro ⟨hk, p, hp, ho⟩ refine ⟨p.take k, ho, ?_⟩ rw [List.length_take, hp.length_eq, Nat.min_eq_left hk] · rintro ⟨o, ho, rfl⟩ have hs := removal_subperm s o ho refine ⟨hs.length_le, ?_⟩ obtain ⟨p, hp, hop⟩ := List.subperm_iff.mp hs obtain ⟨t, ht⟩ := hop.exists_perm_append refine ⟨o ++ t, ht.symm.trans hp, ?_⟩ simpa only [List.take_left] using ho /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxRemovableStones_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxRemovableStones_check input result ↔ maxRemovableStones_spec input result := by exact root_of_bridges orders_bridge input result /-! ### Implementation helpers -/ /-- Whether `stone` shares a row or a column with some stone in `group`. -/ def touchesGroup (stone : Nat × Nat) (group : List (Nat × Nat)) : Bool := group.any fun s => s.1 = stone.1 || s.2 = stone.2 /-- Folds `stone` into the component groups: every group it touches is merged with it into a single group. -/ def mergeIntoGroups (stone : Nat × Nat) (groups : List (List (Nat × Nat))) : List (List (Nat × Nat)) := (stone :: (groups.filter (touchesGroup stone)).flatten) :: groups.filter (fun g => !(touchesGroup stone g)) /-- The number of connected components of the row/column graph on `stones`, by folding each stone into the groups it touches. -/ def countComponents (stones : Input) : Nat := (stones.foldl (fun groups stone => mergeIntoGroups stone groups) []).length /-! ### Main algorithm (impl) -/ /-- Maximum removable stones: the stone count minus the number of connected components of the row/column graph, counted by a one-pass group merge in O(n^2). -/ def removeStones (input : Input) : Output := input.length - countComponents input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem removeStones_correct (input : Input) (h : isValidInput input) : maxRemovableStones_spec input (removeStones input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (stonesBridge [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]) #guard isValidInput (stonesBridge [[0, 0]]) #guard isValidInput (stonesBridge [[1, 2], [2, 3], [3, 4]]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (stonesBridge [])) #guard !(isValidInput (stonesBridge [[10001, 0]])) #guard !(isValidInput (stonesBridge [[0, 0], [0, 0]])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxRemovableStones_check (stonesBridge [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]) 3 #guard maxRemovableStones_check (stonesBridge [[0, 0]]) 0 #guard maxRemovableStones_check (stonesBridge [[1, 2], [2, 3], [3, 4]]) 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxRemovableStones_check (stonesBridge [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]) 4) #guard !(maxRemovableStones_check (stonesBridge [[0, 0]]) 1) #guard !(maxRemovableStones_check (stonesBridge [[1, 2], [2, 3], [3, 4]]) 1) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard removeStones (stonesBridge [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]) == 3 #guard removeStones (stonesBridge [[0, 0]]) == 0 #guard removeStones (stonesBridge [[1, 2], [2, 3], [3, 4]]) == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxRemovableStones_check (stonesBridge [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]) (removeStones (stonesBridge [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]])) #guard maxRemovableStones_check (stonesBridge [[0, 0]]) (removeStones (stonesBridge [[0, 0]])) #guard maxRemovableStones_check (stonesBridge [[1, 2], [2, 3], [3, 4]]) (removeStones (stonesBridge [[1, 2], [2, 3], [3, 4]])) end PMostStonesRemovedWithSameRowOrColumn