import Mathlib /-! # Escape The Ghosts You are playing a simplified PAC-MAN game on an infinite 2-D grid. You start at the point [0, 0], and you are given a destination point target = [xtarget, ytarget] that you are trying to get to. There are several ghosts on the map with their starting positions given as a 2D array ghosts, where ghosts[i] = [x_i, y_i] represents the starting position of the ith ghost. All inputs are integral coordinates. Each turn, you and all the ghosts may independently choose to either move 1 unit in any of the four cardinal directions: north, east, south, or west, or stay still. All actions happen simultaneously. You escape if and only if you can reach the target before any ghost reaches you. If you reach any square (including the target) at the same time as a ghost, it does not count as an escape. Return true if it is possible to escape regardless of how the ghosts move, otherwise return false. ## Constraints - 1 <= ghosts.length <= 100 - ghosts[i].length == 2 - -10^4 <= x_i, y_i <= 10^4 - There can be multiple ghosts in the same location. - target.length == 2 - -10^4 <= xtarget, ytarget <= 10^4 ## Provided examples - `ghosts = [[1, 0], [0, 3]], target = [0, 1]` → `true` - `ghosts = [[1, 0]], target = [2, 0]` → `false` - `ghosts = [[2, 0]], target = [1, 0]` → `false` ## Synthesized negative examples - invalid input: `ghosts = [], target = [0, 0]` ([structural] a predicate that admits 1 <= ghosts.length <= 100. empty ghost list where at least one ghost is required) - invalid input: `ghosts = [[0, 0, 0]], target = [0, 0]` ([structural] a predicate that admits ghosts[i].length == 2. ghost row has three coordinates; checking bounds but not row length accepts it) - invalid input: `ghosts = [[10001, 0]], target = [0, 0]` ([structural] a predicate that admits -10^4 <= xi, yi <= 10^4. one past the stated ghost coordinate maximum) - `ghosts = [[1, 0], [0, 3]], target = [0, 1]` → `false` is wrong ([structural] not_optimal is inapplicable to a boolean; using relaxed_reading. The flaw drops the four-cardinal-directions restriction and permits diagonal movement.. Allowing diagonal moves lets ghost at (1,0) reach target in one turn.) - `ghosts = [[1, 0]], target = [2, 0]` → `true` is wrong ([structural] ghosts are assumed not to move. if ghosts stay still, player can go around and reach) - `ghosts = [[2, 0]], target = [1, 0]` → `true` is wrong ([structural] specification omits the condition that ghosts prevent escape. without ghosts, target is reachable in one step) -/ namespace PEscapeTheGhosts abbrev Input := (List (List Int)) × (Int × Int) abbrev Output := Bool /-! ### Specification helpers -/ /-- Shortest number of cardinal-move turns from `a` to `b`, the Manhattan distance. -/ def MinTurns (a b : Int × Int) : Nat := (a.1 - b.1).natAbs + (a.2 - b.2).natAbs /-- The grid point a two-element coordinate list denotes, with the origin as fallback. -/ def listToPoint (l : List Int) : Int × Int := match l with | [x, y] => (x, y) | _ => (0, 0) /-- Bridge from the serialized ghost list to the input's ghost coordinate rows. -/ def fromGhostLists (l : List (List Int)) : List (List Int) := l /-- Bridge from the serialized target pair to the input's target point. -/ def fromTargetList (l : List Int) : Int × Int := listToPoint l /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 100 ghosts, each a coordinate pair with coordinates in [−10^4, 10^4], and a target pair in the same range. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 100 && input.1.all (fun g => g.length = 2 && g.all (fun c => -(10^4) ≤ c && c ≤ 10^4)) && -(10^4) ≤ input.2.1 && input.2.1 ≤ 10^4 && -(10^4) ≤ input.2.2 && input.2.2 ≤ 10^4 /-! ### Ideal specification (P_spec) -/ /-- `result` holds exactly when the player's cardinal-move distance from the origin to the target is strictly less than every ghost's distance to the target. -/ def canEscapeGhosts_spec (input : Input) (result : Output) : Prop := result ↔ ∀ g ∈ input.1, MinTurns (0, 0) input.2 < MinTurns (listToPoint g) input.2 /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def canEscapeGhosts_check (input : Input) (result : Output) : Bool := @decide (canEscapeGhosts_spec input result) (by unfold canEscapeGhosts_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem canEscapeGhosts_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : canEscapeGhosts_check input result ↔ canEscapeGhosts_spec input result := by simp [canEscapeGhosts_check] /-! ### Implementation helpers -/ /-- Whether every ghost row in `gs` lies strictly farther from `target` than the player's distance `d`. -/ def allGhostsFurther (d : Nat) (target : Int × Int) (gs : List (List Int)) : Bool := match gs with | [] => true | g :: rest => d < MinTurns (listToPoint g) target && allGhostsFurther d target rest /-! ### Main algorithm (impl) -/ /-- Escape decision by a linear scan: the player's Manhattan distance to the target must be strictly less than every ghost's. -/ def escapeGhosts (input : Input) : Output := allGhostsFurther (MinTurns (0, 0) input.2) input.2 input.1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem escapeGhosts_correct (input : Input) (h : isValidInput input) : canEscapeGhosts_spec input (escapeGhosts input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (fromGhostLists [[1, 0], [0, 3]], fromTargetList [0, 1]) #guard isValidInput (fromGhostLists [[1, 0]], fromTargetList [2, 0]) #guard isValidInput (fromGhostLists [[2, 0]], fromTargetList [1, 0]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (fromGhostLists [], fromTargetList [0, 0])) #guard !(isValidInput (fromGhostLists [[0, 0, 0]], fromTargetList [0, 0])) #guard !(isValidInput (fromGhostLists [[10001, 0]], fromTargetList [0, 0])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard canEscapeGhosts_check ((fromGhostLists [[1, 0], [0, 3]]), (fromTargetList [0, 1])) true #guard canEscapeGhosts_check ((fromGhostLists [[1, 0]]), (fromTargetList [2, 0])) false #guard canEscapeGhosts_check ((fromGhostLists [[2, 0]]), (fromTargetList [1, 0])) false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(canEscapeGhosts_check ((fromGhostLists [[1, 0], [0, 3]]), (fromTargetList [0, 1])) false) #guard !(canEscapeGhosts_check ((fromGhostLists [[1, 0]]), (fromTargetList [2, 0])) true) #guard !(canEscapeGhosts_check ((fromGhostLists [[2, 0]]), (fromTargetList [1, 0])) true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard escapeGhosts (fromGhostLists [[1, 0], [0, 3]], fromTargetList [0, 1]) == true #guard escapeGhosts (fromGhostLists [[1, 0]], fromTargetList [2, 0]) == false #guard escapeGhosts (fromGhostLists [[2, 0]], fromTargetList [1, 0]) == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard canEscapeGhosts_check (fromGhostLists [[1, 0], [0, 3]], fromTargetList [0, 1]) (escapeGhosts (fromGhostLists [[1, 0], [0, 3]], fromTargetList [0, 1])) #guard canEscapeGhosts_check (fromGhostLists [[1, 0]], fromTargetList [2, 0]) (escapeGhosts (fromGhostLists [[1, 0]], fromTargetList [2, 0])) #guard canEscapeGhosts_check (fromGhostLists [[2, 0]], fromTargetList [1, 0]) (escapeGhosts (fromGhostLists [[2, 0]], fromTargetList [1, 0])) end PEscapeTheGhosts