import Mathlib /-! # Word Search Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. ## Constraints - m == board.length - n = board[i].length - 1 <= m, n <= 6 - 1 <= word.length <= 15 - board and word consists of only lowercase and uppercase English letters. ## Provided examples - `board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCCED"` → `true` - `board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "SEE"` → `true` - `board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCB"` → `false` ## Synthesized negative examples - invalid input: `board = [["A"], ["B", "C"]], word = "A"` ([structural] a predicate that admits n = board[i].length. predicate checking rows are nonempty but not equal width accepts it) - invalid input: `board = [[]], word = "A"` ([structural] a predicate that admits 1 <= m, n <= 6. a predicate checking only row count passes) - invalid input: `board = [["A"]], word = ""` ([structural] a predicate that admits 1 <= word.length <= 15. a predicate checking letters but not length accepts) - `board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCCED"` → `false` is wrong ([structural] the existential half is omitted; returning false always satisfies it. constant false passes a specification that never requires a positive case) - `board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "SEE"` → `false` is wrong ([structural] nothing requires a true answer when the word is present. false does no work; no search required) - `board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCB"` → `true` is wrong ([structural] the restriction that no cell may be reused is dropped. A-B-C-B reuses the B at (0,1)) -/ namespace PWordSearch abbrev Input := (List (List String)) × (String) abbrev Output := Bool /-! ### Specification helpers -/ /-- The character at position `pos` of `board`, or `none` if it is out of bounds. -/ def cellAt (board : List (List String)) (pos : Nat × Nat) : Option String := (board[pos.1]?).bind (·[pos.2]?) /-- Whether `c` is a lowercase or uppercase English letter. -/ def isLetter (c : Char) : Bool := ('a' ≤ c && c ≤ 'z') || ('A' ≤ c && c ≤ 'Z') /-- Two positions are horizontally or vertically adjacent: equal in one coordinate and differing by exactly one in the other. -/ def adjacent (a b : Nat × Nat) : Prop := (a.1 = b.1 ∧ (a.2 + 1 = b.2 ∨ b.2 + 1 = a.2)) ∨ (a.2 = b.2 ∧ (a.1 + 1 = b.1 ∨ b.1 + 1 = a.1)) /-- `p` is a path through `board` spelling `word`: its positions lie inside the board and match the characters of `word` in order (forcing equal lengths), consecutive positions are adjacent, and no cell is used twice. -/ def IsPath (board : List (List String)) (word : String) (p : List (Nat × Nat)) : Prop := List.Forall₂ (fun pos c => cellAt board pos = some (String.singleton c)) p word.toList ∧ List.Chain' adjacent p ∧ p.Nodup /-! ### Validity predicate (V) -/ /-- Valid input: a rectangular board of 1–6 rows, each of width 1–6, whose cells are single-character letter strings, and a nonempty word of at most 15 letters. -/ def isValidInput (input : Input) : Bool := let board := input.1 let word := input.2 1 ≤ board.length && board.length ≤ 6 && board.all (fun row => row.length = board.head!.length) && board.all (fun row => 1 ≤ row.length && row.length ≤ 6) && board.all (fun row => row.all (fun s => s.length = 1 && s.toList.all isLetter)) && 1 ≤ word.length && word.length ≤ 15 && word.toList.all isLetter /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when some path through the board spells the word. -/ def wordExists_spec (input : Input) (result : Output) : Prop := result ↔ ∃ p : List (Nat × Nat), IsPath input.1 input.2 p /-! ### Decidable specification (P_check) -/ /-- One step from `pos` in direction `d`: 0 down, 1 up, 2 right, 3 left, saturating at zero. -/ def step (pos : Nat × Nat) (d : Fin 4) : Nat × Nat := match d.val with | 0 => (pos.1 + 1, pos.2) | 1 => (pos.1 - 1, pos.2) | 2 => (pos.1, pos.2 + 1) | _ => (pos.1, pos.2 - 1) /-- The walk starting at `start` and following `moves`; its length is `moves.length + 1`. -/ def decodeWalk (start : Nat × Nat) (moves : List (Fin 4)) : List (Nat × Nat) := moves.scanl step start /-- All positions inside `board`, listed row by row. -/ def allCells (board : List (List String)) : List (Nat × Nat) := (List.range board.length).flatMap fun r => (List.range board[r]!.length).map fun c => (r, c) /-- Boolean version of `adjacent`: equal in one coordinate, differing by one in the other. -/ def adjacentBool (a b : Nat × Nat) : Bool := (a.1 == b.1 && (a.2 + 1 == b.2 || b.2 + 1 == a.2)) || (a.2 == b.2 && (a.1 + 1 == b.1 || b.1 + 1 == a.1)) /-- Boolean check that a list has no duplicate elements. -/ def nodupBool [BEq α] : List α → Bool | [] => true | x :: xs => !xs.contains x && nodupBool xs /-- Boolean version of `IsPath`: the positions match the characters of `word` in order, consecutive positions are adjacent, and no cell is used twice. -/ def isPathBool (board : List (List String)) (word : String) (p : List (Nat × Nat)) : Bool := p.length == word.length && (p.zip word.toList).all (fun (pos, c) => cellAt board pos == some (String.singleton c)) && (p.zip p.tail).all (fun (a, b) => adjacentBool a b) && nodupBool p /-- All lists of `n` directions, each entry one of the four moves. -/ def allMoveSeqs : Nat → List (List (Fin 4)) | 0 => [[]] | n + 1 => (allMoveSeqs n).flatMap fun rest => ([0, 1, 2, 3] : List (Fin 4)).map fun d => d :: rest /-- Executable checker for `wordExists_spec`: a start cell plus one of four moves per gap between consecutive letters encodes every candidate path. -/ def wordExists_check (input : Input) (result : Output) : Bool := result == (allCells input.1).any fun start => (allMoveSeqs (input.2.length - 1)).any fun moves => isPathBool input.1 input.2 (decodeWalk start moves) theorem wx_root (reflect : ∀ b w p, isPathBool b w p = true ↔ IsPath b w p) (cover : ∀ b w p, 0 < w.length → IsPath b w p → ∃ s ∈ allCells b, ∃ m ∈ allMoveSeqs (w.length - 1), decodeWalk s m = p) (input : Input) (result : Output) (h : isValidInput input) : wordExists_check input result ↔ wordExists_spec input result := by have hw : 0 < input.2.length := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h omega have hex : ((allCells input.1).any fun s => (allMoveSeqs (input.2.length - 1)).any fun m => isPathBool input.1 input.2 (decodeWalk s m)) = true ↔ ∃ p, IsPath input.1 input.2 p := by simp only [List.any_eq_true, reflect] constructor · rintro ⟨s, hs, m, hm, hp⟩ exact ⟨_, hp⟩ · rintro ⟨p, hp⟩ obtain ⟨s, hs, m, hm, he⟩ := cover _ _ _ hw hp exact ⟨s, hs, m, hm, he.symm ▸ hp⟩ unfold wordExists_check wordExists_spec cases result <;> simp_all <;> grind only [] theorem wx_adj (a b : Nat × Nat) : adjacentBool a b = true ↔ adjacent a b := by simp [adjacentBool, adjacent] theorem wx_nodup (p : List (Nat × Nat)) : nodupBool p = true ↔ p.Nodup := by induction p with | nil => simp [nodupBool] | cons a p ih => simp [nodupBool, ih] theorem wx_chain (p : List (Nat × Nat)) : (p.zip p.tail).all (fun (a,b) => adjacentBool a b) = true ↔ List.Chain' adjacent p := by unfold List.Chain' induction p with | nil => simp | cons a p ih => cases p with | nil => simp | cons b p => simpa [wx_adj] using (and_congr (wx_adj a b) ih) theorem wx_reflect (b : List (List String)) (w : String) (p : List (Nat × Nat)) : isPathBool b w p = true ↔ IsPath b w p := by simp only [isPathBool, Bool.and_eq_true, beq_iff_eq, wx_chain, wx_nodup, IsPath] simp only [List.forall₂_iff_zip, String.length_toList, List.all_eq_true, beq_iff_eq] grind only [] theorem wx_step_of_adjacent (a b : Nat × Nat) : adjacent a b → ∃ d : Fin 4, step a d = b := by rcases a with ⟨ar, ac⟩ rcases b with ⟨br, bc⟩ rintro (h | h) · rcases h with ⟨h1, h2 | h2⟩ · refine ⟨2, ?_⟩ simp [step] omega · refine ⟨3, ?_⟩ simp [step] omega · rcases h with ⟨h1, h2 | h2⟩ · refine ⟨0, ?_⟩ simp [step] omega · refine ⟨1, ?_⟩ simp [step] omega theorem wx_mem_allMoveSeqs (n : Nat) (m : List (Fin 4)) : m ∈ allMoveSeqs n ↔ m.length = n := by induction n generalizing m with | zero => cases m <;> simp [allMoveSeqs] | succ n ih => cases m with | nil => simp [allMoveSeqs] | cons d ds => fin_cases d <;> simp [allMoveSeqs, ih] theorem wx_encode_walk (a : Nat × Nat) : ∀ xs : List (Nat × Nat), List.Chain' adjacent (a :: xs) → ∃ m : List (Fin 4), m.length = xs.length ∧ decodeWalk a m = a :: xs := by intro xs induction xs generalizing a with | nil => intro h exact ⟨[], by simp, by simp [decodeWalk]⟩ | cons b xs ih => intro h unfold List.Chain' at h simp only [List.isChain_cons_cons] at h obtain ⟨m, hm, hd⟩ := ih b h.2 obtain ⟨d, hs⟩ := wx_step_of_adjacent a b h.1 refine ⟨d :: m, by simp [hm], ?_⟩ simp only [decodeWalk, List.scanl_cons, hs] exact congrArg (List.cons a) (by simpa only [decodeWalk] using hd) theorem wx_cell_mem (b : List (List String)) (pos : Nat × Nat) (x : String) (h : cellAt b pos = some x) : pos ∈ allCells b := by rcases pos with ⟨r, c⟩ unfold cellAt at h obtain ⟨row, hb, hc⟩ := Option.bind_eq_some_iff.mp h obtain ⟨hr, hbget⟩ := List.getElem?_eq_some_iff.mp hb obtain ⟨hcol, hcget⟩ := List.getElem?_eq_some_iff.mp hc simp [allCells, hr, hbget, hcol] theorem wx_cover : ∀ (b : List (List String)) (w : String) (p : List (Nat × Nat)), 0 < w.length → IsPath b w p → ∃ s ∈ allCells b, ∃ m ∈ allMoveSeqs (w.length - 1), decodeWalk s m = p := by intro b w p hw hp have hlen : p.length = w.length := hp.1.length_eq cases p with | nil => simp at hlen omega | cons s ps => cases hfw : w.toList with | nil => have hf := hp.1 rw [hfw] at hf simp at hf | cons c cs => have hf := hp.1 rw [hfw] at hf simp only [List.forall₂_cons] at hf have hs : s ∈ allCells b := wx_cell_mem b s _ hf.1 obtain ⟨m, hm, hdec⟩ := wx_encode_walk s ps hp.2.1 refine ⟨s, hs, m, ?_, hdec⟩ apply (wx_mem_allMoveSeqs _ _).2 simp only [List.length_cons] at hlen omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem wordExists_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : wordExists_check input result ↔ wordExists_spec input result := by exact wx_root wx_reflect wx_cover input result h /-! ### Implementation helpers -/ /-- The first `some` produced by `f` over `xs`, or `none` if there is none. -/ def firstSome (f : α → Option β) : List α → Option β | [] => none | x :: xs => match f x with | some y => some y | none => firstSome f xs /-- The bit index of board position `pos` for a board of row width `width`. -/ def idxOf (width : Nat) (pos : Nat × Nat) : Nat := pos.1 * width + pos.2 /-- Whether `pos` lies inside a `board` whose rows have width `width`. -/ def isInside (board : List (List String)) (width : Nat) (pos : Nat × Nat) : Bool := Nat.ble (pos.1 + 1) board.length && Nat.ble (pos.2 + 1) width /-- Backtracking search from `pos` for the remaining characters, with visited cells in `mask`. -/ def dfs (board : List (List String)) (width : Nat) (pos : Nat × Nat) (mask : Nat) (pathRev : List (Nat × Nat)) : List Char → Option (List (Nat × Nat)) | [] => some pathRev.reverse | c :: cs => let neighbors := [(pos.1 + 1, pos.2), (pos.1 - 1, pos.2), (pos.1, pos.2 + 1), (pos.1, pos.2 - 1)] firstSome (fun q => let idx := idxOf width q if isInside board width q && (Nat.shiftRight mask idx) % 2 == 0 && cellAt board q == some (String.singleton c) then dfs board width q (mask + Nat.shiftLeft 1 idx) (pos :: pathRev) cs else none) neighbors /-- Try every cell whose character starts the remaining word as a DFS root. -/ def search (board : List (List String)) (width : Nat) : List Char → Option (List (Nat × Nat)) | [] => none | c :: cs => firstSome (fun pos => if cellAt board pos == some (String.singleton c) then dfs board width pos (Nat.shiftLeft 1 (idxOf width pos)) [pos] cs else none) (allCells board) /-! ### Main algorithm (impl) -/ /-- Backtracking DFS over adjacent cells with a visited bitmask. -/ def doesWordExist (input : Input) : Output := let board := input.1 let width := match board with | [] => 0 | row :: _ => row.length match search board width input.2.toList with | some _ => true | none => false /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem doesWordExist_correct (input : Input) (h : isValidInput input) : wordExists_spec input (doesWordExist input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCCED") #guard isValidInput ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "SEE") #guard isValidInput ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCB") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([["A"], ["B", "C"]], "A")) #guard !(isValidInput ([[]], "A")) #guard !(isValidInput ([["A"]], "")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard wordExists_check ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCCED") true #guard wordExists_check ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "SEE") true #guard wordExists_check ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCB") false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(wordExists_check ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCCED") false) #guard !(wordExists_check ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "SEE") false) #guard !(wordExists_check ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCB") true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard doesWordExist ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCCED") == true #guard doesWordExist ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "SEE") == true #guard doesWordExist ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCB") == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard wordExists_check ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCCED") (doesWordExist ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCCED")) #guard wordExists_check ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "SEE") (doesWordExist ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "SEE")) #guard wordExists_check ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCB") (doesWordExist ([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCB")) end PWordSearch