import Mathlib /-! # Exclusive Time Of Functions On a single-threaded CPU, we execute a program containing n functions. Each function has a unique ID between 0 and n-1. Function calls are stored in a call stack: when a function call starts, its ID is pushed onto the stack, and when a function call ends, its ID is popped off the stack. The function whose ID is at the top of the stack is the current function being executed. Each time a function starts or ends, we write a log with the ID, whether it started or ended, and the timestamp. You are given a list logs, where logs[i] represents the ith log message formatted as a string "{function_id}:{"start" | "end"}:{timestamp}". For example, "0:start:3" means a function call with function ID 0 started at the beginning of timestamp 3, and "1:end:2" means a function call with function ID 1 ended at the end of timestamp 2. Note that a function can be called multiple times, possibly recursively. A function's exclusive time is the total time spent executing that function across all its calls, excluding time spent in other functions called from it. For example, if a function is called twice, one call executing for 2 time units and another call executing for 1 time unit, the exclusive time is 2 + 1 = 3. Return the exclusive time of each function in an array, where the value at the ith index represents the exclusive time for the function with ID i. ## Constraints - 1 <= n <= 100 - 1 <= logs.length <= 500 - 0 <= function_id < n - 0 <= timestamp <= 10^9 - No two start events will happen at the same timestamp. - No two end events will happen at the same timestamp. - Each function has an "end" log for each "start" log. ## Provided examples - `n = 2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]` → `[3, 4]` - `n = 1, logs = ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]` → `[8]` - `n = 2, logs = ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]` → `[7, 1]` ## Synthesized negative examples - invalid input: `n = 101, logs = ["0:start:0", "0:end:1"]` ([structural] a predicate that admits 1 <= n <= 100. one past the maximum n) - invalid input: `n = 1, logs = []` ([structural] a predicate that admits 1 <= logs.length <= 500. empty log list where at least one is required) - invalid input: `n = 2, logs = ["0:start:0", "1:start:0", "0:end:1", "1:end:2"]` ([structural] a predicate that admits No two start events will happen at the same timestamp.. two starts at the same timestamp; skips start-time uniqueness) - `n = 2, logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]` → `[3, 3]` is wrong ([structural] end timestamp treated as exclusive rather than inclusive. function 1's interval counted as 2..4 instead of 2..5) - `n = 1, logs = ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]` → `[7]` is wrong ([structural] end timestamps are treated as exclusive, losing one unit per end. forgets an end event covers its whole timestamp) - `n = 2, logs = ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]` → `[8, 1]` is wrong ([structural] exclusive time defined as whole span from first start to last end. id 0 counted from 0 to 7) -/ namespace PExclusiveTimeOfFunctions abbrev Input := (Nat) × (List String) abbrev Output := List Nat /-! ### Specification helpers -/ /-- Parse a log of the form `id:label:timestamp` into its ID, start flag, and timestamp. -/ def parseLog (l : String) : Option (Nat × Bool × Nat) := match l.splitOn ":" with | [a, b, c] => match a.toNat?, c.toNat? with | some id, some ts => if b == "start" then some (id, true, ts) else if b == "end" then some (id, false, ts) else none | _, _ => none | _ => none /-- One call-stack scan step: a start pushes its call, an end closes the top call's interval. -/ def intervalStep (state : List (Nat × Nat) × List (Nat × Nat × Nat)) (l : String) : List (Nat × Nat) × List (Nat × Nat × Nat) := match parseLog l with | some (id, true, ts) => ((id, ts) :: state.1, state.2) | some (_, false, ts) => match state.1 with | (g, s) :: rest => (rest, (g, s, ts) :: state.2) | [] => state | none => state /-- The call intervals `⟨id, start, end⟩` closed by the logs, in order of closing. -/ def intervalsFromLogs (logs : List String) : List (Nat × Nat × Nat) := (logs.foldl intervalStep ([], [])).2 /-- Function `i` tops the call stack at unit `t`: its innermost active interval covers `t`. -/ def IsCurrentFunctionAt (_n : Nat) (logs : List String) (t : Nat) (i : Nat) : Prop := ∃ s e : Nat, (i, s, e) ∈ intervalsFromLogs logs ∧ s ≤ t ∧ t ≤ e ∧ ∀ g s' e' : Nat, (g, s', e') ∈ intervalsFromLogs logs → s' ≤ t → t ≤ e' → s' ≤ s /-- The timestamps of the events of the given kind, in log order. -/ def eventTimes (evs : List (Nat × Bool × Nat)) (isStart : Bool) : List Nat := (evs.filter fun e => e.2.1 == isStart).map fun e => e.2.2 /-- Whether the list has no duplicate entries. -/ def nodupList (l : List Nat) : Bool := l.eraseDup.length == l.length /-- Timestamps never decrease, and at a shared timestamp a start precedes an end. -/ def chronological (evs : List (Nat × Bool × Nat)) : Bool := (evs.zip evs.tail).all fun p => p.1.2.2 ≤ p.2.2.2 && (!(p.1.2.2 == p.2.2.2) || p.1.2.1) /-- One call-stack step: a start pushes its ID, an end pops the top only if it matches. -/ def callStackStep (st : Option (List Nat)) (e : Nat × Bool × Nat) : Option (List Nat) := match st with | none => none | some stack => if e.2.1 then some (e.1 :: stack) else match stack with | g :: rest => if g == e.1 then some rest else none | [] => none /-- The parsed events form a balanced call stack whose ends pop the named IDs. -/ def callStackValid (evs : List (Nat × Bool × Nat)) : Bool := match evs.foldl callStackStep (some []) with | some [] => true | _ => false /-- Boolean form of the event-level validity clauses over parsed logs. -/ def validEvents (n : Nat) (evs : List (Nat × Bool × Nat)) : Bool := evs.all (fun e => e.1 < n && e.2.2 ≤ 1000000000) && chronological evs && nodupList (eventTimes evs true) && nodupList (eventTimes evs false) && callStackValid evs /-! ### Validity predicate (V) -/ /-- Valid input: `n` and the log count in range, and logs forming a well-formed call stack. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1 && input.1 ≤ 100 && 1 ≤ input.2.length && input.2.length ≤ 500 && (match input.2.mapM parseLog with | none => false | some evs => validEvents input.1 evs) /-! ### Ideal specification (P_spec) -/ /-- `result` credits each function with exactly the time units it tops the call stack. -/ def exclusiveTimes_spec (input : Input) (result : Output) : Prop := result.length = input.1 ∧ ∀ i : Nat, i < input.1 → ∃ S : Finset Nat, S.card = result.getD i 0 ∧ ∀ t : Nat, t ∈ S ↔ IsCurrentFunctionAt input.1 input.2 t i /-! ### Decidable specification (P_check) -/ /-- Decides the current-function predicate by bounding both the interval search and the innermost-interval check to the finitely many intervals closed by the logs. -/ instance decIsCurrentFunctionAt (n : Nat) (logs : List String) (t i : Nat) : Decidable (IsCurrentFunctionAt n logs t i) := decidable_of_iff (∃ x ∈ intervalsFromLogs logs, x.1 = i ∧ x.2.1 ≤ t ∧ t ≤ x.2.2 ∧ ∀ y ∈ intervalsFromLogs logs, y.2.1 ≤ t → t ≤ y.2.2 → y.2.1 ≤ x.2.1) (by unfold IsCurrentFunctionAt constructor · intro h rcases h with ⟨x, hx, hxi, hs, he, hmax⟩ have hxe : x = (x.1, x.2.1, x.2.2) := rfl rw [hxi] at hxe refine ⟨x.2.1, x.2.2, ?_, hs, he, ?_⟩ · rwa [hxe] at hx · intro g' s' e' hmem hs' he' exact hmax (g', s', e') hmem hs' he' · intro h rcases h with ⟨s, e, hmem, hs, he, hmax⟩ refine ⟨(i, s, e), hmem, rfl, hs, he, ?_⟩ intro y hy hsy hey rcases y with ⟨g, s', e'⟩ exact hmax g s' e' hy hsy hey) /-- Decides the unfolded specification by using, for each function, the unique finite set obtained by filtering all logged interval times with the current-function predicate. -/ instance decExclusiveTimesSpec (input : Input) (result : Output) : Decidable (result.length = input.1 ∧ ∀ i : Nat, i < input.1 → ∃ S : Finset Nat, S.card = result.getD i 0 ∧ ∀ t : Nat, t ∈ S ↔ IsCurrentFunctionAt input.1 input.2 t i) := by let C : Nat → Finset Nat := fun i => ((intervalsFromLogs input.2).toFinset.biUnion fun x => Finset.Icc x.2.1 x.2.2).filter fun t => IsCurrentFunctionAt input.1 input.2 t i exact decidable_of_iff (result.length = input.1 ∧ ∀ i < input.1, (C i).card = result.getD i 0) (by have hC : ∀ i t, t ∈ C i ↔ IsCurrentFunctionAt input.1 input.2 t i := by intro i t dsimp [C] constructor · intro ht exact (Finset.mem_filter.mp ht).2 · intro ht apply Finset.mem_filter.mpr constructor · rcases ht with ⟨s, e, hmem, hst, hte, _hmax⟩ rw [Finset.mem_biUnion] exact ⟨(i, s, e), by simpa using hmem, Finset.mem_Icc.mpr ⟨hst, hte⟩⟩ · exact ht have key : ∀ i, (∃ S : Finset Nat, S.card = result.getD i 0 ∧ ∀ t : Nat, t ∈ S ↔ IsCurrentFunctionAt input.1 input.2 t i) ↔ (C i).card = result.getD i 0 := by intro i constructor · intro h rcases h with ⟨S, hcard, hS⟩ have hSC : S = C i := by apply Finset.ext intro t exact Iff.trans (hS t) (hC i t).symm simpa [hSC] using hcard · intro h exact ⟨C i, h, fun t => hC i t⟩ constructor · intro h exact ⟨h.1, fun i hi => (key i).mpr (h.2 i hi)⟩ · intro h exact ⟨h.1, fun i hi => (key i).mp (h.2 i hi)⟩) /-- Executable checker obtained mechanically from the specification. -/ def exclusiveTimes_check (input : Input) (result : Output) : Bool := @decide (exclusiveTimes_spec input result) (by unfold exclusiveTimes_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem exclusiveTimes_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : exclusiveTimes_check input result ↔ exclusiveTimes_spec input result := by simp [exclusiveTimes_check] /-! ### Implementation helpers -/ /-- One simulation step: parse one log and update the stack, previous timestamp, and totals. -/ def applyLog (state : List Nat × Nat × (Nat → Nat)) (l : String) : List Nat × Nat × (Nat → Nat) := match parseLog l with | some (id, true, ts) => let totals := match state.1 with | [] => state.2.2 | top :: _ => Function.update state.2.2 top (state.2.2 top + (ts - state.2.1)) (id :: state.1, ts, totals) | some (_, false, ts) => match state.1 with | top :: rest => (rest, ts + 1, Function.update state.2.2 top (state.2.2 top + (ts - state.2.1 + 1))) | [] => state | none => state /-- Project the final totals at IDs `0` through `n-1` into the output list. -/ def finalizeList (n : Nat) (f : Nat → Nat) : List Nat := (List.range n).map f /-! ### Main algorithm (impl) -/ /-- Exclusive times by a single-pass call-stack simulation crediting elapsed time to the top ID. -/ def computeExclusiveTimes (input : Input) : Output := let st := input.2.foldl applyLog ([], 0, fun _ => 0) finalizeList input.1 st.2.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem computeExclusiveTimes_correct (input : Input) (h : isValidInput input) : exclusiveTimes_spec input (computeExclusiveTimes input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]) #guard isValidInput (1, ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]) #guard isValidInput (2, ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (101, ["0:start:0", "0:end:1"])) #guard !(isValidInput (1, [])) #guard !(isValidInput (2, ["0:start:0", "1:start:0", "0:end:1", "1:end:2"])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard exclusiveTimes_check (2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]) [3, 4] #guard exclusiveTimes_check (1, ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]) [8] #guard exclusiveTimes_check (2, ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]) [7, 1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(exclusiveTimes_check (2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]) [3, 3]) #guard !(exclusiveTimes_check (1, ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]) [7]) #guard !(exclusiveTimes_check (2, ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]) [8, 1]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard computeExclusiveTimes (2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]) == [3, 4] #guard computeExclusiveTimes (1, ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]) == [8] #guard computeExclusiveTimes (2, ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]) == [7, 1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard exclusiveTimes_check (2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]) (computeExclusiveTimes (2, ["0:start:0", "1:start:2", "1:end:5", "0:end:6"])) #guard exclusiveTimes_check (1, ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"]) (computeExclusiveTimes (1, ["0:start:0", "0:start:2", "0:end:5", "0:start:6", "0:end:6", "0:end:7"])) #guard exclusiveTimes_check (2, ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]) (computeExclusiveTimes (2, ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"])) end PExclusiveTimeOfFunctions