import Mathlib /-! # Climbing Stairs You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? ## Constraints - 1 <= n <= 45 ## Provided examples - `n = 2` → `2` - `n = 3` → `3` - `n = 4` → `5` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 45. one below the stated minimum) - invalid input: `n = 46` ([structural] a predicate that admits 1 <= n <= 45. one above the stated maximum) - invalid input: `n = 100` ([structural] a predicate that admits 1 <= n <= 45. round number far above the range) - `n = 2` → `3` is wrong ([structural] count is for n+1 via off-by-one in recurrence base. one above true count; equals true value for n+1) - `n = 3` → `2` is wrong ([structural] off-by-one in recurrence base: counts Fib(n) instead of Fib(n+1). for n=3, Fibonacci indexing gives 2) - `n = 4` → `7` is wrong ([structural] step size is not restricted to 1 or 2. allows 3-step climbs, giving 7 sequences) -/ namespace PClimbingStairs abbrev Input := Nat abbrev Output := Nat /-! ### Specification helpers -/ /-- `seq` is a valid climb of `n` steps when every element is 1 or 2 and the elements sum to `n`. -/ def IsClimbSequence (n : Nat) (seq : List Nat) : Prop := (∀ step ∈ seq, step = 1 ∨ step = 2) ∧ seq.sum = n /-! ### Validity predicate (V) -/ /-- Valid input: a step count `n` with `1 ≤ n ≤ 45`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 45 /-! ### Ideal specification (P_spec) -/ /-- `result` is the number of distinct ways to climb `input` steps: some finite collection of step sequences has size `result` and contains exactly the valid climbs. -/ def climbStairs_spec (input : Input) (result : Output) : Prop := ∃ climbs : Finset (List Nat), climbs.card = result ∧ ∀ seq : List Nat, seq ∈ climbs ↔ IsClimbSequence input seq /-! ### Decidable specification (P_check) -/ /-- Decides `climbStairs_spec input result`. The finset of all valid climbs of `input` steps is enumerated by a two-step recursion (`E n` pairs the climb lists for `n` and `n + 1`), and its size follows the Fibonacci-style pair recursion `C n`, so the existential specification holds iff `(C input).1 = result`, which Lean decides by `Nat` equality. -/ instance decClimbStairsSpec (input result : Nat) : Decidable (∃ climbs : Finset (List Nat), climbs.card = result ∧ ∀ seq : List Nat, seq ∈ climbs ↔ IsClimbSequence input seq) := decidable_of_iff ((Nat.rec (motive := fun _ => Nat × Nat) (1, 1) (fun _ p => (p.2, p.1 + p.2)) input).1 = result) (by let E : Nat → List (List Nat) × List (List Nat) := fun n => Nat.rec (motive := fun _ => List (List Nat) × List (List Nat)) ([[]], [[1]]) (fun _ p => (p.2, p.2.map (1 :: ·) ++ p.1.map (2 :: ·))) n let C : Nat → Nat × Nat := fun n => Nat.rec (motive := fun _ => Nat × Nat) (1, 1) (fun _ p => (p.2, p.1 + p.2)) n have hE0 : E 0 = ([[]], [[1]]) := rfl have hEs : ∀ n, E (n + 1) = ((E n).2, (E n).2.map (1 :: ·) ++ (E n).1.map (2 :: ·)) := fun n => rfl have hC0 : C 0 = (1, 1) := rfl have hCs : ∀ n, C (n + 1) = ((C n).2, (C n).1 + (C n).2) := fun n => rfl have hcons1 : Function.Injective fun x : List Nat => 1 :: x := by intro a b h rw [List.cons.injEq] at h exact h.2 have hcons2 : Function.Injective fun x : List Nat => 2 :: x := by intro a b h rw [List.cons.injEq] at h exact h.2 have key : ∀ n : Nat, ((E n).1.Nodup ∧ (E n).1.length = (C n).1) ∧ ((E n).2.Nodup ∧ (E n).2.length = (C n).2) ∧ (∀ seq, seq ∈ (E n).1 ↔ IsClimbSequence n seq) ∧ (∀ seq, seq ∈ (E n).2 ↔ IsClimbSequence (n + 1) seq) := by intro n induction n with | zero => rw [hE0, hC0] refine ⟨⟨List.nodup_singleton _, rfl⟩, ⟨List.nodup_singleton _, rfl⟩, ?_, ?_⟩ · intro seq show (seq ∈ [[]] ↔ IsClimbSequence 0 seq) simp only [List.mem_singleton] constructor · intro h subst h exact ⟨by simp, rfl⟩ · rintro ⟨hsteps, hsum⟩ cases seq with | nil => rfl | cons a as => exfalso have h1 := hsteps a (by simp) simp only [List.sum_cons] at hsum omega · intro seq show (seq ∈ [[1]] ↔ IsClimbSequence 1 seq) simp only [List.mem_singleton] constructor · intro h subst h exact ⟨by simp, rfl⟩ · rintro ⟨hsteps, hsum⟩ cases seq with | nil => simp at hsum | cons a as => have h1 := hsteps a (by simp) cases as with | nil => simp only [List.sum_cons, List.sum_nil] at hsum have ha : a = 1 := by omega rw [ha] | cons b bs => exfalso have h2 := hsteps b (by simp) simp only [List.sum_cons] at hsum omega | succ n ih => obtain ⟨⟨nd1, len1⟩, ⟨nd2, len2⟩, mem1, mem2⟩ := ih rw [hEs n, hCs n] refine ⟨⟨nd2, len2⟩, ⟨?_, ?_⟩, ?_, ?_⟩ · apply List.nodup_append.2 refine ⟨nd2.map hcons1, nd1.map hcons2, ?_⟩ intro a ha b hb hab simp only [List.mem_map] at ha hb obtain ⟨t, -, ht⟩ := ha obtain ⟨u, -, hu⟩ := hb rw [← ht, ← hu] at hab rw [List.cons.injEq] at hab omega · rw [List.length_append, List.length_map, List.length_map, len1, len2] omega · intro seq exact mem2 seq · intro seq show (seq ∈ (E n).2.map (1 :: ·) ++ (E n).1.map (2 :: ·) ↔ IsClimbSequence (n + 1 + 1) seq) simp only [List.mem_append, List.mem_map] constructor · rintro (⟨t, ht, rfl⟩ | ⟨t, ht, rfl⟩) · obtain ⟨hsteps, hsum⟩ := (mem2 t).mp ht constructor · intro s hs simp only [List.mem_cons] at hs rcases hs with rfl | hs · exact Or.inl rfl · exact hsteps s hs · rw [List.sum_cons, hsum] omega · obtain ⟨hsteps, hsum⟩ := (mem1 t).mp ht constructor · intro s hs simp only [List.mem_cons] at hs rcases hs with rfl | hs · exact Or.inr rfl · exact hsteps s hs · rw [List.sum_cons, hsum] omega · rintro ⟨hsteps, hsum⟩ cases seq with | nil => rw [List.sum_nil] at hsum exact absurd hsum (by omega) | cons a as => have h1 := hsteps a (by simp) simp only [List.sum_cons] at hsum rcases h1 with rfl | rfl · left exact ⟨as, (mem2 as).mpr ⟨fun s hs => hsteps s (List.mem_cons_of_mem 1 hs), by omega⟩, rfl⟩ · right exact ⟨as, (mem1 as).mpr ⟨fun s hs => hsteps s (List.mem_cons_of_mem 2 hs), by omega⟩, rfl⟩ change ((C input).1 = result) ↔ _ constructor · intro hcard refine ⟨(E input).1.toFinset, ?_, fun seq => ?_⟩ · rw [List.toFinset_card_of_nodup (key input).1.1, (key input).1.2] exact hcard · rw [List.mem_toFinset] exact (key input).2.2.1 seq · rintro ⟨climbs, hcard, hiff⟩ have hext : climbs = (E input).1.toFinset := by apply Finset.ext intro seq rw [hiff seq, List.mem_toFinset] exact ((key input).2.2.1 seq).symm rw [hext, List.toFinset_card_of_nodup (key input).1.1, (key input).1.2] at hcard exact hcard) /-- Executable checker obtained mechanically from the specification. -/ def climbStairs_check (input : Input) (result : Output) : Bool := @decide (climbStairs_spec input result) (by unfold climbStairs_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem climbStairs_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : climbStairs_check input result ↔ climbStairs_spec input result := by simp [climbStairs_check] /-! ### Main algorithm (impl) -/ /-- Iterative Fibonacci accumulator: `climbFibAux k a b` is the `k`-fold shift of the pair `(a, b)` along the Fibonacci recurrence, structurally recursive on `k`. -/ def climbFibAux : Nat → Nat → Nat → Nat | 0, a, _ => a | k + 1, a, b => climbFibAux k b (a + b) /-- Number of distinct climbs of `input` steps, computed as the (input+1)th Fibonacci number by a linear-time tail-style iteration. -/ def countClimbStairs (input : Input) : Output := climbFibAux (input + 1) 0 1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countClimbStairs_correct (input : Input) (h : isValidInput input) : climbStairs_spec input (countClimbStairs input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 2 #guard isValidInput 3 #guard isValidInput 4 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 46) #guard !(isValidInput 100) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard climbStairs_check 2 2 #guard climbStairs_check 3 3 #guard climbStairs_check 4 5 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(climbStairs_check 2 3) #guard !(climbStairs_check 3 2) #guard !(climbStairs_check 4 7) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countClimbStairs 2 == 2 #guard countClimbStairs 3 == 3 #guard countClimbStairs 4 == 5 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard climbStairs_check 2 (countClimbStairs 2) #guard climbStairs_check 3 (countClimbStairs 3) #guard climbStairs_check 4 (countClimbStairs 4) end PClimbingStairs