import Mathlib /-! # Compare Version Numbers Given two version strings, version1 and version2, compare them. A version string consists of revisions separated by dots '.'. The value of the revision is its integer conversion ignoring leading zeros. To compare version strings, compare their revision values in left-to-right order. If one of the version strings has fewer revisions, treat the missing revision values as 0. Return the following: If version1 < version2, return -1. If version1 > version2, return 1. Otherwise, return 0. ## Constraints - 1 <= version1.length, version2.length <= 500 - version1 and version2 only contain digits and '.'. - version1 and version2 are valid version numbers. - All the given revisions in version1 and version2 can be stored in a 32-bit integer. ## Provided examples - `version1 = "1.2", version2 = "1.10"` → `-1` - `version1 = "1.01", version2 = "1.001"` → `0` - `version1 = "1.0", version2 = "1.0.0.0"` → `0` ## Synthesized negative examples - invalid input: `version1 = "1.2147483648", version2 = "1"` ([structural] a predicate that admits All the given revisions in version1 and version2 can be stored in a 32-bit integer.. revision 2147483648 overflows signed 32-bit) - invalid input: `version1 = "1..2", version2 = "1"` ([structural] a predicate that admits version1 and version2 are valid version numbers.. consecutive dots create an empty revision) - invalid input: `version1 = "1.٣", version2 = "1"` ([structural] a predicate that admits version1 and version2 only contain digits and '.'.. non-ASCII digit passes a predicate using isdigit()) - `version1 = "1.2", version2 = "1.10"` → `-2` is wrong ([structural] exact value -1 is not required, only a negative result for less-than. negative indicator one below the true -1) - `version1 = "1.01", version2 = "1.001"` → `1` is wrong ([structural] equality treated as greater-than in comparison. true is 0, but equal versions yield 1) - `version1 = "1.0", version2 = "1.0.0.0"` → `-1` is wrong ([structural] missing revisions are not treated as zero. shorter version considered smaller after equal prefix) -/ namespace PCompareVersionNumbers abbrev Input := (String) × (String) abbrev Output := Int /-! ### Specification helpers -/ /-- The integer value of a revision, read from its digit characters ignoring leading zeros. -/ def revisionValue (cs : List Char) : Nat := cs.foldl (fun acc c => acc * 10 + (c.toNat - '0'.toNat)) 0 /-- Splits characters at dots, accumulating the current piece and the finished pieces. -/ def splitDotsAux : List Char → List Char → List (List Char) → List (List Char) | [], cur, acc => (cur.reverse :: acc).reverse | '.' :: cs, cur, acc => splitDotsAux cs [] (cur.reverse :: acc) | c :: cs, cur, acc => splitDotsAux cs (c :: cur) acc /-- The dot-separated pieces of a version string as character lists. -/ def splitDots (v : String) : List (List Char) := splitDotsAux v.toList [] [] /-- The revision values of a version string in left-to-right order. -/ def versionRevisions (v : String) : List Nat := (splitDots v).map revisionValue /-- `v1` is strictly less than `v2` under left-to-right revision comparison, missing revisions read as 0. -/ def VersionLT (v1 v2 : String) : Prop := ∃ i : Nat, (versionRevisions v1).getI i < (versionRevisions v2).getI i ∧ ∀ j : Nat, j < i → (versionRevisions v1).getI j = (versionRevisions v2).getI j /-- A well-formed version: bounded length, ASCII digits and dots, no empty revision, revisions fit in 32 bits. -/ def validVersion (v : String) : Bool := 1 ≤ v.length && v.length ≤ 500 && v.toList.all (fun c => ('0' ≤ c && c ≤ '9') || c == '.') && !(splitDots v).any (·.isEmpty) && (splitDots v).all (fun r => revisionValue r ≤ 2147483647) /-! ### Validity predicate (V) -/ /-- Valid input: both version strings are well-formed versions. -/ def isValidInput (input : Input) : Bool := validVersion input.1 && validVersion input.2 /-! ### Ideal specification (P_spec) -/ /-- `result` is -1 exactly when `version1 < version2`, 1 exactly when `version2 < version1`, and 0 otherwise. -/ def compareVersion_spec (input : Input) (result : Output) : Prop := (result = -1 ↔ VersionLT input.1 input.2) ∧ (result = 1 ↔ VersionLT input.2 input.1) ∧ (result = 0 ↔ ¬ VersionLT input.1 input.2 ∧ ¬ VersionLT input.2 input.1) /-! ### Decidable specification (P_check) -/ /-- Decides `VersionLT`, the first-difference comparison inside `compareVersion_spec`. A witness needs `(versionRevisions v2).getI i > 0`, which forces `i < (versionRevisions v2).length` since `getI` returns the default `0` out of range; hence the unbounded `∃ i : Nat` reduces to a bounded search over `List.range (max _ _)`, decided by `List.decidableBEx` with the prefix check decided by `Nat.decidableBallLT`. The remaining conjunction and iff structure of `compareVersion_spec` is then decided by Lean's own instances for `And`, `Iff`, and `Not`. -/ instance decVersionLT (v1 v2 : String) : Decidable (VersionLT v1 v2) := decidable_of_iff (∃ i ∈ List.range (max (versionRevisions v1).length (versionRevisions v2).length), (versionRevisions v1).getI i < (versionRevisions v2).getI i ∧ ∀ j : Nat, j < i → (versionRevisions v1).getI j = (versionRevisions v2).getI j) (by constructor · rintro ⟨i, -, hi, hpre⟩ exact ⟨i, hi, hpre⟩ · rintro ⟨i, hi, hpre⟩ have hi2 : i < (versionRevisions v2).length := by by_contra h have h0 : (versionRevisions v2).getI i = 0 := List.getI_eq_default (versionRevisions v2) (Nat.le_of_not_lt h) rw [h0] at hi exact (Nat.not_lt_zero _) hi exact ⟨i, List.mem_range.mpr (lt_of_lt_of_le hi2 (Nat.le_max_right _ _)), hi, hpre⟩) /-- Executable checker obtained mechanically from the specification. -/ def compareVersion_check (input : Input) (result : Output) : Bool := @decide (compareVersion_spec input result) (by unfold compareVersion_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem compareVersion_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : compareVersion_check input result ↔ compareVersion_spec input result := by simp [compareVersion_check] /-! ### Implementation helpers -/ /-- Compares two revision lists left-to-right, treating missing trailing revisions as 0, and returns -1, 0, or 1. -/ def compareRevs : List Nat → List Nat → Int | [], [] => 0 | [], b :: bs => if b = 0 then compareRevs [] bs else -1 | a :: as, [] => if a = 0 then compareRevs as [] else 1 | a :: as, b :: bs => if a < b then -1 else if b < a then 1 else compareRevs as bs termination_by l1 l2 => l1.length + l2.length /-! ### Main algorithm (impl) -/ /-- First-difference scan over the parsed revision lists of the two version strings. -/ def compareVersions (input : Input) : Output := compareRevs (versionRevisions input.1) (versionRevisions input.2) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem compareVersions_correct (input : Input) (h : isValidInput input) : compareVersion_spec input (compareVersions input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("1.2", "1.10") #guard isValidInput ("1.01", "1.001") #guard isValidInput ("1.0", "1.0.0.0") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("1.2147483648", "1")) #guard !(isValidInput ("1..2", "1")) #guard !(isValidInput ("1.٣", "1")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard compareVersion_check ("1.2", "1.10") (-1) #guard compareVersion_check ("1.01", "1.001") 0 #guard compareVersion_check ("1.0", "1.0.0.0") 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(compareVersion_check ("1.2", "1.10") (-2)) #guard !(compareVersion_check ("1.01", "1.001") 1) #guard !(compareVersion_check ("1.0", "1.0.0.0") (-1)) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard compareVersions ("1.2", "1.10") == (-1) #guard compareVersions ("1.01", "1.001") == 0 #guard compareVersions ("1.0", "1.0.0.0") == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard compareVersion_check ("1.2", "1.10") (compareVersions ("1.2", "1.10")) #guard compareVersion_check ("1.01", "1.001") (compareVersions ("1.01", "1.001")) #guard compareVersion_check ("1.0", "1.0.0.0") (compareVersions ("1.0", "1.0.0.0")) end PCompareVersionNumbers