import Mathlib /-! # Boats To Save People You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit. Return the minimum number of boats to carry every given person. ## Constraints - 1 <= people.length <= 5 * 10^4 - 1 <= people[i] <= limit <= 3 * 10^4 ## Provided examples - `people = [1, 2], limit = 3` → `1` - `people = [3, 2, 2, 1], limit = 3` → `3` - `people = [3, 5, 3, 4], limit = 5` → `4` ## Synthesized negative examples - invalid input: `people = [], limit = 1` ([structural] a predicate that admits 1 <= people.length <= 5 * 10^4. empty array breaks the length floor; a predicate checking only weights accepts it) - invalid input: `people = [0], limit = 1` ([structural] a predicate that admits 1 <= people[i] <= limit <= 3 * 10^4. zero is one below the weight floor; a predicate checking length and limit accepts it) - invalid input: `people = [2], limit = 1` ([structural] a predicate that admits 1 <= people[i] <= limit <= 3 * 10^4. single person is heavier than the boat; checking each parameter alone accepts it) - `people = [1, 2], limit = 3` → `0` is wrong ([structural] requirement to carry every person is dropped. ignoring the need to carry anyone makes 0 correct) - `people = [3, 2, 2, 1], limit = 3` → `4` is wrong ([structural] minimum stated as achievability alone; 4 is attainable by solo boats. real assignment, not least) - `people = [3, 5, 3, 4], limit = 5` → `0` is wrong ([structural] nothing requires every person to be carried. zero boats carry nobody, satisfying a no-carry reading) -/ namespace PBoatsToSavePeople abbrev Input := (List Nat) × (Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- `boats` partitions `people`, each boat carrying at most two people with total weight at most `limit`. -/ def IsValidBoatAssignment (people : List Nat) (limit : Nat) (boats : List (List Nat)) : Prop := boats.flatten.Perm people ∧ ∀ b ∈ boats, b.length ≤ 2 ∧ b.sum ≤ limit /-! ### Validity predicate (V) -/ /-- Valid input: 1 ≤ people.length ≤ 5·10^4, each weight in [1, limit], and limit ≤ 3·10^4. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 5 * 10^4 && input.1.all (fun w => 1 ≤ w && w ≤ input.2) && input.2 ≤ 3 * 10^4 /-! ### Ideal specification (P_spec) -/ /-- `result` is the least number of boats admitted by any valid assignment for `input`. -/ def minBoats_spec (input : Input) (result : Output) : Prop := IsLeast {n | ∃ boats : List (List Nat), IsValidBoatAssignment input.1 input.2 boats ∧ boats.length = n} result /-! ### Decidable specification (P_check) -/ /-- A partner for each person: `f i = i` means `i` sails alone, otherwise `i` shares a boat with `f i`. -/ abbrev BoatCode (people : List Nat) : Type := Fin people.length → Fin people.length /-- The boats chosen by `f`: solo boats at fixed points, each pair emitted once at its smaller index. -/ def decodeBoats (people : List Nat) (f : BoatCode people) : List (List Nat) := (List.finRange people.length).filterMap fun i => if f i = i then some [people.get i] else if i < f i then some [people.get i, people.get (f i)] else none /-- All tuples of length `k` with entries drawn from `Fin n`, in lexicographic order. -/ def finTuples (n k : Nat) : List (List (Fin n)) := match k with | 0 => [[]] | k + 1 => (finTuples n k).flatMap fun t => (List.finRange n).map (· :: t) /-- All partner functions on `people`: the finite search space of `minBoats_check`. Each function is read off its list of output values; the list always has length `people.length`, so the fallback `i` is never reached. -/ def allBoatCodes (people : List Nat) : List (BoatCode people) := (finTuples people.length people.length).map fun vals (i : Fin people.length) => (vals[i.val]?).getD i /-- Boolean form of `IsValidBoatAssignment`: `boats` partitions `people` and each boat carries at most two people with total weight at most `limit`. -/ def validBoatAssignment (people : List Nat) (limit : Nat) (boats : List (List Nat)) : Bool := decide (boats.flatten.Perm people) && boats.all fun b => decide (b.length ≤ 2) && decide (b.sum ≤ limit) /-- Executable checker for `minBoats_spec` over the finite `BoatCode`. -/ def minBoats_check (input : Input) (result : Output) : Bool := let assignments := (allBoatCodes input.1).map (decodeBoats input.1) (assignments.any fun boats => validBoatAssignment input.1 input.2 boats && decide (boats.length = result)) && assignments.all fun boats => !(validBoatAssignment input.1 input.2 boats) || decide (result ≤ boats.length) theorem bsp_mem_finTuples (n : Nat) : ∀ (k : Nat) (t : List (Fin n)), t.length = k → t ∈ finTuples n k := by intro k induction k with | zero => intro t ht rw [List.length_eq_zero_iff] at ht subst ht simp [finTuples] | succ k ih => intro t ht cases t with | nil => simp at ht | cons a t => simp only [finTuples, List.mem_flatMap, List.mem_map] exact ⟨t, ih t (by simpa using ht), a, List.mem_finRange a, rfl⟩ theorem bsp_mem_allBoatCodes (people : List Nat) (f : BoatCode people) : f ∈ allBoatCodes people := by unfold allBoatCodes rw [List.mem_map] refine ⟨List.ofFn f, bsp_mem_finTuples _ _ _ (by simp), ?_⟩ funext i simp theorem bsp_valid_iff (people : List Nat) (limit : Nat) (boats : List (List Nat)) : validBoatAssignment people limit boats = true ↔ IsValidBoatAssignment people limit boats := by simp [validBoatAssignment, IsValidBoatAssignment] theorem bsp_perm_index (people : List Nat) : ∀ (l : List Nat) (S : List (Fin people.length)), l.Perm (S.map people.get) → ∃ idx : List (Fin people.length), idx.Perm S ∧ idx.map people.get = l := by intro l induction l with | nil => intro S hS simp at hS subst hS exact ⟨[], List.Perm.refl _, rfl⟩ | cons a l ih => intro S hS have ha : a ∈ S.map people.get := hS.subset (by simp) obtain ⟨s, hs, rfl⟩ := List.mem_map.mp ha have h1 : List.Perm (S.map people.get) (people.get s :: (S.erase s).map people.get) := by have := (List.perm_cons_erase hs).map people.get simpa using this obtain ⟨idx, hidx, hmap⟩ := ih (S.erase s) (List.Perm.cons_inv (hS.trans h1)) exact ⟨s :: idx, (hidx.cons s).trans (List.perm_cons_erase hs).symm, by simp [hmap]⟩ theorem bsp_split_flatten {α β : Type} (g : α → β) : ∀ (B : List (List β)) (idx : List α), idx.map g = B.flatten → ∃ IB : List (List α), IB.flatten = idx ∧ IB.map (List.map g) = B := by intro B induction B with | nil => intro idx h simp at h exact ⟨[], by simp [h], rfl⟩ | cons b B ih => intro idx h have h1 : (idx.take b.length).map g = b := by rw [List.map_take, h] simp have h2 : (idx.drop b.length).map g = B.flatten := by rw [List.map_drop, h] simp obtain ⟨IB, hIB, hmap⟩ := ih _ h2 exact ⟨idx.take b.length :: IB, by simp [hIB], by simp [h1, hmap]⟩ def bspPartner {m : Nat} : List (List (Fin m)) → Fin m → Fin m | [], j => j | b :: rest, j => match b with | [a, c] => if j = a then c else if j = c then a else bspPartner rest j | [a] => if j = a then j else bspPartner rest j | _ => bspPartner rest j def bspNorm {m : Nat} (b : List (Fin m)) : List (Fin m) := match b with | [a, c] => if a < c then [a, c] else [c, a] | b => b def bspIdx {m : Nat} (f : Fin m → Fin m) : List (List (Fin m)) := (List.finRange m).filterMap fun i => if f i = i then some [i] else if i < f i then some [i, f i] else none theorem bsp_partner_pair {m : Nat} : ∀ (IB : List (List (Fin m))) (a c : Fin m), IB.flatten.Nodup → [a, c] ∈ IB → bspPartner IB a = c ∧ bspPartner IB c = a := by intro IB induction IB with | nil => intro a c _ h; simp at h | cons b rest ih => intro a c hnd hmem rw [List.flatten_cons, List.nodup_append] at hnd obtain ⟨hb, hr, hdisj⟩ := hnd rcases List.mem_cons.mp hmem with rfl | hm · have hac : a ≠ c := by simpa using hb simp [bspPartner, hac.symm] · have ha : a ∈ rest.flatten := List.mem_flatten.mpr ⟨_, hm, by simp⟩ have hc : c ∈ rest.flatten := List.mem_flatten.mpr ⟨_, hm, by simp⟩ have hab : a ∉ b := fun h => hdisj a h a ha rfl have hcb : c ∉ b := fun h => hdisj c h c hc rfl have key := ih a c hr hm rcases b with _ | ⟨x, _ | ⟨y, _ | ⟨z, t⟩⟩⟩ · simpa [bspPartner] using key · simp only [List.mem_cons, List.not_mem_nil, or_false] at hab hcb simp [bspPartner, hab, hcb, key] · simp only [List.mem_cons, List.not_mem_nil, or_false, not_or] at hab hcb simp [bspPartner, hab.1, hab.2, hcb.1, hcb.2, key] · simpa [bspPartner] using key theorem bsp_partner_single {m : Nat} : ∀ (IB : List (List (Fin m))) (a : Fin m), IB.flatten.Nodup → [a] ∈ IB → bspPartner IB a = a := by intro IB induction IB with | nil => intro a _ h; simp at h | cons b rest ih => intro a hnd hmem rw [List.flatten_cons, List.nodup_append] at hnd obtain ⟨hb, hr, hdisj⟩ := hnd rcases List.mem_cons.mp hmem with rfl | hm · simp [bspPartner] · have ha : a ∈ rest.flatten := List.mem_flatten.mpr ⟨_, hm, by simp⟩ have hab : a ∉ b := fun h => hdisj a h a ha rfl have key := ih a hr hm rcases b with _ | ⟨x, _ | ⟨y, _ | ⟨z, t⟩⟩⟩ · simpa [bspPartner] using key · simp only [List.mem_cons, List.not_mem_nil, or_false] at hab simp [bspPartner, hab, key] · simp only [List.mem_cons, List.not_mem_nil, or_false, not_or] at hab simp [bspPartner, hab.1, hab.2, key] · simpa [bspPartner] using key theorem bsp_norm_perm {m : Nat} (b : List (Fin m)) : (bspNorm b).Perm b := by rcases b with _ | ⟨x, _ | ⟨y, _ | ⟨z, t⟩⟩⟩ · simp [bspNorm] · simp [bspNorm] · show (if x < y then [x, y] else [y, x]).Perm [x, y] split_ifs · exact List.Perm.refl _ · exact List.Perm.swap _ _ _ · simp [bspNorm] theorem bsp_flatten_map_norm {m : Nat} : ∀ (L : List (List (Fin m))), (L.map bspNorm).flatten.Perm L.flatten := by intro L induction L with | nil => simp | cons b L ih => simp only [List.map_cons, List.flatten_cons] exact (bsp_norm_perm b).append ih theorem bsp_boat_cases {m : Nat} (IB : List (List (Fin m))) (hnd : IB.flatten.Nodup) (hlen : ∀ b ∈ IB, b.length ≤ 2) (i : Fin m) (hi : i ∈ IB.flatten) : ([i] ∈ IB ∧ bspPartner IB i = i) ∨ ∃ c, c ≠ i ∧ bspPartner IB i = c ∧ ([i, c] ∈ IB ∨ [c, i] ∈ IB) := by obtain ⟨d, hd, hid⟩ := List.mem_flatten.mp hi have hdn : d.Nodup := (List.nodup_flatten.mp hnd).1 d hd have hl := hlen d hd rcases d with _ | ⟨x, _ | ⟨y, _ | ⟨z, t⟩⟩⟩ · simp at hid · simp only [List.mem_cons, List.not_mem_nil, or_false] at hid subst hid exact Or.inl ⟨hd, bsp_partner_single IB _ hnd hd⟩ · simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, or_false, not_false_eq_true, List.nodup_nil, and_true] at hdn simp only [List.mem_cons, List.not_mem_nil, or_false] at hid rcases hid with rfl | rfl · exact Or.inr ⟨y, fun h => hdn h.symm, (bsp_partner_pair IB _ _ hnd hd).1, Or.inl hd⟩ · exact Or.inr ⟨x, hdn, (bsp_partner_pair IB _ _ hnd hd).2, Or.inr hd⟩ · simp at hl theorem bsp_idx_perm {m : Nat} (IB : List (List (Fin m))) (hperm : IB.flatten.Perm (List.finRange m)) (hlen : ∀ b ∈ IB, b.length ≤ 2) : (bspIdx (bspPartner IB)).Perm ((IB.filter (fun b => b ≠ [])).map bspNorm) := by have hnd : IB.flatten.Nodup := hperm.nodup_iff.mpr (List.nodup_finRange m) have hl : (bspIdx (bspPartner IB)).Nodup := by refine List.Nodup.filterMap ?_ (List.nodup_finRange m) intro a a' b h1 h2 simp only [Option.mem_def] at h1 h2 split_ifs at h1 h2 <;> simp_all <;> grind have hr : ((IB.filter (fun b => b ≠ [])).map bspNorm).Nodup := by rw [List.Nodup, List.pairwise_map] refine List.Pairwise.imp_of_mem ?_ ((List.nodup_flatten.mp hnd).2.filter _) intro d d' hd hd' hdis heq have hne : d ≠ [] := by simpa using (List.mem_filter.mp hd).2 obtain ⟨x, hx⟩ := List.exists_mem_of_ne_nil d hne have hx1 : x ∈ bspNorm d := (bsp_norm_perm d).symm.subset hx rw [heq] at hx1 exact hdis hx ((bsp_norm_perm d').subset hx1) rw [List.perm_ext_iff_of_nodup hl hr] intro x simp only [bspIdx, List.mem_filterMap, List.mem_map, List.mem_filter, List.mem_finRange, true_and] constructor · rintro ⟨i, hi⟩ have hcases := bsp_boat_cases IB hnd hlen i (hperm.mem_iff.mpr (List.mem_finRange i)) split_ifs at hi with h1 h2 · simp only [Option.some.injEq] at hi subst hi rcases hcases with ⟨hs, -⟩ | ⟨c, hc, hpc, -⟩ · exact ⟨[i], ⟨hs, by simp⟩, by simp [bspNorm]⟩ · exact absurd (hpc.symm.trans h1) hc · simp only [Option.some.injEq] at hi subst hi rcases hcases with ⟨-, hs⟩ | ⟨c, hc, hpc, hd | hd⟩ · exact absurd hs h1 · rw [hpc] at h2 ⊢ exact ⟨[i, c], ⟨hd, by simp⟩, by simp [bspNorm, h2]⟩ · rw [hpc] at h2 ⊢ exact ⟨[c, i], ⟨hd, by simp⟩, by simp [bspNorm, not_lt.mpr h2.le]⟩ all_goals simp at hi · rintro ⟨d, ⟨hd, hne⟩, rfl⟩ have hdn : d.Nodup := (List.nodup_flatten.mp hnd).1 d hd have hl2 := hlen d hd have hne' : d ≠ [] := by simpa using hne clear hne rcases d with _ | ⟨a, _ | ⟨c, _ | ⟨z, t⟩⟩⟩ · exact absurd rfl hne' · exact ⟨a, by simp [bsp_partner_single IB a hnd hd, bspNorm]⟩ · have hac : a ≠ c := by simpa using hdn obtain ⟨hpa, hpc⟩ := bsp_partner_pair IB a c hnd hd by_cases hlt : a < c · exact ⟨a, by simp [hpa, hac.symm, hlt, bspNorm]⟩ · have hca : c < a := lt_of_le_of_ne (not_lt.mp hlt) hac.symm exact ⟨c, by simp [hpc, hac, hca, hlt, bspNorm]⟩ · simp at hl2 theorem bsp_decode_eq (people : List Nat) (f : BoatCode people) : decodeBoats people f = (bspIdx f).map (List.map people.get) := by unfold decodeBoats bspIdx rw [List.map_filterMap] congr 1 funext i split_ifs <;> simp theorem bsp_exists_code_idx (people : List Nat) (limit : Nat) (IB : List (List (Fin people.length))) (hperm : IB.flatten.Perm (List.finRange people.length)) (hb : ∀ b ∈ IB, b.length ≤ 2 ∧ (b.map people.get).sum ≤ limit) : ∃ f : BoatCode people, IsValidBoatAssignment people limit (decodeBoats people f) ∧ (decodeBoats people f).length ≤ IB.length := by have hP := bsp_idx_perm IB hperm (fun b hb' => (hb b hb').1) have h4 : (List.finRange people.length).map people.get = people := by rw [← List.ofFn_eq_map, List.ofFn_get] refine ⟨bspPartner IB, ⟨?_, ?_⟩, ?_⟩ · rw [bsp_decode_eq, ← List.map_flatten] have h1 : (bspIdx (bspPartner IB)).flatten.Perm (List.finRange people.length) := by have h2 := bsp_flatten_map_norm (IB.filter (fun b => b ≠ [])) rw [List.flatten_filter_ne_nil] at h2 exact hP.flatten.trans (h2.trans hperm) exact (h1.map people.get).trans (by rw [h4]) · intro b hbm rw [bsp_decode_eq, List.mem_map] at hbm obtain ⟨c, hc, rfl⟩ := hbm obtain ⟨d, hd, rfl⟩ := List.mem_map.mp (hP.subset hc) have hdIB := (List.mem_filter.mp hd).1 have hpd := bsp_norm_perm d refine ⟨?_, ?_⟩ · rw [List.length_map, hpd.length_eq] exact (hb d hdIB).1 · rw [(hpd.map people.get).sum_eq] exact (hb d hdIB).2 · rw [bsp_decode_eq, List.length_map, hP.length_eq, List.length_map] exact List.length_filter_le _ _ theorem bsp_exists_code (people : List Nat) (limit : Nat) (boats : List (List Nat)) (hB : IsValidBoatAssignment people limit boats) : ∃ f : BoatCode people, IsValidBoatAssignment people limit (decodeBoats people f) ∧ (decodeBoats people f).length ≤ boats.length := by obtain ⟨hperm, hb⟩ := hB have h4 : (List.finRange people.length).map people.get = people := by rw [← List.ofFn_eq_map, List.ofFn_get] obtain ⟨idx, hidx, hmap⟩ := bsp_perm_index people boats.flatten (List.finRange people.length) (hperm.trans (by rw [h4])) obtain ⟨IB, hIB, hIBmap⟩ := bsp_split_flatten people.get boats idx hmap have hlenB : boats.length = IB.length := by rw [← hIBmap, List.length_map] obtain ⟨f, hf, hlen⟩ := bsp_exists_code_idx people limit IB (by rw [hIB]; exact hidx) (by intro b hbIB have hm : b.map people.get ∈ boats := by rw [← hIBmap] exact List.mem_map_of_mem hbIB obtain ⟨h1, h2⟩ := hb _ hm exact ⟨by simpa using h1, h2⟩) exact ⟨f, hf, by rw [hlenB]; exact hlen⟩ theorem bsp_check_eq (input : Input) (result : Output) : minBoats_check input result = ((((allBoatCodes input.1).map (decodeBoats input.1)).any fun boats => validBoatAssignment input.1 input.2 boats && decide (boats.length = result)) && ((allBoatCodes input.1).map (decodeBoats input.1)).all fun boats => !(validBoatAssignment input.1 input.2 boats) || decide (result ≤ boats.length)) := rfl theorem bsp_isLeast_iff (S : Set Nat) (r : Nat) : IsLeast S r ↔ (r ∈ S ∧ ∀ y : Nat, y ∈ S → r ≤ y) := Iff.rfl /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minBoats_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minBoats_check input result ↔ minBoats_spec input result := by obtain ⟨people, limit⟩ := input rw [bsp_check_eq, Bool.and_eq_true, List.any_eq_true, List.all_eq_true] unfold minBoats_spec rw [bsp_isLeast_iff] constructor · rintro ⟨⟨B, -, hB⟩, hall⟩ rw [Bool.and_eq_true, bsp_valid_iff, decide_eq_true_eq] at hB refine ⟨⟨B, hB.1, hB.2⟩, ?_⟩ rintro m ⟨B', hB', rfl⟩ obtain ⟨f, hf, hlen⟩ := bsp_exists_code people limit B' hB' have hmem : decodeBoats people f ∈ (allBoatCodes people).map (decodeBoats people) := List.mem_map_of_mem (bsp_mem_allBoatCodes people f) have h2 := hall _ hmem rw [Bool.or_eq_true, Bool.not_eq_true', decide_eq_true_eq] at h2 rcases h2 with h2 | h2 · rw [← bsp_valid_iff] at hf simp [hf] at h2 · exact le_trans h2 hlen · rintro ⟨⟨B, hB, hBlen⟩, hlb⟩ obtain ⟨f, hf, hlen⟩ := bsp_exists_code people limit B hB have hmem : decodeBoats people f ∈ (allBoatCodes people).map (decodeBoats people) := List.mem_map_of_mem (bsp_mem_allBoatCodes people f) refine ⟨⟨_, hmem, ?_⟩, ?_⟩ · rw [Bool.and_eq_true, bsp_valid_iff, decide_eq_true_eq] refine ⟨hf, ?_⟩ have hge := hlb _ ⟨_, hf, rfl⟩ exact le_antisymm (le_trans hlen (le_of_eq hBlen)) hge · intro B' _ rw [Bool.or_eq_true, Bool.not_eq_true', decide_eq_true_eq] by_cases hv : validBoatAssignment people limit B' = true · exact Or.inr (hlb _ ⟨B', (bsp_valid_iff _ _ _).mp hv, rfl⟩) · exact Or.inl (by simpa using hv) /-! ### Implementation helpers -/ /-- Merge sort of the weights into nondecreasing order. -/ def sortWeights (people : List Nat) : List Nat := people.mergeSort (· ≤ ·) /-- Two-pointer scan over ascending weights: pair the lightest remaining person with the heaviest one when they fit, else send the heaviest alone. -/ def greedyBoatCount (a : Array Nat) (limit lo hi : Nat) : Nat := if h : hi ≤ lo then if lo = hi then 1 else 0 else if a[lo]! + a[hi]! ≤ limit then 1 + greedyBoatCount a limit (lo + 1) (hi - 1) else 1 + greedyBoatCount a limit lo (hi - 1) termination_by hi + 1 - lo decreasing_by all_goals omega /-! ### Main algorithm (impl) -/ /-- Minimum boats by sorting the weights and greedily pairing lightest with heaviest via the two-pointer scan. -/ def numRescueBoats (input : Input) : Output := let a := (sortWeights input.1).toArray if a.size = 0 then 0 else greedyBoatCount a input.2 0 (a.size - 1) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem numRescueBoats_correct (input : Input) (h : isValidInput input) : minBoats_spec input (numRescueBoats input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 2], 3) #guard isValidInput ([3, 2, 2, 1], 3) #guard isValidInput ([3, 5, 3, 4], 5) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 1)) #guard !(isValidInput ([0], 1)) #guard !(isValidInput ([2], 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minBoats_check ([1, 2], 3) 1 #guard minBoats_check ([3, 2, 2, 1], 3) 3 #guard minBoats_check ([3, 5, 3, 4], 5) 4 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minBoats_check ([1, 2], 3) 0) #guard !(minBoats_check ([3, 2, 2, 1], 3) 4) #guard !(minBoats_check ([3, 5, 3, 4], 5) 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard numRescueBoats ([1, 2], 3) == 1 #guard numRescueBoats ([3, 2, 2, 1], 3) == 3 #guard numRescueBoats ([3, 5, 3, 4], 5) == 4 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minBoats_check ([1, 2], 3) (numRescueBoats ([1, 2], 3)) #guard minBoats_check ([3, 2, 2, 1], 3) (numRescueBoats ([3, 2, 2, 1], 3)) #guard minBoats_check ([3, 5, 3, 4], 5) (numRescueBoats ([3, 5, 3, 4], 5)) end PBoatsToSavePeople