import Mathlib /-! # Invalid Transactions A transaction is possibly invalid if: the amount exceeds $1000, or; if it occurs within (and including) 60 minutes of another transaction with the same name in a different city. You are given an array of strings transactions where transactions[i] consists of comma-separated values representing the name, time (in minutes), amount, and city of the transaction. Return a list of transactions that are possibly invalid. You may return the answer in any order. ## Constraints - transactions.length <= 1000 - Each transactions[i] takes the form "{name},{time},{amount},{city}" - Each {name} and {city} consist of lowercase English letters, and have lengths between 1 and 10. - Each {time} consist of digits, and represent an integer between 0 and 1000. - Each {amount} consist of digits, and represent an integer between 0 and 2000. ## Provided examples - `transactions = ["alice,20,800,mtv", "alice,50,100,beijing"]` → `["alice,20,800,mtv", "alice,50,100,beijing"]` - `transactions = ["alice,20,800,mtv", "alice,50,1200,mtv"]` → `["alice,50,1200,mtv"]` - `transactions = ["alice,20,800,mtv", "bob,50,1200,mtv"]` → `["bob,50,1200,mtv"]` ## Synthesized negative examples - invalid input: `transactions = ["alice,20,100"]` ([structural] a predicate that admits Each transactions[i] takes the form "{name},{time},{amount},{city}". missing city field; a predicate that parses only first three fields accepts) - invalid input: `transactions = ["Alice,20,100,mtv"]` ([structural] a predicate that admits Each {name} and {city} consist of lowercase English letters, and have lengths between 1 and 10.. uppercase name; a predicate checking only time and amount accepts) - invalid input: `transactions = ["alice,1001,100,mtv"]` ([structural] a predicate that admits Each {time} consist of digits, and represent an integer between 0 and 1000.. time 1001; a predicate that skips the time ceiling accepts) - `transactions = ["alice,20,800,mtv", "alice,50,100,beijing"]` → `[]` is wrong ([structural] no requirement to include every invalid transaction. empty list is sound but omits both invalid transactions) - `transactions = ["alice,20,800,mtv", "alice,50,1200,mtv"]` → `[]` is wrong ([structural] completeness is not required; empty list passes a soundness-only spec. missing the only invalid transaction) - `transactions = ["alice,20,800,mtv", "bob,50,1200,mtv"]` → `["alice,20,800,mtv", "bob,50,1200,mtv"]` is wrong ([structural] returned transactions are not all required to be invalid. valid alice is included; accepted if only invalid transactions need to appear) -/ namespace PInvalidTransactions abbrev Input := List String abbrev Output := List String /-! ### Specification helpers -/ /-- Folds `cs` into comma-separated fields, keeping empty fields, with the current field in `cur` and finished fields reversed in `acc`. -/ def splitCommasGo : List Char → String → List String → List String | [], cur, acc => (cur :: acc).reverse | ',' :: cs, cur, acc => splitCommasGo cs "" (cur :: acc) | c :: cs, cur, acc => splitCommasGo cs (cur.push c) acc /-- The comma-separated fields of `s`, empty fields preserved. -/ def commaFields (s : String) : List String := splitCommasGo s.toList "" [] /-- The name field of `t`, or `""` when `t` has no first field. -/ def txnName (t : String) : String := (commaFields t)[0]?.getD "" /-- The time field of `t` as a natural number, or `0` when absent or non-numeric. -/ def txnTime (t : String) : Nat := (((commaFields t)[1]?.getD "").toNat?).getD 0 /-- The amount field of `t` as a natural number, or `0` when absent or non-numeric. -/ def txnAmount (t : String) : Nat := (((commaFields t)[2]?.getD "").toNat?).getD 0 /-- The city field of `t`, or `""` when `t` has no fourth field. -/ def txnCity (t : String) : String := (commaFields t)[3]?.getD "" /-- `t` is a member of `ts` and is possibly invalid: its amount exceeds 1000, or some other member of `ts` has the same name, a different city, and a time within 60 minutes. -/ def IsInvalidTransaction (ts : List String) (t : String) : Prop := t ∈ ts ∧ (txnAmount t > 1000 ∨ ∃ u ∈ ts, (u ≠ t ∨ 2 ≤ ts.count u) ∧ txnName u = txnName t ∧ txnCity u ≠ txnCity t ∧ Nat.dist (txnTime u) (txnTime t) ≤ 60) /-- `s` is a nonempty string of at most ten lowercase English letters. -/ def isNameWord (s : String) : Bool := 0 < s.length && s.length ≤ 10 && s.toList.all (fun c => 'a' ≤ c && c ≤ 'z') /-- `s` is a nonempty all-digit string whose value is at most `bound`. -/ def isBoundedNat (bound : Nat) (s : String) : Bool := 0 < s.length && s.toList.all (fun c => '0' ≤ c && c ≤ '9') && (s.toNat?).getD (bound + 1) ≤ bound /-- `t` is a four-field record with lowercase name and city of length at most 10, time at most 1000, and amount at most 2000. -/ def validTxnString (t : String) : Bool := match commaFields t with | [name, time, amount, city] => isNameWord name && isNameWord city && isBoundedNat 1000 time && isBoundedNat 2000 amount | _ => false /-! ### Validity predicate (V) -/ /-- Valid input: at most 1000 transactions, each a well-formed four-field transaction record. -/ def isValidInput (input : Input) : Bool := input.length ≤ 1000 && input.all validTxnString /-! ### Ideal specification (P_spec) -/ /-- `result` lists exactly the possibly-invalid transactions of `input`: every element is invalid, and every invalid string occurs in `result` exactly as many times as in `input`. -/ def invalidTransactions_spec (input : Input) (result : Output) : Prop := (∀ t ∈ result, IsInvalidTransaction input t) ∧ ∀ t : String, IsInvalidTransaction input t → result.count t = input.count t /-! ### Decidable specification (P_check) -/ /-- Decide the helper predicate by unfolding it into bounded list membership and bounded list existential over the transaction list. -/ instance (ts : List String) (t : String) : Decidable (IsInvalidTransaction ts t) := by unfold IsInvalidTransaction infer_instance /-- Decide the unfolded specification: the unbounded string quantifier is equivalent to the bounded quantifier over `input`, because `IsInvalidTransaction input t` already includes `t ∈ input`. -/ instance (input result : List String) : Decidable ((∀ t ∈ result, IsInvalidTransaction input t) ∧ ∀ t : String, IsInvalidTransaction input t → result.count t = input.count t) := decidable_of_iff ((∀ t ∈ result, IsInvalidTransaction input t) ∧ ∀ t ∈ input, IsInvalidTransaction input t → result.count t = input.count t) (by constructor · rintro ⟨hres, hin⟩ refine ⟨hres, fun t ht => ?_⟩ have hmem : t ∈ input := by unfold IsInvalidTransaction at ht exact ht.1 exact hin t hmem ht · rintro ⟨hres, hall⟩ exact ⟨hres, fun t _ ht => hall t ht⟩) /-- Executable checker obtained mechanically from the specification. -/ def invalidTransactions_check (input : Input) (result : Output) : Bool := @decide (invalidTransactions_spec input result) (by unfold invalidTransactions_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem invalidTransactions_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : invalidTransactions_check input result ↔ invalidTransactions_spec input result := by simp [invalidTransactions_check] /-! ### Implementation helpers -/ /-- Whether `t` is invalid by amount or by a same-name different-city nearby-time transaction in `ts`. -/ def isInvalidTxn (ts : List String) (t : String) : Bool := decide (txnAmount t > 1000) || ts.any (fun u => txnName u == txnName t && txnCity u != txnCity t && decide (Nat.dist (txnTime u) (txnTime t) ≤ 60)) /-! ### Main algorithm (impl) -/ /-- Filter the input to transactions invalid by amount or by a same-name different-city nearby-time pair. -/ def findInvalidTransactions (input : Input) : Output := input.filter (fun t => isInvalidTxn input t) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findInvalidTransactions_correct (input : Input) (h : isValidInput input) : invalidTransactions_spec input (findInvalidTransactions input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ["alice,20,800,mtv", "alice,50,100,beijing"] #guard isValidInput ["alice,20,800,mtv", "alice,50,1200,mtv"] #guard isValidInput ["alice,20,800,mtv", "bob,50,1200,mtv"] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ["alice,20,100"]) #guard !(isValidInput ["Alice,20,100,mtv"]) #guard !(isValidInput ["alice,1001,100,mtv"]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard invalidTransactions_check ["alice,20,800,mtv", "alice,50,100,beijing"] ["alice,20,800,mtv", "alice,50,100,beijing"] #guard invalidTransactions_check ["alice,20,800,mtv", "alice,50,1200,mtv"] ["alice,50,1200,mtv"] #guard invalidTransactions_check ["alice,20,800,mtv", "bob,50,1200,mtv"] ["bob,50,1200,mtv"] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(invalidTransactions_check ["alice,20,800,mtv", "alice,50,100,beijing"] []) #guard !(invalidTransactions_check ["alice,20,800,mtv", "alice,50,1200,mtv"] []) #guard !(invalidTransactions_check ["alice,20,800,mtv", "bob,50,1200,mtv"] ["alice,20,800,mtv", "bob,50,1200,mtv"]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findInvalidTransactions ["alice,20,800,mtv", "alice,50,100,beijing"] == ["alice,20,800,mtv", "alice,50,100,beijing"] #guard findInvalidTransactions ["alice,20,800,mtv", "alice,50,1200,mtv"] == ["alice,50,1200,mtv"] #guard findInvalidTransactions ["alice,20,800,mtv", "bob,50,1200,mtv"] == ["bob,50,1200,mtv"] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard invalidTransactions_check ["alice,20,800,mtv", "alice,50,100,beijing"] (findInvalidTransactions ["alice,20,800,mtv", "alice,50,100,beijing"]) #guard invalidTransactions_check ["alice,20,800,mtv", "alice,50,1200,mtv"] (findInvalidTransactions ["alice,20,800,mtv", "alice,50,1200,mtv"]) #guard invalidTransactions_check ["alice,20,800,mtv", "bob,50,1200,mtv"] (findInvalidTransactions ["alice,20,800,mtv", "bob,50,1200,mtv"]) end PInvalidTransactions