import Mathlib /-! # Fraction To Recurring Decimal Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses. If multiple answers are possible, return any of them. It is guaranteed that the length of the answer string is less than 10^4 for all the given inputs. ## Constraints - -2^31 <= numerator, denominator <= 2^31 - 1 - denominator != 0 ## Provided examples - `numerator = 1, denominator = 2` → `"0.5"` - `numerator = 2, denominator = 1` → `"2"` - `numerator = 4, denominator = 333` → `"0.(012)"` ## Synthesized negative examples - invalid input: `numerator = -2147483649, denominator = 1` ([structural] a predicate that admits -2^31 <= numerator, denominator <= 2^31 - 1. one below the minimum numerator) - invalid input: `numerator = 1, denominator = 0` ([structural] a predicate that admits denominator != 0. zero denominator; a predicate checking only the numerator accepts it) - invalid input: `numerator = 2147483648, denominator = 1` ([structural] a predicate that admits -2^31 <= numerator, denominator <= 2^31 - 1. one above the maximum numerator) - `numerator = 1, denominator = 2` → `"0.51"` is wrong (its value differs from 1/2; "0.50" is valid) - `numerator = 2, denominator = 1` → `"2/1"` is wrong ([structural] decimal notation is not required. slash notation preserves the value but is not decimal) - `numerator = 4, denominator = 333` → `"0.(012013)"` is wrong (its value differs from 4/333; "0.(012012)" is valid) -/ namespace PFractionToRecurringDecimal abbrev Input := (Int) × (Int) abbrev Output := String /-! ### Specification helpers -/ /-- Decimal digit test. -/ def isDigitChar (c : Char) : Bool := decide ('0' ≤ c ∧ c ≤ '9') /-- The natural number denoted by a list of decimal digits. -/ def digitsValue (ds : List Char) : Nat := ds.foldl (fun acc c => 10 * acc + (c.toNat - '0'.toNat)) 0 /-- Split a leading '-' sign from a character list. -/ def splitSign (cs : List Char) : Bool × List Char := match cs with | '-' :: t => (true, t) | _ => (false, cs) /-- Split the leading decimal digits from a character list. -/ def splitDigits (cs : List Char) : List Char × List Char := (cs.takeWhile isDigitChar, cs.dropWhile isDigitChar) /-- Split a leading '.' together with the digits following it, if present. -/ def splitFrac (cs : List Char) : Option (List Char) × List Char := match cs with | '.' :: t => let (f, r) := splitDigits t; (some f, r) | _ => (none, cs) /-- Parse the remaining tail: empty, or exactly one parenthesized nonempty block of digits. -/ def parseTail (cs : List Char) : Option (Option (List Char)) := match cs with | [] => some none | '(' :: t => match t.reverse with | ')' :: rev => let inner := rev.reverse if !inner.isEmpty && inner.all isDigitChar then some (some inner) else none | _ => none | _ => none /-- Parse a decimal string into sign, integer digits, fractional digits and repetend. -/ def parseDecimal (s : String) : Option (Bool × List Char × Option (List Char) × Option (List Char)) := let (neg, cs) := splitSign s.toList let (ip, r1) := splitDigits cs let (fp, r2) := splitFrac r1 match parseTail r2 with | none => none | some rep => if !ip.isEmpty && (!(fp == some []) || rep.isSome) && (!rep.isSome || fp.isSome) then some (neg, ip, fp, rep) else none /-- The rational value of a parsed decimal expansion. -/ def expansionValue (neg : Bool) (ip fp : List Char) (rep : Option (List Char)) : Rat := let k : Rat := (10 : Rat) ^ fp.length let base : Rat := (digitsValue ip : Rat) + (digitsValue fp : Rat) / k let full : Rat := match rep with | none => base | some r => base + (digitsValue r : Rat) / (k * ((10 : Rat) ^ r.length - 1)) if neg then -full else full /-- A word that is not a nontrivial repetition of a shorter word. -/ def IsPrimitiveWord (w : List Char) : Prop := ∀ t : List Char, ∀ k : Nat, w = List.flatten (List.replicate k t) → t = [] ∨ k = 1 /-- A rational admitting a finite decimal expansion. -/ def HasFiniteDecimalExpansion (q : Rat) : Prop := ∃ k : Nat, ∃ m : Int, q = (m : Rat) / (10 : Rat) ^ k /-- `s` has the accepted decimal shape and denotes the rational `n / d`. -/ def IsDecimalFractionString (s : String) (n d : Int) : Prop := ∃ neg ip fp rep, parseDecimal s = some (neg, ip, fp, rep) ∧ expansionValue neg ip (fp.getD []) rep = (n : Rat) / (d : Rat) /-- `s` is the canonical decimal expansion of the rational `n / d`. -/ def IsCanonicalDecimalFractionString (s : String) (n d : Int) : Prop := IsDecimalFractionString s n d ∧ ∀ neg ip fp rep, parseDecimal s = some (neg, ip, fp, rep) → (ip = ['0'] ∨ ip.head? ≠ some '0') ∧ (neg ↔ (n : Rat) / (d : Rat) < 0) ∧ ((∃ m : Int, (n : Rat) / (d : Rat) = m) → fp = none) ∧ (HasFiniteDecimalExpansion ((n : Rat) / (d : Rat)) → rep = none ∧ ∀ f, fp = some f → f.reverse.head? ≠ some '0') ∧ (∀ r, rep = some r → IsPrimitiveWord r ∧ (fp.getD []).reverse.head? ≠ r.reverse.head?) /-! ### Validity predicate (V) -/ /-- Valid input: both integers in signed 32-bit range and the denominator nonzero. -/ def isValidInput (input : Input) : Bool := decide ((-2^31 : Int) ≤ input.1 ∧ input.1 ≤ (2^31 : Int) - 1 ∧ (-2^31 : Int) ≤ input.2 ∧ input.2 ≤ (2^31 : Int) - 1 ∧ input.2 ≠ 0) /-! ### Ideal specification (P_spec) -/ /-- `result` is a decimal expansion of the fraction `input.1 / input.2`. -/ def fractionToRecurringDecimal_spec (input : Input) (result : Output) : Prop := IsDecimalFractionString result input.1 input.2 /-! ### Decidable specification (P_check) -/ /-- Remove all factors of 2 and 5 from `m`, leaving the part coprime to 10. -/ def stripTwoFive (m : Nat) : Nat := if h : 2 ≤ m ∧ m % 2 = 0 then stripTwoFive (m / 2) else if h' : 5 ≤ m ∧ m % 5 = 0 then stripTwoFive (m / 5) else m termination_by m decreasing_by all_goals omega /-- `q` admits a finite decimal expansion iff its reduced denominator has no prime factors but 2 and 5. -/ def hasFiniteDecimalExpansionCheck (q : Rat) : Bool := stripTwoFive q.den == 1 /-- A nonempty word with no decomposition into two or more repeats of a shorter block. -/ def isPrimitiveWordCheck (w : List Char) : Bool := !w.isEmpty && (List.range' 2 (w.length - 1)).all (fun k => w != List.flatten (List.replicate k (w.take (w.length / k)))) /-- Executable checker for `fractionToRecurringDecimal_spec`. -/ def fractionToRecurringDecimal_check (input : Input) (result : Output) : Bool := match parseDecimal result with | none => false | some (neg, ip, fp, rep) => let q : Rat := (input.1 : Rat) / (input.2 : Rat) decide (expansionValue neg ip (fp.getD []) rep = q) theorem check_eq (input : Input) (result : Output) : fractionToRecurringDecimal_check input result = (match parseDecimal result with | none => false | some (neg, ip, fp, rep) => decide (expansionValue neg ip (fp.getD []) rep = (input.1 : Rat) / (input.2 : Rat))) := rfl /-- On valid input the checker accepts exactly the specified outputs. -/ theorem fractionToRecurringDecimal_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : fractionToRecurringDecimal_check input result ↔ fractionToRecurringDecimal_spec input result := by rw [check_eq] unfold fractionToRecurringDecimal_spec IsDecimalFractionString cases hp : parseDecimal result with | none => simp only [Bool.false_eq_true, false_iff, not_exists] rintro neg ip fp rep ⟨hs, -⟩ exact absurd hs (by simp) | some t => obtain ⟨neg, ip, fp, rep⟩ := t simp only [decide_eq_true_eq] constructor · intro hval exact ⟨neg, ip, fp, rep, rfl, hval⟩ · rintro ⟨neg', ip', fp', rep', hs, hval⟩ simp only [Option.some.injEq, Prod.mk.injEq] at hs obtain ⟨rfl, rfl, rfl, rfl⟩ := hs exact hval /-! ### Implementation helpers -/ /-- Long-division generation of the fractional digits, returning the digits and the index where the repeating block starts, if any. -/ def buildFractionalDigits (d r : Nat) (seen : List (Nat × Char)) (avail : List Nat) : List Char × Option Nat := if r = 0 then (seen.map Prod.snd, none) else match seen.findIdx? (fun p => p.1 == r) with | some k => (seen.map Prod.snd, some k) | none => let digit := Char.ofNat ('0'.toNat + (10 * r) / d) let r' := (10 * r) % d if h : r ∈ avail then buildFractionalDigits d r' (seen ++ [(r, digit)]) (avail.erase r) else (seen.map Prod.snd, some 0) termination_by avail.length decreasing_by · have hlen := List.length_erase_add_one h omega /-! ### Main algorithm (impl) -/ /-- Canonical decimal expansion of `input.1 / input.2` by long division with a seen-remainder table. -/ def fractionToDecimal (input : Input) : Output := let n := input.1 let d := input.2 let sign := if (n < 0 ∧ 0 < d) ∨ (0 < n ∧ d < 0) then "-" else "" let a := n.natAbs let b := d.natAbs let intPart := toString (a / b) let r0 := a % b if r0 = 0 then sign ++ intPart else let (digits, rep) := buildFractionalDigits b r0 [] (List.range b) match rep with | none => sign ++ intPart ++ "." ++ String.mk digits | some k => sign ++ intPart ++ "." ++ String.mk (digits.take k) ++ "(" ++ String.mk (digits.drop k) ++ ")" /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem fractionToDecimal_correct (input : Input) (h : isValidInput input) : fractionToRecurringDecimal_spec input (fractionToDecimal input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (1, 2) #guard isValidInput (2, 1) #guard isValidInput (4, 333) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (-2147483649, 1)) #guard !(isValidInput (1, 0)) #guard !(isValidInput (2147483648, 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard fractionToRecurringDecimal_check (1, 2) "0.5" #guard fractionToRecurringDecimal_check (2, 1) "2" #guard fractionToRecurringDecimal_check (4, 333) "0.(012)" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(fractionToRecurringDecimal_check (1, 2) "0.51") #guard !(fractionToRecurringDecimal_check (2, 1) "2/1") #guard !(fractionToRecurringDecimal_check (4, 333) "0.(012013)") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard fractionToDecimal (1, 2) == "0.5" #guard fractionToDecimal (2, 1) == "2" #guard fractionToDecimal (4, 333) == "0.(012)" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard fractionToRecurringDecimal_check (1, 2) (fractionToDecimal (1, 2)) #guard fractionToRecurringDecimal_check (2, 1) (fractionToDecimal (2, 1)) #guard fractionToRecurringDecimal_check (4, 333) (fractionToDecimal (4, 333)) end PFractionToRecurringDecimal