import Mathlib /-! # Minimum Swaps To Group All 1S Together Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array. ## Constraints - 1 <= data.length <= 10^5 - data[i] is either 0 or 1. ## Provided examples - `data = [1, 0, 1, 0, 1]` → `1` - `data = [0, 0, 0, 1, 0]` → `0` - `data = [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1]` → `3` ## Synthesized negative examples - invalid input: `data = []` ([structural] a predicate that admits 1 <= data.length <= 10^5. empty array where at least one element is required) - invalid input: `data = [2]` ([structural] a predicate that admits data[i] is either 0 or 1.. a predicate that allows non-negative integers accepts it) - invalid input: `data = [-1]` ([structural] a predicate that admits data[i] is either 0 or 1.. a predicate that allows negative integers accepts it) - `data = [1, 0, 1, 0, 1]` → `0` is wrong ([structural] drops the requirement that the 1s be grouped together. no swaps needed if contiguity is ignored) - `data = [0, 0, 0, 1, 0]` → `2` is wrong ([structural] minimality stated as achievability alone. 2 is achieved by redundant swaps but is not least) - `data = [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1]` → `2` is wrong ([structural] minimum stated without soundness; no swap sequence uses only 2 swaps. Two is below every achievable swap count for this array.) -/ namespace PMinimumSwapsToGroupAll1sTogether abbrev Input := List Int abbrev Output := Nat /-! ### Specification helpers -/ /-- Swaps the entries at positions `i` and `j` of `l`. -/ def applySwap (l : List Int) (i j : Nat) : List Int := (l.set i (l.getD j 0)).set j (l.getD i 0) /-- Applies a sequence of swaps to `l` in order. -/ def applySwapSeq (l : List Int) (swaps : List (Nat × Nat)) : List Int := match swaps with | [] => l | (i, j) :: rest => applySwapSeq (applySwap l i j) rest /-- The 1s of `l` form one contiguous block, vacuously true when there are none. -/ def onesContiguous (l : List Int) : Prop := ∃ w : List Int, w <:+: l ∧ w.length = l.count 1 ∧ ∀ x ∈ w, x = 1 /-- `swaps` is a sequence of in-range swaps of distinct positions of `data` whose application in order groups all 1s of `data` into one contiguous block. -/ def IsGroupingSwapSequence (data : List Int) (swaps : List (Nat × Nat)) : Prop := (∀ p ∈ swaps, p.1 < data.length ∧ p.2 < data.length ∧ p.1 ≠ p.2) ∧ onesContiguous (applySwapSeq data swaps) /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty array of length at most 10^5 whose elements are each 0 or 1. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 100000 && input.all (fun x => x == 0 || x == 1) /-! ### Ideal specification (P_spec) -/ /-- `result` is the least length of any swap sequence that groups all 1s of `input` into one contiguous block: such a sequence of length `result` exists, and no grouping sequence is shorter. -/ def minSwapsToGroupAllOnes_spec (input : Input) (result : Output) : Prop := IsLeast {k | ∃ swaps : List (Nat × Nat), IsGroupingSwapSequence input swaps ∧ swaps.length = k} result /-! ### Decidable specification (P_check) -/ /-- Number of `0`s in the length-`ones` block of `input` starting at `start`. -/ def windowCost (input : Input) (ones start : Nat) : Nat := ((input.drop start).take ones).count 0 /-- Finite index of a length-`ones` contiguous block of `input`. -/ abbrev WindowIndex (input : Input) (ones : Nat) : Type := Fin (input.length - ones + 1) /-- Executable checker for `minSwapsToGroupAllOnes_spec` over contiguous target blocks. -/ def minSwapsToGroupAllOnes_check (input : Input) (result : Output) : Bool := let ones := input.count 1 if ones = 0 then result == 0 else decide ((∃ start : WindowIndex input ones, windowCost input ones start.val = result) ∧ (∀ start : WindowIndex input ones, result ≤ windowCost input ones start.val)) /-- Swap two in-range positions, leaving the list unchanged otherwise. -/ def sw (l : List Int) (p : Nat × Nat) : List Int := match l[p.1]?, l[p.2]? with | some a, some b => (l.set p.1 b).set p.2 a | _, _ => l /-- Apply guarded swaps in order. -/ def sws (l : List Int) (s : List (Nat × Nat)) : List Int := s.foldl sw l theorem sw_eq_sets (l : List Int) (i j : Nat) (hi : i < l.length) (hj : j < l.length) : sw l (i, j) = (l.set i l[j]).set j l[i] := by simp [sw, hi, hj] theorem applySwap_eq_sw (l : List Int) (i j : Nat) (hi : i < l.length) (hj : j < l.length) : applySwap l i j = sw l (i, j) := by rw [sw_eq_sets l i j hi hj] simp only [applySwap, List.getD_eq_getElem?_getD, List.getElem?_eq_getElem hi, List.getElem?_eq_getElem hj, Option.getD_some] theorem sw_perm (l : List Int) (p : Nat × Nat) : (sw l p).Perm l := by by_cases hi : p.1 < l.length · by_cases hj : p.2 < l.length · simpa [sw, List.getElem?_eq_getElem hi, List.getElem?_eq_getElem hj] using (List.set_set_perm hi hj) · simp [sw, List.getElem?_eq_none (Nat.le_of_not_lt hj)] · simp [sw, List.getElem?_eq_none (Nat.le_of_not_lt hi)] theorem sws_perm (l : List Int) (s : List (Nat × Nat)) : (sws l s).Perm l := by induction s generalizing l with | nil => exact List.Perm.refl l | cons p s ih => exact (ih (sw l p)).trans (sw_perm l p) theorem applySwapSeq_eq : ∀ (s : List (Nat × Nat)) (l : List Int), (∀ p ∈ s, p.1 < l.length ∧ p.2 < l.length) → applySwapSeq l s = sws l s | [], l, _ => rfl | (i, j) :: rest, l, hb => by have h1 := hb (i, j) (by simp) have hlen := (sw_perm l (i, j)).length_eq show applySwapSeq (applySwap l i j) rest = sws (sw l (i, j)) rest rw [applySwap_eq_sw l i j h1.1 h1.2] exact applySwapSeq_eq rest (sw l (i, j)) (fun p hp => by rw [hlen]; exact hb p (by simp [hp])) theorem prefix_swaps : ∀ (d : Nat) (l : List Int) (k : Nat), k ≤ l.length → l.count 1 = k → k - (l.take k).count 1 = d → ∃ swaps : List (Nat × Nat), (∀ p ∈ swaps, p.1 < l.length ∧ p.2 < l.length ∧ p.1 ≠ p.2) ∧ (∀ x ∈ (sws l swaps).take k, x = 1) ∧ swaps.length = d := by intro d induction d using Nat.strong_induction_on with | h d ih => intro l k hk hcount hd by_cases hd0 : d = 0 · subst d refine ⟨[], by simp, ?_, hd0.symm⟩ have hlen : (l.take k).length = k := by simp [hk] have hcle : (l.take k).count 1 ≤ k := by calc (l.take k).count 1 ≤ (l.take k).length := List.count_le_length (a := (1 : Int)) (l := l.take k) _ = k := hlen have hc : (l.take k).count 1 = k := by omega have hall : ∀ b ∈ l.take k, (1 : Int) = b := List.count_eq_length.mp (by simpa [hlen] using hc) simpa [sws] using fun x hx => (hall x hx).symm · have hdpos : 0 < d := Nat.pos_of_ne_zero hd0 have hprefixlt : (l.take k).count 1 < k := by have hc_le : (l.take k).count 1 ≤ k := by calc (l.take k).count 1 ≤ (l.take k).length := List.count_le_length (a := (1 : Int)) (l := l.take k) _ = k := by simp [hk] omega have hbadmem : ∃ b ∈ l.take k, b ≠ 1 := by by_contra hn have hn' : ∀ b ∈ l.take k, b = 1 := fun b hb => by by_contra hne exact hn ⟨b, hb, hne⟩ have hcfull : (l.take k).count 1 = (l.take k).length := List.count_eq_length.mpr (fun b hb => (hn' b hb).symm) simp [hk] at hcfull omega obtain ⟨b, hbmem, hbne⟩ := hbadmem obtain ⟨i, hi0, hib⟩ := List.mem_take_iff_getElem.mp hbmem have hi : i < k := by simpa [hk] using hi0 have hil : i < l.length := lt_of_lt_of_le hi hk have hli : l[i] ≠ 1 := by simpa [hib] using hbne have hsplit : l.count 1 = (l.take k).count 1 + (l.drop k).count 1 := by simpa only [List.count_append] using congrArg (List.count 1) (List.take_append_drop k l).symm have houtpos : 0 < (l.drop k).count 1 := by omega have houtmem : 1 ∈ l.drop k := List.count_pos_iff.mp houtpos obtain ⟨j0, hj0, hjval⟩ := List.mem_drop_iff_getElem.mp houtmem let j := k + j0 have hj : j < l.length := by simpa [j, Nat.add_comm] using hj0 have hkj : k ≤ j := by simp [j] have hlj : l[j] = 1 := by simpa [j, Nat.add_comm] using hjval have hij : i ≠ j := by omega let l' := sw l (i,j) have hl'eq : l' = (l.set i l[j]).set j l[i] := sw_eq_sets l i j hil hj have hl'len : l'.length = l.length := by simp [hl'eq] have hl'count : l'.count 1 = k := by have hsetj : (l.set i l[j])[j]'(by simpa using hj) = l[j] := by simp [hij] rw [hl'eq, List.count_set (by simpa using hj), List.count_set hil] simp [hsetj, hli, hlj, hij] exact hcount have htakecount : (l'.take k).count 1 = (l.take k).count 1 + 1 := by rw [hl'eq, List.take_set_of_le hkj, List.take_set] rw [List.count_set (by simpa [List.length_take, hk] using hi)] simp [hli, hlj] have hdef : k - (l'.take k).count 1 < d := by omega obtain ⟨rest, hrestvalid, hrestones, hrestlen⟩ := ih (k - (l'.take k).count 1) hdef l' k (by simpa [hl'len] using hk) hl'count rfl refine ⟨(i,j) :: rest, ?_, ?_, ?_⟩ · intro p hp simp only [List.mem_cons] at hp rcases hp with rfl | hp · exact ⟨hil, hj, hij⟩ · simpa [hl'len] using hrestvalid p hp · simpa [sws, l'] using hrestones · simp [hrestlen] omega /-- Positions where a 1 appears in `b` but not in `a`. -/ def gains : List Int → List Int → Nat | a :: l, b :: r => (if a ≠ 1 ∧ b = 1 then 1 else 0) + gains l r | _, _ => 0 @[simp] theorem gains_self (l : List Int) : gains l l = 0 := by induction l with | nil => rfl | cons a l ih => simp [gains, ih] theorem gains_set (l : List Int) (i : Nat) (v : Int) (hi : i < l.length) : gains l (l.set i v) = if l[i] ≠ 1 ∧ v = 1 then 1 else 0 := by induction l generalizing i with | nil => simp at hi | cons a l ih => cases i with | zero => simp [gains] | succ i => simp [gains, ih i (by simpa using hi)] theorem gains_swap (l : List Int) (i j : Nat) (hi : i < l.length) (hj : j < l.length) : gains l ((l.set i l[j]).set j l[i]) ≤ 1 := by induction l generalizing i j with | nil => simp at hi | cons a l ih => cases i with | zero => cases j with | zero => simp [gains] | succ j => simp only [List.getElem_cons_succ, List.getElem_cons_zero, List.set_cons_zero, List.set_cons_succ, gains] rw [gains_set l j a (by simpa using hj)] split <;> split <;> omega | succ i => cases j with | zero => simp only [List.getElem_cons_succ, List.getElem_cons_zero, List.set_cons_zero, List.set_cons_succ, gains] rw [gains_set l i a (by simpa using hi)] split <;> split <;> omega | succ j => simpa [gains] using ih i j (by simpa using hi) (by simpa using hj) theorem gains_sw (l : List Int) (p : Nat × Nat) : gains l (sw l p) ≤ 1 := by by_cases hi : p.1 < l.length · by_cases hj : p.2 < l.length · simpa [sw, List.getElem?_eq_getElem hi, List.getElem?_eq_getElem hj] using gains_swap l p.1 p.2 hi hj · simp [sw, List.getElem?_eq_none (Nat.le_of_not_lt hj)] · simp [sw, List.getElem?_eq_none (Nat.le_of_not_lt hi)] theorem gains_triangle (a b c : List Int) (hab : a.length = b.length) (hbc : b.length = c.length) : gains a c ≤ gains a b + gains b c := by induction a generalizing b c with | nil => simp [gains] | cons x a ih => cases b with | nil => simp at hab | cons y b => cases c with | nil => simp at hbc | cons z c => have ht := ih b c (by simpa using hab) (by simpa using hbc) simp only [gains] split <;> split <;> split <;> omega theorem gains_sws (l : List Int) (s : List (Nat × Nat)) : gains l (sws l s) ≤ s.length := by induction s generalizing l with | nil => simp [sws] | cons p s ih => have ht := gains_triangle l (sw l p) (sws (sw l p) s) (sw_perm l p).length_eq.symm (sws_perm (sw l p) s).length_eq.symm have h1 := gains_sw l p have h2 := ih (sw l p) change gains l (sws (sw l p) s) ≤ s.length + 1 omega theorem take_count_le_gains (a b : List Int) (k : Nat) (hab : a.length = b.length) : (b.take k).count 1 ≤ (a.take k).count 1 + gains a b := by induction a generalizing b k with | nil => have hb : b = [] := List.eq_nil_of_length_eq_zero hab.symm subst b simp [gains] | cons x a ih => cases b with | nil => simp at hab | cons y b => cases k with | zero => simp | succ k => have ht := ih b k (by simpa using hab) simp only [List.take_succ_cons, List.count_cons, gains, beq_iff_eq] split <;> split <;> split <;> omega theorem gains_eq_count (a b : List Int) : gains a b = (List.zipWith (fun x y => decide (x ≠ 1 ∧ y = 1)) a b).count true := by induction a generalizing b with | nil => simp [gains] | cons x a ih => cases b with | nil => simp [gains] | cons y b => simp only [gains, List.zipWith_cons_cons, List.count_cons, ih] by_cases h : x ≠ 1 ∧ y = 1 <;> simp [h, Nat.add_comm] theorem gains_rotate (a b : List Int) (n : Nat) (hab : a.length = b.length) : gains (a.rotate n) (b.rotate n) = gains a b := by rw [gains_eq_count, gains_eq_count, ← List.zipWith_rotate_distrib _ a b n hab] exact (List.rotate_perm _ _).count_eq true theorem shift_inj (L n i j : Nat) (hi : i < L) (hj : j < L) : (i + n) % L = (j + n) % L ↔ i = j := by constructor · intro h have hm : Nat.ModEq L i j := Nat.ModEq.add_right_cancel' n h simpa only [Nat.ModEq, Nat.mod_eq_of_lt hi, Nat.mod_eq_of_lt hj] using hm · rintro rfl; rfl theorem rotate_set (l : List Int) (n i : Nat) (v : Int) (hi : i < l.length) : (l.set ((i+n)%l.length) v).rotate n = (l.rotate n).set i v := by apply List.ext_getElem (by simp) intro j hj hj' have hjl : j < l.length := by simpa using hj simp only [List.getElem_rotate, List.getElem_set, List.length_set, shift_inj l.length n i j hi hjl] theorem rotate_sw (l : List Int) (n i j : Nat) (hi : i < l.length) (hj : j < l.length) : (sw l (((i+n)%l.length), ((j+n)%l.length))).rotate n = sw (l.rotate n) (i,j) := by have hp : 0 < l.length := by omega have hi' := Nat.mod_lt (i+n) hp have hj' := Nat.mod_lt (j+n) hp have hir : i < (l.rotate n).length := by simpa using hi have hjr : j < (l.rotate n).length := by simpa using hj simp only [sw, List.getElem?_eq_getElem hi', List.getElem?_eq_getElem hj', List.getElem?_eq_getElem hir, List.getElem?_eq_getElem hjr, List.getElem_rotate] have hs := rotate_set (l.set ((i+n)%l.length) l[(j+n)%l.length]) n j l[(i+n)%l.length] (by simpa using hj) simp only [List.length_set] at hs rw [hs, rotate_set l n i _ hi] theorem rotate_sws (l : List Int) (n : Nat) (s : List (Nat × Nat)) (hb : ∀ p ∈ s, p.1 < l.length ∧ p.2 < l.length) : (sws l (s.map (fun p => ((p.1+n)%l.length, (p.2+n)%l.length)))).rotate n = sws (l.rotate n) s := by induction s generalizing l with | nil => rfl | cons p s ih => have hp := hb p (by simp) have hlen := (sw_perm l ((p.1+n)%l.length, (p.2+n)%l.length)).length_eq have ht := ih (sw l ((p.1+n)%l.length, (p.2+n)%l.length)) (by intro q hq simpa only [hlen] using hb q (by simp [hq])) simp only [hlen] at ht change (sws (sw l ((p.1+n)%l.length, (p.2+n)%l.length)) (s.map (fun q => ((q.1+n)%l.length, (q.2+n)%l.length)))).rotate n = sws (sw (l.rotate n) p) s rw [ht, rotate_sw l n p.1 p.2 hp.1 hp.2] theorem rotate_take (l : List Int) (n k : Nat) (h : n + k ≤ l.length) : (l.rotate n).take k = (l.drop n).take k := by rw [List.rotate_eq_drop_append_take (by omega), List.take_append_of_le_length (by simp only [List.length_drop]; omega)] theorem vals_of_valid (input : Input) (h : isValidInput input) : ∀ x ∈ input, x = 0 ∨ x = 1 := by unfold isValidInput at h simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, Bool.or_eq_true, beq_iff_eq] at h exact h.2 theorem len_of_valid (input : Input) (h : isValidInput input) : 0 < input.length := by unfold isValidInput at h simp only [Bool.and_eq_true, decide_eq_true_eq] at h exact h.1.1 theorem count01 : ∀ (W : List Int), (∀ x ∈ W, x = 0 ∨ x = 1) → W.count 0 + W.count 1 = W.length | [], _ => rfl | x :: W, hW => by have ih := count01 W (fun y hy => hW y (by simp [hy])) rcases hW x (by simp) with rfl | rfl <;> simp [List.count_cons] <;> omega theorem window_facts (input : Input) (h : isValidInput input) (s : Nat) (hs : s + input.count 1 ≤ input.length) : windowCost input (input.count 1) s + ((input.drop s).take (input.count 1)).count 1 = input.count 1 := by have h01 := count01 ((input.drop s).take (input.count 1)) (fun x hx => vals_of_valid input h x (List.mem_of_mem_drop (List.mem_of_mem_take hx))) have hWlen : ((input.drop s).take (input.count 1)).length = input.count 1 := by simp only [List.length_take, List.length_drop]; omega unfold windowCost omega theorem dominate (input : Input) (h : isValidInput input) (swaps : List (Nat × Nat)) (hs : IsGroupingSwapSequence input swaps) : ∃ s, s + input.count 1 ≤ input.length ∧ windowCost input (input.count 1) s ≤ swaps.length := by obtain ⟨hb, hcont⟩ := hs have hb' : ∀ p ∈ swaps, p.1 < input.length ∧ p.2 < input.length := fun p hp => ⟨(hb p hp).1, (hb p hp).2.1⟩ rw [applySwapSeq_eq swaps input hb'] at hcont have hp := sws_perm input swaps have hc := hp.count_eq 1 have hl := hp.length_eq obtain ⟨w, ⟨u, v, huv⟩, hwlen, hall⟩ := hcont have hwc : w.length = input.count 1 := hwlen.trans hc have hlen : u.length + input.count 1 ≤ input.length := by have := congrArg List.length huv simp only [List.length_append] at this omega refine ⟨u.length, hlen, ?_⟩ have hwin : ((sws input swaps).rotate u.length).take (input.count 1) = w := by rw [rotate_take (sws input swaps) u.length (input.count 1) (by omega), ← huv, List.append_assoc, List.drop_left, ← hwc, List.take_left] have hwcount : w.count 1 = input.count 1 := by rw [List.count_eq_length.mpr (fun x hx => (hall x hx).symm), hwc] have ht := take_count_le_gains (input.rotate u.length) ((sws input swaps).rotate u.length) (input.count 1) (by simp only [List.length_rotate, hl]) rw [hwin, hwcount, gains_rotate input (sws input swaps) u.length hl.symm, rotate_take input u.length (input.count 1) hlen] at ht have hg := gains_sws input swaps have hf := window_facts input h u.length hlen omega theorem attain (input : Input) (h : isValidInput input) (s : Nat) (hs : s + input.count 1 ≤ input.length) : ∃ swaps, IsGroupingSwapSequence input swaps ∧ swaps.length = windowCost input (input.count 1) s := by have hc : (input.rotate s).count 1 = input.count 1 := (List.rotate_perm _ _).count_eq 1 have hW := rotate_take input s (input.count 1) hs obtain ⟨sq, hb, hall, hslen⟩ := prefix_swaps (input.count 1 - ((input.rotate s).take (input.count 1)).count 1) (input.rotate s) (input.count 1) (by rw [List.length_rotate]; omega) hc rfl have hp : 0 < input.length := len_of_valid input h have hbounds : ∀ p ∈ sq, p.1 < input.length ∧ p.2 < input.length := by intro p hps have hh := hb p hps simpa only [List.length_rotate] using And.intro hh.1 hh.2.1 have htb : ∀ p ∈ sq.map (fun p => ((p.1+s)%input.length, (p.2+s)%input.length)), p.1 < input.length ∧ p.2 < input.length ∧ p.1 ≠ p.2 := by intro p hpt obtain ⟨q, hqs, rfl⟩ := List.mem_map.mp hpt refine ⟨Nat.mod_lt _ hp, Nat.mod_lt _ hp, ?_⟩ intro he exact (hb q hqs).2.2 ((shift_inj input.length s q.1 q.2 (hbounds q hqs).1 (hbounds q hqs).2).mp he) have ht : (sws input (sq.map (fun p => ((p.1+s)%input.length, (p.2+s)%input.length)))).rotate s = sws (input.rotate s) sq := rotate_sws input s sq hbounds have hperm := sws_perm input (sq.map (fun p => ((p.1+s)%input.length, (p.2+s)%input.length))) refine ⟨sq.map (fun p => ((p.1+s)%input.length, (p.2+s)%input.length)), ⟨htb, ?_⟩, ?_⟩ · rw [applySwapSeq_eq _ input (fun p hp => ⟨(htb p hp).1, (htb p hp).2.1⟩)] have hlen' : s + input.count 1 ≤ (sws input (sq.map (fun p => ((p.1+s)%input.length, (p.2+s)%input.length)))).length := by rw [hperm.length_eq]; exact hs refine ⟨((sws input (sq.map (fun p => ((p.1+s)%input.length, (p.2+s)%input.length)))).drop s).take (input.count 1), ⟨(sws input (sq.map (fun p => ((p.1+s)%input.length, (p.2+s)%input.length)))).take s, (((sws input (sq.map (fun p => ((p.1+s)%input.length, (p.2+s)%input.length)))).drop s).drop (input.count 1)), ?_⟩, ?_, ?_⟩ · rw [List.append_assoc, List.take_append_drop, List.take_append_drop] · rw [hperm.count_eq 1, List.length_take, List.length_drop] rw [hperm.length_eq] omega · rw [← rotate_take _ s (input.count 1) hlen', ht] exact hall · rw [List.length_map, hslen, hW] have hf := window_facts input h s hs omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minSwapsToGroupAllOnes_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minSwapsToGroupAllOnes_check input result ↔ minSwapsToGroupAllOnes_spec input result := by have hcl : input.count 1 ≤ input.length := List.count_le_length unfold minSwapsToGroupAllOnes_check dsimp only split · rename_i hz rw [beq_iff_eq] unfold minSwapsToGroupAllOnes_spec have hmem : 0 ∈ {k | ∃ swaps : List (Nat × Nat), IsGroupingSwapSequence input swaps ∧ swaps.length = k} := ⟨[], ⟨by simp, [], ⟨[], applySwapSeq input [], by simp⟩, by simp [applySwapSeq, hz], by simp⟩, rfl⟩ constructor · rintro rfl exact ⟨hmem, fun k _ => Nat.zero_le k⟩ · rintro ⟨_, hlb⟩ exact Nat.le_zero.mp (hlb hmem) · rename_i hz simp only [decide_eq_true_eq] have hA : (∃ start : WindowIndex input (input.count 1), windowCost input (input.count 1) start.val = result) ↔ ∃ s, s + input.count 1 ≤ input.length ∧ windowCost input (input.count 1) s = result := by constructor · rintro ⟨⟨s, hs⟩, he⟩; exact ⟨s, by omega, he⟩ · rintro ⟨s, hs, he⟩; exact ⟨⟨s, by omega⟩, he⟩ have hB : (∀ start : WindowIndex input (input.count 1), result ≤ windowCost input (input.count 1) start.val) ↔ ∀ s, s + input.count 1 ≤ input.length → result ≤ windowCost input (input.count 1) s := by constructor · intro H s hs; exact H ⟨s, by omega⟩ · intro H st; exact H st.val (by have := st.isLt; omega) refine (and_congr hA hB).trans ?_ unfold minSwapsToGroupAllOnes_spec constructor · rintro ⟨⟨s, hs, he⟩, hlo⟩ obtain ⟨sq, hsq, hlen⟩ := attain input h s hs refine ⟨⟨sq, hsq, hlen.trans he⟩, fun k hk => ?_⟩ obtain ⟨t, ht, rfl⟩ := hk obtain ⟨m, hm, hb⟩ := dominate input h t ht exact le_trans (hlo m hm) hb · rintro ⟨⟨sq, hsq, he⟩, hlo⟩ have lower : ∀ s, s + input.count 1 ≤ input.length → result ≤ windowCost input (input.count 1) s := by intro s hs obtain ⟨t, ht, hlen⟩ := attain input h s hs exact hlo ⟨t, ht, hlen⟩ obtain ⟨m, hm, hb⟩ := dominate input h sq hsq exact ⟨⟨m, hm, le_antisymm (he ▸ hb) (lower m hm)⟩, lower⟩ /-! ### Implementation helpers -/ /-- Slides a fixed-length window through the remaining input, keeping the current window in a two-list queue and the minimum zero count seen in `best`. -/ def slidingWindowMinZeros (front back incoming : List Int) (zeros best : Nat) : Nat := match incoming with | [] => best | x :: rest => let (out, front', back') := match front with | o :: f => (o, f, back) | [] => match back.reverse with | o :: f => (o, f, []) | [] => (0, [], []) let zeros' := zeros - (if out = 0 then 1 else 0) + (if x = 0 then 1 else 0) slidingWindowMinZeros front' (x :: back') rest zeros' (Nat.min best zeros') termination_by incoming.length /-! ### Main algorithm (impl) -/ /-- Minimum swaps by a fixed-size sliding window: the fewest zeros in any contiguous window whose length is the total number of ones. -/ def computeMinSwapsToGroupAllOnes (input : Input) : Output := let ones := input.count 1 if ones = 0 then 0 else let first := input.take ones let zeros := windowCost input ones 0 slidingWindowMinZeros first [] (input.drop ones) zeros zeros /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem computeMinSwapsToGroupAllOnes_correct (input : Input) (h : isValidInput input) : minSwapsToGroupAllOnes_spec input (computeMinSwapsToGroupAllOnes input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 0, 1, 0, 1] #guard isValidInput [0, 0, 0, 1, 0] #guard isValidInput [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [2]) #guard !(isValidInput [(-1)]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minSwapsToGroupAllOnes_check [1, 0, 1, 0, 1] 1 #guard minSwapsToGroupAllOnes_check [0, 0, 0, 1, 0] 0 #guard minSwapsToGroupAllOnes_check [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1] 3 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minSwapsToGroupAllOnes_check [1, 0, 1, 0, 1] 0) #guard !(minSwapsToGroupAllOnes_check [0, 0, 0, 1, 0] 2) #guard !(minSwapsToGroupAllOnes_check [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1] 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard computeMinSwapsToGroupAllOnes [1, 0, 1, 0, 1] == 1 #guard computeMinSwapsToGroupAllOnes [0, 0, 0, 1, 0] == 0 #guard computeMinSwapsToGroupAllOnes [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1] == 3 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minSwapsToGroupAllOnes_check [1, 0, 1, 0, 1] (computeMinSwapsToGroupAllOnes [1, 0, 1, 0, 1]) #guard minSwapsToGroupAllOnes_check [0, 0, 0, 1, 0] (computeMinSwapsToGroupAllOnes [0, 0, 0, 1, 0]) #guard minSwapsToGroupAllOnes_check [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1] (computeMinSwapsToGroupAllOnes [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1]) end PMinimumSwapsToGroupAll1sTogether