import Mathlib /-! # Minimum Cost For Tickets You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365. Train tickets are sold in three different ways: a 1-day pass is sold for costs[0] dollars, a 7-day pass is sold for costs[1] dollars, and a 30-day pass is sold for costs[2] dollars. The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8. Return the minimum number of dollars you need to travel every day in the given list of days. ## Constraints - 1 <= days.length <= 365 - 1 <= days[i] <= 365 - days is in strictly increasing order. - costs.length == 3 - 1 <= costs[i] <= 1000 ## Provided examples - `days = [1], costs = [2, 7, 15]` → `2` - `days = [365], costs = [2, 7, 15]` → `2` - `days = [1, 5, 9, 14, 20, 25], costs = [1, 6, 10]` → `6` ## Synthesized negative examples - invalid input: `days = [], costs = [2, 7, 15]` ([structural] a predicate that admits 1 <= days.length <= 365. empty list violates the minimum travel-day count) - invalid input: `days = [0], costs = [2, 7, 15]` ([structural] a predicate that admits 1 <= days[i] <= 365. day zero is outside the 1..365 calendar range) - invalid input: `days = [1, 2, 2], costs = [2, 7, 15]` ([structural] a predicate that admits days is in strictly increasing order.. duplicate day; a predicate checking nondecreasing order accepts it) - `days = [1], costs = [2, 7, 15]` → `4` is wrong ([structural] minimality stated as achievability alone. 4 is a real cost (two 1-day passes) but not least) - `days = [365], costs = [2, 7, 15]` → `0` is wrong ([structural] nothing requires every day to be covered. zero dollars buys no pass and covers nothing) - `days = [1, 5, 9, 14, 20, 25], costs = [1, 6, 10]` → `4` is wrong ([structural] no purchase plan reaches this total. below the cost of covering six separate days.) -/ namespace PMinimumCostForTickets abbrev Input := (List Nat) × (List Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- The number of consecutive days a pass of category `kind` covers: 1, 7, or 30. -/ def passDuration (kind : Nat) : Nat := match kind with | 0 => 1 | 1 => 7 | 2 => 30 | _ => 0 /-- `plan` is a list of pass purchases of categories 0, 1, or 2 such that every day in `days` lies in some purchase's covered interval. -/ def IsValidPassPlan (days : List Nat) (plan : List (Nat × Nat)) : Prop := (∀ p ∈ plan, p.2 < 3) ∧ ∀ d ∈ days, ∃ p ∈ plan, p.1 ≤ d ∧ d < p.1 + passDuration p.2 /-- The total cost of a plan: the sum of `costs[kind]` over its purchases. -/ def PlanCost (costs : List Nat) (plan : List (Nat × Nat)) : Nat := (plan.map (fun p => costs.getD p.2 0)).sum /-- Whether the list is strictly increasing, adjacent pair by adjacent pair. -/ def strictlyIncreasing : List Nat → Bool | [] => true | [_] => true | a :: b :: rest => a < b && strictlyIncreasing (b :: rest) /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 365 strictly increasing travel days in `1..365`, and exactly three pass costs in `1..1000`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 365 && input.1.all (fun d => 1 ≤ d && d ≤ 365) && strictlyIncreasing input.1 && input.2.length = 3 && input.2.all (fun c => 1 ≤ c && c ≤ 1000) /-! ### Ideal specification (P_spec) -/ /-- `result` is the least total cost among valid pass plans covering every travel day: some valid plan costs exactly `result`, and none costs less. -/ def minCostTickets_spec (input : Input) (result : Output) : Prop := IsLeast {k | ∃ plan : List (Nat × Nat), IsValidPassPlan input.1 plan ∧ PlanCost input.2 plan = k} result /-! ### Decidable specification (P_check) -/ /-- One pass choice per travel day: kinds 0, 1, 2 buy that pass starting that day, 3 buys nothing. -/ abbrev PlanCode (days : List Nat) : Type := Fin days.length → Fin 4 /-- The pass plan selected by `code`: one purchase `(day, kind)` at each travel day whose code is not 3. -/ def decodePlan (days : List Nat) (code : PlanCode days) : List (Nat × Nat) := (List.finRange days.length).filterMap fun i => if code i = 3 then none else some (days.getD i.val 0, (code i).val) /-- Boolean validity test for a pass plan, mirroring `IsValidPassPlan`. -/ def isValidPassPlanB (days : List Nat) (plan : List (Nat × Nat)) : Bool := plan.all (fun p => p.2 < 3) && days.all fun d => plan.any fun p => p.1 ≤ d && d < p.1 + passDuration p.2 /-- All choice lists of length `n` over the four codes; mapping position lookup over them enumerates every `Fin n → Fin 4`. -/ def allCodeLists : (n : Nat) → List (List (Fin 4)) | 0 => [[]] | n + 1 => (allCodeLists n).flatMap fun rest => (List.finRange 4).map fun c => c :: rest /-- Executable checker for `minCostTickets_spec` over the finite `PlanCode`. -/ def minCostTickets_check (input : Input) (result : Output) : Bool := let codes := (allCodeLists input.1.length).map fun l (i : Fin input.1.length) => l.getD i.val 0 codes.any (fun code => isValidPassPlanB input.1 (decodePlan input.1 code) && PlanCost input.2 (decodePlan input.1 code) == result) && codes.all (fun code => !isValidPassPlanB input.1 (decodePlan input.1 code) || result ≤ PlanCost input.2 (decodePlan input.1 code)) /-- The checker's candidate list: every choice list of length `n` read as a function. -/ def mct_codesOf (n : Nat) : List (Fin n → Fin 4) := (allCodeLists n).map fun l (i : Fin n) => l.getD i.val 0 theorem mct_check_eq (days costs : List Nat) (result : Nat) : minCostTickets_check (days, costs) result = ((mct_codesOf days.length).any (fun code => isValidPassPlanB days (decodePlan days code) && PlanCost costs (decodePlan days code) == result) && (mct_codesOf days.length).all (fun code => !isValidPassPlanB days (decodePlan days code) || decide (result ≤ PlanCost costs (decodePlan days code)))) := rfl theorem mct_spec_unfold (days costs : List Nat) (result : Nat) : minCostTickets_spec (days, costs) result ↔ ((∃ plan : List (Nat × Nat), IsValidPassPlan days plan ∧ PlanCost costs plan = result) ∧ ∀ k : Nat, (∃ plan : List (Nat × Nat), IsValidPassPlan days plan ∧ PlanCost costs plan = k) → result ≤ k) := Iff.rfl theorem mct_validB_iff (days : List Nat) (plan : List (Nat × Nat)) : isValidPassPlanB days plan = true ↔ IsValidPassPlan days plan := by simp only [isValidPassPlanB, IsValidPassPlan, Bool.and_eq_true, List.all_eq_true, List.any_eq_true, decide_eq_true_eq] theorem mct_exists_codeList : ∀ (n : Nat) (code : Fin n → Fin 4), ∃ l ∈ allCodeLists n, ∀ i : Fin n, l.getD i.val 0 = code i | 0, _ => ⟨[], by simp [allCodeLists], fun i => i.elim0⟩ | n + 1, code => by obtain ⟨l, hl, hli⟩ := mct_exists_codeList n (fun i => code i.succ) refine ⟨code ⟨0, Nat.succ_pos n⟩ :: l, ?_, ?_⟩ · simp only [allCodeLists, List.mem_flatMap, List.mem_map] exact ⟨l, hl, code ⟨0, Nat.succ_pos n⟩, List.mem_finRange _, rfl⟩ · rintro ⟨_ | j, hj⟩ · exact List.getD_cons_zero · rw [List.getD_cons_succ] exact hli ⟨j, Nat.lt_of_succ_lt_succ hj⟩ theorem mct_mem_codesOf (n : Nat) (code : Fin n → Fin 4) : code ∈ mct_codesOf n := by obtain ⟨l, hl, hli⟩ := mct_exists_codeList n code unfold mct_codesOf rw [List.mem_map] exact ⟨l, hl, funext hli⟩ theorem mct_mem_decodePlan (days : List Nat) (code : PlanCode days) (q : Nat × Nat) : q ∈ decodePlan days code ↔ ∃ i : Fin days.length, code i ≠ 3 ∧ q = (days.getD i.val 0, (code i).val) := by unfold decodePlan rw [List.mem_filterMap] constructor · rintro ⟨i, -, hi⟩ by_cases h3 : code i = 3 · rw [if_pos h3] at hi cases hi · rw [if_neg h3] at hi exact ⟨i, h3, (Option.some.inj hi).symm⟩ · rintro ⟨i, h3, rfl⟩ exact ⟨i, List.mem_finRange i, by rw [if_neg h3]⟩ /-- The cost charged for one code: nothing for `3`, the pass price otherwise. -/ def mct_codeCost (costs : List Nat) (c : Fin 4) : Nat := if c = 3 then 0 else costs.getD c.val 0 theorem mct_sum_filterMap_map {α β : Type} (l : List α) (g : α → Option β) (h : β → Nat) : ((l.filterMap g).map h).sum = (l.map fun x => ((g x).map h).getD 0).sum := by induction l with | nil => rfl | cons x t ih => rcases hgx : g x with _ | b · simp [hgx, ih] · simp [hgx, ih] theorem mct_cost_decodePlan (days costs : List Nat) (code : PlanCode days) : PlanCost costs (decodePlan days code) = ∑ i : Fin days.length, mct_codeCost costs (code i) := by rw [Fin.sum_univ_def] unfold PlanCost decodePlan rw [mct_sum_filterMap_map] congr 1 apply List.map_congr_left intro i _ by_cases h3 : code i = 3 <;> simp [mct_codeCost, h3] /-- The longer-lasting of two codes, so its pass covers whatever either one covers. -/ def mct_better (a b : Fin 4) : Fin 4 := if passDuration b.val ≤ passDuration a.val then a else b theorem mct_fin4_ne_three (c : Fin 4) : c ≠ 3 ↔ c.val < 3 := by revert c; decide theorem mct_better_ne (a b : Fin 4) (hb : b ≠ 3) : mct_better a b ≠ 3 := by revert a b; decide theorem mct_better_dur_left (a b : Fin 4) : passDuration a.val ≤ passDuration (mct_better a b).val := by unfold mct_better split_ifs with h · exact Nat.le_refl _ · exact Nat.le_of_lt (Nat.lt_of_not_le h) theorem mct_better_dur_right (a b : Fin 4) : passDuration b.val ≤ passDuration (mct_better a b).val := by unfold mct_better split_ifs with h · exact h · exact Nat.le_refl _ theorem mct_better_eq_or (a b : Fin 4) : mct_better a b = a ∨ mct_better a b = b := by unfold mct_better split_ifs <;> simp theorem mct_better_cost (costs : List Nat) (a b : Fin 4) : mct_codeCost costs (mct_better a b) ≤ mct_codeCost costs a + mct_codeCost costs b := by rcases mct_better_eq_or a b with h | h <;> rw [h] · exact Nat.le_add_right _ _ · exact Nat.le_add_left _ _ /-- Every plan of kinds below `3` is dominated by a code plan: same travel days covered, no more cost. -/ theorem mct_trunc_aux (days costs : List Nat) : ∀ plan : List (Nat × Nat), (∀ p ∈ plan, p.2 < 3) → ∃ code : PlanCode days, (∀ d ∈ days, (∃ p ∈ plan, p.1 ≤ d ∧ d < p.1 + passDuration p.2) → ∃ q ∈ decodePlan days code, q.1 ≤ d ∧ d < q.1 + passDuration q.2) ∧ PlanCost costs (decodePlan days code) ≤ PlanCost costs plan | [], _ => by refine ⟨fun _ => 3, ?_, ?_⟩ · rintro d - ⟨q, hq, -⟩ simp at hq · rw [mct_cost_decodePlan] simp [mct_codeCost, PlanCost] | p :: rest, hk => by have hp3 : p.2 < 3 := hk p List.mem_cons_self have hrest : ∀ q ∈ rest, q.2 < 3 := fun q hq => hk q (List.mem_cons_of_mem p hq) obtain ⟨c, hcov, hcost⟩ := mct_trunc_aux days costs rest hrest have hPC : PlanCost costs (p :: rest) = costs.getD p.2 0 + PlanCost costs rest := rfl by_cases hex : ∃ d, d ∈ days ∧ p.1 ≤ d ∧ d < p.1 + passDuration p.2 · have hd0 := Nat.find_spec hex have hmin : ∀ d, d ∈ days → p.1 ≤ d → d < p.1 + passDuration p.2 → Nat.find hex ≤ d := fun d h1 h2 h3 => Nat.find_min' hex ⟨h1, h2, h3⟩ obtain ⟨i0, hi0⟩ := List.mem_iff_get.mp hd0.1 obtain ⟨k, hk⟩ : ∃ k : Fin 4, k.val = p.2 := ⟨⟨p.2, by omega⟩, rfl⟩ have hk3 : k ≠ 3 := (mct_fin4_ne_three k).mpr (by omega) obtain ⟨c', hc'⟩ : ∃ c' : PlanCode days, ∀ j, c' j = if j = i0 then mct_better (c i0) k else c j := ⟨_, fun _ => rfl⟩ have hgd : days.getD i0.val 0 = Nat.find hex := by rw [List.getD_eq_get (l := days) (d := 0) i0] exact hi0 refine ⟨c', ?_, ?_⟩ · rintro d hd ⟨q, hq, hqd⟩ rcases List.mem_cons.mp hq with hqp | hq' · rw [hqp] at hqd refine ⟨(days.getD i0.val 0, (mct_better (c i0) k).val), ?_, ?_⟩ · rw [mct_mem_decodePlan] exact ⟨i0, by rw [hc', if_pos rfl]; exact mct_better_ne _ _ hk3, by rw [hc', if_pos rfl]⟩ · have hle : Nat.find hex ≤ d := hmin d hd hqd.1 hqd.2 have hdur : passDuration p.2 ≤ passDuration (mct_better (c i0) k).val := by rw [← hk] exact mct_better_dur_right (c i0) k have hd0' : p.1 ≤ Nat.find hex := hd0.2.1 show days.getD i0.val 0 ≤ d ∧ d < days.getD i0.val 0 + passDuration (mct_better (c i0) k).val rw [hgd] omega · obtain ⟨q', hq'mem, hq'd⟩ := hcov d hd ⟨q, hq', hqd⟩ rw [mct_mem_decodePlan] at hq'mem obtain ⟨j, hj3, rfl⟩ := hq'mem by_cases hji : j = i0 · refine ⟨(days.getD j.val 0, (mct_better (c i0) k).val), ?_, ?_⟩ · rw [mct_mem_decodePlan] exact ⟨j, by rw [hc', if_pos hji]; exact mct_better_ne _ _ hk3, by rw [hc', if_pos hji]⟩ · have hdur : passDuration (c j).val ≤ passDuration (mct_better (c i0) k).val := by rw [hji] exact mct_better_dur_left (c i0) k have hq'd' : days.getD j.val 0 ≤ d ∧ d < days.getD j.val 0 + passDuration (c j).val := hq'd show days.getD j.val 0 ≤ d ∧ d < days.getD j.val 0 + passDuration (mct_better (c i0) k).val omega · refine ⟨(days.getD j.val 0, (c j).val), ?_, hq'd⟩ rw [mct_mem_decodePlan] exact ⟨j, by rw [hc', if_neg hji]; exact hj3, by rw [hc', if_neg hji]⟩ · rw [mct_cost_decodePlan] at hcost ⊢ rw [hPC] have hkc : mct_codeCost costs k = costs.getD p.2 0 := by rw [mct_codeCost, if_neg hk3, hk] have hpt : ∀ j : Fin days.length, mct_codeCost costs (c' j) ≤ mct_codeCost costs (c j) + (if j = i0 then mct_codeCost costs k else 0) := by intro j rw [hc' j] by_cases hj : j = i0 · rw [if_pos hj, if_pos hj, hj] exact mct_better_cost costs (c i0) k · rw [if_neg hj, if_neg hj] exact Nat.le_add_right _ _ calc ∑ j, mct_codeCost costs (c' j) ≤ ∑ j, (mct_codeCost costs (c j) + (if j = i0 then mct_codeCost costs k else 0)) := Finset.sum_le_sum (fun j _ => hpt j) _ = ∑ j, mct_codeCost costs (c j) + ∑ j : Fin days.length, (if j = i0 then mct_codeCost costs k else 0) := Finset.sum_add_distrib _ = ∑ j, mct_codeCost costs (c j) + mct_codeCost costs k := by rw [Finset.sum_ite_eq' Finset.univ i0 (fun _ => mct_codeCost costs k), if_pos (Finset.mem_univ i0)] _ ≤ PlanCost costs rest + costs.getD p.2 0 := by rw [hkc] exact Nat.add_le_add_right hcost _ _ = costs.getD p.2 0 + PlanCost costs rest := Nat.add_comm _ _ · refine ⟨c, ?_, ?_⟩ · rintro d hd ⟨q, hq, hqd⟩ rcases List.mem_cons.mp hq with hqp | hq' · rw [hqp] at hqd exact absurd ⟨d, hd, hqd.1, hqd.2⟩ hex · exact hcov d hd ⟨q, hq', hqd⟩ · rw [hPC] exact Nat.le_trans hcost (Nat.le_add_left _ _) theorem mct_trunc (days costs : List Nat) (plan : List (Nat × Nat)) (hv : IsValidPassPlan days plan) : ∃ code : PlanCode days, IsValidPassPlan days (decodePlan days code) ∧ PlanCost costs (decodePlan days code) ≤ PlanCost costs plan := by obtain ⟨c, hcov, hcost⟩ := mct_trunc_aux days costs plan hv.1 refine ⟨c, ⟨?_, ?_⟩, hcost⟩ · intro q hq rw [mct_mem_decodePlan] at hq obtain ⟨i, hi3, rfl⟩ := hq exact (mct_fin4_ne_three _).mp hi3 · intro d hd exact hcov d hd (hv.2 d hd) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minCostTickets_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minCostTickets_check input result ↔ minCostTickets_spec input result := by obtain ⟨days, costs⟩ := input rw [mct_check_eq, mct_spec_unfold, Bool.and_eq_true, List.any_eq_true, List.all_eq_true] constructor · rintro ⟨⟨code, -, hcode⟩, hall⟩ rw [Bool.and_eq_true, beq_iff_eq, mct_validB_iff] at hcode refine ⟨⟨decodePlan days code, hcode.1, hcode.2⟩, ?_⟩ rintro k ⟨plan, hplan, rfl⟩ obtain ⟨code', hval', hle⟩ := mct_trunc days costs plan hplan have h1 := hall code' (mct_mem_codesOf _ code') rw [Bool.or_eq_true, Bool.not_eq_true', decide_eq_true_eq] at h1 rcases h1 with hnv | hres · have hb := (mct_validB_iff days _).mpr hval' rw [hnv] at hb exact absurd hb Bool.false_ne_true · exact Nat.le_trans hres hle · rintro ⟨⟨plan, hplan, hcost⟩, hlb⟩ refine ⟨?_, ?_⟩ · obtain ⟨code, hval, hle⟩ := mct_trunc days costs plan hplan refine ⟨code, mct_mem_codesOf _ code, ?_⟩ rw [Bool.and_eq_true, beq_iff_eq, mct_validB_iff] refine ⟨hval, ?_⟩ have hge := hlb _ ⟨decodePlan days code, hval, rfl⟩ rw [hcost] at hle exact Nat.le_antisymm hle hge · intro code _ rw [Bool.or_eq_true, Bool.not_eq_true', decide_eq_true_eq] by_cases hv : isValidPassPlanB days (decodePlan days code) = true · exact Or.inr (hlb _ ⟨decodePlan days code, (mct_validB_iff _ _).mp hv, rfl⟩) · exact Or.inl (Bool.eq_false_iff.mpr hv) /-! ### Implementation helpers -/ /-- Advance `j` past every start day whose `kind`-pass window no longer covers `days[i]`. -/ def advanceWindow (days : Array Nat) (i j kind : Nat) : Nat := if h : j ≤ i then if days[i]! ≥ days[j]! + passDuration kind then advanceWindow days i (j + 1) kind else j else j termination_by i + 1 - j /-- The DP table: entry 0 is 0 and entry `i + 1` is the minimum cost covering the first `i + 1` travel days. -/ def minCosts (days : List Nat) (costs : List Nat) : Array Nat := let da := days.toArray ((List.range days.length).foldl (fun (dp, j7, j30) i => let j7' := advanceWindow da i j7 1 let j30' := advanceWindow da i j30 2 let c0 := dp[i]! + costs.getD 0 0 let c1 := dp[j7']! + costs.getD 1 0 let c2 := dp[j30']! + costs.getD 2 0 (dp.push (Nat.min c0 (Nat.min c1 c2)), j7', j30')) ((#[0] : Array Nat), 0, 0)).1 /-! ### Main algorithm (impl) -/ /-- Minimum pass cost by O(n) dynamic programming over the sorted travel days with two sliding window indices. -/ def minimumCostForTickets (input : Input) : Output := let dp := minCosts input.1 input.2 dp[input.1.length]! /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem minimumCostForTickets_correct (input : Input) (h : isValidInput input) : minCostTickets_spec input (minimumCostForTickets input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1], [2, 7, 15]) #guard isValidInput ([365], [2, 7, 15]) #guard isValidInput ([1, 5, 9, 14, 20, 25], [1, 6, 10]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], [2, 7, 15])) #guard !(isValidInput ([0], [2, 7, 15])) #guard !(isValidInput ([1, 2, 2], [2, 7, 15])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minCostTickets_check ([1], [2, 7, 15]) 2 #guard minCostTickets_check ([365], [2, 7, 15]) 2 #guard minCostTickets_check ([1, 5, 9, 14, 20, 25], [1, 6, 10]) 6 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minCostTickets_check ([1], [2, 7, 15]) 4) #guard !(minCostTickets_check ([365], [2, 7, 15]) 0) #guard !(minCostTickets_check ([1, 5, 9, 14, 20, 25], [1, 6, 10]) 4) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard minimumCostForTickets ([1], [2, 7, 15]) == 2 #guard minimumCostForTickets ([365], [2, 7, 15]) == 2 #guard minimumCostForTickets ([1, 5, 9, 14, 20, 25], [1, 6, 10]) == 6 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minCostTickets_check ([1], [2, 7, 15]) (minimumCostForTickets ([1], [2, 7, 15])) #guard minCostTickets_check ([365], [2, 7, 15]) (minimumCostForTickets ([365], [2, 7, 15])) #guard minCostTickets_check ([1, 5, 9, 14, 20, 25], [1, 6, 10]) (minimumCostForTickets ([1, 5, 9, 14, 20, 25], [1, 6, 10])) end PMinimumCostForTickets