Source lean/Determinize/Proof/FiniteModel/BuildModel.lean
import Determinize.Proof.FiniteModel.Buildimport Determinize.Proof.FiniteModel.SparseRownamespace Determinize.Finite.Builderopen Spec.FiniteModel Checkingopen Spec.Paper (Core)variable [Hashable State]abbrev Work.record (work : Work) (complete : work.rows.size = work.table.states.size)    (i : Fin work.table.states.size) : Record := work.rows[i.val]'(by omega)theorem Work.record_state (work : Work) (complete : work.rows.size = work.table.states.size)    (i : Fin work.table.states.size) :    (work.record complete i).state = work.table.states[i.val] := by  have h := work.aligned (⟨i.val, by omega⟩ : Fin work.rows.size)  simpa using h.symmdef Work.weight (work : Work) (complete : work.rows.size = work.table.states.size)    (i j : Fin work.table.states.size) : Rat :=  ((work.record complete i).action.successors.map fun outcome ↦    if outcome.2 = work.table.states[j.val] then outcome.1 else 0).sumtheorem Work.weight_nonnegative (work : Work) (complete : work.rows.size = work.table.states.size)    (i j : Fin work.table.states.size) : 0 ≤ work.weight complete i j := by  apply List.sum_nonneg  intro q member  obtain ⟨outcome, inOutcomes, rfl⟩ := List.mem_map.mp member  split  · exact (work.record complete i).action.nonnegative outcome inOutcomes  · exact le_rfltheorem Work.weight_normalized (work : Work) (complete : work.rows.size = work.table.states.size)    (i : Fin work.table.states.size) : ∑ j, work.weight complete i j = 1 := by  simp only [Work.weight]  rw [sum_list_comm]  trans ((work.record complete i).action.successors.map Prod.fst).sum  · congr 1    apply List.map_congr_left    intro outcome member    by_cases zero : outcome.1 = 0    · simp [zero]    · have positive : 0 < outcome.1 := lt_of_le_of_ne        ((work.record complete i).action.nonnegative outcome member) (Ne.symm zero)      obtain ⟨j, hj⟩ := work.closed _ (Array.getElem_mem _) outcome member positive      have only (k : Fin work.table.states.size) :          outcome.2 = work.table.states[k.val] ↔ j = k := by        rw [← hj]        exact work.table.injective.eq_iff      simp [only]  · exact (work.record complete i).action.normalizedabbrev Work.candidate (work : Work) (complete : work.rows.size = work.table.states.size) :    Candidate where  initial := 0  states := work.table.states  rows := Array.ofFn fun i : Fin work.table.states.size ↦    ⟨(work.record complete i).action.kind, sparseEdges (work.weight complete i)⟩@[simp] theorem Work.candidate_row (work : Work)    (complete : work.rows.size = work.table.states.size)    (i : Fin work.table.states.size) : (work.candidate complete).row i =      ⟨(work.record complete i).action.kind, sparseEdges (work.weight complete i)⟩ := by  simp [Candidate.row, Work.candidate, i.isLt]@[simp] theorem Work.candidate_weight (work : Work)    (complete : work.rows.size = work.table.states.size)    (i j : Fin work.table.states.size) :    (work.candidate complete).weight i j = work.weight complete i j := by  simp only [Candidate.weight, work.candidate_row]  exact sparseEdges_weight _ (work.weight_nonnegative complete i) jtheorem Work.replays (work : Work) (complete : work.rows.size = work.table.states.size)    (i : Fin work.table.states.size) : (work.candidate complete).RowReplays i := by  have correct := (work.record complete i).action.correct  simp only [work.record_state complete i] at correct  change match step work.table.states[i.val] with    | .error _ => False    | .ok (.returned r) => _    | .ok .rejected => _    | .ok (.next _ _) => _  cases h : step work.table.states[i.val] with  | error failure => simp [h] at correct  | ok action => cases action with    | returned reward => simp only [h] at correct; simpa [h] using correct.1    | rejected => simp only [h] at correct; simpa [h] using correct.1    | next evidence outcomes =>      simp only [h] at correct      refine ⟨by simpa using correct.1, ?_, ?_, ?_⟩      · rw [← correct.2]; exact (work.record complete i).action.nonnegative      · intro outcome member positive        exact work.closed _ (Array.getElem_mem _) outcome (correct.2.symm ▸ member) positive      · intro j        simp only [work.candidate_weight, Work.weight, correct.2]        rfltheorem Work.absorbing (work : Work) (complete : work.rows.size = work.table.states.size)    (i : Fin work.table.states.size) (terminal : (work.record complete i).action.kind ≠ .transient)    (j : Fin work.table.states.size) : work.weight complete i j = if i = j then 1 else 0 := by  have correct := (work.record complete i).action.correct  have outcomes : (work.record complete i).action.successors = [(1, work.table.states[i.val])] := by    cases h : step (work.record complete i).state with    | error failure => simp [h] at correct    | ok action => cases action with      | returned r =>        simp only [h] at correct; simpa only [work.record_state complete i] using correct.2      | rejected =>        simp only [h] at correct; simpa only [work.record_state complete i] using correct.2      | next evidence outcomes => simp only [h] at correct; exact (terminal correct.1).elim  simp only [Work.weight, outcomes, List.map_cons, List.map_nil, List.sum_cons, List.sum_nil,    add_zero]  have eq : work.table.states[i.val] = work.table.states[j.val] ↔ i = j :=    work.table.injective.eq_iff  simp only [eq]theorem Work.valid (work : Work) (complete : work.rows.size = work.table.states.size)    (source : Core) (subject : Subject)    (root : work.root = initialState source subject)    (sourceScoped : Proof.FiniteModel.Binding.Scoped 0 source) :    (work.candidate complete).ReplayValid source subject := by  refine ⟨by simp, ?_, ⟨?_, sourceScoped, work.table.injective⟩,    ⟨?_, ?_, ?_⟩, ?_, work.replays complete⟩  · exact (Array.getElem?_eq_some_iff.mp work.initial).1  · exact work.initial.trans (congrArg some root)  · intro i j; simpa using work.weight_nonnegative complete i j  · intro i; simpa using work.weight_normalized complete i  · intro i terminal j    simpa using work.absorbing complete i (by simpa using terminal) j  · intro i    simpa [Candidate.EdgesValid] using sparseEdges_valid (work.weight complete i)end Determinize.Finite.Builder