import Mathlib /-! # Create Maximum Number You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k. Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved. Return an array of the k digits representing the answer. ## Constraints - m == nums1.length - n == nums2.length - 1 <= m, n <= 500 - 0 <= nums1[i], nums2[i] <= 9 - 1 <= k <= m + n - nums1 and nums2 do not have leading zeros. ## Provided examples - `nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], k = 5` → `[9, 8, 6, 5, 3]` - `nums1 = [6, 7], nums2 = [6, 0, 4], k = 5` → `[6, 7, 6, 0, 4]` - `nums1 = [3, 9], nums2 = [8, 9], k = 3` → `[9, 8, 9]` ## Synthesized negative examples - invalid input: `nums1 = [], nums2 = [1], k = 1` ([structural] a predicate that admits 1 <= m, n <= 500. empty nums1 below length minimum) - invalid input: `nums1 = [10], nums2 = [1], k = 1` ([structural] a predicate that admits 0 <= nums1[i], nums2[i] <= 9. digit 10 outside allowed range) - invalid input: `nums1 = [1], nums2 = [1], k = 0` ([structural] a predicate that admits 1 <= k <= m + n. k below stated lower bound) - `nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], k = 5` → `[9, 1, 2, 5, 8, 3]` is wrong ([structural] does not require the answer to have exactly k digits. length k+1 still a valid digit sequence) - `nums1 = [6, 7], nums2 = [6, 0, 4], k = 5` → `[6, 6, 7, 0, 4]` is wrong ([structural] maximality stated as achievability alone. valid merge, but not the lexicographically largest) - `nums1 = [3, 9], nums2 = [8, 9], k = 3` → `[9, 8]` is wrong ([structural] output length is not required to equal k. length is k-1 instead of 3) -/ namespace PCreateMaximumNumber abbrev Input := (List Nat) × (List Nat) × (Nat) abbrev Output := List Nat /-! ### Specification helpers -/ /-- `DigitInterleave xs ys zs` means `zs` is obtained by shuffling `xs` and `ys` while preserving each list's order. -/ inductive DigitInterleave : List Nat → List Nat → List Nat → Prop where | nil : DigitInterleave [] [] [] | left {x : Nat} {xs ys zs : List Nat} : DigitInterleave xs ys zs → DigitInterleave (x :: xs) ys (x :: zs) | right {x : Nat} {xs ys zs : List Nat} : DigitInterleave xs ys zs → DigitInterleave xs (x :: ys) (x :: zs) /-- `result` is a length-`k` merge of order-preserving subsequences of `nums1` and `nums2`. -/ def IsValidMerge (nums1 nums2 : List Nat) (k : Nat) (result : List Nat) : Prop := result.length = k ∧ ∃ a b : List Nat, List.Sublist a nums1 ∧ List.Sublist b nums2 ∧ DigitInterleave a b result /-! ### Validity predicate (V) -/ /-- Valid input: lengths and `k` are in range, all digits are at most 9, and longer numbers have nonzero first digit. -/ def isValidInput (input : Input) : Bool := let nums1 := input.1 let nums2 := input.2.1 let k := input.2.2 (1 ≤ nums1.length) && (nums1.length ≤ 500) && (1 ≤ nums2.length) && (nums2.length ≤ 500) && nums1.all (· ≤ 9) && nums2.all (· ≤ 9) && (1 ≤ k) && (k ≤ nums1.length + nums2.length) && (nums1.length ≤ 1 || nums1.head? != some 0) && (nums2.length ≤ 1 || nums2.head? != some 0) /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest valid length-`k` merge of the two digit lists under lexicographic order. -/ def maxNumber_spec (input : Input) (result : Output) : Prop := IsGreatest {r : List Nat | IsValidMerge input.1 input.2.1 input.2.2 r} result /-! ### Decidable specification (P_check) -/ /-- All order-preserving shuffles of `xs` and `ys`; `fuel` bounds the recursion depth. -/ def interleaveAllAux : Nat → List Nat → List Nat → List (List Nat) | 0, _, _ => [] | _ + 1, [], ys => [ys] | _ + 1, xs, [] => [xs] | n + 1, x :: xs, y :: ys => (interleaveAllAux n xs (y :: ys)).map (x :: ·) ++ (interleaveAllAux n (x :: xs) ys).map (y :: ·) /-- All order-preserving shuffles of `xs` and `ys`. -/ def interleaveAll (xs ys : List Nat) : List (List Nat) := interleaveAllAux (xs.length + ys.length + 1) xs ys /-- All valid length-`k` merges: interleavings of sublists of `nums1` and `nums2` whose lengths add to `k`. -/ def mergeCandidates (nums1 nums2 : List Nat) (k : Nat) : List (List Nat) := nums1.sublists.flatMap fun a => nums2.sublists.flatMap fun b => if a.length + b.length = k then interleaveAll a b else [] /-- Executable checker for `maxNumber_spec` over the finite list of merge candidates. -/ def maxNumber_check (input : Input) (result : Output) : Bool := decide (result ∈ mergeCandidates input.1 input.2.1 input.2.2 ∧ ∀ r ∈ mergeCandidates input.1 input.2.1 input.2.2, r ≤ result) theorem wx_interleave_nil_left (ys zs : List Nat) : DigitInterleave [] ys zs ↔ zs = ys := by induction ys generalizing zs with | nil => constructor · intro h cases h rfl · intro h subst zs exact .nil | cons y ys ih => constructor · intro h cases h with | right h => simpa using congrArg (List.cons y) ((ih _).mp h) · intro h subst zs exact .right ((ih ys).mpr rfl) theorem wx_interleave_nil_right (xs zs : List Nat) : DigitInterleave xs [] zs ↔ zs = xs := by induction xs generalizing zs with | nil => constructor · intro h cases h rfl · intro h subst zs exact .nil | cons x xs ih => constructor · intro h cases h with | left h => simpa using congrArg (List.cons x) ((ih _).mp h) · intro h subst zs exact .left ((ih xs).mpr rfl) theorem wx_interleave_mem (xs ys zs : List Nat) : zs ∈ interleaveAll xs ys ↔ DigitInterleave xs ys zs := by induction xs generalizing ys zs with | nil => simp [interleaveAll, interleaveAllAux, wx_interleave_nil_left] | cons x xs ihx => induction ys generalizing zs with | nil => simp [interleaveAll, interleaveAllAux, wx_interleave_nil_right] | cons y ys ihy => simp only [interleaveAll, interleaveAllAux, List.mem_append, List.mem_map] rw [show interleaveAllAux ((x :: xs).length + (y :: ys).length) xs (y :: ys) = interleaveAll xs (y :: ys) by simp [interleaveAll, Nat.add_assoc, Nat.add_comm, Nat.add_left_comm]] rw [show interleaveAllAux ((x :: xs).length + (y :: ys).length) (x :: xs) ys = interleaveAll (x :: xs) ys by simp [interleaveAll, Nat.add_assoc, Nat.add_comm, Nat.add_left_comm]] simp only [ihx, ihy] constructor · rintro (⟨zs, h, rfl⟩ | ⟨zs, h, rfl⟩) · exact .left h · exact .right h · intro h cases h with | left h => exact Or.inl ⟨_, h, rfl⟩ | right h => exact Or.inr ⟨_, h, rfl⟩ theorem wx_interleave_length {xs ys zs : List Nat} (h : DigitInterleave xs ys zs) : zs.length = xs.length + ys.length := by induction h <;> simp_all <;> omega theorem wx_mergeCandidates_mem (nums1 nums2 : List Nat) (k : Nat) (r : List Nat) : r ∈ mergeCandidates nums1 nums2 k ↔ IsValidMerge nums1 nums2 k r := by constructor · intro hr simp only [mergeCandidates, List.mem_flatMap] at hr rcases hr with ⟨a, ha, b, hb, hr⟩ split at hr next hab => have hi : DigitInterleave a b r := (wx_interleave_mem a b r).mp hr refine ⟨?_, a, b, ?_, ?_, hi⟩ · rw [wx_interleave_length hi] exact hab · simpa using ha · simpa using hb next hne => simp at hr · rintro ⟨hrlen, a, b, ha, hb, hi⟩ simp only [mergeCandidates, List.mem_flatMap] refine ⟨a, ?_, b, ?_, ?_⟩ · simpa using ha · simpa using hb · have hab : a.length + b.length = k := by rw [← hrlen, wx_interleave_length hi] simp [hab, wx_interleave_mem, hi] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxNumber_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxNumber_check input result ↔ maxNumber_spec input result := by simp [maxNumber_check, maxNumber_spec, IsGreatest, upperBounds, wx_mergeCandidates_mem] /-! ### Implementation helpers -/ /-- Pop stack entries smaller than `x` while drops remain, returning the new stack and remaining drops. -/ def popSmaller : List Nat → Nat → Nat → List Nat × Nat | stk, 0, _ => (stk, 0) | [], d, _ => ([], d) | s :: ss, d + 1, x => if s < x then popSmaller ss d x else (s :: ss, d + 1) /-- Scan `xs` left to right, pushing each digit onto the stack after dropping smaller tops while drops remain. -/ def stackPass : List Nat → List Nat → Nat → List Nat | [], stk, _ => stk.reverse | x :: xs, stk, d => let (stk', d') := popSmaller stk d x stackPass xs (x :: stk') d' /-- Lexicographically maximum order-preserving subsequence of `t` digits from `xs`, by the stack-greedy rule. -/ def maxSubsequence (xs : List Nat) (t : Nat) : List Nat := (stackPass xs [] (xs.length - t)).take t /-- Whether `xs` is lexicographically greater than `ys`. -/ def lexGreater : List Nat → List Nat → Bool | [], _ => false | _ :: _, [] => true | x :: xs, y :: ys => if y < x then true else if x < y then false else lexGreater xs ys /-- Merge two digit lists into the lexicographically largest order-preserving interleaving. -/ def mergeMax : List Nat → List Nat → List Nat | [], ys => ys | xs, [] => xs | x :: xs, y :: ys => if lexGreater (x :: xs) (y :: ys) then x :: mergeMax xs (y :: ys) else y :: mergeMax (x :: xs) ys termination_by a b => a.length + b.length /-- Candidate answer for the split taking `i` digits from `nums1` and `k - i` from `nums2`. -/ def maxNumberForSplit (nums1 nums2 : List Nat) (k i : Nat) : List Nat := mergeMax (maxSubsequence nums1 i) (maxSubsequence nums2 (k - i)) /-- Largest candidate over every feasible split of `k` between the two lists. -/ def chooseBestSplit (nums1 nums2 : List Nat) (k : Nat) : List Nat := let lo := k - min k nums2.length let hi := min k nums1.length (List.range' lo (hi + 1 - lo)).foldl (fun best i => let cand := maxNumberForSplit nums1 nums2 k i if lexGreater cand best then cand else best) [] /-! ### Main algorithm (impl) -/ /-- Maximum `k`-digit merge by greedy maximum subsequences per split and lexicographic-suffix merging. -/ def createMaxNumber (input : Input) : Output := chooseBestSplit input.1 input.2.1 input.2.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem createMaxNumber_correct (input : Input) (h : isValidInput input) : maxNumber_spec input (createMaxNumber input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([3, 4, 6, 5], [9, 1, 2, 5, 8, 3], 5) #guard isValidInput ([6, 7], [6, 0, 4], 5) #guard isValidInput ([3, 9], [8, 9], 3) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], [1], 1)) #guard !(isValidInput ([10], [1], 1)) #guard !(isValidInput ([1], [1], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxNumber_check ([3, 4, 6, 5], [9, 1, 2, 5, 8, 3], 5) [9, 8, 6, 5, 3] #guard maxNumber_check ([6, 7], [6, 0, 4], 5) [6, 7, 6, 0, 4] #guard maxNumber_check ([3, 9], [8, 9], 3) [9, 8, 9] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxNumber_check ([3, 4, 6, 5], [9, 1, 2, 5, 8, 3], 5) [9, 1, 2, 5, 8, 3]) #guard !(maxNumber_check ([6, 7], [6, 0, 4], 5) [6, 6, 7, 0, 4]) #guard !(maxNumber_check ([3, 9], [8, 9], 3) [9, 8]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard createMaxNumber ([3, 4, 6, 5], [9, 1, 2, 5, 8, 3], 5) == [9, 8, 6, 5, 3] #guard createMaxNumber ([6, 7], [6, 0, 4], 5) == [6, 7, 6, 0, 4] #guard createMaxNumber ([3, 9], [8, 9], 3) == [9, 8, 9] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxNumber_check ([3, 4, 6, 5], [9, 1, 2, 5, 8, 3], 5) (createMaxNumber ([3, 4, 6, 5], [9, 1, 2, 5, 8, 3], 5)) #guard maxNumber_check ([6, 7], [6, 0, 4], 5) (createMaxNumber ([6, 7], [6, 0, 4], 5)) #guard maxNumber_check ([3, 9], [8, 9], 3) (createMaxNumber ([3, 9], [8, 9], 3)) end PCreateMaximumNumber