import Mathlib /-! # Restore Ip Addresses A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses. Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order. ## Constraints - 1 <= s.length <= 20 - s consists of digits only. ## Provided examples - `s = "25525511135"` → `["255.255.11.135", "255.255.111.35"]` - `s = "0000"` → `["0.0.0.0"]` - `s = "101023"` → `["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 20. empty string below minimum) - invalid input: `s = "1.2.3.4"` ([structural] a predicate that admits s consists of digits only.. dots are not digits; IPv4-validator predicate accepts) - invalid input: `s = "111111111111111111111"` ([structural] a predicate that admits 1 <= s.length <= 20. 21 digits one past maximum) - `s = "25525511135"` → `[]` is wrong ([structural] no completeness requirement; empty list vacuously sound. Returns no addresses; accepted if any valid IP need not appear) - `s = "0000"` → `["0.0.0.0", "0.0.0.0"]` is wrong ([structural] output length is not required to equal the number of valid addresses. wrong answer accepted if exactness is omitted) - `s = "101023"` → `["1.0.1.023", "1.0.10.23", "1.0.102.3", "1.01.0.23", "1.01.02.3", "1.010.2.3", "10.1.0.23", "10.1.02.3", "10.10.2.3", "101.0.2.3"]` is wrong ([structural] no-leading-zero constraint dropped. all 10 partitions are valid if leading zeros allowed) -/ namespace PRestoreIpAddresses abbrev Input := String abbrev Output := List String /-! ### Specification helpers -/ /-- `p` is the canonical decimal numeral of some `n ≤ 255`, hence a valid IP block with no leading zeros. -/ def validIpBlock (p : String) : Prop := ∃ n : ℕ, n ≤ 255 ∧ p = Nat.repr n /-- `addr` is a valid IPv4 address formed from `s` by inserting exactly three dots without reordering or removing digits. -/ def IsValidIPAddressOf (s addr : String) : Prop := ∃ parts : List String, parts.length = 4 ∧ addr.toList = ['.'].intercalate (parts.map String.toList) ∧ (parts.map String.toList).flatten = s.toList ∧ ∀ p ∈ parts, validIpBlock p /-! ### Validity predicate (V) -/ /-- Valid input: a string of 1 to 20 characters, all digits. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 20 && input.toList.all Char.isDigit /-! ### Ideal specification (P_spec) -/ /-- `result` is duplicate-free, contains only valid IP addresses formed from `input`, and contains every such address. -/ def restoreIpAddresses_spec (input : Input) (result : Output) : Prop := result.Nodup ∧ (∀ addr ∈ result, IsValidIPAddressOf input addr) ∧ (∀ addr, IsValidIPAddressOf input addr → addr ∈ result) /-! ### Decidable specification (P_check) -/ /-- Whether `p` is the decimal numeral of some `n ≤ 255`, checked by enumerating the range. -/ def validIpBlockB (p : String) : Bool := (List.range 256).any fun n => decide (p = Nat.repr n) /-- Whether `addr` splits on dots into four valid blocks whose digits reassemble to `s`. -/ def validAddressOfB (s addr : String) : Bool := let parts := List.splitOn '.' addr.toList decide (parts.length = 4) && parts.all (fun p => validIpBlockB (String.ofList p)) && decide (parts.flatten = s.toList) /-- The possible digit counts of one block: a valid block has one to three digits. -/ def blockLengths : List Nat := [1, 2, 3] /-- Every valid address formed from `s`, found by enumerating the four block lengths. -/ def candidateAddresses (s : String) : List String := let chars := s.toList blockLengths.flatMap fun a => blockLengths.flatMap fun b => blockLengths.filterMap fun c => let d := chars.length - a - b - c if 1 ≤ d && d ≤ 3 then let parts := [chars.take a, (chars.drop a).take b, (chars.drop (a + b)).take c, chars.drop (a + b + c)] let addr := String.ofList (['.'].intercalate parts) if validAddressOfB s addr then some addr else none else none /-- Executable checker for `restoreIpAddresses_spec` over the enumerated valid addresses. -/ def restoreIpAddresses_check (input : Input) (result : Output) : Bool := decide (result.Nodup) && result.all (fun addr => validAddressOfB input addr) && (candidateAddresses input).all (fun addr => decide (addr ∈ result)) theorem validIpBlockB_iff_validIpBlock (p : String) : validIpBlockB p ↔ validIpBlock p := by simp [validIpBlockB, validIpBlock, Nat.lt_succ_iff] set_option maxRecDepth 4096 in set_option maxHeartbeats 800000 in theorem repr_no_dot : ∀ n : Fin 256, '.' ∉ (Nat.repr n.val).toList := by decide theorem address_bridge : ∀ s addr, validAddressOfB s addr ↔ IsValidIPAddressOf s addr := by intro s addr let ps := List.splitOn '.' addr.toList change (decide (ps.length = 4) && ps.all (fun p => validIpBlockB (String.ofList p)) && decide (ps.flatten = s.toList)) ↔ IsValidIPAddressOf s addr simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, validIpBlockB_iff_validIpBlock] constructor · rintro ⟨⟨hlen, hall⟩, hflat⟩ refine ⟨ps.map String.ofList, ?_, ?_, ?_, ?_⟩ · simpa using hlen · simpa [ps] using (List.intercalate_splitOn (xs := addr.toList) '.').symm · simpa using hflat · intro p hp rcases List.mem_map.mp hp with ⟨l, hl, rfl⟩ simpa using hall l hl · rintro ⟨parts, hlen, haddr, hflat, hvalid⟩ have hnodot : ∀ l ∈ parts.map String.toList, '.' ∉ l := by intro l hl rcases List.mem_map.mp hl with ⟨p, hp, rfl⟩ rcases hvalid p hp with ⟨n, hn, rfl⟩ exact repr_no_dot ⟨n, Nat.lt_succ_iff.mpr hn⟩ have hne : parts.map String.toList ≠ [] := by intro he have hh := congrArg List.length he simp [hlen] at hh have hsplit : ps = parts.map String.toList := by dsimp only [ps] rw [haddr, List.splitOn_intercalate '.' hnodot hne] rw [hsplit] refine ⟨⟨?_, ?_⟩, ?_⟩ · simpa using hlen · intro l hl rcases List.mem_map.mp hl with ⟨p, hp, rfl⟩ simpa using hvalid p hp · simpa using hflat theorem root_of_bridges (hb : ∀ s a, validAddressOfB s a ↔ IsValidIPAddressOf s a) (hc : ∀ s a, IsValidIPAddressOf s a → a ∈ candidateAddresses s) (s : Input) (r : Output) : restoreIpAddresses_check s r ↔ restoreIpAddresses_spec s r := by simp only [restoreIpAddresses_check, restoreIpAddresses_spec, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] constructor · rintro ⟨⟨hn, hs⟩, hc'⟩ exact ⟨hn, fun a ha => (hb s a).mp (hs a ha), fun a ha => hc' a (hc s a ha)⟩ · rintro ⟨hn, hs, hc'⟩ refine ⟨⟨hn, fun a ha => (hb s a).mpr (hs a ha)⟩, ?_⟩ intro a ha unfold candidateAddresses at ha simp only [List.mem_flatMap, List.mem_filterMap] at ha obtain ⟨i, hi, j, hj, k, hk, he⟩ := ha split at he <;> simp_all (config := { failIfUnchanged := false }) only [Option.some.injEq, reduceCtorEq] split at he <;> simp_all (config := { failIfUnchanged := false }) only [Option.some.injEq, reduceCtorEq] set_option maxRecDepth 4096 in set_option maxHeartbeats 800000 in theorem block_size (p : String) (hp : validIpBlock p) : 1 ≤ p.toList.length ∧ p.toList.length ≤ 3 := by obtain ⟨n, hn, rfl⟩ := hp have hh : ∀ n : Fin 256, 1 ≤ (Nat.repr n.val).toList.length ∧ (Nat.repr n.val).toList.length ≤ 3 := by decide exact hh ⟨n, by omega⟩ theorem candidate_complete (hb : ∀ s a, validAddressOfB s a ↔ IsValidIPAddressOf s a) : ∀ s a, IsValidIPAddressOf s a → a ∈ candidateAddresses s := by intro s addr hv obtain ⟨parts, hlen, haddr, hflat, hvalid⟩ := hv obtain ⟨p, q, r, t, rfl⟩ := List.length_eq_four.mp hlen have hp := block_size p (hvalid p (by simp)) have hq := block_size q (hvalid q (by simp)) have hr := block_size r (hvalid r (by simp)) have ht := block_size t (hvalid t (by simp)) have hs : s.toList = p.toList ++ q.toList ++ r.toList ++ t.toList := by simpa using hflat.symm have hd : s.toList.length - p.toList.length - q.toList.length - r.toList.length = t.toList.length := by simp [hs, List.length_append] have ha : p.toList.length ∈ blockLengths := by simp [blockLengths]; omega have hb' : q.toList.length ∈ blockLengths := by simp [blockLengths]; omega have hc : r.toList.length ∈ blockLengths := by simp [blockLengths]; omega have hparts : [s.toList.take p.toList.length, (s.toList.drop p.toList.length).take q.toList.length, (s.toList.drop (p.toList.length + q.toList.length)).take r.toList.length, s.toList.drop (p.toList.length + q.toList.length + r.toList.length)] = [p.toList, q.toList, r.toList, t.toList] := by simp only [hs, List.append_assoc, ← List.drop_drop, List.drop_append_length, List.take_append_length] have he : String.ofList (['.'].intercalate [p.toList,q.toList,r.toList,t.toList]) = addr := by apply String.toList_injective simpa using haddr.symm have hv' : validAddressOfB s addr = true := (hb s addr).mpr ⟨[p,q,r,t], by simp, haddr, hflat, hvalid⟩ unfold candidateAddresses apply List.mem_flatMap.mpr refine ⟨p.toList.length, ha, List.mem_flatMap.mpr ?_⟩ refine ⟨q.toList.length, hb', List.mem_filterMap.mpr ?_⟩ refine ⟨r.toList.length, hc, ?_⟩ dsimp only rw [hd] simp only [show (decide (1 ≤ t.toList.length) && decide (t.toList.length ≤ 3)) = true by simp [ht.1, ht.2], ↓reduceIte, hparts, he, hv'] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem restoreIpAddresses_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : restoreIpAddresses_check input result ↔ restoreIpAddresses_spec input result := by exact root_of_bridges address_bridge (candidate_complete address_bridge) input result /-! ### Main algorithm (impl) -/ /-- All valid IP addresses formed from `input`, by enumerating block lengths via `candidateAddresses`. -/ def restoreIpAddressesImpl (input : Input) : Output := candidateAddresses input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem restoreIpAddressesImpl_correct (input : Input) (h : isValidInput input) : restoreIpAddresses_spec input (restoreIpAddressesImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "25525511135" #guard isValidInput "0000" #guard isValidInput "101023" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput "1.2.3.4") #guard !(isValidInput "111111111111111111111") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard restoreIpAddresses_check "25525511135" ["255.255.11.135", "255.255.111.35"] #guard restoreIpAddresses_check "0000" ["0.0.0.0"] #guard restoreIpAddresses_check "101023" ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(restoreIpAddresses_check "25525511135" []) #guard !(restoreIpAddresses_check "0000" ["0.0.0.0", "0.0.0.0"]) #guard !(restoreIpAddresses_check "101023" ["1.0.1.023", "1.0.10.23", "1.0.102.3", "1.01.0.23", "1.01.02.3", "1.010.2.3", "10.1.0.23", "10.1.02.3", "10.10.2.3", "101.0.2.3"]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard restoreIpAddressesImpl "25525511135" == ["255.255.11.135", "255.255.111.35"] #guard restoreIpAddressesImpl "0000" == ["0.0.0.0"] #guard restoreIpAddressesImpl "101023" == ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard restoreIpAddresses_check "25525511135" (restoreIpAddressesImpl "25525511135") #guard restoreIpAddresses_check "0000" (restoreIpAddressesImpl "0000") #guard restoreIpAddresses_check "101023" (restoreIpAddressesImpl "101023") end PRestoreIpAddresses