import Mathlib /-! # Candy Crush This question is about implementing a basic elimination algorithm for Candy Crush. Given an m x n integer array board representing the grid of candy where board[i][j] represents the type of candy. A value of board[i][j] == 0 represents that the cell is empty. The given board represents the state of the game following the player's move. Now, you need to restore the board to a stable state by crushing candies according to the following rules: If three or more candies of the same type are adjacent vertically or horizontally, crush them all at the same time - these positions become empty. After crushing all candies simultaneously, if an empty space on the board has candies on top of itself, then these candies will drop until they hit a candy or bottom at the same time. No new candies will drop outside the top boundary. After the above steps, there may exist more candies that can be crushed. If so, you need to repeat the above steps. If there does not exist more candies that can be crushed (i.e., the board is stable), then return the current board. You need to perform the above rules until the board becomes stable, then return the stable board. ## Constraints - m == board.length - n == board[i].length - 3 <= m, n <= 50 - 1 <= board[i][j] <= 2000 ## Provided examples - `board = [[1, 3, 5, 5, 2], [3, 4, 3, 3, 1], [3, 2, 4, 5, 2], [2, 4, 4, 5, 5], [1, 4, 4, 1, 1]]` → `[[1, 3, 0, 0, 0], [3, 4, 0, 5, 2], [3, 2, 0, 3, 1], [2, 4, 0, 5, 2], [1, 4, 3, 1, 1]]` - `board = [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]` → `[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]` - `board = [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]` → `[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]` ## Synthesized negative examples - invalid input: `board = [[1, 1, 1], [1, 1, 1, 1], [1, 1, 1]]` ([structural] a predicate that admits n == board[i].length. rows have different widths; a row-length range check alone accepts it) - invalid input: `board = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]` ([structural] a predicate that admits 1 <= board[i][j] <= 2000. one below the stated candy-type minimum) - invalid input: `board = [[1, 1, 1], [1, 1, 1]]` ([structural] a predicate that admits 3 <= m, n <= 50. one row below the minimum height) - `board = [[1, 3, 5, 5, 2], [3, 4, 3, 3, 1], [3, 2, 4, 5, 2], [2, 4, 4, 5, 5], [1, 4, 4, 1, 1]]` → `[[1, 3, 0, 0, 0], [3, 4, 0, 5, 2], [3, 2, 0, 3, 1], [2, 4, 0, 5, 2], [1, 4, 2, 1, 1]]` is wrong ([structural] final cell values are not required to match the stable process. One candy type is one less but the grid is stable.) - `board = [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]` → `[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [1, 2, 3, 4, 5]]` is wrong ([structural] vertical crush loop misses the bottom row by one. bottom row remains, so output is one row short of full crush) - `board = [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]` → `[[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]` is wrong ([structural] returns state one iteration before stability. true result needs one round; this is zero rounds) -/ namespace PCandyCrush abbrev Input := List (List Int) abbrev Output := List (List Int) /-! ### Specification helpers -/ /-- Returns the candy at row `i` and column `j`, if both indices exist. -/ def cellAt? (board : List (List Int)) (i j : Nat) : Option Int := board[i]? >>= fun row => row[j]? /-- Whether cell `(i, j)` belongs to a horizontal or vertical crushable triple. -/ def isCrushedCell (board : List (List Int)) (i j : Nat) : Prop := match cellAt? board i j with | some candy => candy ≠ 0 ∧ ((∃ start : Nat, start ≤ i ∧ i < start + 3 ∧ cellAt? board start j = some candy ∧ cellAt? board (start + 1) j = some candy ∧ cellAt? board (start + 2) j = some candy) ∨ (∃ start : Nat, start ≤ j ∧ j < start + 3 ∧ cellAt? board i start = some candy ∧ cellAt? board i (start + 1) = some candy ∧ cellAt? board i (start + 2) = some candy)) | none => False /-- Whether two boards have the same number of rows and the same row lengths. -/ def sameShape (before after : List (List Int)) : Prop := before.length = after.length ∧ ∀ i : Nat, (before[i]?).map (fun row => row.length) = (after[i]?).map (fun row => row.length) /-- Whether `after` results from simultaneously crushing every crushable cell in `before`. -/ def isCrushOf (before after : List (List Int)) : Prop := sameShape before after ∧ ∀ i j : Nat, (isCrushedCell before i j ∧ cellAt? after i j = some 0) ∨ (¬ isCrushedCell before i j ∧ cellAt? after i j = cellAt? before i j) /-- Returns the entries of column `j` from top to bottom. -/ def columnValues (board : List (List Int)) (j : Nat) : List Int := board.map (fun row => row[j]!) /-- Whether each column of `after` is the corresponding column of `before` after gravity. -/ def dropsTo (before after : List (List Int)) : Prop := sameShape before after ∧ ∀ j : Nat, columnValues after j = List.replicate ((columnValues before j).count 0) 0 ++ (columnValues before j).filter (fun candy => candy != 0) /-- One round crushes all crushable candies simultaneously and then drops every column. -/ def CrushDropStep (before after : List (List Int)) : Prop := ∃ crushed : List (List Int), isCrushOf before crushed ∧ dropsTo crushed after /-- A board is stable when none of its cells belongs to a crushable run. -/ def Stable (board : List (List Int)) : Prop := ∀ i j : Nat, ¬ isCrushedCell board i j /-- Whether `boards` is a CrushDropStep derivation from `start` to `finish`. -/ def isCrushTrace (start finish : List (List Int)) (boards : List (List (List Int))) : Prop := boards.head? = some start ∧ boards.getLast? = some finish ∧ ∀ i : Nat, ∀ before after : List (List Int), boards[i]? = some before → boards[i + 1]? = some after → CrushDropStep before after /-! ### Validity predicate (V) -/ /-- Valid input: a 3-by-3 to 50-by-50 rectangular board with candy types from 1 to 2000. -/ def isValidInput (input : Input) : Bool := 3 ≤ input.length && input.length ≤ 50 && match input.head? with | some firstRow => 3 ≤ firstRow.length && firstRow.length ≤ 50 && input.all (fun row => row.length == firstRow.length) && input.all (fun row => row.all (fun candy => 1 ≤ candy && candy ≤ 2000)) | none => false /-! ### Ideal specification (P_spec) -/ /-- `result` is the unique stable board reached by a finite CrushDropStep derivation. -/ def candyCrush_spec (input : Input) (result : Output) : Prop := (∃ trace : List (List (List Int)), isCrushTrace input result trace ∧ Stable result) ∧ ∀ trace : List (List (List Int)), ∀ stableBoard : List (List Int), (isCrushTrace input stableBoard trace ∧ Stable stableBoard) → stableBoard = result /-! ### Decidable specification (P_check) -/ /-- Whether a vertical run of three `candy` cells covering `(i, j)` starts at `start`. -/ def verticalTripleFrom (board : List (List Int)) (i j : Nat) (candy : Int) (start : Nat) : Bool := decide (start ≤ i) && decide (i < start + 3) && decide (cellAt? board start j = some candy) && decide (cellAt? board (start + 1) j = some candy) && decide (cellAt? board (start + 2) j = some candy) /-- Whether a horizontal run of three `candy` cells covering `(i, j)` starts at `start`. -/ def horizontalTripleFrom (board : List (List Int)) (i j : Nat) (candy : Int) (start : Nat) : Bool := decide (start ≤ j) && decide (j < start + 3) && decide (cellAt? board i start = some candy) && decide (cellAt? board i (start + 1) = some candy) && decide (cellAt? board i (start + 2) = some candy) /-- Decidable form of `isCrushedCell` for one board cell. -/ def cellIsCrushed (board : List (List Int)) (i j : Nat) : Bool := match cellAt? board i j with | some candy => candy != 0 && ((List.range (i + 1)).any (fun start => verticalTripleFrom board i j candy start) || (List.range (j + 1)).any (fun start => horizontalTripleFrom board i j candy start)) | none => false /-- The unique board obtained by zeroing every crushable cell. -/ def crushMarkedBoard (board : List (List Int)) : List (List Int) := board.mapIdx fun i row => row.mapIdx fun j candy => if cellIsCrushed board i j = true then 0 else candy /-- The unique board obtained by dropping every column of `board`. -/ def dropMarkedBoard (board : List (List Int)) : List (List Int) := let width := match board.head? with | some row => row.length | none => 0 (List.range board.length).map fun i => (List.range width).map fun j => let column := columnValues board j let dropped : List Int := List.replicate (column.count 0) 0 ++ column.filter (fun candy => candy != 0) dropped[i]! /-- The unique board after one crush-and-drop round. -/ def stepBoard (board : List (List Int)) : List (List Int) := dropMarkedBoard (crushMarkedBoard board) /-- Decidable form of `Stable`, checking every existing board cell. -/ def boardIsStable (board : List (List Int)) : Bool := (List.range board.length).all fun i => match board[i]? with | some row => (List.range row.length).all fun j => cellIsCrushed board i j = false | none => true /-- Decidable form of `sameShape`. -/ def shapeMatches (before after : List (List Int)) : Bool := decide (before.length = after.length) && (List.range before.length).all fun i => decide ((before[i]?).map (fun row => row.length) = (after[i]?).map (fun row => row.length)) /-- Decidable form of `isCrushOf`. -/ def crushMatches (before after : List (List Int)) : Bool := shapeMatches before after && (List.range before.length).all fun i => match before[i]? with | some row => (List.range row.length).all fun j => let crushed := cellIsCrushed before i j (crushed && decide (cellAt? after i j = some 0)) || (!crushed && decide (cellAt? after i j = cellAt? before i j)) | none => true /-- Decidable form of `dropsTo`. -/ def dropMatches (before after : List (List Int)) : Bool := let width := match before.head? with | some row => row.length | none => 0 shapeMatches before after && (List.range width).all fun j => decide (columnValues after j = List.replicate ((columnValues before j).count 0) 0 ++ (columnValues before j).filter (fun candy => candy != 0)) /-- Decidable form of `CrushDropStep`, using its uniquely determined crushed board. -/ def roundMatches (before after : List (List Int)) : Bool := let crushed := crushMarkedBoard before crushMatches before crushed && dropMatches crushed after /-- Decidable form of `isCrushTrace`. -/ def traceMatches (start finish : List (List Int)) (boards : List (List (List Int))) : Bool := decide (boards.head? = some start) && decide (boards.getLast? = some finish) && (List.range boards.length).all fun i => match boards[i]?, boards[i + 1]? with | some before, some after => roundMatches before after | _, _ => true /-- The trace of exactly `rounds` crush-and-drop steps beginning at `board`. -/ def traceFrom (board : List (List Int)) : Nat → List (List (List Int)) | 0 => [board] | rounds + 1 => board :: traceFrom (stepBoard board) rounds /-- The number of nonzero cells in `board`. -/ def nonzeroCellCount (board : List (List Int)) : Nat := (board.map fun row => row.length - row.count 0).sum /-- Whether the trace of `rounds` steps reaches the stable board `result`. -/ def traceReachesResult (input result : List (List Int)) (rounds : Nat) : Bool := let trace := traceFrom input rounds traceMatches input result trace && boardIsStable result /-- Whether the trace of `rounds` steps excludes stable final boards other than `result`. -/ def traceExcludesOther (input result : List (List Int)) (rounds : Nat) : Bool := let trace := traceFrom input rounds match trace.getLast? with | some stableBoard => !(traceMatches input stableBoard trace && boardIsStable stableBoard) || decide (stableBoard = result) | none => true /-- Executable checker for `candyCrush_spec` over round counts bounded by nonzero cells. -/ def candyCrush_check (input : Input) (result : Output) : Bool := let roundLimit := nonzeroCellCount input / 3 (List.range (roundLimit + 1)).any (traceReachesResult input result) && (List.range (roundLimit + 1)).all (traceExcludesOther input result) /-- A rectangular board with `n` rows of width `w`. -/ def Shape (n w : Nat) (b : List (List Int)) : Prop := b.length = n ∧ ∀ row ∈ b, row.length = w /-- Nonzero cells of the first `w` columns, counted column by column. -/ def colMeasure (w : Nat) (b : List (List Int)) : Nat := ((List.range w).map fun j => (columnValues b j).countP (fun x => x != 0)).sum theorem cellAt?_eq (b : List (List Int)) (i j : Nat) : cellAt? b i j = b[i]?.bind (fun row => row[j]?) := rfl theorem not_crushed_of_none (b : List (List Int)) (i j : Nat) (h : cellAt? b i j = none) : ¬ isCrushedCell b i j := by simp [isCrushedCell, h] theorem cellIsCrushed_iff (b : List (List Int)) (i j : Nat) : cellIsCrushed b i j = true ↔ isCrushedCell b i j := by unfold cellIsCrushed isCrushedCell cases hc : cellAt? b i j with | none => simp | some candy => simp only [verticalTripleFrom, horizontalTripleFrom, Bool.and_eq_true, Bool.or_eq_true, List.any_eq_true, List.mem_range, decide_eq_true_eq, bne_iff_ne, ne_eq] constructor · rintro ⟨h0, (⟨s, _, ⟨⟨⟨⟨h1, h2⟩, h3⟩, h4⟩, h5⟩⟩ | ⟨s, _, ⟨⟨⟨⟨h1, h2⟩, h3⟩, h4⟩, h5⟩⟩)⟩ · exact ⟨h0, Or.inl ⟨s, h1, h2, h3, h4, h5⟩⟩ · exact ⟨h0, Or.inr ⟨s, h1, h2, h3, h4, h5⟩⟩ · rintro ⟨h0, (⟨s, h1, h2, h3, h4, h5⟩ | ⟨s, h1, h2, h3, h4, h5⟩)⟩ · exact ⟨h0, Or.inl ⟨s, by omega, ⟨⟨⟨⟨h1, h2⟩, h3⟩, h4⟩, h5⟩⟩⟩ · exact ⟨h0, Or.inr ⟨s, by omega, ⟨⟨⟨⟨h1, h2⟩, h3⟩, h4⟩, h5⟩⟩⟩ theorem stable_iff (b : List (List Int)) : boardIsStable b = true ↔ Stable b := by unfold boardIsStable Stable simp only [List.all_eq_true, List.mem_range] constructor · intro hall i j hc by_cases hi : i < b.length · have h1 := hall i hi rw [List.getElem?_eq_getElem hi] at h1 simp only [List.all_eq_true, List.mem_range] at h1 by_cases hj : j < b[i].length · have h2 := h1 j hj rw [(cellIsCrushed_iff b i j).mpr hc] at h2 exact absurd h2 (by decide) · refine not_crushed_of_none b i j ?_ hc rw [cellAt?_eq, List.getElem?_eq_getElem hi] exact List.getElem?_eq_none (by omega) · refine not_crushed_of_none b i j ?_ hc rw [cellAt?_eq, List.getElem?_eq_none (by omega)] rfl · intro hs i hi rw [List.getElem?_eq_getElem hi] simp only [List.all_eq_true, List.mem_range] intro j _ cases hcc : cellIsCrushed b i j with | false => rfl | true => exact absurd ((cellIsCrushed_iff b i j).mp hcc) (hs i j) theorem board_ext (x y : List (List Int)) (hl : x.length = y.length) (h : ∀ i j, cellAt? x i j = cellAt? y i j) : x = y := by apply List.ext_getElem? intro i by_cases hi : i < x.length · have hi' : i < y.length := by omega rw [List.getElem?_eq_getElem hi, List.getElem?_eq_getElem hi'] congr 1 apply List.ext_getElem? intro j have := h i j rw [cellAt?_eq, cellAt?_eq, List.getElem?_eq_getElem hi, List.getElem?_eq_getElem hi'] at this exact this · rw [List.getElem?_eq_none (by omega), List.getElem?_eq_none (by omega)] theorem crush_unique (b c1 c2 : List (List Int)) (h1 : isCrushOf b c1) (h2 : isCrushOf b c2) : c1 = c2 := by obtain ⟨⟨hl1, _⟩, hc1⟩ := h1 obtain ⟨⟨hl2, _⟩, hc2⟩ := h2 refine board_ext c1 c2 (by omega) (fun i j => ?_) rcases hc1 i j with ⟨hx, e1⟩ | ⟨hx, e1⟩ <;> rcases hc2 i j with ⟨hy, e2⟩ | ⟨hy, e2⟩ · rw [e1, e2] · exact absurd hx hy · exact absurd hy hx · rw [e1, e2] theorem drop_unique (c a1 a2 : List (List Int)) (h1 : dropsTo c a1) (h2 : dropsTo c a2) : a1 = a2 := by obtain ⟨⟨hl1, hs1⟩, hc1⟩ := h1 obtain ⟨⟨hl2, hs2⟩, hc2⟩ := h2 refine board_ext a1 a2 (by omega) (fun i j => ?_) have hcol : columnValues a1 j = columnValues a2 j := by rw [hc1 j, hc2 j] have hrow : (a1[i]?).map (fun row => row.length) = (a2[i]?).map (fun row => row.length) := by rw [← hs1 i, ← hs2 i] have hv := congrArg (fun l => l[i]?) hcol simp only [columnValues, List.getElem?_map] at hv rw [cellAt?_eq, cellAt?_eq] cases e1 : a1[i]? with | none => cases e2 : a2[i]? with | none => rfl | some r2 => rw [e1, e2] at hrow; simp at hrow | some r1 => cases e2 : a2[i]? with | none => rw [e1, e2] at hrow; simp at hrow | some r2 => rw [e1, e2] at hrow hv simp only [Option.map_some, Option.some.injEq] at hrow hv show r1[j]? = r2[j]? by_cases hj : j < r1.length · have hj2 : j < r2.length := by omega rw [List.getElem!_eq_getElem?_getD, List.getElem!_eq_getElem?_getD, List.getElem?_eq_getElem hj, List.getElem?_eq_getElem hj2] at hv rw [List.getElem?_eq_getElem hj, List.getElem?_eq_getElem hj2] simpa using hv · rw [List.getElem?_eq_none (by omega), List.getElem?_eq_none (by omega)] theorem cellAt?_crush (b : List (List Int)) (i j : Nat) : cellAt? (crushMarkedBoard b) i j = (cellAt? b i j).map (fun candy => if cellIsCrushed b i j = true then 0 else candy) := by simp only [cellAt?_eq, crushMarkedBoard, List.getElem?_mapIdx] rcases b[i]? with _ | row · rfl · simp [List.getElem?_mapIdx] theorem crush_spec (n w : Nat) (b : List (List Int)) (hb : Shape n w b) : isCrushOf b (crushMarkedBoard b) ∧ Shape n w (crushMarkedBoard b) := by refine ⟨⟨⟨by simp [crushMarkedBoard], fun i => ?_⟩, fun i j => ?_⟩, ?_, ?_⟩ · simp [crushMarkedBoard, List.getElem?_mapIdx, Function.comp_def] · by_cases hc : isCrushedCell b i j · left refine ⟨hc, ?_⟩ rw [cellAt?_crush] cases hcell : cellAt? b i j with | none => exact absurd hc (not_crushed_of_none b i j hcell) | some candy => simp [(cellIsCrushed_iff b i j).mpr hc] · right refine ⟨hc, ?_⟩ have hf : cellIsCrushed b i j = false := by cases hcc : cellIsCrushed b i j with | false => rfl | true => exact absurd ((cellIsCrushed_iff b i j).mp hcc) hc rw [cellAt?_crush] simp [hf] · simp [crushMarkedBoard, hb.1] · intro row hr simp only [crushMarkedBoard, List.mem_mapIdx] at hr obtain ⟨i, hi, rfl⟩ := hr simp [hb.2 _ (List.getElem_mem hi)] theorem drop_cons (r : List Int) (rs : List (List Int)) : dropMarkedBoard (r :: rs) = (List.range (r :: rs).length).map fun i => (List.range r.length).map fun j => (List.replicate ((columnValues (r :: rs) j).count 0) 0 ++ (columnValues (r :: rs) j).filter (fun candy => candy != 0))[i]! := rfl theorem dropped_length (l : List Int) : (List.replicate (l.count 0) 0 ++ l.filter (fun candy => candy != 0)).length = l.length := by induction l with | nil => simp | cons x l ih => by_cases hx : x = 0 · subst hx simp only [List.length_append, List.length_replicate] at ih simp omega · simp only [List.length_append, List.length_replicate] at ih simp [hx] omega theorem map_range_getElem! (l : List Int) (n : Nat) (h : l.length = n) : (List.range n).map (fun i => l[i]!) = l := by apply List.ext_getElem? intro i rw [List.getElem?_map] by_cases hi : i < n · rw [List.getElem?_range hi, List.getElem?_eq_getElem (by omega)] simp [List.getElem!_eq_getElem?_getD, List.getElem?_eq_getElem (show i < l.length by omega)] · rw [List.getElem?_eq_none (by simp; omega), List.getElem?_eq_none (by omega)] rfl theorem col_of_grid (N W : Nat) (g : Nat → Nat → Int) (j : Nat) : columnValues ((List.range N).map fun i => (List.range W).map fun j => g j i) j = if j < W then (List.range N).map (g j) else List.replicate N 0 := by unfold columnValues rw [List.map_map] split_ifs with hj · apply List.map_congr_left intro i _ simp [List.getElem!_eq_getElem?_getD, List.getElem?_range hj] · rw [List.eq_replicate_iff] refine ⟨by simp, ?_⟩ intro x hx simp only [List.mem_map, Function.comp_apply] at hx obtain ⟨i, _, rfl⟩ := hx simp [hj] theorem col_out (n w : Nat) (c : List (List Int)) (hc : Shape n w c) (j : Nat) (hj : ¬ j < w) : columnValues c j = List.replicate c.length 0 := by rw [List.eq_replicate_iff] refine ⟨by simp [columnValues], fun x hx => ?_⟩ simp only [columnValues, List.mem_map] at hx obtain ⟨row, hr, rfl⟩ := hx rw [List.getElem!_eq_getElem?_getD, List.getElem?_eq_none (by rw [hc.2 row hr]; omega)] rfl theorem drop_spec (n w : Nat) (c : List (List Int)) (hn : 1 ≤ n) (hc : Shape n w c) : dropsTo c (dropMarkedBoard c) ∧ Shape n w (dropMarkedBoard c) := by rcases c with _ | ⟨r, rs⟩ · have := hc.1 simp at this omega have hw : r.length = w := hc.2 r (by simp) have hlen : (r :: rs).length = n := hc.1 rw [drop_cons] refine ⟨⟨⟨by simp, fun i => ?_⟩, fun j => ?_⟩, ⟨by simp [hlen], fun row hr => ?_⟩⟩ · by_cases hi : i < (r :: rs).length · rw [List.getElem?_eq_getElem hi, List.getElem?_map, List.getElem?_range hi] simp [hc.2 _ (List.getElem_mem hi), hw] · rw [List.getElem?_eq_none (by omega), List.getElem?_map, List.getElem?_eq_none (by simp only [List.length_range]; omega)] rfl · rw [col_of_grid] split_ifs with hj · exact map_range_getElem! _ _ (by rw [dropped_length]; simp [columnValues]) · rw [col_out n w (r :: rs) hc j (by omega)] simp · simp only [List.mem_map] at hr obtain ⟨i, _, rfl⟩ := hr simp [hw] theorem step_spec (n w : Nat) (b : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) : CrushDropStep b (stepBoard b) ∧ Shape n w (stepBoard b) := by obtain ⟨h1, h2⟩ := crush_spec n w b hb obtain ⟨h3, h4⟩ := drop_spec n w _ hn h2 exact ⟨⟨_, h1, h3⟩, h4⟩ theorem step_det (n w : Nat) (b a : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) (h : CrushDropStep b a) : a = stepBoard b := by obtain ⟨c, hc, ha⟩ := h obtain ⟨h1, h2⟩ := crush_spec n w b hb have e := crush_unique b c _ hc h1 subst e exact drop_unique _ a _ ha (drop_spec n w _ hn h2).1 theorem shapeMatches_of (b c : List (List Int)) (h : sameShape b c) : shapeMatches b c = true := by obtain ⟨hl, hs⟩ := h simp only [shapeMatches, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, List.mem_range] exact ⟨hl, fun i _ => hs i⟩ theorem crushMatches_of (b c : List (List Int)) (h : isCrushOf b c) : crushMatches b c = true := by obtain ⟨hsh, hcell⟩ := h unfold crushMatches rw [shapeMatches_of b c hsh, Bool.true_and] simp only [List.all_eq_true, List.mem_range] intro i hi rw [List.getElem?_eq_getElem hi] simp only [List.all_eq_true, List.mem_range] intro j _ rcases hcell i j with ⟨hx, e⟩ | ⟨hx, e⟩ · rw [(cellIsCrushed_iff b i j).mpr hx, e] simp · have hf : cellIsCrushed b i j = false := by cases hcc : cellIsCrushed b i j with | false => rfl | true => exact absurd ((cellIsCrushed_iff b i j).mp hcc) hx rw [hf, e] simp theorem dropMatches_of (c a : List (List Int)) (h : dropsTo c a) : dropMatches c a = true := by obtain ⟨hsh, hcol⟩ := h unfold dropMatches simp only [shapeMatches_of c a hsh, Bool.true_and, List.all_eq_true, List.mem_range, decide_eq_true_eq] intro j _ exact hcol j theorem roundMatches_step (n w : Nat) (b : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) : roundMatches b (stepBoard b) = true := by obtain ⟨h1, h2⟩ := crush_spec n w b hb obtain ⟨h3, _⟩ := drop_spec n w _ hn h2 show (crushMatches b (crushMarkedBoard b) && dropMatches (crushMarkedBoard b) (dropMarkedBoard (crushMarkedBoard b))) = true rw [crushMatches_of _ _ h1, dropMatches_of _ _ h3] rfl theorem gn_of_drops (c a : List (List Int)) (h : dropsTo c a) : dropsTo a a := by obtain ⟨_, hcol⟩ := h refine ⟨⟨rfl, fun _ => rfl⟩, fun j => ?_⟩ rw [hcol j] have h0 : List.count 0 (List.filter (fun candy => candy != 0) (columnValues c j)) = 0 := List.count_eq_zero.mpr (fun hm => by simp at hm) simp [List.filter_append, List.filter_filter, h0] theorem fixed_of_stable (n w : Nat) (b : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) (hs : Stable b) (hg : dropsTo b b) : stepBoard b = b := by have hcr : isCrushOf b b := ⟨⟨rfl, fun _ => rfl⟩, fun i j => Or.inr ⟨hs i j, rfl⟩⟩ exact (step_det n w b b hn hb ⟨b, hcr, hg⟩).symm theorem measure_drop (w : Nat) (c a : List (List Int)) (h : dropsTo c a) : colMeasure w a = colMeasure w c := by obtain ⟨_, hcol⟩ := h unfold colMeasure congr 1 apply List.map_congr_left intro j _ rw [hcol j] simp [List.countP_append, List.countP_filter] /-- One when the cell exists and is nonzero. -/ def ind (X : List (List Int)) (i j : Nat) : Nat := if (cellAt? X i j).getD 0 ≠ 0 then 1 else 0 theorem countP_col (X : List (List Int)) (j : Nat) : (columnValues X j).countP (fun x => x != 0) = ∑ i ∈ Finset.range X.length, ind X i j := by induction X with | nil => simp [columnValues] | cons r X ih => rw [List.length_cons, Finset.sum_range_succ'] have e : columnValues (r :: X) j = r[j]! :: columnValues X j := rfl have es : ∀ i, ind (r :: X) (i + 1) j = ind X i j := fun i => rfl rw [e, List.countP_cons, ih] simp only [es] simp [ind, cellAt?_eq, List.getElem!_eq_getElem?_getD] theorem list_sum_range (w : Nat) (f : Nat → Nat) : ((List.range w).map f).sum = ∑ j ∈ Finset.range w, f j := by induction w with | zero => simp | succ w ih => rw [List.range_succ, List.map_append, List.sum_append, ih, Finset.sum_range_succ] simp theorem colMeasure_eq (w : Nat) (X : List (List Int)) : colMeasure w X = ∑ j ∈ Finset.range w, ∑ i ∈ Finset.range X.length, ind X i j := by unfold colMeasure simp only [countP_col] exact list_sum_range w _ theorem ind_crush_le (b : List (List Int)) (i j : Nat) : ind (crushMarkedBoard b) i j ≤ ind b i j := by unfold ind rw [cellAt?_crush] cases cellAt? b i j with | none => simp | some c => by_cases hc : cellIsCrushed b i j = true · simp [hc] · simp [hc] split_ifs <;> omega theorem crushed_some (b : List (List Int)) (i j : Nat) (h : isCrushedCell b i j) : ∃ c, cellAt? b i j = some c ∧ c ≠ 0 := by cases hcell : cellAt? b i j with | none => simp [isCrushedCell, hcell] at h | some c => simp only [isCrushedCell, hcell] at h exact ⟨c, rfl, h.1⟩ theorem ind_crush_lt (b : List (List Int)) (i j : Nat) (h : isCrushedCell b i j) : ind (crushMarkedBoard b) i j + 1 ≤ ind b i j := by obtain ⟨c, hcell, hc0⟩ := crushed_some b i j h have hc := (cellIsCrushed_iff b i j).mpr h unfold ind rw [cellAt?_crush, hcell] simp [hc, hc0] theorem vert_crushed (b : List (List Int)) (s j : Nat) (c : Int) (hc : c ≠ 0) (h0 : cellAt? b s j = some c) (h1 : cellAt? b (s + 1) j = some c) (h2 : cellAt? b (s + 2) j = some c) (k : Nat) (hk : k < 3) : isCrushedCell b (s + k) j := by have hv : cellAt? b (s + k) j = some c := by interval_cases k · simpa using h0 · exact h1 · exact h2 simp only [isCrushedCell, hv] exact ⟨hc, Or.inl ⟨s, by omega, by omega, h0, h1, h2⟩⟩ theorem horiz_crushed (b : List (List Int)) (i s : Nat) (c : Int) (hc : c ≠ 0) (h0 : cellAt? b i s = some c) (h1 : cellAt? b i (s + 1) = some c) (h2 : cellAt? b i (s + 2) = some c) (k : Nat) (hk : k < 3) : isCrushedCell b i (s + k) := by have hv : cellAt? b i (s + k) = some c := by interval_cases k · simpa using h0 · exact h1 · exact h2 simp only [isCrushedCell, hv] exact ⟨hc, Or.inr ⟨s, by omega, by omega, h0, h1, h2⟩⟩ theorem cell_bounds (n w : Nat) (b : List (List Int)) (hb : Shape n w b) (i j : Nat) (c : Int) (h : cellAt? b i j = some c) : i < n ∧ j < w := by rw [cellAt?_eq] at h have hl := hb.1 by_cases hi : i < b.length · rw [List.getElem?_eq_getElem hi] at h have h' : b[i][j]? = some c := h have hw := hb.2 _ (List.getElem_mem hi) by_cases hj : j < b[i].length · exact ⟨by omega, by omega⟩ · rw [List.getElem?_eq_none (by omega)] at h' exact absurd h' (by simp) · rw [List.getElem?_eq_none (by omega)] at h exact absurd h (by simp) theorem sum_add_card_le (s t : Finset ℕ) (ht : t ⊆ s) (f g : ℕ → ℕ) (hle : ∀ x ∈ s, g x ≤ f x) (hlt : ∀ x ∈ t, g x + 1 ≤ f x) : ∑ x ∈ s, g x + t.card ≤ ∑ x ∈ s, f x := by have h1 : ∑ x ∈ s, f x = ∑ x ∈ s, g x + ∑ x ∈ s, (f x - g x) := by rw [← Finset.sum_add_distrib] exact Finset.sum_congr rfl (fun x hx => by have := hle x hx; omega) have h2 : t.card ≤ ∑ x ∈ s, (f x - g x) := by calc t.card = ∑ x ∈ t, 1 := by simp _ ≤ ∑ x ∈ t, (f x - g x) := Finset.sum_le_sum (fun x hx => by have := hlt x hx; omega) _ ≤ ∑ x ∈ s, (f x - g x) := Finset.sum_le_sum_of_subset_of_nonneg ht (fun _ _ _ => Nat.zero_le _) omega theorem sum_le_add (s : Finset ℕ) (a : ℕ) (ha : a ∈ s) (f g : ℕ → ℕ) (hle : ∀ x ∈ s, g x ≤ f x) (k : ℕ) (hk : g a + k ≤ f a) : ∑ x ∈ s, g x + k ≤ ∑ x ∈ s, f x := by rw [← Finset.add_sum_erase s f ha, ← Finset.add_sum_erase s g ha] have h3 : ∑ x ∈ s.erase a, g x ≤ ∑ x ∈ s.erase a, f x := Finset.sum_le_sum (fun x hx => hle x (Finset.mem_of_mem_erase hx)) omega theorem measure_crush (n w : Nat) (b : List (List Int)) (hb : Shape n w b) (hs : ¬ Stable b) : colMeasure w (crushMarkedBoard b) + 3 ≤ colMeasure w b := by have hlen : (crushMarkedBoard b).length = b.length := by simp [crushMarkedBoard] rw [colMeasure_eq, colMeasure_eq, hlen] simp only [Stable, not_forall, not_not] at hs obtain ⟨i0, j0, hc⟩ := hs obtain ⟨c, hcell, hc0⟩ := crushed_some b i0 j0 hc have hc' := hc simp only [isCrushedCell, hcell] at hc' have hl := hb.1 obtain ⟨-, (⟨s, -, -, h0, h1, h2⟩ | ⟨s, -, -, h0, h1, h2⟩)⟩ := hc' · have hb2 := cell_bounds n w b hb _ _ _ h2 have hsub : Finset.Ico s (s + 3) ⊆ Finset.range b.length := by intro x hx rw [Finset.mem_Ico] at hx rw [Finset.mem_range] omega have key := sum_add_card_le (Finset.range b.length) (Finset.Ico s (s + 3)) hsub (fun i => ind b i j0) (fun i => ind (crushMarkedBoard b) i j0) (fun i _ => ind_crush_le b i j0) (fun i hi => by rw [Finset.mem_Ico] at hi obtain ⟨k, rfl⟩ : ∃ k, i = s + k := ⟨i - s, by omega⟩ exact ind_crush_lt b _ j0 (vert_crushed b s j0 c hc0 h0 h1 h2 k (by omega))) rw [Nat.card_Ico] at key simp only [Nat.add_sub_cancel_left] at key exact sum_le_add (Finset.range w) j0 (Finset.mem_range.mpr hb2.2) (fun j => ∑ i ∈ Finset.range b.length, ind b i j) (fun j => ∑ i ∈ Finset.range b.length, ind (crushMarkedBoard b) i j) (fun j _ => Finset.sum_le_sum (fun i _ => ind_crush_le b i j)) 3 key · have hb2 := cell_bounds n w b hb _ _ _ h2 have hsub : Finset.Ico s (s + 3) ⊆ Finset.range w := by intro x hx rw [Finset.mem_Ico] at hx rw [Finset.mem_range] omega have key := sum_add_card_le (Finset.range w) (Finset.Ico s (s + 3)) hsub (fun j => ∑ i ∈ Finset.range b.length, ind b i j) (fun j => ∑ i ∈ Finset.range b.length, ind (crushMarkedBoard b) i j) (fun j _ => Finset.sum_le_sum (fun i _ => ind_crush_le b i j)) (fun j hj => by rw [Finset.mem_Ico] at hj obtain ⟨k, rfl⟩ : ∃ k, j = s + k := ⟨j - s, by omega⟩ exact sum_le_add (Finset.range b.length) i0 (Finset.mem_range.mpr (by omega)) (fun i => ind b i (s + k)) (fun i => ind (crushMarkedBoard b) i (s + k)) (fun i _ => ind_crush_le b i (s + k)) 1 (ind_crush_lt b i0 (s + k) (horiz_crushed b i0 s c hc0 h0 h1 h2 k (by omega)))) rw [Nat.card_Ico] at key simp only [Nat.add_sub_cancel_left] at key exact key theorem shape_iter (n w : Nat) (b : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) : ∀ k, Shape n w (stepBoard^[k] b) := by intro k induction k with | zero => exact hb | succ k ih => rw [Function.iterate_succ_apply'] exact (step_spec n w _ hn ih).2 theorem gn_iter (n w : Nat) (b : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) (hg : dropsTo b b) : ∀ k, dropsTo (stepBoard^[k] b) (stepBoard^[k] b) := by intro k cases k with | zero => exact hg | succ k => rw [Function.iterate_succ_apply'] obtain ⟨⟨c, _, hc⟩, _⟩ := step_spec n w _ hn (shape_iter n w b hn hb k) exact gn_of_drops _ _ hc theorem stabilize (n w : Nat) (hn : 1 ≤ n) : ∀ (M : Nat) (b : List (List Int)), Shape n w b → colMeasure w b ≤ M → ∃ r, 3 * r ≤ colMeasure w b ∧ Stable (stepBoard^[r] b) := by intro M induction M with | zero => intro b hb hM by_cases hs : Stable b · exact ⟨0, by omega, hs⟩ · have := measure_crush n w b hb hs omega | succ M ih => intro b hb hM by_cases hs : Stable b · exact ⟨0, by omega, hs⟩ · have h1 := measure_crush n w b hb hs obtain ⟨_, h3⟩ := crush_spec n w b hb have h4 := measure_drop w _ _ (drop_spec n w _ hn h3).1 have e : stepBoard b = dropMarkedBoard (crushMarkedBoard b) := rfl obtain ⟨r, hr, hst⟩ := ih (stepBoard b) (step_spec n w b hn hb).2 (by rw [e, h4]; omega) refine ⟨r + 1, ?_, ?_⟩ · rw [e, h4] at hr omega · rw [Function.iterate_succ_apply] exact hst theorem orbit_stable_eq (n w : Nat) (b : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) (hg : dropsTo b b) (r s : Nat) (hr : Stable (stepBoard^[r] b)) (hs : Stable (stepBoard^[s] b)) : stepBoard^[r] b = stepBoard^[s] b := by have key : ∀ r s, r ≤ s → Stable (stepBoard^[r] b) → stepBoard^[s] b = stepBoard^[r] b := by intro r s hrs hr obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hrs rw [Nat.add_comm, Function.iterate_add_apply] exact Function.iterate_fixed (fixed_of_stable n w _ hn (shape_iter n w b hn hb r) hr (gn_iter n w b hn hb hg r)) d rcases le_total r s with h | h · exact (key r s h hr).symm · exact key s r h hs theorem traceFrom_getElem? (b : List (List Int)) : ∀ r k, (traceFrom b r)[k]? = if k ≤ r then some (stepBoard^[k] b) else none := by intro r induction r generalizing b with | zero => intro k cases k with | zero => simp [traceFrom] | succ k => simp [traceFrom] | succ r ih => intro k cases k with | zero => simp [traceFrom] | succ k => show (b :: traceFrom (stepBoard b) r)[k + 1]? = _ rw [List.getElem?_cons_succ, ih (stepBoard b) k, Function.iterate_succ_apply] by_cases hk : k ≤ r · rw [if_pos hk, if_pos (by omega)] · rw [if_neg hk, if_neg (by omega)] theorem traceFrom_getLast? (b : List (List Int)) (r : Nat) : (traceFrom b r).getLast? = some (stepBoard^[r] b) := by induction r generalizing b with | zero => rfl | succ r ih => show (b :: traceFrom (stepBoard b) r).getLast? = _ simp only [List.getLast?_cons, ih, Option.getD_some, Function.iterate_succ_apply] theorem traceFrom_head? (b : List (List Int)) (r : Nat) : (traceFrom b r).head? = some b := by cases r <;> rfl theorem trace_isCrushTrace (n w : Nat) (b : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) (r : Nat) : isCrushTrace b (stepBoard^[r] b) (traceFrom b r) := by refine ⟨traceFrom_head? b r, traceFrom_getLast? b r, fun i before after h1 h2 => ?_⟩ rw [traceFrom_getElem?] at h1 h2 by_cases hi : i + 1 ≤ r · rw [if_pos (by omega), Option.some.injEq] at h1 rw [if_pos hi, Option.some.injEq] at h2 subst h1 subst h2 rw [Function.iterate_succ_apply'] exact (step_spec n w _ hn (shape_iter n w b hn hb i)).1 · rw [if_neg hi] at h2 exact absurd h2 (by simp) theorem trace_det (n w : Nat) (b : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) (sb : List (List Int)) (tr : List (List (List Int))) (h : isCrushTrace b sb tr) : ∃ m, sb = stepBoard^[m] b := by obtain ⟨hh, hl, hstep⟩ := h have key : ∀ k, k < tr.length → tr[k]? = some (stepBoard^[k] b) := by intro k induction k with | zero => intro _ rw [← List.head?_eq_getElem?] exact hh | succ k ih => intro hk have h1 := ih (by omega) have ha : tr[k + 1]? = some (tr[k + 1]'hk) := List.getElem?_eq_getElem hk have e := step_det n w _ _ hn (shape_iter n w b hn hb k) (hstep k _ _ h1 ha) rw [ha, e, Function.iterate_succ_apply'] have hne : tr.length ≠ 0 := by intro h0 rw [List.length_eq_zero_iff] at h0 subst h0 simp at hh refine ⟨tr.length - 1, ?_⟩ rw [List.getLast?_eq_getElem?, key _ (by omega), Option.some.injEq] at hl exact hl.symm theorem traceMatches_traceFrom (n w : Nat) (b : List (List Int)) (hn : 1 ≤ n) (hb : Shape n w b) (r : Nat) (sb : List (List Int)) : traceMatches b sb (traceFrom b r) = true ↔ sb = stepBoard^[r] b := by simp only [traceMatches, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, List.mem_range, traceFrom_head?, traceFrom_getLast?, Option.some.injEq, true_and] constructor · rintro ⟨h, _⟩ exact h.symm · rintro rfl refine ⟨rfl, fun i _ => ?_⟩ rw [traceFrom_getElem?, traceFrom_getElem?] by_cases hi : i + 1 ≤ r · rw [if_pos (by omega), if_pos hi, Function.iterate_succ_apply'] exact roundMatches_step n w _ hn (shape_iter n w b hn hb i) · rw [if_neg hi] generalize (if i ≤ r then some (stepBoard^[i] b) else none) = o cases o <;> rfl theorem valid_facts (input : List (List Int)) (h : isValidInput input = true) : ∃ n w, 1 ≤ n ∧ Shape n w input ∧ dropsTo input input ∧ colMeasure w input = nonzeroCellCount input := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h obtain ⟨⟨h3, _⟩, hrest⟩ := h rcases input with _ | ⟨r0, rows⟩ · simp at h3 simp only [List.head?_cons, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, beq_iff_eq] at hrest obtain ⟨⟨_, hw⟩, hval⟩ := hrest have hb : Shape (r0 :: rows).length r0.length (r0 :: rows) := ⟨rfl, hw⟩ have hnz : ∀ row ∈ (r0 :: rows), ∀ x ∈ row, x ≠ 0 := by intro row hr x hx have := hval row hr x hx omega have hcol : ∀ j, j < r0.length → ∀ x ∈ columnValues (r0 :: rows) j, x ≠ 0 := by intro j hj x hx simp only [columnValues, List.mem_map] at hx obtain ⟨row, hr, rfl⟩ := hx have hlen := hb.2 row hr rw [List.getElem!_eq_getElem?_getD, List.getElem?_eq_getElem (by omega)] exact hnz row hr _ (List.getElem_mem _) refine ⟨_, _, by simp, hb, ⟨⟨rfl, fun _ => rfl⟩, fun j => ?_⟩, ?_⟩ · by_cases hj : j < r0.length · rw [List.count_eq_zero.mpr (fun hm => hcol j hj 0 hm rfl), List.filter_eq_self.mpr (fun x hx => by simpa using hcol j hj x hx)] simp · have e := col_out _ _ _ hb j hj rw [e] simp · have h1 : colMeasure r0.length (r0 :: rows) = r0.length * (r0 :: rows).length := by unfold colMeasure have hc : ∀ j ∈ List.range r0.length, (columnValues (r0 :: rows) j).countP (fun x => x != 0) = (r0 :: rows).length := by intro j hj rw [List.mem_range] at hj rw [List.countP_eq_length.mpr (fun x hx => by simpa using hcol j hj x hx)] simp [columnValues] rw [List.map_congr_left hc] simp have h2 : nonzeroCellCount (r0 :: rows) = (r0 :: rows).length * r0.length := by unfold nonzeroCellCount have hc : ∀ row ∈ (r0 :: rows), row.length - row.count 0 = r0.length := by intro row hr rw [hb.2 row hr, List.count_eq_zero.mpr (fun hm => hnz row hr 0 hm rfl)] simp rw [List.map_congr_left hc] simp ring rw [h1, h2, Nat.mul_comm] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem candyCrush_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : candyCrush_check input result ↔ candyCrush_spec input result := by obtain ⟨n, w, hn, hb, hg, hM⟩ := valid_facts input h simp only [candyCrush_check, Bool.and_eq_true, List.any_eq_true, List.all_eq_true, List.mem_range] unfold candyCrush_spec constructor · rintro ⟨⟨r, _, hreach⟩, _⟩ simp only [traceReachesResult, Bool.and_eq_true] at hreach obtain ⟨htm, hst⟩ := hreach have hres := (traceMatches_traceFrom n w input hn hb r result).mp htm subst hres refine ⟨⟨traceFrom input r, trace_isCrushTrace n w input hn hb r, (stable_iff _).mp hst⟩, ?_⟩ rintro trace sb ⟨htr, hsb⟩ obtain ⟨m, rfl⟩ := trace_det n w input hn hb sb trace htr exact orbit_stable_eq n w input hn hb hg m r hsb ((stable_iff _).mp hst) · rintro ⟨⟨trace, htr, hst⟩, huniq⟩ obtain ⟨m, rfl⟩ := trace_det n w input hn hb _ trace htr obtain ⟨r, hr, hsr⟩ := stabilize n w hn _ input hb le_rfl have e := orbit_stable_eq n w input hn hb hg r m hsr hst refine ⟨⟨r, by omega, ?_⟩, fun r' _ => ?_⟩ · simp only [traceReachesResult, Bool.and_eq_true] rw [← e] exact ⟨(traceMatches_traceFrom n w input hn hb r _).mpr rfl, (stable_iff _).mpr hsr⟩ · simp only [traceExcludesOther, traceFrom_getLast?] by_cases hs' : Stable (stepBoard^[r'] input) · have := huniq (traceFrom input r') _ ⟨trace_isCrushTrace n w input hn hb r', hs'⟩ simp [this] · have hf : boardIsStable (stepBoard^[r'] input) = false := by cases hb' : boardIsStable (stepBoard^[r'] input) with | false => rfl | true => exact absurd ((stable_iff _).mp hb') hs' simp [hf] /-! ### Implementation helpers -/ /-- Converts a board list to arrays for constant-time cell reads and writes. -/ def boardRows (board : List (List Int)) : Array (Array Int) := board.toArray.map (fun row => row.toArray) /-- Reads cell `(i, j)`, returning `0` outside the array shape. -/ def cellValue (rows : Array (Array Int)) (i j : Nat) : Int := (rows.getD i #[]).getD j 0 /-- Marks the horizontal span `[start, finish)` in row `i`. -/ def markHorizontalRun (marks : Array (Array Bool)) (i start finish : Nat) : Array (Array Bool) := (List.range (finish - start)).foldl (fun acc k => let j := start + k if h : i < acc.size then let row := acc[i] if h2 : j < row.size then acc.set i (row.set j true h2) h else acc else acc) marks /-- Marks the vertical span `[start, finish)` in column `j`. -/ def markVerticalRun (marks : Array (Array Bool)) (j start finish : Nat) : Array (Array Bool) := (List.range (finish - start)).foldl (fun acc k => let i := start + k if h : i < acc.size then let row := acc[i] if h2 : j < row.size then acc.set i (row.set j true h2) h else acc else acc) marks /-- Scans one row for runs of equal nonzero candies and marks every run of length at least three. -/ def scanRowForRuns (rows : Array (Array Int)) (marks : Array (Array Bool)) (i n : Nat) : Array (Array Bool) := let step := fun (state : Array (Array Bool) × Nat × Int) (j : Nat) => let acc := state.1 let start := state.2.1 let val := state.2.2 let current := if j < n then cellValue rows i j else 0 if current != 0 && current == val then (acc, start, val) else let acc1 := if val != 0 && start + 3 ≤ j then markHorizontalRun acc i start j else acc let start2 := if current != 0 then j else j + 1 let val2 := if current != 0 then current else 0 (acc1, start2, val2) ((List.range (n + 1)).foldl step (marks, 0, 0)).1 /-- Scans one column for runs of equal nonzero candies and marks every run of length at least three. -/ def scanColumnForRuns (rows : Array (Array Int)) (marks : Array (Array Bool)) (j m : Nat) : Array (Array Bool) := let step := fun (state : Array (Array Bool) × Nat × Int) (i : Nat) => let acc := state.1 let start := state.2.1 let val := state.2.2 let current := if i < m then cellValue rows i j else 0 if current != 0 && current == val then (acc, start, val) else let acc1 := if val != 0 && start + 3 ≤ i then markVerticalRun acc j start i else acc let start2 := if current != 0 then i else i + 1 let val2 := if current != 0 then current else 0 (acc1, start2, val2) ((List.range (m + 1)).foldl step (marks, 0, 0)).1 /-- Marks every cell belonging to a horizontal or vertical run of at least three equal nonzero candies. -/ def markCrushableCells (rows : Array (Array Int)) : Array (Array Bool) := let m := rows.size let n := rows.foldl (fun acc row => Nat.max acc row.size) 0 let initial := rows.map (fun row => (List.replicate row.size false).toArray) let afterRows := (List.range m).foldl (fun acc i => scanRowForRuns rows acc i n) initial (List.range n).foldl (fun acc j => scanColumnForRuns rows acc j m) afterRows /-- Applies gravity to unmarked nonzero candies, putting zeros above survivors in every column. -/ def dropColumns (rows : Array (Array Int)) (marks : Array (Array Bool)) : List (List Int) := let m := rows.size let n := rows.foldl (fun acc row => Nat.max acc row.size) 0 let emptyOut := (List.replicate m #[]).toArray let filled := (List.range n).foldl (fun acc j => let survivors := (List.range m).foldl (fun col i => let candy := cellValue rows i j let crushed := (marks.getD i #[]).getD j false if candy != 0 && !crushed then col.push candy else col) #[] let zeros := m - survivors.size let column := (List.replicate zeros 0).toArray ++ survivors (List.range m).foldl (fun accRows i => let row := accRows.getD i #[] if h : i < accRows.size then accRows.set i (row.push (column.getD i 0)) h else accRows) acc) emptyOut filled.toList.map (fun row => row.toList) /-- Produces the board after one simultaneous crush followed by column gravity. -/ def stepBoardEfficient (board : List (List Int)) : List (List Int) := let rows := boardRows board let marks := markCrushableCells rows dropColumns rows marks /-! ### Main algorithm (impl) -/ /-- Iterates efficient crush-and-drop steps to the fixed point using the nonzero-cell round bound. -/ def crushCandies (input : Input) : Output := let rounds := nonzeroCellCount input / 3 + 1 (List.range rounds).foldl (fun board _ => let next := stepBoardEfficient board if next == board then board else next) input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem crushCandies_correct (input : Input) (h : isValidInput input) : candyCrush_spec input (crushCandies input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([[1, 3, 5, 5, 2], [3, 4, 3, 3, 1], [3, 2, 4, 5, 2], [2, 4, 4, 5, 5], [1, 4, 4, 1, 1]]) #guard isValidInput ([[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]) #guard isValidInput ([[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([[1, 1, 1], [1, 1, 1, 1], [1, 1, 1]])) #guard !(isValidInput ([[1, 1, 1], [1, 0, 1], [1, 1, 1]])) #guard !(isValidInput ([[1, 1, 1], [1, 1, 1]])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard candyCrush_check [[1, 3, 5, 5, 2], [3, 4, 3, 3, 1], [3, 2, 4, 5, 2], [2, 4, 4, 5, 5], [1, 4, 4, 1, 1]] [[1, 3, 0, 0, 0], [3, 4, 0, 5, 2], [3, 2, 0, 3, 1], [2, 4, 0, 5, 2], [1, 4, 3, 1, 1]] #guard candyCrush_check [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]] [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] #guard candyCrush_check [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]] [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(candyCrush_check [[1, 3, 5, 5, 2], [3, 4, 3, 3, 1], [3, 2, 4, 5, 2], [2, 4, 4, 5, 5], [1, 4, 4, 1, 1]] [[1, 3, 0, 0, 0], [3, 4, 0, 5, 2], [3, 2, 0, 3, 1], [2, 4, 0, 5, 2], [1, 4, 2, 1, 1]]) #guard !(candyCrush_check [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]] [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [1, 2, 3, 4, 5]]) #guard !(candyCrush_check [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]] [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard crushCandies [[1, 3, 5, 5, 2], [3, 4, 3, 3, 1], [3, 2, 4, 5, 2], [2, 4, 4, 5, 5], [1, 4, 4, 1, 1]] == [[1, 3, 0, 0, 0], [3, 4, 0, 5, 2], [3, 2, 0, 3, 1], [2, 4, 0, 5, 2], [1, 4, 3, 1, 1]] #guard crushCandies [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]] == [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] #guard crushCandies [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]] == [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard candyCrush_check [[1, 3, 5, 5, 2], [3, 4, 3, 3, 1], [3, 2, 4, 5, 2], [2, 4, 4, 5, 5], [1, 4, 4, 1, 1]] (crushCandies [[1, 3, 5, 5, 2], [3, 4, 3, 3, 1], [3, 2, 4, 5, 2], [2, 4, 4, 5, 5], [1, 4, 4, 1, 1]]) #guard candyCrush_check [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]] (crushCandies [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]) #guard candyCrush_check [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]] (crushCandies [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]) end PCandyCrush