import Mathlib /-! # Self Crossing You are given an array of integers distance. You start at the point (0, 0) on an X-Y plane, and you move distance[0] meters to the north, then distance[1] meters to the west, distance[2] meters to the south, distance[3] meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise. Return true if your path crosses itself or false if it does not. ## Constraints - 1 <= distance.length <= 10^5 - 1 <= distance[i] <= 10^5 ## Provided examples - `distance = [2, 1, 1, 2]` → `true` - `distance = [1, 2, 3, 4]` → `false` - `distance = [1, 1, 1, 2, 1]` → `true` ## Synthesized negative examples - invalid input: `distance = []` ([structural] a predicate that admits 1 <= distance.length <= 10^5. empty where at least one move is required) - invalid input: `distance = [0]` ([structural] a predicate that admits 1 <= distance[i] <= 10^5. one below the minimum step length) - invalid input: `distance = [-1]` ([structural] a predicate that admits 1 <= distance[i] <= 10^5. negative step length; legal List[int] but outside stated range) - `distance = [2, 1, 1, 2]` → `false` is wrong ([structural] crossing defined as repeated vertex, not segment intersection. interior crossing at (0,1) ignored under vertex-only reading) - `distance = [1, 2, 3, 4]` → `true` is wrong ([structural] treats adjacent segment endpoints as crossings. the segments touch only at adjacent endpoints; true only if endpoints count) - `distance = [1, 1, 1, 2, 1]` → `false` is wrong ([structural] endpoint touching is not considered a crossing. misses origin crossing, so returns false) -/ namespace PSelfCrossing abbrev Input := List Int abbrev Output := Bool /-! ### Specification helpers -/ /-- The displacement direction of move `i`: north, west, south, east cyclically. -/ def stepDir (i : Nat) : ℝ × ℝ := match i % 4 with | 0 => (0, 1) | 1 => (-1, 0) | 2 => (0, -1) | _ => (1, 0) /-- The vertices visited when walking `ds` starting at point `p` with heading offset `i`. -/ def walkFrom (i : Nat) (p : ℝ × ℝ) : List Int → List (ℝ × ℝ) | [] => [p] | d :: ds => p :: walkFrom (i + 1) (p + (d : ℝ) • stepDir i) ds /-- The vertices of the polygonal path determined by `distance`, origin first. -/ def pathVertices (distance : List Int) : List (ℝ × ℝ) := walkFrom 0 (0, 0) distance /-- The `i`-th segment of the path as a point set, empty when `i` is out of range. -/ def pathSegment (distance : List Int) (i : Nat) : Set (ℝ × ℝ) := let v := pathVertices distance match v[i]?, v[i + 1]? with | some a, some b => affineSegment ℝ a b | _, _ => ∅ /-- Two non-consecutive segments of the path determined by `distance` share a point. -/ def IsSelfCrossing (distance : List Int) : Prop := ∃ i j : Nat, i + 1 < j ∧ j < distance.length ∧ ∃ p : ℝ × ℝ, p ∈ pathSegment distance i ∧ p ∈ pathSegment distance j /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10^5 moves, each step length between 1 and 10^5. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10 ^ 5 && input.all (fun d => 1 ≤ d && d ≤ 10 ^ 5) /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when the polygonal path determined by `input` crosses itself. -/ def isSelfCrossing_spec (input : Input) (result : Output) : Prop := result ↔ IsSelfCrossing input /-! ### Decidable specification (P_check) -/ /-- The displacement direction of move `i` as an integer vector, cycling north, west, south, east. -/ def stepDirZ (i : Nat) : Int × Int := match i % 4 with | 0 => (0, 1) | 1 => (-1, 0) | 2 => (0, -1) | _ => (1, 0) /-- The integer point reached from `p` by a step of length `d` in the direction of move `i`. -/ def stepZ (p : Int × Int) (d : Int) (i : Nat) : Int × Int := (p.1 + d * (stepDirZ i).1, p.2 + d * (stepDirZ i).2) /-- The integer vertices visited when walking `ds` starting at `p` with heading offset `i`. -/ def walkFromZ (i : Nat) (p : Int × Int) : List Int → List (Int × Int) | [] => [p] | d :: ds => p :: walkFromZ (i + 1) (stepZ p d i) ds /-- The integer vertices of the polygonal path determined by `distance`, origin first. -/ def pathVerticesZ (distance : List Int) : List (Int × Int) := walkFromZ 0 (0, 0) distance /-- The integer endpoints of the `i`-th segment of the path, `none` when `i` is out of range. -/ def segEndsZ (distance : List Int) (i : Nat) : Option ((Int × Int) × (Int × Int)) := let v := pathVerticesZ distance match v[i]?, v[i + 1]? with | some a, some b => some (a, b) | _, _ => none /-- The closed integer intervals from `a` to `b` and from `c` to `d` share a point. -/ def rangeOverlapZ (a b c d : Int) : Bool := decide (max (min a b) (min c d) ≤ min (max a b) (max c d)) /-- The closed axis-aligned segments `a`-`b` and `c`-`d` share a point. -/ def segmentsMeetZ (a b c d : Int × Int) : Bool := rangeOverlapZ a.1 b.1 c.1 d.1 && rangeOverlapZ a.2 b.2 c.2 d.2 /-- Segments `i` and `j` of the path determined by `distance` share a point. -/ def pairCrossesZ (distance : List Int) (i j : Nat) : Bool := match segEndsZ distance i, segEndsZ distance j with | some (a, b), some (c, d) => segmentsMeetZ a b c d | _, _ => false /-- Two non-consecutive segments of the path determined by `distance` share a point. -/ def existsCrossingZ (distance : List Int) : Bool := let n := distance.length (List.finRange n).any fun i => (List.finRange n).any fun j => decide (i.val + 1 < j.val) && pairCrossesZ distance i.val j.val /-- Executable checker for `isSelfCrossing_spec`: `result` matches the existence of a crossing. -/ def isSelfCrossing_check (input : Input) (result : Output) : Bool := existsCrossingZ input == result /-- The real point with the given integer coordinates. -/ def sc_cast (p : Int × Int) : ℝ × ℝ := ((p.1 : ℝ), (p.2 : ℝ)) theorem sc_stepDir (i : Nat) : stepDir i = sc_cast (stepDirZ i) := by unfold stepDir stepDirZ sc_cast have h := Nat.mod_lt i (show 4 > 0 by norm_num) interval_cases hk : i % 4 <;> simp theorem sc_dirZ (k : Nat) : (stepDirZ k).1 = 0 ∨ (stepDirZ k).2 = 0 := by unfold stepDirZ have h := Nat.mod_lt k (show 4 > 0 by norm_num) interval_cases hk : k % 4 <;> simp theorem sc_walk (i : Nat) (p : Int × Int) (ds : List Int) : walkFrom i (sc_cast p) ds = (walkFromZ i p ds).map sc_cast := by induction ds generalizing i p with | nil => simp [walkFrom, walkFromZ] | cons d ds ih => have hs : sc_cast p + (d : ℝ) • stepDir i = sc_cast (stepZ p d i) := by rw [sc_stepDir] ext <;> simp [sc_cast, stepZ] simp only [walkFrom, walkFromZ, List.map_cons, hs, ih] theorem sc_path (distance : List Int) : pathVertices distance = (pathVerticesZ distance).map sc_cast := by unfold pathVertices pathVerticesZ rw [show ((0, 0) : ℝ × ℝ) = sc_cast (0, 0) by simp [sc_cast]] exact sc_walk 0 (0, 0) distance theorem sc_walk_head (k : Nat) (p : Int × Int) (ds : List Int) : (walkFromZ k p ds)[0]? = some p := by cases ds <;> simp [walkFromZ] theorem sc_axis (k : Nat) (p : Int × Int) (ds : List Int) : ∀ i a b, (walkFromZ k p ds)[i]? = some a → (walkFromZ k p ds)[i + 1]? = some b → a.1 = b.1 ∨ a.2 = b.2 := by induction ds generalizing k p with | nil => intro i a b _ h2 simp [walkFromZ] at h2 | cons d ds ih => intro i a b h1 h2 cases i with | zero => simp only [walkFromZ, List.getElem?_cons_zero, List.getElem?_cons_succ, Option.some.injEq] at h1 h2 rw [sc_walk_head] at h2 simp only [Option.some.injEq] at h2 subst h1 subst h2 rcases sc_dirZ k with h | h · left simp [stepZ, h] · right simp [stepZ, h] | succ i => simp only [walkFromZ, List.getElem?_cons_succ] at h1 h2 exact ih (k + 1) _ i a b h1 h2 theorem sc_seg_prod (a b : Int × Int) (h : a.1 = b.1 ∨ a.2 = b.2) : segment ℝ (sc_cast a) (sc_cast b) = Set.uIcc (a.1 : ℝ) b.1 ×ˢ Set.uIcc (a.2 : ℝ) b.2 := by obtain ⟨a1, a2⟩ := a obtain ⟨b1, b2⟩ := b simp only at h rcases h with h | h · subst h simp only [sc_cast] rw [← Prod.image_mk_segment_right, segment_eq_uIcc, Set.uIcc_self, Set.singleton_prod] · subst h simp only [sc_cast] rw [← Prod.image_mk_segment_left, segment_eq_uIcc, Set.uIcc_self, Set.prod_singleton] theorem sc_uIcc_meet (a b c d : Int) : (∃ x : ℝ, x ∈ Set.uIcc (a : ℝ) b ∧ x ∈ Set.uIcc (c : ℝ) d) ↔ max (min a b) (min c d) ≤ min (max a b) (max c d) := by have hinf : ∀ u v : ℝ, u ⊓ v = min u v := fun _ _ => rfl have hsup : ∀ u v : ℝ, u ⊔ v = max u v := fun _ _ => rfl simp only [Set.uIcc, Set.mem_Icc, hinf, hsup] constructor · rintro ⟨x, ⟨h1, h2⟩, ⟨h3, h4⟩⟩ have e : ((max (min a b) (min c d) : Int) : ℝ) ≤ ((min (max a b) (max c d) : Int) : ℝ) := by push_cast exact le_trans (max_le h1 h3) (le_min h2 h4) exact_mod_cast e · intro h have h' : ((max (min a b) (min c d) : Int) : ℝ) ≤ ((min (max a b) (max c d) : Int) : ℝ) := by exact_mod_cast h push_cast at h' refine ⟨((max (min a b) (min c d) : Int) : ℝ), ⟨?_, ?_⟩, ⟨?_, ?_⟩⟩ · push_cast exact le_max_left _ _ · push_cast exact h'.trans (min_le_left _ _) · push_cast exact le_max_right _ _ · push_cast exact h'.trans (min_le_right _ _) theorem sc_meet (a b c d : Int × Int) (hab : a.1 = b.1 ∨ a.2 = b.2) (hcd : c.1 = d.1 ∨ c.2 = d.2) : (∃ p : ℝ × ℝ, p ∈ segment ℝ (sc_cast a) (sc_cast b) ∧ p ∈ segment ℝ (sc_cast c) (sc_cast d)) ↔ segmentsMeetZ a b c d = true := by rw [sc_seg_prod a b hab, sc_seg_prod c d hcd] unfold segmentsMeetZ rangeOverlapZ rw [Bool.and_eq_true, decide_eq_true_eq, decide_eq_true_eq, ← sc_uIcc_meet, ← sc_uIcc_meet] constructor · rintro ⟨p, ⟨h1, h2⟩, ⟨h3, h4⟩⟩ exact ⟨⟨p.1, h1, h3⟩, ⟨p.2, h2, h4⟩⟩ · rintro ⟨⟨x, h1, h3⟩, ⟨y, h2, h4⟩⟩ exact ⟨(x, y), ⟨h1, h2⟩, ⟨h3, h4⟩⟩ theorem sc_mem_seg (distance : List Int) (i : Nat) (p : ℝ × ℝ) : p ∈ pathSegment distance i ↔ ∃ a b, (pathVerticesZ distance)[i]? = some a ∧ (pathVerticesZ distance)[i + 1]? = some b ∧ p ∈ segment ℝ (sc_cast a) (sc_cast b) := by unfold pathSegment rw [sc_path] simp only [List.getElem?_map] cases h1 : (pathVerticesZ distance)[i]? <;> cases h2 : (pathVerticesZ distance)[i + 1]? <;> simp [affineSegment_eq_segment] theorem sc_pair_iff (distance : List Int) (i j : Nat) : pairCrossesZ distance i j = true ↔ ∃ a b c d, (pathVerticesZ distance)[i]? = some a ∧ (pathVerticesZ distance)[i + 1]? = some b ∧ (pathVerticesZ distance)[j]? = some c ∧ (pathVerticesZ distance)[j + 1]? = some d ∧ segmentsMeetZ a b c d = true := by unfold pairCrossesZ simp only [segEndsZ] cases h1 : (pathVerticesZ distance)[i]? <;> cases h2 : (pathVerticesZ distance)[i + 1]? <;> cases h3 : (pathVerticesZ distance)[j]? <;> cases h4 : (pathVerticesZ distance)[j + 1]? <;> simp theorem sc_bridge (distance : List Int) : existsCrossingZ distance = true ↔ IsSelfCrossing distance := by unfold existsCrossingZ IsSelfCrossing simp only [List.any_eq_true, Bool.and_eq_true, decide_eq_true_eq] constructor · rintro ⟨i, _, j, _, hij, hc⟩ obtain ⟨a, b, c, d, h1, h2, h3, h4, hm⟩ := (sc_pair_iff distance i.val j.val).mp hc obtain ⟨p, hp1, hp2⟩ := (sc_meet a b c d (sc_axis 0 (0, 0) distance _ _ _ h1 h2) (sc_axis 0 (0, 0) distance _ _ _ h3 h4)).mpr hm exact ⟨i.val, j.val, hij, j.isLt, p, (sc_mem_seg distance i.val p).mpr ⟨a, b, h1, h2, hp1⟩, (sc_mem_seg distance j.val p).mpr ⟨c, d, h3, h4, hp2⟩⟩ · rintro ⟨i, j, hij, hj, p, hp1, hp2⟩ obtain ⟨a, b, h1, h2, hq1⟩ := (sc_mem_seg distance i p).mp hp1 obtain ⟨c, d, h3, h4, hq2⟩ := (sc_mem_seg distance j p).mp hp2 refine ⟨⟨i, by omega⟩, List.mem_finRange _, ⟨j, hj⟩, List.mem_finRange _, hij, ?_⟩ exact (sc_pair_iff distance i j).mpr ⟨a, b, c, d, h1, h2, h3, h4, (sc_meet a b c d (sc_axis 0 (0, 0) distance _ _ _ h1 h2) (sc_axis 0 (0, 0) distance _ _ _ h3 h4)).mp ⟨p, hq1, hq2⟩⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isSelfCrossing_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isSelfCrossing_check input result ↔ isSelfCrossing_spec input result := by unfold isSelfCrossing_check isSelfCrossing_spec rw [beq_iff_eq, Bool.eq_iff_iff, sc_bridge] exact Iff.comm /-! ### Implementation helpers -/ /-- The three local crossing tests applied to distance `d` with previous distances `prev` (most recent first). -/ def crossingAt (d : Int) (prev : List Int) : Bool := match prev with | d1 :: d2 :: d3 :: rest => decide (d2 ≤ d ∧ d1 ≤ d3) || (match rest with | d4 :: rest2 => decide (d1 = d3 ∧ d2 ≤ d + d4) || (match rest2 with | d5 :: _ => decide (d4 ≤ d2 ∧ d1 ≤ d3 ∧ d2 - d4 ≤ d ∧ d3 - d5 ≤ d1) | [] => false) | [] => false) | _ => false /-- Left-to-right scan over the remaining distances, carrying the last five in `prev`. -/ def scanCrossings (prev : List Int) : List Int → Bool | [] => false | d :: ds => if crossingAt d prev then true else scanCrossings ((d :: prev).take 5) ds /-! ### Main algorithm (impl) -/ /-- Self-crossing test by a single left-to-right scan keeping the last five distances. -/ def selfCrossing (distance : Input) : Output := scanCrossings [] distance /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem selfCrossing_correct (input : Input) (h : isValidInput input) : isSelfCrossing_spec input (selfCrossing input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [2, 1, 1, 2] #guard isValidInput [1, 2, 3, 4] #guard isValidInput [1, 1, 1, 2, 1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [0]) #guard !(isValidInput [(-1)]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isSelfCrossing_check [2, 1, 1, 2] true #guard isSelfCrossing_check [1, 2, 3, 4] false #guard isSelfCrossing_check [1, 1, 1, 2, 1] true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isSelfCrossing_check [2, 1, 1, 2] false) #guard !(isSelfCrossing_check [1, 2, 3, 4] true) #guard !(isSelfCrossing_check [1, 1, 1, 2, 1] false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard selfCrossing [2, 1, 1, 2] == true #guard selfCrossing [1, 2, 3, 4] == false #guard selfCrossing [1, 1, 1, 2, 1] == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isSelfCrossing_check [2, 1, 1, 2] (selfCrossing [2, 1, 1, 2]) #guard isSelfCrossing_check [1, 2, 3, 4] (selfCrossing [1, 2, 3, 4]) #guard isSelfCrossing_check [1, 1, 1, 2, 1] (selfCrossing [1, 1, 1, 2, 1]) end PSelfCrossing