import Mathlib /-! # Evaluate Division You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A_i, B_i] and values[i] represent the equation A_i / B_i = values[i]. Each A_i or B_i is a string that represents a single variable. You are also given some queries, where queries[j] = [C_j, D_j] represents the jth query where you must find the answer for C_j / D_j = ?. Return the answers to all queries. If a single answer cannot be determined, return -1.0. Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction. Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them. ## Constraints - 1 <= equations.length <= 20 - equations[i].length == 2 - 1 <= A_i.length, B_i.length <= 5 - values.length == equations.length - 0.0 < values[i] <= 20.0 - 1 <= queries.length <= 20 - queries[i].length == 2 - 1 <= C_j.length, D_j.length <= 5 - A_i, B_i, C_j, D_j consist of lower case English letters and digits. ## Provided examples - `equations = [["a", "b"], ["b", "c"]], values = [2.0, 3.0], queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]` → `[6.0, 0.5, -1.0, 1.0, -1.0]` - `equations = [["a", "b"], ["b", "c"], ["bc", "cd"]], values = [1.5, 2.5, 5.0], queries = [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]]` → `[3.75, 0.4, 5.0, 0.2]` - `equations = [["a", "b"]], values = [0.5], queries = [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]]` → `[0.5, 2.0, -1.0, -1.0]` ## Synthesized negative examples - invalid input: `equations = [], values = [], queries = [["a", "b"]]` ([structural] a predicate that admits 1 <= equations.length <= 20. no equations; a predicate checking only queries accepts it) - invalid input: `equations = [["a"]], values = [1.0], queries = [["a", "a"]]` ([structural] a predicate that admits equations[i].length == 2. pair of length one; a predicate checking only the first variable accepts it) - invalid input: `equations = [["abcdef", "b"]], values = [1.0], queries = [["a", "a"]]` ([structural] a predicate that admits 1 <= Ai.length, Bi.length <= 5. variable length six, one past the maximum; a predicate checking only nonempty accepts it) - `equations = [["a", "b"], ["b", "c"]], values = [2.0, 3.0], queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]` → `[5.0, 0.5, -1.0, 1.0, -1.0]` is wrong ([structural] Exact ratio for each query is not required. a/c is 5.0 instead of 6.0) - `equations = [["a", "b"], ["b", "c"], ["bc", "cd"]], values = [1.5, 2.5, 5.0], queries = [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]]` → `[-1.0, 0.4, 5.0, 0.2]` is wrong ([structural] not_optimal inapplicable; chain inference is not required. a/c needs chain a/b times b/c; only direct lookup done) - `equations = [["a", "b"]], values = [0.5], queries = [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]]` → `[0.5, -1.0, -1.0, -1.0]` is wrong ([structural] reverse division not handled; only exact equation pairs are used. b/a should be 2.0, but is -1.0) -/ namespace PEvaluateDivision abbrev Input := (List (List String)) × (List Rat) × (List (List String)) abbrev Output := List Rat /-! ### Specification helpers -/ /-- `x` appears among the variables of the equations. -/ def occursIn (eqs : List (List String)) (x : String) : Prop := ∃ e ∈ eqs, x ∈ e /-- `r` is the quotient `x / y` forced by the equations: a chain from `x` to `y` of equations used forward or backward whose values multiply to `r`, with the empty chain giving `1` when `x` occurs. -/ inductive RatioFromEquations (eqs : List (List String)) (vals : List Rat) : String → String → Rat → Prop where | refl {x : String} (h : occursIn eqs x) : RatioFromEquations eqs vals x x 1 | forward {x y z : String} {r w : Rat} (h : RatioFromEquations eqs vals x y r) (hw : ([y, z], w) ∈ eqs.zip vals) : RatioFromEquations eqs vals x z (r * w) | backward {x y z : String} {r w : Rat} (h : RatioFromEquations eqs vals x y r) (hw : ([z, y], w) ∈ eqs.zip vals) : RatioFromEquations eqs vals x z (r * w⁻¹) /-- A variable name is one to five lowercase letters or digits. -/ def validVar (s : String) : Bool := 1 ≤ s.length && s.length ≤ 5 && s.toList.all (fun c => ('a' ≤ c && c ≤ 'z') || ('0' ≤ c && c ≤ '9')) /-- The value currently assigned to `x`, if any. -/ def lookupValue (asg : List (String × Rat)) (x : String) : Option Rat := (asg.find? fun p => p.1 == x).map Prod.snd /-- One pass over the equations, extending the assignment or failing on a violated equation. -/ def propagate (eqs : List (List String)) (vals : List Rat) (asg : List (String × Rat)) : Except Unit (List (String × Rat)) := List.foldl (fun acc ev => match acc with | .error u => .error u | .ok m => match ev.1 with | [a, b] => match lookupValue m a, lookupValue m b with | some va, some vb => if va == ev.2 * vb then .ok m else .error () | some va, none => .ok ((b, va / ev.2) :: m) | none, some vb => .ok ((a, ev.2 * vb) :: m) | none, none => .ok m | _ => .ok m) (.ok asg) (eqs.zip vals) /-- Close the assignment under repeated propagation, at most `fuel` passes. -/ def closeValues (fuel : Nat) (eqs : List (List String)) (vals : List Rat) (asg : List (String × Rat)) : Except Unit (List (String × Rat)) := match fuel with | 0 => .ok asg | n + 1 => match propagate eqs vals asg with | .error u => .error u | .ok asg' => if asg'.length == asg.length then .ok asg' else closeValues n eqs vals asg' /-- Seed each still-unassigned variable with `1` and verify propagation never violates an equation. -/ def consistentLoop (fuel : Nat) (vars : List String) (eqs : List (List String)) (vals : List Rat) (asg : List (String × Rat)) : Bool := match fuel with | 0 => true | n + 1 => match closeValues (vars.length + 1) eqs vals asg with | .error _ => false | .ok asg' => match vars.find? (fun x => (lookupValue asg' x).isNone) with | none => true | some x => consistentLoop n vars eqs vals ((x, 1) :: asg') /-- No contradiction: seeding every component with an arbitrary value never violates an equation. -/ def noContradiction (eqs : List (List String)) (vals : List Rat) : Bool := let vars := eqs.flatten.eraseDups consistentLoop (vars.length + 1) vars eqs vals [] /-! ### Validity predicate (V) -/ /-- Valid input: the stated bounds on equations, values, and queries, with consistent equations. -/ def isValidInput (input : Input) : Bool := match input with | (eqs, vals, qs) => 1 ≤ eqs.length && eqs.length ≤ 20 && eqs.all (fun e => e.length == 2) && eqs.flatten.all validVar && vals.length == eqs.length && vals.all (fun v => 0 < v && v ≤ 20) && 1 ≤ qs.length && qs.length ≤ 20 && qs.all (fun q => q.length == 2) && qs.flatten.all validVar && noContradiction eqs vals /-! ### Ideal specification (P_spec) -/ /-- `result` has one entry per query: the ratio the equations force for that query, or `-1` when they force none. -/ def evaluateDivision_spec (input : Input) (result : Output) : Prop := match input with | (eqs, vals, qs) => result.length = qs.length ∧ ∀ j (hj : j < qs.length) (C D : String), qs[j] = [C, D] → (∀ r : Rat, RatioFromEquations eqs vals C D r → result[j]? = some r) ∧ (¬ (∃ r : Rat, RatioFromEquations eqs vals C D r) → result[j]? = some (-1)) /-! ### Decidable specification (P_check) -/ /-- The variables appearing anywhere in the equation list, without duplicates. -/ def eqVars (eqs : List (List String)) : List String := eqs.flatten.eraseDups /-- The quotient `C / D` forced by closing the equations from the seed `D = 1`, if any. -/ def forcedRatio (eqs : List (List String)) (vals : List Rat) (C D : String) : Option Rat := let vars := eqVars eqs if vars.any (fun x => x == D) then match closeValues (vars.length + 1) eqs vals [(D, 1)] with | .ok asg => lookupValue asg C | .error _ => none else none /-- Executable checker for `evaluateDivision_spec` by querywise closure of the equation graph. -/ def evaluateDivision_check (input : Input) (result : Output) : Bool := match input with | (eqs, vals, qs) => result.length == qs.length && (List.finRange qs.length).all fun j => match qs.get j with | [C, D] => (match forcedRatio eqs vals C D with | some r => result[j.val]? == some r | none => result[j.val]? == some (-1)) | _ => true theorem occursIn_of_mem {eqs : List (List String)} {e : List String} {x : String} (he : e ∈ eqs) (hx : x ∈ e) : occursIn eqs x := by unfold occursIn exact ⟨e, he, hx⟩ theorem ratio_congr {eqs : List (List String)} {vals : List Rat} {x y : String} {r r' : Rat} (h : RatioFromEquations eqs vals x y r) (e : r = r') : RatioFromEquations eqs vals x y r' := e ▸ h theorem ratio_trans {eqs : List (List String)} {vals : List Rat} {x y z : String} {r s : Rat} (h1 : RatioFromEquations eqs vals x y r) (h2 : RatioFromEquations eqs vals y z s) : RatioFromEquations eqs vals x z (r * s) := by revert h1 induction h2 with | refl _ => intro h1; exact ratio_congr h1 (mul_one r).symm | forward _ hw ih => intro h1; exact ratio_congr (RatioFromEquations.forward (ih h1) hw) (mul_assoc _ _ _) | backward _ hw ih => intro h1; exact ratio_congr (RatioFromEquations.backward (ih h1) hw) (mul_assoc _ _ _) theorem ratio_occurs {eqs : List (List String)} {vals : List Rat} {x y : String} {r : Rat} (h : RatioFromEquations eqs vals x y r) : occursIn eqs x ∧ occursIn eqs y := by induction h with | refl h => exact ⟨h, h⟩ | forward _ hw ih => exact ⟨ih.1, occursIn_of_mem (List.of_mem_zip hw).1 (by simp)⟩ | backward _ hw ih => exact ⟨ih.1, occursIn_of_mem (List.of_mem_zip hw).1 (by simp)⟩ theorem ratio_edge_fwd {eqs : List (List String)} {vals : List Rat} {a b : String} {w : Rat} (hw : ([a, b], w) ∈ eqs.zip vals) : RatioFromEquations eqs vals a b w := by have h0 : RatioFromEquations eqs vals a a 1 := RatioFromEquations.refl (occursIn_of_mem (List.of_mem_zip hw).1 (by simp)) exact ratio_congr (RatioFromEquations.forward h0 hw) (one_mul w) theorem ratio_edge_bwd {eqs : List (List String)} {vals : List Rat} {a b : String} {w : Rat} (hw : ([a, b], w) ∈ eqs.zip vals) : RatioFromEquations eqs vals b a w⁻¹ := by have h0 : RatioFromEquations eqs vals b b 1 := RatioFromEquations.refl (occursIn_of_mem (List.of_mem_zip hw).1 (by simp)) exact ratio_congr (RatioFromEquations.backward h0 hw) (one_mul w⁻¹) theorem lookup_mem {m : List (String × Rat)} {x : String} {v : Rat} (h : lookupValue m x = some v) : (x, v) ∈ m := by unfold lookupValue at h cases hf : m.find? (fun p => p.1 == x) with | none => simp [hf] at h | some p => have hp : p.1 = x := by simpa using List.find?_some hf have hv : p.2 = v := by simpa [hf] using h have hm := List.mem_of_find?_eq_some hf rw [← hp, ← hv] exact hm theorem lookup_isSome_of_mem {m : List (String × Rat)} {x : String} {v : Rat} (h : (x, v) ∈ m) : (lookupValue m x).isSome := by unfold lookupValue rw [Option.isSome_map, List.find?_isSome] exact ⟨(x, v), h, by simp⟩ theorem lookup_none {m : List (String × Rat)} {x : String} (h : lookupValue m x = none) : x ∉ m.map Prod.fst := by intro hx obtain ⟨p, hp, hpx⟩ := List.mem_map.mp hx have hs := lookup_isSome_of_mem (m := m) (x := p.1) (v := p.2) hp rw [hpx, h] at hs simp at hs def pstep (acc : Except Unit (List (String × Rat))) (ev : List String × Rat) : Except Unit (List (String × Rat)) := match acc with | .error u => .error u | .ok m => match ev.1 with | [a, b] => match lookupValue m a, lookupValue m b with | some va, some vb => if va == ev.2 * vb then .ok m else .error () | some va, none => .ok ((b, va / ev.2) :: m) | none, some vb => .ok ((a, ev.2 * vb) :: m) | none, none => .ok m | _ => .ok m abbrev Good (S : String → Prop) (Q : String → Rat → Prop) (m : List (String × Rat)) : Prop := (m.map Prod.fst).Nodup ∧ ∀ p ∈ m, S p.1 ∧ Q p.1 p.2 theorem good_weaken {S : String → Prop} {Q : String → Rat → Prop} {m : List (String × Rat)} (hg : Good S Q m) : Good S (fun _ _ => True) m := ⟨hg.1, fun p hp => ⟨(hg.2 p hp).1, trivial⟩⟩ theorem good_length_le (vars : List String) (Q : String → Rat → Prop) (m : List (String × Rat)) (hg : Good (· ∈ vars) Q m) : m.length ≤ vars.length := by have hsub : m.map Prod.fst ⊆ vars := by intro x hx obtain ⟨p, hp, rfl⟩ := List.mem_map.mp hx exact (hg.2 p hp).1 have := (List.subperm_of_subset hg.1 hsub).length_le simpa using this theorem foldl_pstep_error (L : List (List String × Rat)) (u : Unit) : List.foldl pstep (.error u) L = .error u := by induction L with | nil => rfl | cons ev t ih => exact ih theorem pstep_cases (m : List (String × Rat)) (e : List String) (w : Rat) : (pstep (.ok m) (e, w) = .ok m ∧ ∀ a b, e = [a, b] → (((lookupValue m a).isSome ↔ (lookupValue m b).isSome) ∧ ∀ va vb, lookupValue m a = some va → lookupValue m b = some vb → va = w * vb)) ∨ (∃ a b va vb, e = [a, b] ∧ lookupValue m a = some va ∧ lookupValue m b = some vb ∧ va ≠ w * vb ∧ pstep (.ok m) (e, w) = .error ()) ∨ (∃ a b va, e = [a, b] ∧ lookupValue m a = some va ∧ lookupValue m b = none ∧ pstep (.ok m) (e, w) = .ok ((b, va / w) :: m)) ∨ (∃ a b vb, e = [a, b] ∧ lookupValue m a = none ∧ lookupValue m b = some vb ∧ pstep (.ok m) (e, w) = .ok ((a, w * vb) :: m)) := by rcases e with _ | ⟨a, _ | ⟨b, _ | ⟨c, t⟩⟩⟩ · exact Or.inl ⟨rfl, fun a' b' he => by simp at he⟩ · exact Or.inl ⟨rfl, fun a' b' he => by simp at he⟩ · cases ha : lookupValue m a with | none => cases hb : lookupValue m b with | none => refine Or.inl ⟨by simp only [pstep, ha, hb], fun a' b' he => ?_⟩ simp only [List.cons.injEq, and_true] at he obtain ⟨rfl, rfl⟩ := he simp [ha, hb] | some vb => exact Or.inr (Or.inr (Or.inr ⟨a, b, vb, rfl, ha, hb, by simp only [pstep, ha, hb]⟩)) | some va => cases hb : lookupValue m b with | none => exact Or.inr (Or.inr (Or.inl ⟨a, b, va, rfl, ha, hb, by simp only [pstep, ha, hb]⟩)) | some vb => by_cases hv : va = w * vb · refine Or.inl ⟨by simp [pstep, ha, hb, hv], fun a' b' he => ?_⟩ simp only [List.cons.injEq, and_true] at he obtain ⟨rfl, rfl⟩ := he simp [ha, hb, hv] · exact Or.inr (Or.inl ⟨a, b, va, vb, rfl, ha, hb, hv, by simp [pstep, ha, hb, hv]⟩) · exact Or.inl ⟨rfl, fun a' b' he => by simp at he⟩ theorem foldl_pstep_prefix : ∀ (L : List (List String × Rat)) (m m' : List (String × Rat)), List.foldl pstep (.ok m) L = .ok m' → ∃ pre, m' = pre ++ m := by intro L induction L with | nil => intro m m' h have h' : Except.ok m = Except.ok m' := h cases h' exact ⟨[], rfl⟩ | cons ev t ih => intro m m' h obtain ⟨e, w⟩ := ev rw [List.foldl_cons] at h rcases pstep_cases m e w with ⟨h1, -⟩ | ⟨a, b, va, vb, -, -, -, -, h1⟩ | ⟨a, b, va, -, -, -, h1⟩ | ⟨a, b, vb, -, -, -, h1⟩ · rw [h1] at h; exact ih m m' h · rw [h1, foldl_pstep_error] at h; cases h · rw [h1] at h obtain ⟨pre, hpre⟩ := ih _ _ h exact ⟨pre ++ [(b, va / w)], by rw [hpre, List.append_assoc]; rfl⟩ · rw [h1] at h obtain ⟨pre, hpre⟩ := ih _ _ h exact ⟨pre ++ [(a, w * vb)], by rw [hpre, List.append_assoc]; rfl⟩ theorem pstep_good (S : String → Prop) (Q : String → Rat → Prop) (e : List String) (w : Rat) (hS : ∀ x ∈ e, S x) (hQ1 : ∀ a b va, e = [a, b] → Q a va → Q b (va / w)) (hQ2 : ∀ a b vb, e = [a, b] → Q b vb → Q a (w * vb)) (m m' : List (String × Rat)) (hg : Good S Q m) (h : pstep (.ok m) (e, w) = .ok m') : Good S Q m' := by rcases pstep_cases m e w with ⟨h1, -⟩ | ⟨a, b, va, vb, -, -, -, -, h1⟩ | ⟨a, b, va, he, ha, hb, h1⟩ | ⟨a, b, vb, he, ha, hb, h1⟩ · rw [h1] at h; cases h; exact hg · rw [h1] at h; cases h · rw [h1] at h cases h subst he refine ⟨?_, ?_⟩ · simp only [List.map_cons, List.nodup_cons]; exact ⟨lookup_none hb, hg.1⟩ · intro p hp rcases List.mem_cons.mp hp with rfl | hp · exact ⟨hS b (by simp), hQ1 a b va rfl (hg.2 _ (lookup_mem ha)).2⟩ · exact hg.2 p hp · rw [h1] at h cases h subst he refine ⟨?_, ?_⟩ · simp only [List.map_cons, List.nodup_cons]; exact ⟨lookup_none ha, hg.1⟩ · intro p hp rcases List.mem_cons.mp hp with rfl | hp · exact ⟨hS a (by simp), hQ2 a b vb rfl (hg.2 _ (lookup_mem hb)).2⟩ · exact hg.2 p hp theorem foldl_pstep_good (S : String → Prop) (Q : String → Rat → Prop) : ∀ (L : List (List String × Rat)), (∀ e w, (e, w) ∈ L → ∀ x ∈ e, S x) → (∀ a b w va, ([a, b], w) ∈ L → Q a va → Q b (va / w)) → (∀ a b w vb, ([a, b], w) ∈ L → Q b vb → Q a (w * vb)) → ∀ m m', Good S Q m → List.foldl pstep (.ok m) L = .ok m' → Good S Q m' := by intro L induction L with | nil => intro _ _ _ m m' hg h have h' : Except.ok m = Except.ok m' := h cases h' exact hg | cons ev t ih => intro hS hQ1 hQ2 m m' hg h obtain ⟨e, w⟩ := ev rw [List.foldl_cons] at h cases hp : pstep (.ok m) (e, w) with | error u => rw [hp, foldl_pstep_error] at h; cases h | ok m1 => rw [hp] at h exact ih (fun e w hm => hS e w (List.mem_cons_of_mem _ hm)) (fun a b w va hm => hQ1 a b w va (List.mem_cons_of_mem _ hm)) (fun a b w vb hm => hQ2 a b w vb (List.mem_cons_of_mem _ hm)) m1 m' (pstep_good S Q e w (hS e w List.mem_cons_self) (fun a b va he hq => hQ1 a b w va (by subst he; exact List.mem_cons_self) hq) (fun a b vb he hq => hQ2 a b w vb (by subst he; exact List.mem_cons_self) hq) m m1 hg hp) h theorem foldl_pstep_ok (S : String → Prop) (Q : String → Rat → Prop) : ∀ (L : List (List String × Rat)), (∀ e w, (e, w) ∈ L → ∀ x ∈ e, S x) → (∀ a b w va, ([a, b], w) ∈ L → Q a va → Q b (va / w)) → (∀ a b w vb, ([a, b], w) ∈ L → Q b vb → Q a (w * vb)) → (∀ a b w va vb, ([a, b], w) ∈ L → Q a va → Q b vb → va = w * vb) → ∀ m, Good S Q m → ∃ m', List.foldl pstep (.ok m) L = .ok m' := by intro L induction L with | nil => intro _ _ _ _ m _; exact ⟨m, rfl⟩ | cons ev t ih => intro hS hQ1 hQ2 hC m hg obtain ⟨e, w⟩ := ev rw [List.foldl_cons] cases hp : pstep (.ok m) (e, w) with | error u => exfalso rcases pstep_cases m e w with ⟨h1, -⟩ | ⟨a, b, va, vb, he, ha, hb, hne, -⟩ | ⟨a, b, va, -, -, -, h1⟩ | ⟨a, b, vb, -, -, -, h1⟩ · rw [h1] at hp; cases hp · subst he exact hne (hC a b w va vb List.mem_cons_self (hg.2 _ (lookup_mem ha)).2 (hg.2 _ (lookup_mem hb)).2) · rw [h1] at hp; cases hp · rw [h1] at hp; cases hp | ok m1 => exact ih (fun e w hm => hS e w (List.mem_cons_of_mem _ hm)) (fun a b w va hm => hQ1 a b w va (List.mem_cons_of_mem _ hm)) (fun a b w vb hm => hQ2 a b w vb (List.mem_cons_of_mem _ hm)) (fun a b w va vb hm => hC a b w va vb (List.mem_cons_of_mem _ hm)) m1 (pstep_good S Q e w (hS e w List.mem_cons_self) (fun a b va he hq => hQ1 a b w va (by subst he; exact List.mem_cons_self) hq) (fun a b vb he hq => hQ2 a b w vb (by subst he; exact List.mem_cons_self) hq) m m1 hg hp) theorem foldl_pstep_stable : ∀ (L : List (List String × Rat)) (m m' : List (String × Rat)), List.foldl pstep (.ok m) L = .ok m' → m'.length = m.length → ∀ a b w, ([a, b], w) ∈ L → ((lookupValue m a).isSome ↔ (lookupValue m b).isSome) ∧ ∀ va vb, lookupValue m a = some va → lookupValue m b = some vb → va = w * vb := by intro L induction L with | nil => intro m m' _ _ a b w hm; simp at hm | cons ev t ih => intro m m' h hlen a b w hm obtain ⟨e, w'⟩ := ev rw [List.foldl_cons] at h rcases pstep_cases m e w' with ⟨h1, hcl⟩ | ⟨a', b', va, vb, -, -, -, -, h1⟩ | ⟨a', b', va, -, -, -, h1⟩ | ⟨a', b', vb, -, -, -, h1⟩ · rw [h1] at h rcases List.mem_cons.mp hm with he | hm · simp only [Prod.mk.injEq] at he obtain ⟨rfl, rfl⟩ := he exact hcl a b rfl · exact ih m m' h hlen a b w hm · rw [h1, foldl_pstep_error] at h; cases h · rw [h1] at h obtain ⟨pre, rfl⟩ := foldl_pstep_prefix t _ _ h rw [List.length_append, List.length_cons] at hlen omega · rw [h1] at h obtain ⟨pre, rfl⟩ := foldl_pstep_prefix t _ _ h rw [List.length_append, List.length_cons] at hlen omega theorem closeValues_succ_err {n : Nat} {eqs : List (List String)} {vals : List Rat} {m : List (String × Rat)} {u : Unit} (hp : propagate eqs vals m = .error u) : closeValues (n + 1) eqs vals m = .error u := by rw [closeValues.eq_2, hp] theorem closeValues_succ_ok {n : Nat} {eqs : List (List String)} {vals : List Rat} {m m1 : List (String × Rat)} (hp : propagate eqs vals m = .ok m1) : closeValues (n + 1) eqs vals m = if m1.length == m.length then .ok m1 else closeValues n eqs vals m1 := by rw [closeValues.eq_2, hp] theorem closeValues_good (S : String → Prop) (Q : String → Rat → Prop) (eqs : List (List String)) (vals : List Rat) (hS : ∀ e w, (e, w) ∈ eqs.zip vals → ∀ x ∈ e, S x) (hQ1 : ∀ a b w va, ([a, b], w) ∈ eqs.zip vals → Q a va → Q b (va / w)) (hQ2 : ∀ a b w vb, ([a, b], w) ∈ eqs.zip vals → Q b vb → Q a (w * vb)) : ∀ n m m', Good S Q m → closeValues n eqs vals m = .ok m' → Good S Q m' ∧ ∃ pre, m' = pre ++ m := by intro n induction n with | zero => intro m m' hg h have h' : Except.ok m = Except.ok m' := h cases h' exact ⟨hg, [], rfl⟩ | succ n ih => intro m m' hg h cases hp : propagate eqs vals m with | error u => rw [closeValues_succ_err hp] at h; cases h | ok m1 => rw [closeValues_succ_ok hp] at h have hg1 := foldl_pstep_good S Q (eqs.zip vals) hS hQ1 hQ2 m m1 hg hp obtain ⟨pre1, hpre1⟩ := foldl_pstep_prefix (eqs.zip vals) m m1 hp by_cases hl : m1.length = m.length · rw [if_pos (beq_iff_eq.mpr hl)] at h cases h exact ⟨hg1, pre1, hpre1⟩ · rw [if_neg (fun hb => hl (beq_iff_eq.mp hb))] at h obtain ⟨hg2, pre2, hpre2⟩ := ih m1 m' hg1 h exact ⟨hg2, pre2 ++ pre1, by rw [hpre2, hpre1, List.append_assoc]⟩ theorem closeValues_ok (S : String → Prop) (Q : String → Rat → Prop) (eqs : List (List String)) (vals : List Rat) (hS : ∀ e w, (e, w) ∈ eqs.zip vals → ∀ x ∈ e, S x) (hQ1 : ∀ a b w va, ([a, b], w) ∈ eqs.zip vals → Q a va → Q b (va / w)) (hQ2 : ∀ a b w vb, ([a, b], w) ∈ eqs.zip vals → Q b vb → Q a (w * vb)) (hC : ∀ a b w va vb, ([a, b], w) ∈ eqs.zip vals → Q a va → Q b vb → va = w * vb) : ∀ n m, Good S Q m → ∃ m', closeValues n eqs vals m = .ok m' := by intro n induction n with | zero => intro m _; exact ⟨m, rfl⟩ | succ n ih => intro m hg obtain ⟨m1, hp⟩ := foldl_pstep_ok S Q (eqs.zip vals) hS hQ1 hQ2 hC m hg rw [closeValues_succ_ok hp] by_cases hl : m1.length = m.length · rw [if_pos (beq_iff_eq.mpr hl)] exact ⟨m1, rfl⟩ · rw [if_neg (fun hb => hl (beq_iff_eq.mp hb))] exact ih m1 (foldl_pstep_good S Q (eqs.zip vals) hS hQ1 hQ2 m m1 hg hp) theorem closeValues_closed (vars : List String) (eqs : List (List String)) (vals : List Rat) (hS : ∀ e w, (e, w) ∈ eqs.zip vals → ∀ x ∈ e, x ∈ vars) : ∀ n m m', Good (· ∈ vars) (fun _ _ => True) m → vars.length < m.length + n → closeValues n eqs vals m = .ok m' → propagate eqs vals m' = .ok m' := by intro n induction n with | zero => intro m m' hg hlt _ have := good_length_le vars _ m hg omega | succ n ih => intro m m' hg hlt h cases hp : propagate eqs vals m with | error u => rw [closeValues_succ_err hp] at h; cases h | ok m1 => rw [closeValues_succ_ok hp] at h have hg1 := foldl_pstep_good (· ∈ vars) (fun _ _ => True) (eqs.zip vals) hS (fun _ _ _ _ _ _ => trivial) (fun _ _ _ _ _ _ => trivial) m m1 hg hp obtain ⟨pre, rfl⟩ := foldl_pstep_prefix (eqs.zip vals) m m1 hp by_cases hl : (pre ++ m).length = m.length · rw [if_pos (beq_iff_eq.mpr hl)] at h cases h have hnil : pre = [] := by rw [List.length_append] at hl exact List.eq_nil_of_length_eq_zero (by omega) subst hnil simp only [List.nil_append] at hp ⊢ exact hp · rw [if_neg (fun hb => hl (beq_iff_eq.mp hb))] at h refine ih (pre ++ m) m' hg1 ?_ h rw [List.length_append] at hl ⊢ omega theorem consistentLoop_err {n : Nat} {vars : List String} {eqs : List (List String)} {vals : List Rat} {asg : List (String × Rat)} {u : Unit} (hc : closeValues (vars.length + 1) eqs vals asg = .error u) : consistentLoop (n + 1) vars eqs vals asg = false := by rw [consistentLoop.eq_2, hc] theorem consistentLoop_some {n : Nat} {vars : List String} {eqs : List (List String)} {vals : List Rat} {asg asg' : List (String × Rat)} {x : String} (hc : closeValues (vars.length + 1) eqs vals asg = .ok asg') (hf : vars.find? (fun x => (lookupValue asg' x).isNone) = some x) : consistentLoop (n + 1) vars eqs vals asg = consistentLoop n vars eqs vals ((x, 1) :: asg') := by rw [consistentLoop.eq_2, hc] simp only [hf] theorem consistentLoop_total (vars : List String) (eqs : List (List String)) (vals : List Rat) (hS : ∀ e w, (e, w) ∈ eqs.zip vals → ∀ x ∈ e, x ∈ vars) (hw : ∀ e w, (e, w) ∈ eqs.zip vals → w ≠ 0) : ∀ n asg, Good (· ∈ vars) (fun _ v => v ≠ 0) asg → vars.length < asg.length + n → consistentLoop n vars eqs vals asg = true → ∃ A, (∀ x ∈ vars, (lookupValue A x).isSome) ∧ (∀ p ∈ A, p.2 ≠ 0) ∧ propagate eqs vals A = .ok A := by have hQ1 : ∀ a b w va, ([a, b], w) ∈ eqs.zip vals → va ≠ 0 → va / w ≠ 0 := fun _ _ w va hm hva => div_ne_zero hva (hw _ w hm) have hQ2 : ∀ a b w vb, ([a, b], w) ∈ eqs.zip vals → vb ≠ 0 → w * vb ≠ 0 := fun _ _ w vb hm hvb => mul_ne_zero (hw _ w hm) hvb intro n induction n with | zero => intro asg hg hlt _ have := good_length_le vars _ asg hg omega | succ n ih => intro asg hg hlt h cases hc : closeValues (vars.length + 1) eqs vals asg with | error u => rw [consistentLoop_err hc] at h; cases h | ok asg' => obtain ⟨hg', pre, hpre⟩ := closeValues_good (· ∈ vars) (fun _ v => v ≠ 0) eqs vals hS hQ1 hQ2 _ _ _ hg hc have hcl := closeValues_closed vars eqs vals hS _ asg asg' (good_weaken hg) (by omega) hc cases hf : vars.find? (fun x => (lookupValue asg' x).isNone) with | none => refine ⟨asg', ?_, fun p hp => (hg'.2 p hp).2, hcl⟩ intro x hx have hnx := List.find?_eq_none.mp hf x hx cases hl : lookupValue asg' x with | none => simp [hl] at hnx | some v => rfl | some x => rw [consistentLoop_some hc hf] at h have hxv : x ∈ vars := List.mem_of_find?_eq_some hf have hxn : lookupValue asg' x = none := by simpa using List.find?_some hf refine ih ((x, 1) :: asg') ⟨?_, ?_⟩ ?_ h · simp only [List.map_cons, List.nodup_cons]; exact ⟨lookup_none hxn, hg'.1⟩ · intro p hp rcases List.mem_cons.mp hp with rfl | hp · exact ⟨hxv, one_ne_zero⟩ · exact hg'.2 p hp · rw [List.length_cons, hpre, List.length_append] omega theorem ratio_value {eqs : List (List String)} {vals : List Rat} (A : List (String × Rat)) (htot : ∀ x, occursIn eqs x → (lookupValue A x).isSome) (hcl : ∀ a b w, ([a, b], w) ∈ eqs.zip vals → ∀ va vb, lookupValue A a = some va → lookupValue A b = some vb → va = w * vb) (hw : ∀ e w, (e, w) ∈ eqs.zip vals → w ≠ 0) {x y : String} {r : Rat} (h : RatioFromEquations eqs vals x y r) : ∀ vx vy, lookupValue A x = some vx → lookupValue A y = some vy → vx = r * vy := by induction h with | refl _ => intro vx vy hx hy rw [hx] at hy cases hy exact (one_mul vx).symm | @forward y z r w hr hm ih => intro vx vz hx hz obtain ⟨vy, hy⟩ := Option.isSome_iff_exists.mp (htot y (ratio_occurs hr).2) rw [ih vx vy hx hy, hcl y z w hm vy vz hy hz, mul_assoc] | @backward y z r w hr hm ih => intro vx vz hx hz obtain ⟨vy, hy⟩ := Option.isSome_iff_exists.mp (htot y (ratio_occurs hr).2) have hzy := hcl z y w hm vz vy hz hy rw [ih vx vy hx hy, hzy, show r * w⁻¹ * (w * vy) = r * (w⁻¹ * w) * vy by ring, inv_mul_cancel₀ (hw _ _ hm), mul_one] theorem ratio_unique (eqs : List (List String)) (vals : List Rat) (hNC : noContradiction eqs vals = true) (hw : ∀ e w, (e, w) ∈ eqs.zip vals → w ≠ 0) {x y : String} {r r' : Rat} (h1 : RatioFromEquations eqs vals x y r) (h2 : RatioFromEquations eqs vals x y r') : r = r' := by have hS : ∀ e w, (e, w) ∈ eqs.zip vals → ∀ z ∈ e, z ∈ eqs.flatten.eraseDups := by intro e w hm z hz rw [List.mem_eraseDups, List.mem_flatten] exact ⟨e, (List.of_mem_zip hm).1, hz⟩ obtain ⟨A, htot, hnz, hcl⟩ := consistentLoop_total (eqs.flatten.eraseDups) eqs vals hS hw (eqs.flatten.eraseDups.length + 1) [] ⟨by simp, by simp⟩ (by simp only [List.length_nil]; omega) hNC have hstab := foldl_pstep_stable (eqs.zip vals) A A hcl rfl have htot' : ∀ z, occursIn eqs z → (lookupValue A z).isSome := by intro z hz unfold occursIn at hz obtain ⟨e, he, hze⟩ := hz exact htot z (by rw [List.mem_eraseDups, List.mem_flatten]; exact ⟨e, he, hze⟩) have hcl' := fun a b w hm => (hstab a b w hm).2 obtain ⟨vx, hx⟩ := Option.isSome_iff_exists.mp (htot' x (ratio_occurs h1).1) obtain ⟨vy, hy⟩ := Option.isSome_iff_exists.mp (htot' y (ratio_occurs h1).2) have e1 := ratio_value A htot' hcl' hw h1 vx vy hx hy have e2 := ratio_value A htot' hcl' hw h2 vx vy hx hy have hvy : vy ≠ 0 := hnz _ (lookup_mem hy) exact mul_right_cancel₀ hvy (e1.symm.trans e2) theorem ratio_known {eqs : List (List String)} {vals : List Rat} (A : List (String × Rat)) (hcl : ∀ a b w, ([a, b], w) ∈ eqs.zip vals → ((lookupValue A a).isSome ↔ (lookupValue A b).isSome)) {x y : String} {r : Rat} (h : RatioFromEquations eqs vals x y r) : (lookupValue A y).isSome → (lookupValue A x).isSome := by induction h with | refl _ => exact id | forward _ hw ih => exact fun hz => ih ((hcl _ _ _ hw).mpr hz) | backward _ hw ih => exact fun hz => ih ((hcl _ _ _ hw).mp hz) theorem forcedRatio_ok {eqs : List (List String)} {vals : List Rat} {C D : String} {asg : List (String × Rat)} (hD : (eqVars eqs).any (fun x => x == D) = true) (hc : closeValues ((eqVars eqs).length + 1) eqs vals [(D, 1)] = .ok asg) : forcedRatio eqs vals C D = lookupValue asg C := by simp only [forcedRatio, hD, hc, if_true] theorem forcedRatio_err {eqs : List (List String)} {vals : List Rat} {C D : String} {u : Unit} (hc : closeValues ((eqVars eqs).length + 1) eqs vals [(D, 1)] = .error u) : forcedRatio eqs vals C D = none := by simp only [forcedRatio, hc, ite_self] theorem forcedRatio_not {eqs : List (List String)} {vals : List Rat} {C D : String} (hD : ¬ (eqVars eqs).any (fun x => x == D) = true) : forcedRatio eqs vals C D = none := by simp only [forcedRatio] rw [if_neg hD] theorem forcedRatio_iff (eqs : List (List String)) (vals : List Rat) (huniq : ∀ x y r r', RatioFromEquations eqs vals x y r → RatioFromEquations eqs vals x y r' → r = r') (C D : String) (r : Rat) : forcedRatio eqs vals C D = some r ↔ RatioFromEquations eqs vals C D r := by have hS : ∀ e w, (e, w) ∈ eqs.zip vals → ∀ z ∈ e, z ∈ eqVars eqs := by intro e w hm z hz unfold eqVars rw [List.mem_eraseDups, List.mem_flatten] exact ⟨e, (List.of_mem_zip hm).1, hz⟩ have hQ1 : ∀ a b w va, ([a, b], w) ∈ eqs.zip vals → RatioFromEquations eqs vals a D va → RatioFromEquations eqs vals b D (va / w) := by intro a b w va hm hq exact ratio_congr (ratio_trans (ratio_edge_bwd hm) hq) (by ring) have hQ2 : ∀ a b w vb, ([a, b], w) ∈ eqs.zip vals → RatioFromEquations eqs vals b D vb → RatioFromEquations eqs vals a D (w * vb) := fun _ _ _ _ hm hq => ratio_trans (ratio_edge_fwd hm) hq have hC : ∀ a b w va vb, ([a, b], w) ∈ eqs.zip vals → RatioFromEquations eqs vals a D va → RatioFromEquations eqs vals b D vb → va = w * vb := fun _ _ _ _ _ hm ha hb => huniq _ _ _ _ ha (ratio_trans (ratio_edge_fwd hm) hb) constructor · intro h by_cases hD : (eqVars eqs).any (fun x => x == D) = true · cases hc : closeValues ((eqVars eqs).length + 1) eqs vals [(D, 1)] with | error u => rw [forcedRatio_err hc] at h; cases h | ok asg => rw [forcedRatio_ok hD hc] at h have hg0 : Good (· ∈ eqVars eqs) (fun x v => RatioFromEquations eqs vals x D v) [(D, 1)] := by refine ⟨by simp, ?_⟩ intro p hp rw [List.mem_singleton] at hp subst hp have hDv := List.any_eq_true.mp hD obtain ⟨z, hz, hzD⟩ := hDv have hzD' : z = D := by simpa using hzD subst hzD' refine ⟨hz, RatioFromEquations.refl ?_⟩ unfold eqVars at hz rw [List.mem_eraseDups, List.mem_flatten] at hz obtain ⟨e, he, hze⟩ := hz exact occursIn_of_mem he hze have hg := (closeValues_good (· ∈ eqVars eqs) (fun x v => RatioFromEquations eqs vals x D v) eqs vals hS hQ1 hQ2 _ _ _ hg0 hc).1 exact (hg.2 _ (lookup_mem h)).2 · rw [forcedRatio_not hD] at h; cases h · intro hr have hDocc := (ratio_occurs hr).2 have hDv : D ∈ eqVars eqs := by unfold occursIn at hDocc obtain ⟨e, he, hx⟩ := hDocc unfold eqVars rw [List.mem_eraseDups, List.mem_flatten] exact ⟨e, he, hx⟩ have hD : (eqVars eqs).any (fun x => x == D) = true := List.any_eq_true.mpr ⟨D, hDv, by simp⟩ have hg0 : Good (· ∈ eqVars eqs) (fun x v => RatioFromEquations eqs vals x D v) [(D, 1)] := by refine ⟨by simp, ?_⟩ intro p hp rw [List.mem_singleton] at hp subst hp exact ⟨hDv, RatioFromEquations.refl hDocc⟩ obtain ⟨asg, hc⟩ := closeValues_ok (· ∈ eqVars eqs) (fun x v => RatioFromEquations eqs vals x D v) eqs vals hS hQ1 hQ2 hC _ _ hg0 rw [forcedRatio_ok hD hc] obtain ⟨hg, pre, hpre⟩ := closeValues_good (· ∈ eqVars eqs) (fun x v => RatioFromEquations eqs vals x D v) eqs vals hS hQ1 hQ2 _ _ _ hg0 hc have hcl := closeValues_closed (eqVars eqs) eqs vals hS _ [(D, 1)] asg (good_weaken hg0) (by simp only [List.length_singleton]; omega) hc have hstab := foldl_pstep_stable (eqs.zip vals) asg asg hcl rfl have hDs : (lookupValue asg D).isSome := lookup_isSome_of_mem (v := 1) (by rw [hpre]; simp) have hCs := ratio_known asg (fun a b w hm => (hstab a b w hm).1) hr hDs obtain ⟨v, hv⟩ := Option.isSome_iff_exists.mp hCs rw [hv, huniq C D v r (hg.2 _ (lookup_mem hv)).2 hr] def qcheck (fr o : Option Rat) : Bool := match fr with | some r => o == some r | none => o == some (-1) theorem query_iff (fr o : Option Rat) (P : Rat → Prop) (hfr : ∀ r, fr = some r ↔ P r) (huniq : ∀ r r', P r → P r' → r = r') : qcheck fr o = true ↔ ((∀ r, P r → o = some r) ∧ (¬ (∃ r, P r) → o = some (-1))) := by cases fr with | none => have hn : ∀ r, ¬ P r := fun r hr => by simpa using (hfr r).mpr hr simp [qcheck, hn] | some r0 => have hr0 : P r0 := (hfr r0).mp rfl simp only [qcheck, beq_iff_eq] constructor · intro ho exact ⟨fun r hr => by rw [huniq r r0 hr hr0]; exact ho, fun hne => absurd ⟨r0, hr0⟩ hne⟩ · rintro ⟨h1, -⟩ exact h1 r0 hr0 theorem check_eq (eqs : List (List String)) (vals : List Rat) (qs : List (List String)) (result : Output) : evaluateDivision_check (eqs, vals, qs) result = (result.length == qs.length && (List.finRange qs.length).all fun j => match qs.get j with | [C, D] => qcheck (forcedRatio eqs vals C D) result[j.val]? | _ => true) := rfl /-- On valid input the checker accepts exactly the specified outputs. -/ theorem evaluateDivision_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : evaluateDivision_check input result ↔ evaluateDivision_spec input result := by obtain ⟨eqs, vals, qs⟩ := input have hv := h simp only [isValidInput, Bool.and_eq_true] at hv obtain ⟨⟨⟨⟨⟨⟨_, hF⟩, _⟩, _⟩, _⟩, _⟩, hK⟩ := hv have hw : ∀ e w, (e, w) ∈ eqs.zip vals → w ≠ 0 := by intro e w hm have hwv := (List.all_eq_true.mp hF) w (List.of_mem_zip hm).2 simp only [Bool.and_eq_true, decide_eq_true_eq] at hwv exact hwv.1.ne' have huniq : ∀ x y r r', RatioFromEquations eqs vals x y r → RatioFromEquations eqs vals x y r' → r = r' := fun _ _ _ _ h1 h2 => ratio_unique eqs vals hK hw h1 h2 have hFR := forcedRatio_iff eqs vals huniq have hq : ∀ (o : Option Rat) (C D : String), qcheck (forcedRatio eqs vals C D) o = true ↔ ((∀ r, RatioFromEquations eqs vals C D r → o = some r) ∧ (¬ (∃ r, RatioFromEquations eqs vals C D r) → o = some (-1))) := fun o C D => query_iff _ o _ (hFR C D) (huniq C D) rw [check_eq] show _ ↔ (result.length = qs.length ∧ ∀ j (hj : j < qs.length) (C D : String), qs[j] = [C, D] → (∀ r : Rat, RatioFromEquations eqs vals C D r → result[j]? = some r) ∧ (¬ (∃ r : Rat, RatioFromEquations eqs vals C D r) → result[j]? = some (-1))) rw [Bool.and_eq_true, beq_iff_eq, List.all_eq_true] apply and_congr Iff.rfl constructor · intro hall j hj C D hqj have hc := hall ⟨j, hj⟩ (List.mem_finRange _) have hqj' : qs.get ⟨j, hj⟩ = [C, D] := hqj rw [hqj'] at hc exact (hq _ C D).mp hc · intro hspec j _ split · rename_i C D heq exact (hq _ C D).mpr (hspec j.val j.isLt C D heq) · rfl /-! ### Main algorithm (impl) -/ /-- Answer each query by the checker's closure `forcedRatio`, mapping undetermined ratios to `-1`. -/ def calcEquation (input : Input) : Output := match input with | (eqs, vals, qs) => qs.map fun q => match q with | [C, D] => (forcedRatio eqs vals C D).getD (-1) | _ => -1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem calcEquation_correct (input : Input) (h : isValidInput input) : evaluateDivision_spec input (calcEquation input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([["a", "b"], ["b", "c"]], [2.0, 3.0], [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]) #guard isValidInput ([["a", "b"], ["b", "c"], ["bc", "cd"]], [1.5, 2.5, 5.0], [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]]) #guard isValidInput ([["a", "b"]], [0.5], [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], [], [["a", "b"]])) #guard !(isValidInput ([["a"]], [1.0], [["a", "a"]])) #guard !(isValidInput ([["abcdef", "b"]], [1.0], [["a", "a"]])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard evaluateDivision_check ([["a", "b"], ["b", "c"]], [2.0, 3.0], [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]) [6.0, 0.5, -1.0, 1.0, -1.0] #guard evaluateDivision_check ([["a", "b"], ["b", "c"], ["bc", "cd"]], [1.5, 2.5, 5.0], [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]]) [3.75, 0.4, 5.0, 0.2] #guard evaluateDivision_check ([["a", "b"]], [0.5], [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]]) [0.5, 2.0, -1.0, -1.0] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(evaluateDivision_check ([["a", "b"], ["b", "c"]], [2.0, 3.0], [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]) [5.0, 0.5, -1.0, 1.0, -1.0]) #guard !(evaluateDivision_check ([["a", "b"], ["b", "c"], ["bc", "cd"]], [1.5, 2.5, 5.0], [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]]) [-1.0, 0.4, 5.0, 0.2]) #guard !(evaluateDivision_check ([["a", "b"]], [0.5], [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]]) [0.5, -1.0, -1.0, -1.0]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard calcEquation ([["a", "b"], ["b", "c"]], [2.0, 3.0], [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]) == [6.0, 0.5, (-1.0), 1.0, (-1.0)] #guard calcEquation ([["a", "b"], ["b", "c"], ["bc", "cd"]], [1.5, 2.5, 5.0], [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]]) == [3.75, 0.4, 5.0, 0.2] #guard calcEquation ([["a", "b"]], [0.5], [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]]) == [0.5, 2.0, (-1.0), (-1.0)] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard evaluateDivision_check ([["a", "b"], ["b", "c"]], [2.0, 3.0], [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]) (calcEquation ([["a", "b"], ["b", "c"]], [2.0, 3.0], [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]])) #guard evaluateDivision_check ([["a", "b"], ["b", "c"], ["bc", "cd"]], [1.5, 2.5, 5.0], [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]]) (calcEquation ([["a", "b"], ["b", "c"], ["bc", "cd"]], [1.5, 2.5, 5.0], [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]])) #guard evaluateDivision_check ([["a", "b"]], [0.5], [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]]) (calcEquation ([["a", "b"]], [0.5], [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]])) end PEvaluateDivision