import Mathlib /-! # Reorder Data In Log Files You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier. There are two types of logs: Letter-logs: All words (except the identifier) consist of lowercase English letters. Digit-logs: All words (except the identifier) consist of digits. Reorder these logs so that: The letter-logs come before all digit-logs. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers. The digit-logs maintain their relative ordering. Return the final order of the logs. ## Constraints - 1 <= logs.length <= 100 - 3 <= logs[i].length <= 100 - All the tokens of logs[i] are separated by a single space. - logs[i] is guaranteed to have an identifier and at least one word after the identifier. ## Provided examples - `logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]` → `["let1 art can", "let3 art zero", "let2 own kit dig", "dig1 8 1 5 1", "dig2 3 6"]` - `logs = ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"]` → `["g1 act car", "a8 act zoo", "ab1 off key dog", "a1 9 2 3 1", "zo4 4 7"]` - `logs = ["z9 2 3 4", "b2 run let", "a1 1 2 3", "x3 jump high", "y8 run let"]` → `["x3 jump high", "b2 run let", "y8 run let", "z9 2 3 4", "a1 1 2 3"]` ## Synthesized negative examples - invalid input: `logs = []` ([structural] a predicate that admits 1 <= logs.length <= 100. empty where the minimum length is one; a predicate checking each string accepts it.) - invalid input: `logs = ["a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1"]` ([structural] a predicate that admits 1 <= logs.length <= 100. one log past the maximum length; a predicate forgetting the ceiling accepts it.) - invalid input: `logs = ["a1 b"]` ([structural] a predicate that admits All the tokens of logs[i] are separated by a single space.. two spaces between tokens; a predicate splitting on whitespace accepts it.) - `logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]` → `["let1 art can", "let3 art zero", "let2 own kit dig", "dig2 3 6", "dig1 8 1 5 1"]` is wrong ([structural] relative order of digit-logs is not required to be preserved. dig2 placed before dig1, all else exact) - `logs = ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"]` → `["a1 9 2 3 1", "zo4 4 7", "g1 act car", "a8 act zoo", "ab1 off key dog"]` is wrong ([structural] letter-logs are not required to precede digit-logs. digit logs first, but sorting and relative order hold) - `logs = ["z9 2 3 4", "b2 run let", "a1 1 2 3", "x3 jump high", "y8 run let"]` → `[]` is wrong ([structural] nothing requires every log to appear in the output. empty list vacuously satisfies all ordering conditions) -/ namespace PReorderDataInLogFiles abbrev Input := List String abbrev Output := List String /-! ### Specification helpers -/ /-- The first space-separated token of a log. -/ def logIdentifier (s : String) : String := (s.splitOn).head! /-- The log's content: its words after the identifier, rejoined by single spaces. -/ def logContent (s : String) : String := " ".intercalate (s.splitOn).tail /-- Every word after the log's identifier consists of lowercase English letters. -/ def IsLetterLog (s : String) : Prop := ∀ w ∈ (s.splitOn).tail, w ≠ "" ∧ ∀ c ∈ w.toList, 'a' ≤ c ∧ c ≤ 'z' /-- Every word after the log's identifier consists of digits. -/ def IsDigitLog (s : String) : Prop := ∀ w ∈ (s.splitOn).tail, w ≠ "" ∧ ∀ c ∈ w.toList, '0' ≤ c ∧ c ≤ '9' /-- Digit-loghood is decidable, so digit-logs can be filtered out of a list. -/ instance instDecidableIsDigitLog : DecidablePred IsDigitLog := fun s => by unfold IsDigitLog; infer_instance /-- Non-strict lexicographic order on letter-logs by content, then by identifier. -/ def LetterLogLe (a b : String) : Prop := toLex (logContent a, logIdentifier a) ≤ toLex (logContent b, logIdentifier b) /-! ### Validity predicate (V) -/ /-- Valid input: 1–100 logs, each 3–100 characters, tokens separated by exactly one space with an identifier and at least one word after it, each log a letter-log or a digit-log. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 100 && input.all fun log => 3 ≤ log.length && log.length ≤ 100 && (let words := log.splitOn 2 ≤ words.length && words.all (· ≠ "") && (words.tail.all (fun w => w.all fun c => 'a' ≤ c && c ≤ 'z') || words.tail.all (fun w => w.all fun c => '0' ≤ c && c ≤ '9'))) /-! ### Ideal specification (P_spec) -/ /-- `result` is a permutation of `input` whose digit-logs form a suffix keeping their input order and whose letter-logs are ordered by content, then identifier. -/ def reorderLogs_spec (input : Input) (result : Output) : Prop := result.Perm input ∧ (∀ i j : Fin result.length, i < j → IsDigitLog (result.get i) → IsDigitLog (result.get j)) ∧ (∀ i j : Fin result.length, i < j → IsLetterLog (result.get i) → IsLetterLog (result.get j) → LetterLogLe (result.get i) (result.get j)) ∧ result.filter IsDigitLog = input.filter IsDigitLog /-! ### Decidable specification (P_check) -/ /-- Letter-loghood is decidable from the bounded checks on each word and character. -/ instance instDecidableIsLetterLog : DecidablePred IsLetterLog := fun s => by unfold IsLetterLog infer_instance /-- Lexicographic comparison of letter-logs by content and then identifier is decidable. -/ instance instDecidableLetterLogLe (a b : String) : Decidable (LetterLogLe a b) := by unfold LetterLogLe infer_instance /-- Executable checker obtained mechanically from the specification. -/ def reorderLogs_check (input : Input) (result : Output) : Bool := @decide (reorderLogs_spec input result) (by unfold reorderLogs_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem reorderLogs_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : reorderLogs_check input result ↔ reorderLogs_spec input result := by simp [reorderLogs_check] /-! ### Implementation helpers -/ /-- One pass splitting logs into letter-logs and digit-logs, each block keeping its input order. -/ def partitionLogs : List String → List String × List String | [] => ([], []) | log :: rest => let (letters, digits) := partitionLogs rest if IsLetterLog log then (log :: letters, digits) else if IsDigitLog log then (letters, log :: digits) else (letters, digits) /-- Merge sort of the letter-log block by the specification's content-then-identifier order. -/ def sortLetterLogs (letters : List String) : List String := letters.mergeSort fun a b => decide (LetterLogLe a b) /-! ### Main algorithm (impl) -/ /-- Stable partition into letter-logs and digit-logs, sorting only the letter-logs, in O(n log n · L). -/ def reorderLogFiles (input : Input) : Output := let (letters, digits) := partitionLogs input sortLetterLogs letters ++ digits /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem reorderLogFiles_correct (input : Input) (h : isValidInput input) : reorderLogs_spec input (reorderLogFiles input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"] #guard isValidInput ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"] #guard isValidInput ["z9 2 3 4", "b2 run let", "a1 1 2 3", "x3 jump high", "y8 run let"] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput ["a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1", "a 1"]) #guard !(isValidInput ["a1 b"]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard reorderLogs_check ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"] ["let1 art can", "let3 art zero", "let2 own kit dig", "dig1 8 1 5 1", "dig2 3 6"] #guard reorderLogs_check ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"] ["g1 act car", "a8 act zoo", "ab1 off key dog", "a1 9 2 3 1", "zo4 4 7"] #guard reorderLogs_check ["z9 2 3 4", "b2 run let", "a1 1 2 3", "x3 jump high", "y8 run let"] ["x3 jump high", "b2 run let", "y8 run let", "z9 2 3 4", "a1 1 2 3"] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(reorderLogs_check ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"] ["let1 art can", "let3 art zero", "let2 own kit dig", "dig2 3 6", "dig1 8 1 5 1"]) #guard !(reorderLogs_check ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"] ["a1 9 2 3 1", "zo4 4 7", "g1 act car", "a8 act zoo", "ab1 off key dog"]) #guard !(reorderLogs_check ["z9 2 3 4", "b2 run let", "a1 1 2 3", "x3 jump high", "y8 run let"] []) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard reorderLogFiles ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"] == ["let1 art can", "let3 art zero", "let2 own kit dig", "dig1 8 1 5 1", "dig2 3 6"] #guard reorderLogFiles ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"] == ["g1 act car", "a8 act zoo", "ab1 off key dog", "a1 9 2 3 1", "zo4 4 7"] #guard reorderLogFiles ["z9 2 3 4", "b2 run let", "a1 1 2 3", "x3 jump high", "y8 run let"] == ["x3 jump high", "b2 run let", "y8 run let", "z9 2 3 4", "a1 1 2 3"] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard reorderLogs_check ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"] (reorderLogFiles ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]) #guard reorderLogs_check ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"] (reorderLogFiles ["a1 9 2 3 1", "g1 act car", "zo4 4 7", "ab1 off key dog", "a8 act zoo"]) #guard reorderLogs_check ["z9 2 3 4", "b2 run let", "a1 1 2 3", "x3 jump high", "y8 run let"] (reorderLogFiles ["z9 2 3 4", "b2 run let", "a1 1 2 3", "x3 jump high", "y8 run let"]) end PReorderDataInLogFiles