import Mathlib /-! # Largest Number Given a list of non-negative integers nums, arrange them such that they form the largest number and return it. Since the result may be very large, so you need to return a string instead of an integer. ## Constraints - 1 <= nums.length <= 100 - 0 <= nums[i] <= 10^9 ## Provided examples - `nums = [10, 2]` → `"210"` - `nums = [3, 30, 34, 5, 9]` → `"9534330"` - `nums = [1]` → `"1"` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 100. empty list where at least one element is required) - invalid input: `nums = [1000000001]` ([structural] a predicate that admits 0 <= nums[i] <= 10^9. one past the stated value maximum) - invalid input: `nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]` ([structural] a predicate that admits 1 <= nums.length <= 100. one past the maximum length) - `nums = [10, 2]` → `"211"` is wrong ([structural] no real arrangement is required to reach the answer. 211 exceeds any arrangement of 10 and 2) - `nums = [3, 30, 34, 5, 9]` → `"9534303"` is wrong ([structural] the answer is only required to be a valid arrangement, not the largest one. a permutation of nums that is not maximal) - `nums = [1]` → `"2"` is wrong ([structural] soundness clause missing: answer need not be achieved by any arrangement. 2 is larger than every arrangement but no arrangement reaches it) -/ namespace PLargestNumber abbrev Input := List Nat abbrev Output := String /-! ### Specification helpers -/ /-- The natural number whose decimal expansion is the concatenation of the decimal expansions of the elements of `l` in order. -/ def DecimalValue (l : List Nat) : Nat := Nat.ofDigits 10 (List.flatten ((l.map (fun n => if n = 0 then [0] else Nat.digits 10 n)).reverse)) /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty list of at most 100 natural numbers, each at most 10^9. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 100 && input.all (fun n => n ≤ 10^9) /-! ### Ideal specification (P_spec) -/ /-- `result` is the canonical decimal string of the greatest value attained by concatenating the elements of any permutation of `input`. -/ def largestNumber_spec (input : Input) (result : Output) : Prop := ∃ v : Nat, IsGreatest {n : Nat | ∃ p : List Nat, p.Perm input ∧ n = DecimalValue p} v ∧ result = toString v /-! ### Decidable specification (P_check) -/ /-- Executable checker for `largestNumber_spec`: some permutation value is the greatest among all permutation values and `result` is its canonical decimal string. -/ def largestNumber_check (input : Input) (result : Output) : Bool := let vals := input.permutations.map DecimalValue vals.any fun v => vals.all (fun n => decide (n ≤ v)) && decide (result = toString v) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem largestNumber_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : largestNumber_check input result ↔ largestNumber_spec input result := by simp only [largestNumber_check, largestNumber_spec, List.any_eq_true, List.all_eq_true, Bool.and_eq_true, decide_eq_true_eq, List.mem_map, List.mem_permutations, IsGreatest, mem_upperBounds, Set.mem_setOf_eq] grind only [] /-! ### Implementation helpers -/ /-- Whether `x` should precede `y` in the largest arrangement: the concatenation `x` then `y` is at least the concatenation `y` then `x`. -/ def concatBetter (x y : Nat) : Bool := decide (DecimalValue [y, x] ≤ DecimalValue [x, y]) /-- Inserts `x` into an already sorted list, keeping the `concatBetter` order. -/ def insertSorted (x : Nat) : List Nat → List Nat | [] => [x] | y :: ys => if concatBetter x y then x :: y :: ys else y :: insertSorted x ys /-- Insertion sorts the list so that earlier elements precede later ones under `concatBetter`. -/ def largestNumberSort : List Nat → List Nat | [] => [] | x :: xs => insertSorted x (largestNumberSort xs) /-! ### Main algorithm (impl) -/ /-- Sorts by the concatenation comparator and renders the decimal value of the sorted list as a string. -/ def arrangeToLargestNumber (input : Input) : Output := toString (DecimalValue (largestNumberSort input)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem arrangeToLargestNumber_correct (input : Input) (h : isValidInput input) : largestNumber_spec input (arrangeToLargestNumber input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [10, 2] #guard isValidInput [3, 30, 34, 5, 9] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [1000000001]) #guard !(isValidInput [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard largestNumber_check [10, 2] "210" #guard largestNumber_check [3, 30, 34, 5, 9] "9534330" #guard largestNumber_check [1] "1" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(largestNumber_check [10, 2] "211") #guard !(largestNumber_check [3, 30, 34, 5, 9] "9534303") #guard !(largestNumber_check [1] "2") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard arrangeToLargestNumber [10, 2] == "210" #guard arrangeToLargestNumber [3, 30, 34, 5, 9] == "9534330" #guard arrangeToLargestNumber [1] == "1" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard largestNumber_check [10, 2] (arrangeToLargestNumber [10, 2]) #guard largestNumber_check [3, 30, 34, 5, 9] (arrangeToLargestNumber [3, 30, 34, 5, 9]) #guard largestNumber_check [1] (arrangeToLargestNumber [1]) end PLargestNumber