Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Rural postman algorithm — Connector-tree construction and Euler adjacency lists

Definition
VehicleRoutingSurvey_RuralPostman1979_Part05

by kmehltretter82 · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theoryrural-postman

This module supplies the Lean definitions and checked auxiliary results for connector-tree construction and Euler adjacency lists in the Table 3 proof. It uses the mission’s rural-run and arithmetic-RAM model.

Definition code
import Mathlib.Tactic.IntervalCases
import Mathlib.Data.List.Forall2
import Mathlib.Tactic.Ring
import Definitions.Def_VehicleRoutingSurvey_RuralPostman1979_Part01
import Definitions.Def_VehicleRoutingSurvey_RuralPostman1979_Part02
import Definitions.Def_VehicleRoutingSurvey_RuralPostman1979_Part03
import Definitions.Def_VehicleRoutingSurvey_RuralPostman1979_Part04

/-! runtime/PrimRound.lean -/
section RppSource_PrimRound
namespace VehicleRoutingSurvey.Routing

structure PrimLayout (n : ℕ) where
  rows : ℕ
  matrix : ℕ
  labels : ℕ
  support : ℕ
  visits : ℕ
  mask : ℕ
  output : ℕ
  rowsBelowLabels : rows + n ≤ labels
  labelsBelowSupport : labels + n ≤ support
  supportBelowVisits : support + n ≤ visits
  visitsBelowMask : visits + n ≤ mask
  maskBelowOutput : mask + n ^ 2 ≤ output

structure PrimRoundFrame (I : Service) (layout : PrimLayout I.graph.n)
    (required seen : Fin I.graph.n → Bool) (cut : Finset (RequiredComponent I))
    (pairs : List (PrimPair I)) (s : ArithmeticState) : Prop where
  mask : PrimMaskFrame I.graph.n layout.rows layout.matrix layout.support layout.visits
    layout.mask required seen s
  labelBase : s.nr 24 = layout.labels
  zero : s.nr 33 = 0
  labels : ∀ u v : Fin I.graph.n, s.nm (layout.labels + u.val) = s.nm (layout.labels + v.val) ↔
    sameComponent I u v
  supported : ∀ v, required v = true ↔ v ∈ requiredVertices I
  selected : ∀ v, seen v = true ↔ v ∈ requiredVertices I ∧ requiredComponent I v ∈ cut
  output : PrimPairOutputFrame I layout.output pairs s
  distances : ∀ p : PrimPair I, s.rm (layout.matrix + primPairOffset p) = distance I.graph p.1 p.2
  sentinel : ∀ p : PrimPair I, distance I.graph p.1 p.2 < s.rm (layout.matrix + I.graph.n ^ 2)

def primRoundBlock : List ArithmeticInstruction :=
  appendBlock primSelectAcrossCutBlock (branchOnUnequal 12 44 commitPrimOffsetBlock)

private theorem PrimMaskFrame.controlOnly {n rows matrix support visits mask : ℕ}
    {required seen : Fin n → Bool} {s t : ArithmeticState}
    (frame : PrimMaskFrame n rows matrix support visits mask required seen s)
    (registers : t.nr = s.nr) (memory : t.nm = s.nm) :
    PrimMaskFrame n rows matrix support visits mask required seen t :=
  ⟨frame.floyd.preserved (fun r _ _ => congrFun registers r) memory,
    (congrFun registers 40).trans frame.supportBase, (congrFun registers 41).trans frame.visitedBase,
    (congrFun registers 42).trans frame.maskBase, frame.supportBeforeMask, frame.visitsBeforeMask,
    frame.rowsBeforeMask, fun v => (congrFun memory _).trans (frame.supportBit v),
    fun v => (congrFun memory _).trans (frame.visitedBit v)⟩

private theorem PrimRoundFrame.controlOnly {I : Service} {layout : PrimLayout I.graph.n}
    {required seen : Fin I.graph.n → Bool} {cut : Finset (RequiredComponent I)} {pairs : List (PrimPair I)}
    {s t : ArithmeticState} (frame : PrimRoundFrame I layout required seen cut pairs s)
    (registers : t.nr = s.nr) (natural : t.nm = s.nm) (real : t.rm = s.rm) :
    PrimRoundFrame I layout required seen cut pairs t :=
  ⟨frame.mask.controlOnly registers natural, (congrFun registers 24).trans frame.labelBase,
    (congrFun registers 33).trans frame.zero, by rw [natural]; exact frame.labels,
    frame.supported, frame.selected,
    ⟨(congrFun registers 43).trans frame.output.baseAt, (congrFun registers 38).trans frame.output.cursor,
      (congrFun registers 39).trans frame.output.length, by rw [natural]; exact frame.output.words⟩,
    by rw [real]; exact frame.distances, by rw [real]; exact frame.sentinel⟩

structure PrimRoundResult (I : Service) (layout : PrimLayout I.graph.n) (root : Fin I.graph.n)
    (required : Fin I.graph.n → Bool) (cut : Finset (RequiredComponent I)) (initial : ArithmeticState)
    (nextCut : Finset (RequiredComponent I)) (nextPairs : List (PrimPair I)) (nextSeen : Fin I.graph.n → Bool)
    (steps : ℕ) (s : ArithmeticState) : Prop where
  run : BlockRuns primRoundBlock steps initial s
  bound : steps ≤ 28 * I.graph.n ^ 2 + 22 * I.graph.n + 34
  running : s.halted = false
  frame : PrimRoundFrame I layout required nextSeen nextCut nextPairs s
  prefixValid : PrimPrefix I root nextCut nextPairs
  progress : nextCut = activeRequiredComponents I ∨ nextCut.card = cut.card + 1
  loopIndex : s.nr 32 = initial.nr 32
  pathsBase : s.nr 26 = initial.nr 26
  realMemory : s.rm = initial.rm
  previousNatural : ∀ k < layout.labels, s.nm k = initial.nm k

/-- One round selects the cheapest crossing pair, appends it, and marks
the new component. Once all components are reached it only tests the cut. -/
theorem primRoundBlock_correct {I : Service} {layout : PrimLayout I.graph.n} {root : Fin I.graph.n}
    {required seen : Fin I.graph.n → Bool} {cut : Finset (RequiredComponent I)} {pairs : List (PrimPair I)}
    {s : ArithmeticState} (state : PrimRoundFrame I layout required seen cut pairs s)
    (current : PrimPrefix I root cut pairs) (undirected : Undirected I.graph)
    (entry : s.pc = 0) (running : s.halted = false) :
    ∃ (nextCut : Finset (RequiredComponent I)) (nextPairs : List (PrimPair I))
      (nextSeen : Fin I.graph.n → Bool) (steps : ℕ) (t : ArithmeticState),
      PrimRoundResult I layout root required cut s nextCut nextPairs nextSeen steps t := by
  classical
  let n := I.graph.n
  have labelsBeforeVisits : layout.labels + n ≤ layout.visits :=
    layout.labelsBelowSupport.trans ((Nat.le_add_right _ _).trans layout.supportBelowVisits)
  have visitsBeforeOutput : layout.visits + n ≤ layout.output :=
    layout.visitsBelowMask.trans ((Nat.le_add_right _ _).trans layout.maskBelowOutput)
  have labelsBeforeMask : layout.labels + n ≤ layout.mask :=
    labelsBeforeVisits.trans ((Nat.le_add_right _ _).trans layout.visitsBelowMask)
  obtain ⟨selected, selectRun, selectReady, foundMask, zero, limit, real, fixed, natural, choice⟩ :=
    primSelectAcrossCutBlock_correct current state.mask entry running state.supported state.selected
      state.distances state.sentinel
  let ready := {selected with pc := 0}
  have beforeMask (k : ℕ) (below : k < layout.mask) : selected.nm k = s.nm k :=
    natural k (fun within => (not_le.mpr below) within.1)
  have afterMask (k : ℕ) (above : layout.output ≤ k) : selected.nm k = s.nm k :=
    natural k (fun within => (not_lt.mpr (layout.maskBelowOutput.trans above)) within.2)
  have safeLabels (u : Fin n) : layout.labels + u.val < layout.mask :=
    (Nat.add_lt_add_left u.isLt _).trans_le labelsBeforeMask
  have selectedLabels (u v : Fin n) :
      selected.nm (layout.labels + u.val) = selected.nm (layout.labels + v.val) ↔ sameComponent I u v := by
    rw [beforeMask _ (safeLabels u), beforeMask _ (safeLabels v)]
    exact state.labels u v
  have selectedOutput : PrimPairOutputFrame I layout.output pairs selected :=
    ⟨(fixed 43 (by decide) (by decide)).trans state.output.baseAt,
      (fixed 38 (by decide) (by decide)).trans state.output.cursor,
      (fixed 39 (by decide) (by decide)).trans state.output.length, fun i =>
        ⟨(afterMask _ (by omega)).trans (state.output.words i).1,
          (afterMask _ (by omega)).trans (state.output.words i).2⟩⟩
  have selectedFrame : PrimRoundFrame I layout required seen cut pairs selected :=
    ⟨foundMask, (fixed 24 (by decide) (by decide)).trans state.labelBase, zero, selectedLabels,
      state.supported, state.selected, selectedOutput,
      by rw [real]; exact state.distances, by rw [real]; exact state.sentinel⟩
  have readyFrame : PrimRoundFrame I layout required seen cut pairs ready :=
    selectedFrame.controlOnly rfl rfl rfl
  rcases choice with ⟨missing, finished⟩ | ⟨p, chosen, eligible, least⟩
  · have skip : ready.nr 12 = ready.nr 44 := missing.trans limit.symm
    have stopped := branchOnUnequal_skip 12 44 commitPrimOffsetBlock ready rfl selectReady skip
    let t := relocateState primSelectAcrossCutBlock.length
      {ready with pc := (branchOnUnequal 12 44 commitPrimOffsetBlock).length}
    have obtains : PrimRoundFrame I layout required seen cut pairs t :=
      readyFrame.controlOnly rfl rfl rfl
    refine ⟨cut, pairs, seen, _, t, ⟨by simpa only [primRoundBlock] using selectRun.append stopped,
      by omega, selectReady, obtains,
      current, Or.inl finished, fixed 32 (by decide) (by decide), fixed 26 (by decide) (by decide), real,
      fun k below => beforeMask k (below.trans_le ((Nat.le_add_right _ _).trans labelsBeforeMask))⟩⟩
  · have available : ready.nr 12 ≠ ready.nr 44 := by
      change selected.nr 12 ≠ selected.nr 44
      rw [chosen, limit]
      exact Nat.ne_of_lt (primPairOffset_lt p)
    obtain ⟨commit, commitRun, commitReady, appended, commitReal, _, stable, outsideVisits, mark⟩ :=
      commitPrimOffsetBlock_correct readyFrame.output rfl selectReady readyFrame.mask.floyd.dimension
        readyFrame.mask.floyd.one readyFrame.zero readyFrame.labelBase readyFrame.mask.visitedBase
        labelsBeforeVisits visitsBeforeOutput p chosen
    have commits := branchOnUnequal_take 12 44 commitPrimOffsetBlock (s := ready) (t := commit)
      rfl selectReady available commitRun
    let t := relocateState primSelectAcrossCutBlock.length (relocateState 3 commit)
    let nextCut := insert (requiredComponent I p.2) cut
    let nextSeen (v : Fin n) : Bool := decide (v ∈ requiredVertices I ∧ requiredComponent I v ∈ nextCut)
    have nextModel : PrimPrefix I root nextCut (pairs ++ [p]) :=
      current.append undirected p eligible least
    have notVisited : requiredComponent I p.2 ∉ cut := eligible.2.2.2
    have outsideLow (k : ℕ) (hk : k < layout.visits) : t.nm k = selected.nm k :=
      outsideVisits k (hk.trans_le ((Nat.le_add_right _ _).trans visitsBeforeOutput))
        (fun inside => (not_le.mpr hk) inside.1)
    have unchangedLabels (w : Fin n) : t.nm (layout.labels + w.val) = selected.nm (layout.labels + w.val) :=
      outsideLow _ ((Nat.add_lt_add_left w.isLt _).trans_le labelsBeforeVisits)
    have seenAsFlag (v : Fin n) : seen v = true ↔
        v ∈ requiredVertices I ∧ requiredComponent I v ∈ cut := state.selected v
    have oldFlags (v : Fin n) : selected.nm (layout.visits + v.val) =
        if v ∈ requiredVertices I ∧ requiredComponent I v ∈ cut then 1 else 0 := by
      rw [foundMask.visitedBit]
      change (if seen v = true then 1 else 0) = _
      simp only [seenAsFlag]
    have marked (w : Fin n) : t.nm (layout.visits + w.val) = if nextSeen w then 1 else 0 := by
      have bit := markPrimComponent_flag cut (fun u => selected.nm (layout.labels + u.val))
        (fun u => selected.nm (layout.visits + u.val)) selectedLabels oldFlags p.2 eligible.2.1 w
      change commit.nm _ = _
      rw [mark]
      simpa [nextSeen, nextCut] using bit
    have withinFrame : FloydFrame n layout.rows layout.matrix t :=
      ⟨(stable 3 (by decide) (by decide) (by decide) (by decide)).trans foundMask.floyd.tableBase,
        (stable 4 (by decide) (by decide) (by decide) (by decide)).trans foundMask.floyd.matrixBase,
        (stable 5 (by decide) (by decide) (by decide) (by decide)).trans foundMask.floyd.dimension,
        (stable 6 (by decide) (by decide) (by decide) (by decide)).trans foundMask.floyd.one,
        fun i hi => (outsideLow _ ((Nat.add_lt_add_left hi _).trans_le
          (layout.rowsBelowLabels.trans ((Nat.le_add_right _ _).trans labelsBeforeVisits)))).trans
          (foundMask.floyd.rows i hi)⟩
    have nextMask : PrimMaskFrame n layout.rows layout.matrix layout.support layout.visits layout.mask
        required nextSeen t :=
      ⟨withinFrame, (stable 40 (by decide) (by decide) (by decide) (by decide)).trans foundMask.supportBase,
        (stable 41 (by decide) (by decide) (by decide) (by decide)).trans foundMask.visitedBase,
        (stable 42 (by decide) (by decide) (by decide) (by decide)).trans foundMask.maskBase,
        foundMask.supportBeforeMask, foundMask.visitsBeforeMask, foundMask.rowsBeforeMask, fun v =>
          (outsideLow _ ((Nat.add_lt_add_left v.isLt _).trans_le layout.supportBelowVisits)).trans
            (foundMask.supportBit v), marked⟩
    have totalReal : t.rm = s.rm := commitReal.trans real
    have actualOutput : PrimPairOutputFrame I layout.output (pairs ++ [p]) t :=
      ⟨appended.baseAt, appended.cursor, appended.length, appended.words⟩
    have nextFrame : PrimRoundFrame I layout required nextSeen nextCut (pairs ++ [p]) t :=
      ⟨nextMask, (stable 24 (by decide) (by decide) (by decide) (by decide)).trans selectedFrame.labelBase,
        (stable 33 (by decide) (by decide) (by decide) (by decide)).trans zero,
        fun u v => by rw [unchangedLabels u, unchangedLabels v]; exact selectedLabels u v,
        state.supported, fun v => by simp [nextSeen], actualOutput,
        by rw [totalReal]; exact state.distances, by rw [totalReal]; exact state.sentinel⟩
    refine ⟨nextCut, pairs ++ [p], nextSeen, _, t,
      ⟨by simpa only [primRoundBlock] using selectRun.append commits, by omega, commitReady,
      nextFrame, nextModel, Or.inr (Finset.card_insert_of_notMem notVisited),
      (stable 32 (by decide) (by decide) (by decide) (by decide)).trans (fixed 32 (by decide) (by decide)),
      (stable 26 (by decide) (by decide) (by decide) (by decide)).trans (fixed 26 (by decide) (by decide)),
      totalReal, ?_⟩⟩
    intro k below
    exact (outsideLow _ (below.trans_le ((Nat.le_add_right _ _).trans labelsBeforeVisits))).trans
      (beforeMask k (below.trans_le ((Nat.le_add_right _ _).trans labelsBeforeMask)))

end VehicleRoutingSurvey.Routing
end RppSource_PrimRound

/-! runtime/PrimInitialization.lean -/
section RppSource_PrimInitialization
namespace VehicleRoutingSurvey.Routing

def adjacentPrimLayout (n rows matrix labels : ℕ) (fits : rows + n ≤ labels) : PrimLayout n :=
  let support := labels + n
  let visits := support + n
  let mask := visits + n
  ⟨rows, matrix, labels, support, visits, mask, mask + n ^ 2, fits, le_rfl, le_rfl, le_rfl, le_rfl⟩

private def configurePrimArrays : List ArithmeticInstruction :=
  [.natAdd 40 24 5, .natAdd 41 40 5, .natAdd 42 41 5,
    .natSub 44 5 6, .natAdd 44 3 44, .natLoad 44 44, .natAdd 44 44 5, .natAdd 43 42 44,
    .natLoad 8 6, .natConst 9 2, .natAdd 45 5 33, .realConst 0 1, .natAdd 51 4 44,
    .natSub 26 37 44, .natAdd 37 40 33, .natAdd 23 5 5]

private def configurePrimState (s : ArithmeticState) : ArithmeticState :=
  let n := s.nr 5
  let support := s.nr 24 + n
  let visits := support + n
  let mask := visits + n
  let cells := s.nm (s.nr 3 + (n - s.nr 6)) + n
  let nr := Function.update (Function.update (Function.update s.nr 40 support) 41 visits) 42 mask
  let nr := Function.update (Function.update nr 44 cells) 43 (mask + cells)
  let nr := Function.update (Function.update (Function.update nr 8 (s.nm (s.nr 6))) 9 2) 45 (n + s.nr 33)
  let nr := Function.update (Function.update nr 51 (s.nr 4 + cells)) 26 (s.nr 37 - cells)
  let nr := Function.update (Function.update nr 37 (support + s.nr 33)) 23 (n + n)
  {s with pc := 16, nr := nr, rr := Function.update s.rr 0 1}

private theorem configurePrimArrays_runs {s : ArithmeticState} (entry : s.pc = 0)
    (running : s.halted = false) : BlockRuns configurePrimArrays 16 s (configurePrimState s) := by
  refine ⟨?_, ?_, rfl⟩
  · have position (i : ℕ) (hi : i ≤ 16) :
        ((arithmeticStep configurePrimArrays)^[i] s).pc = i ∧
          ((arithmeticStep configurePrimArrays)^[i] s).halted = false := by
      induction i with
      | zero => exact ⟨entry, running⟩
      | succ i ih =>
        have below : i < 16 := by omega
        have previous := ih below.le
        rw [Function.iterate_succ_apply']
        simp only [arithmeticStep, previous.1, previous.2, Bool.false_eq_true, ↓reduceIte]
        interval_cases i <;> exact ⟨rfl, rfl⟩
    intro i hi
    change ((arithmeticStep configurePrimArrays)^[i] s).pc < 16
    rwa [(position i (by omega)).1]
  · simp [configurePrimState, configurePrimArrays, arithmeticStep, entry, running,
      Function.iterate_succ_apply', Function.update_idem]

private def retainPrimSentinel : List ArithmeticInstruction :=
  [.realStore 51 0, .natAdd 38 43 33, .natConst 39 0]

def initializePrimArraysBlock : List ArithmeticInstruction :=
  appendBlock configurePrimArrays
    (appendBlock clearRequiredBitsBlock (appendBlock apspWeightBlock retainPrimSentinel))

structure PrimArraySeed (I : Service) (layout : PrimLayout I.graph.n) (next : ℕ)
    (initial final : ArithmeticState) : Prop where
  frame : PrimSupportFrame I layout.rows layout.matrix layout.support final
  running : final.halted = false
  nextBase : final.nr 26 = next
  labelBase : final.nr 24 = layout.labels
  visitedBase : final.nr 41 = layout.visits
  maskBase : final.nr 42 = layout.mask
  cursor : final.nr 9 = 2
  noRoot : final.nr 45 = I.graph.n
  output : PrimPairOutputFrame I layout.output [] final
  supportZeros : ∀ u : Fin I.graph.n, final.nm (layout.support + u.val) = 0
  visitedZeros : ∀ u : Fin I.graph.n, final.nm (layout.visits + u.val) = 0
  beforeSupport : ∀ k < layout.support, final.nm k = initial.nm k
  real : final.rm = Function.update initial.rm (layout.matrix + I.graph.n ^ 2)
    (1 + (ruralRealInput I).sum)

/-- Lay out Prim's arrays, clear support and visited flags, and reserve a
real sentinel obtained from a single raw-weight scan. -/
theorem initializePrimArraysBlock_correct {I : Service} {rows matrix labels next : ℕ}
    {s : ArithmeticState} (frame : FloydFrame I.graph.n rows matrix s)
    (positive : 0 < I.graph.n) (entry : s.pc = 0) (running : s.halted = false)
    (labelBase : s.nr 24 = labels) (oldBits : s.nr 37 = next + I.graph.n ^ 2) (zero : s.nr 33 = 0)
    (rowsFit : rows + I.graph.n ≤ labels) (inputFit : 2 + 3 * I.graph.q ≤ labels)
    (naturalInput : ∀ k < 2 + 3 * I.graph.q, s.nm k = (ruralNatInput I)[k]?.getD 0)
    (weightInput : ∀ e : Fin I.graph.q, s.rm e.val = I.graph.weight e) :
    let layout := adjacentPrimLayout I.graph.n rows matrix labels rowsFit
    ∃ t, BlockRuns initializePrimArraysBlock (10 * I.graph.n + 5 * I.graph.q + 23) s t ∧
      PrimArraySeed I layout next s t := by
  intro layout
  let n := I.graph.n
  let configured := configurePrimState s
  let clearing := {configured with pc := 0}
  have last : n - 1 < n := by omega
  have successor : (n - 1).succ = n := by omega
  have cells : s.nm (s.nr 3 + (n - 1)) + n = n ^ 2 := by
    rw [frame.tableBase, frame.rows _ last, pow_two, ← Nat.mul_succ, successor]
  have qAt : s.nm 1 = I.graph.q := by
    rw [naturalInput _ (by omega)]
    simp [ruralNatInput]
  have one : clearing.nr 6 = 1 := frame.one
  have reserve : clearing.nr 37 = layout.support := by
    simp [clearing, configured, configurePrimState, frame.dimension, labelBase, zero, layout, adjacentPrimLayout]
  have count : clearing.nr 23 = 2 * n := by
    simp [clearing, configured, configurePrimState, frame.dimension, n, two_mul]
  obtain ⟨cleared, clear, ready, fixed, clearRm, clearRr, clearNm⟩ :=
    clearRequiredBitsBlock_correct (s := clearing) rfl running one zero reserve count
  let summing := {cleared with pc := 0}
  have clearedOne : summing.nr 6 = 1 := (fixed 6 (by decide) (by decide)).trans one
  have totalEdges : summing.nr 8 = I.graph.q := by
    change cleared.nr 8 = _
    rw [fixed 8 (by decide) (by decide)]
    simp [clearing, configured, configurePrimState, frame.one, qAt]
  have initialSum : summing.rr 0 = 1 := by
    change cleared.rr 0 = 1
    rw [clearRr]
    simp [clearing, configured, configurePrimState]
  obtain ⟨weighted, weightRun, summed, weightsNm, weightsRm, total, weightFixed⟩ :=
    apspWeightBlock_correct I summing rfl ready clearedOne totalEdges initialSum
      (fun e => (congrFun clearRm e.val).trans (weightInput e))
  let retaining := {weighted with pc := 0}
  let kept := {weighted with
    pc := 3
    nr := Function.update (Function.update weighted.nr 38 (layout.output)) 39 0
    rm := Function.update weighted.rm (weighted.nr 51) (weighted.rr 0)}
  have unchanged (r : ℕ) (notIndex : r ≠ 7) (notScratch : r ≠ 38) : weighted.nr r = configured.nr r :=
    (weightFixed r notIndex).trans (fixed r notIndex notScratch)
  have savedZero : weighted.nr 33 = 0 := (unchanged 33 (by decide) (by decide)).trans zero
  have outputBase : weighted.nr 43 = layout.output := by
    rw [unchanged 43 (by decide) (by decide)]
    simp [configured, configurePrimState, frame.dimension, frame.one, labelBase, cells, n, layout, adjacentPrimLayout]
  have reserveReal : weighted.nr 51 = layout.matrix + n ^ 2 := by
    rw [unchanged 51 (by decide) (by decide)]
    simp [configured, configurePrimState, frame.matrixBase, frame.dimension, frame.one, cells, n,
      layout, adjacentPrimLayout]
  have keepRun : BlockRuns retainPrimSentinel 3 retaining kept := by
    refine ⟨?_, ?_, rfl⟩
    · intro i hi
      interval_cases i <;> simp [retaining, retainPrimSentinel, arithmeticStep, summed, Function.iterate_succ_apply']
    · simp [retaining, kept, retainPrimSentinel, arithmeticStep, summed, Function.iterate_succ_apply',
        outputBase, savedZero]
  let finish := relocateState configurePrimArrays.length (relocateState clearRequiredBitsBlock.length
    (relocateState apspWeightBlock.length kept))
  have stable (r : ℕ) (notIndex : r ≠ 7) (notCursor : r ≠ 38) (notSize : r ≠ 39) :
      finish.nr r = configured.nr r := by
    change Function.update (Function.update weighted.nr 38 layout.output) 39 0 r = _
    rw [Function.update_of_ne notSize, Function.update_of_ne notCursor]
    exact unchanged r notIndex notCursor
  have mem (k : ℕ) : finish.nm k =
      if layout.support ≤ k ∧ k < layout.support + 2 * n then 0 else s.nm k := by
    change weighted.nm k = _
    rw [weightsNm, show summing.nm = cleared.nm from rfl, clearNm] <;> rfl
  have lower (k : ℕ) (early : k < layout.support) : finish.nm k = s.nm k := by
    rw [mem, if_neg (fun writes => (not_le.mpr early) writes.1)]
  have floyd : FloydFrame n rows matrix finish := by
    refine ⟨?_, ?_, ?_, ?_, fun i hi => ?_⟩
    · rw [stable 3 (by decide) (by decide) (by decide)]
      exact frame.tableBase
    · rw [stable 4 (by decide) (by decide) (by decide)]
      exact frame.matrixBase
    · rw [stable 5 (by decide) (by decide) (by decide)]
      exact frame.dimension
    · rw [stable 6 (by decide) (by decide) (by decide)]
      exact frame.one
    · have bounds : rows + n ≤ layout.support := rowsFit.trans (Nat.le_add_right _ _)
      exact (lower _ ((Nat.add_lt_add_left hi _).trans_le bounds)).trans (frame.rows i hi)
  have rewrites (r : ℕ) (i : ℕ) (r7 : r ≠ 7) (r38 : r ≠ 38) (r39 : r ≠ 39)
      (value : configured.nr r = i) : finish.nr r = i :=
    (stable r r7 r38 r39).trans value
  have supportAt : finish.nr 40 = layout.support := rewrites 40 _ (by decide) (by decide) (by decide)
    (by simp [configured, configurePrimState, frame.dimension, labelBase, layout, adjacentPrimLayout])
  have bits : PrimSupportFrame I rows matrix layout.support finish :=
    ⟨floyd, rewrites 8 _ (by decide) (by decide) (by decide)
      (by simp [configured, configurePrimState, frame.one, qAt]), supportAt,
      rewrites 33 _ (by decide) (by decide) (by decide) zero,
      fun a ha => (lower a (ha.trans_le (inputFit.trans (Nat.le_add_right _ _)))).trans (naturalInput a ha),
      inputFit.trans (Nat.le_add_right _ _), rowsFit.trans (Nat.le_add_right _ _)⟩
  have empty : PrimPairOutputFrame I layout.output [] finish := by
    refine ⟨?_, ?_, ?_, fun i => Fin.elim0 i⟩
    · exact (stable 43 (by decide) (by decide) (by decide)).trans ((unchanged 43 (by decide) (by decide)).symm.trans outputBase)
    · change Function.update (Function.update weighted.nr 38 layout.output) 39 0 38 = _
      simp
    · change Function.update (Function.update weighted.nr 38 layout.output) 39 0 39 = _
      simp
  have steps : 16 + ((5 * (2 * n) + 2) + ((5 * I.graph.q + 2) + 3)) =
      10 * n + 5 * I.graph.q + 23 := by ring
  refine ⟨finish, by simpa only [initializePrimArraysBlock, steps] using
    (configurePrimArrays_runs entry running).append (clear.append (weightRun.append keepRun)), ?_⟩
  refine ⟨bits, summed, rewrites 26 _ (by decide) (by decide) (by decide) ?_,
    rewrites 24 _ (by decide) (by decide) (by decide) labelBase,
    rewrites 41 _ (by decide) (by decide) (by decide) ?_, rewrites 42 _ (by decide) (by decide) (by decide) ?_,
    rewrites 9 _ (by decide) (by decide) (by decide) rfl, rewrites 45 _ (by decide) (by decide) (by decide) ?_,
    empty, ?_, ?_, lower, ?_⟩
  · simp [configured, configurePrimState, oldBits, frame.dimension, frame.one, cells, n]
  · simp [configured, configurePrimState, frame.dimension, labelBase, layout, adjacentPrimLayout]
  · simp [configured, configurePrimState, frame.dimension, labelBase, layout, adjacentPrimLayout]
  · simp [configured, configurePrimState, frame.dimension, zero]
  · intro u
    rw [mem, if_pos]
    have bound := u.isLt
    omega
  · intro u
    rw [mem, if_pos]
    have bound := u.isLt
    change layout.support ≤ layout.support + n + u.val ∧ layout.support + n + u.val < layout.support + 2 * n
    omega
  · change Function.update weighted.rm (weighted.nr 51) (weighted.rr 0) = _
    rw [weightsRm, clearRm, reserveReal, total] <;> rfl

end VehicleRoutingSurvey.Routing
end RppSource_PrimInitialization

/-! runtime/PrimSweep.lean -/
section RppSource_PrimSweep
namespace VehicleRoutingSurvey.Routing

private theorem PrimRoundFrame.keepCounter {I : Service} {layout : PrimLayout I.graph.n}
    {required seen : Fin I.graph.n → Bool} {cut : Finset (RequiredComponent I)} {pairs : List (PrimPair I)}
    {s t : ArithmeticState} (frame : PrimRoundFrame I layout required seen cut pairs s)
    (register : ∀ r, r ≠ 32 → t.nr r = s.nr r) (natural : t.nm = s.nm) (real : t.rm = s.rm) :
    PrimRoundFrame I layout required seen cut pairs t := by
  have old := frame.mask
  have mask : PrimMaskFrame I.graph.n layout.rows layout.matrix layout.support layout.visits
      layout.mask required seen t :=
    ⟨old.floyd.preserved (fun r _ upper => register r (by omega)) natural,
      (register 40 (by decide)).trans old.supportBase, (register 41 (by decide)).trans old.visitedBase,
      (register 42 (by decide)).trans old.maskBase, old.supportBeforeMask, old.visitsBeforeMask,
      old.rowsBeforeMask, fun v => (congrFun natural _).trans (old.supportBit v),
      fun v => (congrFun natural _).trans (old.visitedBit v)⟩
  exact ⟨mask, (register 24 (by decide)).trans frame.labelBase,
    (register 33 (by decide)).trans frame.zero, by rw [natural]; exact frame.labels,
    frame.supported, frame.selected,
    ⟨(register 43 (by decide)).trans frame.output.baseAt, (register 38 (by decide)).trans frame.output.cursor,
      (register 39 (by decide)).trans frame.output.length, by rw [natural]; exact frame.output.words⟩,
    by rw [real]; exact frame.distances, by rw [real]; exact frame.sentinel⟩

private def primRoundLoop : List ArithmeticInstruction :=
  countedLoopFromZero 6 32 5 primRoundBlock

def primComponentTreeBlock : List ArithmeticInstruction :=
  appendBlock primRoundLoop primPairOutputInterface

/-- Starting from a valid Prim prefix, at most n rounds produce a minimum
component tree. The result supplies the contiguous pair-array interface for
shortest-path expansion. -/
theorem primComponentTreeBlock_correct {I : Service} {layout : PrimLayout I.graph.n} {root : Fin I.graph.n}
    {required seen : Fin I.graph.n → Bool} {cut : Finset (RequiredComponent I)} {pairs : List (PrimPair I)}
    {s : ArithmeticState} (frame : PrimRoundFrame I layout required seen cut pairs s)
    (current : PrimPrefix I root cut pairs) (undirected : Undirected I.graph)
    (entry : s.pc = 0) (running : s.halted = false) :
    ∃ (t : ArithmeticState) (tree : List (PrimPair I)) (steps : ℕ),
      BlockRuns primComponentTreeBlock steps s t ∧ t.halted = false ∧
      steps ≤ 28 * I.graph.n ^ 3 + 22 * I.graph.n ^ 2 + 37 * I.graph.n + 4 ∧
      MinimumComponentTree I tree ∧ FloydFrame I.graph.n layout.rows layout.matrix t ∧
      t.nr 34 = layout.output ∧ t.nr 35 = tree.length ∧ t.nr 26 = s.nr 26 ∧
      t.rm = s.rm ∧ (∀ k < layout.labels, t.nm k = s.nm k) ∧
      ∀ i : Fin tree.length,
        t.nm (layout.output + 2 * i.val) = (tree.get i).1.val ∧
        t.nm (layout.output + 2 * i.val + 1) = (tree.get i).2.val := by
  classical
  let n := I.graph.n
  let componentCount := (activeRequiredComponents I).card
  let budget := 28 * n ^ 2 + 22 * n + 34
  let inv (i : ℕ) (m : ArithmeticState) : Prop :=
    m.pc = 0 ∧ m.halted = false ∧ m.nr 32 = i ∧ m.nr 26 = s.nr 26 ∧ m.rm = s.rm ∧
    (∀ k < layout.labels, m.nm k = s.nm k) ∧
    ∃ (cut : Finset (RequiredComponent I)) (pairs : List (PrimPair I)) (seen : Fin n → Bool),
      PrimRoundFrame I layout required seen cut pairs m ∧
      PrimPrefix I root cut pairs ∧ min i componentCount ≤ cut.card
  let first := {s with pc := 0, nr := Function.update s.nr 32 0}
  have firstFrame : PrimRoundFrame I layout required seen cut pairs first :=
    frame.keepCounter (fun _ different => Function.update_of_ne different _ _) rfl rfl
  have initial : inv 0 first :=
    ⟨rfl, running, by simp [first], rfl, rfl, fun _ _ => rfl,
      cut, pairs, seen, firstFrame, current, by simp⟩
  have control (i : ℕ) (m : ArithmeticState) (h : inv i m) :
      m.pc = 0 ∧ m.halted = false ∧ m.nr 32 = i ∧ m.nr 5 = n := by
    obtain ⟨pc, ready, index, _, _, _, _, _, _, f, _, _⟩ := h
    exact ⟨pc, ready, index, f.mask.floyd.dimension⟩
  have substep (i : ℕ) (_ : i < n) (m : ArithmeticState) (h : inv i m) :
      ∃ t ticks, ticks ≤ budget ∧ BlockRuns primRoundBlock ticks m t ∧ t.halted = false ∧
        inv (i + 1) {t with pc := 0, nr := Function.update t.nr 32 (t.nr 32 + t.nr 6)} := by
    obtain ⟨pc, ready, index, oldPaths, oldReal, oldMemory, oldCut, oldPairs, oldSeen, f, prior, progress⟩ := h
    obtain ⟨nextCut, nextPairs, nextSeen, ticks, t, round⟩ :=
      primRoundBlock_correct f prior undirected pc ready
    let next := {t with pc := 0, nr := Function.update t.nr 32 (t.nr 32 + t.nr 6)}
    have nextFrame : PrimRoundFrame I layout required nextSeen nextCut nextPairs next :=
      round.frame.keepCounter (fun _ different => Function.update_of_ne different _ _) rfl rfl
    have nextProgress : min (i + 1) componentCount ≤ nextCut.card := by
      rcases round.progress with complete | advance
      · rw [complete]
        exact Nat.min_le_right _ _
      · rw [advance]
        have stepBound : min (i + 1) componentCount ≤ min i componentCount + 1 := by
          by_cases before : i ≤ componentCount
          · rw [Nat.min_eq_left before]
            exact Nat.min_le_left _ _
          · rw [Nat.min_eq_right (Nat.le_of_lt (Nat.lt_of_not_ge before))]
            exact (Nat.min_le_right _ _).trans (Nat.le_succ _)
        exact stepBound.trans (Nat.add_le_add_right progress 1)
    refine ⟨t, ticks, round.bound, round.run, round.running, rfl, round.running, ?_, ?_,
      round.realMemory.trans oldReal, fun k below => (round.previousNatural k below).trans (oldMemory k below),
      nextCut, nextPairs, nextSeen, nextFrame, round.prefixValid, nextProgress⟩
    · simp [next, round.loopIndex, index, round.frame.mask.floyd.one]
    · exact round.pathsBase.trans oldPaths
  obtain ⟨last, actual, done, bound, loop⟩ :=
    countedLoopFromZero_bounded 6 32 5 n budget primRoundBlock inv entry running initial control substep
  obtain ⟨_, lastReady, _, lastPaths, lastReal, lastMemory, completed, tree, lastSeen, lastFrame, prefixValid,
    full⟩ := done
  have countFits : componentCount ≤ n := requiredComponentCount_le_vertices I
  have all : completed = activeRequiredComponents I := by
    apply Finset.eq_of_subset_of_card_le prefixValid.activeOnly
    simpa only [Nat.min_eq_right countFits] using full
  have minimum := prefixValid.finish all
  let startOutput := {last with pc := 0}
  have layoutRun : BlockRuns primRoundLoop actual s
      (relocateState 1 {last with pc := (countedLoop 6 32 5 primRoundBlock).length}) := loop
  obtain ⟨out, expose, doneReady, base, count, outNm, outRm, _, stable⟩ :=
    primPairOutputInterface_correct (s := startOutput) rfl lastReady lastFrame.zero
  let finish := relocateState primRoundLoop.length out
  have steps : 1 + (n * (budget + 3) + 1) + 2 =
      28 * n ^ 3 + 22 * n ^ 2 + 37 * n + 4 := by
    dsimp only [budget]
    ring
  have finalBound : actual + 2 ≤ 28 * n ^ 3 + 22 * n ^ 2 + 37 * n + 4 :=
    (Nat.add_le_add_right bound 2).trans_eq steps
  have fixed (r : ℕ) (lo : 3 ≤ r) (hi : r < 7) : out.nr r = last.nr r :=
    stable r (by omega) (by omega)
  have floyd : FloydFrame n layout.rows layout.matrix finish :=
    lastFrame.mask.floyd.preserved fixed outNm
  refine ⟨finish, tree, actual + 2, by simpa only [primComponentTreeBlock] using layoutRun.append expose,
    doneReady, finalBound, minimum, floyd, base.trans lastFrame.output.baseAt,
    count.trans lastFrame.output.length, (stable 26 (by decide) (by decide)).trans lastPaths,
    outRm.trans lastReal, fun k before => (congrFun outNm k).trans (lastMemory k before), ?_⟩
  intro i
  exact ⟨(congrFun outNm _).trans (lastFrame.output.words i).1,
    (congrFun outNm _).trans (lastFrame.output.words i).2⟩

end VehicleRoutingSurvey.Routing
end RppSource_PrimSweep

/-! runtime/PrimFromLabels.lean -/
section RppSource_PrimFromLabels
namespace VehicleRoutingSurvey.Routing

def primFromLabelsBlock : List ArithmeticInstruction :=
  appendBlock initializePrimArraysBlock
    (appendBlock primSupportScanBlock (appendBlock markPrimTargetBlock primComponentTreeBlock))

/-- Starting from the verified component labels and shortest distances,
produce a minimum component tree and the path expander's pair array. -/
theorem primFromLabelsBlock_correct {I : Service} {rows matrix labels next : ℕ} {s : ArithmeticState}
    (rural : Rural I) (requiredLinks : I.links.Nonempty) (frame : FloydFrame I.graph.n rows matrix s)
    (entry : s.pc = 0) (running : s.halted = false)
    (labelBase : s.nr 24 = labels) (oldBits : s.nr 37 = next + I.graph.n ^ 2) (zero : s.nr 33 = 0)
    (rowsFit : rows + I.graph.n ≤ labels) (inputFit : 2 + 3 * I.graph.q ≤ labels)
    (weightsFit : I.graph.q ≤ matrix)
    (naturalInput : ∀ k < 2 + 3 * I.graph.q, s.nm k = (ruralNatInput I)[k]?.getD 0)
    (weightInput : ∀ e : Fin I.graph.q, s.rm e.val = I.graph.weight e)
    (distances : ∀ p : PrimPair I, s.rm (matrix + primPairOffset p) = distance I.graph p.1 p.2)
    (classes : ∀ u v : Fin I.graph.n, s.nm (labels + u.val) = s.nm (labels + v.val) ↔
      sameComponent I u v) :
    let layout := adjacentPrimLayout I.graph.n rows matrix labels rowsFit
    ∃ (t : ArithmeticState) (tree : List (PrimPair I)) (steps : ℕ),
      BlockRuns primFromLabelsBlock steps s t ∧ t.halted = false ∧
      steps ≤ 28 * I.graph.n ^ 3 + 22 * I.graph.n ^ 2 + 58 * I.graph.n + 20 * I.graph.q + 33 ∧
      MinimumComponentTree I tree ∧ FloydFrame I.graph.n rows matrix t ∧
      t.nr 34 = layout.output ∧ t.nr 35 = tree.length ∧ t.nr 26 = next ∧
      (∀ k < labels, t.nm k = s.nm k) ∧
      (∀ p : PrimPair I, t.rm (matrix + primPairOffset p) = distance I.graph p.1 p.2) ∧
      (∀ e : Fin I.graph.q, t.rm e.val = I.graph.weight e) ∧
      ∀ i : Fin tree.length,
        t.nm (layout.output + 2 * i.val) = (tree.get i).1.val ∧
        t.nm (layout.output + 2 * i.val + 1) = (tree.get i).2.val := by
  classical
  intro layout
  let n := I.graph.n
  obtain ⟨seeded, seedRun, seed⟩ := initializePrimArraysBlock_correct frame rural.1.1 entry running
    labelBase oldBits zero rowsFit inputFit naturalInput weightInput
  let scanning := {seeded with pc := 0}
  let f := seed.frame
  have scanFrame : PrimSupportFrame I rows matrix layout.support scanning :=
    ⟨⟨f.floyd.tableBase, f.floyd.matrixBase, f.floyd.dimension, f.floyd.one, f.floyd.rows⟩,
      f.count, f.base, f.zero, f.input, f.inputBelow, f.rowsBelow⟩
  obtain ⟨found, root, supportRun, supportReady, supportFrame, supportFixed, rootAt, neededRoot,
    supportReal, _, supportMemory, supportFlags⟩ :=
    primSupportScanBlock_correct scanFrame rfl seed.running seed.cursor seed.noRoot seed.supportZeros requiredLinks
  have beforeSupport (k : ℕ) (before : k < layout.support) : found.nm k = s.nm k :=
    (supportMemory k (fun h => (not_le.mpr before) h.1)).trans (seed.beforeSupport k before)
  have labelRead (u : Fin n) : found.nm (labels + u.val) = s.nm (labels + u.val) :=
    beforeSupport _ ((Nat.add_lt_add_left u.isLt _).trans_le layout.labelsBelowSupport)
  have foundComponents (u v : Fin n) :
      found.nm (labels + u.val) = found.nm (labels + v.val) ↔ sameComponent I u v := by
    rw [labelRead u, labelRead v]
    exact classes u v
  have notYet (u : Fin n) : found.nm (layout.visits + u.val) = 0 := by
    have leAddress : layout.support + n ≤ layout.visits + u.val :=
      layout.supportBelowVisits.trans (Nat.le_add_right _ _)
    exact (supportMemory _ (fun inSupport => (not_lt.mpr leAddress) inSupport.2)).trans
      (seed.visitedZeros u)
  let marking := {found with pc := 0}
  have labelsBeforeVisits : labels + n ≤ layout.visits :=
    layout.labelsBelowSupport.trans ((Nat.le_add_right _ _).trans layout.supportBelowVisits)
  obtain ⟨marked, markRun, markReady, markFixed, markReal, _, markKeeps, markedFlag⟩ :=
    markPrimTargetBlock_correct (s := marking) rfl supportReady supportFrame.floyd.dimension
      supportFrame.floyd.one supportFrame.zero ((supportFixed 24 (by decide)).trans seed.labelBase)
      ((supportFixed 41 (by decide)).trans seed.visitedBase) root rootAt labelsBeforeVisits
  let start := {marked with pc := 0}
  let required (v : Fin n) : Bool := decide (v ∈ requiredVertices I)
  let cut : Finset (RequiredComponent I) := {requiredComponent I root}
  let seen (v : Fin n) : Bool := decide (v ∈ requiredVertices I ∧ requiredComponent I v ∈ cut)
  have belowVisits (k : ℕ) (below : k < layout.visits) : marked.nm k = found.nm k :=
    markKeeps k (fun possible => (not_le.mpr below) possible.1)
  have readMarked (u : Fin n) : marked.nm (labels + u.val) = s.nm (labels + u.val) :=
    (belowVisits _ ((Nat.add_lt_add_left u.isLt _).trans_le labelsBeforeVisits)).trans (labelRead u)
  have currentFloyd : FloydFrame n rows matrix start := by
    refine ⟨(markFixed 3 (by decide) (by decide) (by decide)).trans supportFrame.floyd.tableBase,
      (markFixed 4 (by decide) (by decide) (by decide)).trans supportFrame.floyd.matrixBase,
      (markFixed 5 (by decide) (by decide) (by decide)).trans supportFrame.floyd.dimension,
      (markFixed 6 (by decide) (by decide) (by decide)).trans supportFrame.floyd.one, ?_⟩
    intro i hi
    exact (belowVisits _ ((Nat.add_lt_add_left hi _).trans_le (rowsFit.trans
      ((Nat.le_add_right _ _).trans labelsBeforeVisits)))).trans (supportFrame.floyd.rows i hi)
  have supportBits (u : Fin n) : start.nm (layout.support + u.val) = if required u then 1 else 0 := by
    change marked.nm _ = _
    rw [belowVisits _ ((Nat.add_lt_add_left u.isLt _).trans_le layout.supportBelowVisits), supportFlags]
    simp [required]
  have markedBits (u : Fin n) : start.nm (layout.visits + u.val) = if seen u then 1 else 0 := by
    have flag := markPrimComponent_flag (∅ : Finset (RequiredComponent I))
      (fun v => found.nm (labels + v.val)) (fun v => found.nm (layout.visits + v.val))
      foundComponents (fun v => by simp [notYet]) root neededRoot u
    change marked.nm _ = _
    rw [markedFlag]
    change (if found.nm (labels + u.val) = found.nm (labels + root.val) then 1
      else found.nm (layout.visits + u.val)) = if seen u then 1 else 0
    simpa [seen, cut] using flag
  have initMask : PrimMaskFrame n rows matrix layout.support layout.visits layout.mask required seen start :=
    ⟨currentFloyd,
      (markFixed 40 (by decide) (by decide) (by decide)).trans supportFrame.base,
      (markFixed 41 (by decide) (by decide) (by decide)).trans ((supportFixed 41 (by decide)).trans seed.visitedBase),
      (markFixed 42 (by decide) (by decide) (by decide)).trans ((supportFixed 42 (by decide)).trans seed.maskBase),
      layout.supportBelowVisits.trans ((Nat.le_add_right _ _).trans layout.visitsBelowMask),
      layout.visitsBelowMask, rowsFit.trans ((Nat.le_add_right _ _).trans
        (labelsBeforeVisits.trans ((Nat.le_add_right _ _).trans layout.visitsBelowMask))),
      supportBits, markedBits⟩
  have storedReal : start.rm = Function.update s.rm (matrix + n ^ 2) (1 + (ruralRealInput I).sum) :=
    (markReal.trans supportReal).trans seed.real
  have stillDistances (p : PrimPair I) : start.rm (matrix + primPairOffset p) = distance I.graph p.1 p.2 := by
    rw [storedReal, Function.update_of_ne (Nat.ne_of_lt (Nat.add_lt_add_left (primPairOffset_lt p) _))]
    exact distances p
  have high (p : PrimPair I) : distance I.graph p.1 p.2 < start.rm (matrix + n ^ 2) := by
    rw [storedReal, Function.update_self]
    simpa [ruralRealInput, ← List.ofFn_eq_map, List.sum_ofFn] using
      distance_lt_weight_sentinel rural.1 rural.2.1 p.1 p.2
  have initOutput : PrimPairOutputFrame I layout.output [] start :=
    ⟨(markFixed 43 (by decide) (by decide) (by decide)).trans ((supportFixed 43 (by decide)).trans seed.output.baseAt),
      (markFixed 38 (by decide) (by decide) (by decide)).trans ((supportFixed 38 (by decide)).trans seed.output.cursor),
      (markFixed 39 (by decide) (by decide) (by decide)).trans ((supportFixed 39 (by decide)).trans seed.output.length),
      fun i => Fin.elim0 i⟩
  have initFrame : PrimRoundFrame I layout required seen cut [] start :=
    ⟨initMask, (markFixed 24 (by decide) (by decide) (by decide)).trans ((supportFixed 24 (by decide)).trans seed.labelBase),
      (markFixed 33 (by decide) (by decide) (by decide)).trans supportFrame.zero,
      fun u v => by
        change start.nm (labels + u.val) = start.nm (labels + v.val) ↔ sameComponent I u v
        rw [show start.nm _ = _ from readMarked u, show start.nm _ = _ from readMarked v]
        exact classes u v,
      fun v => by simp [required], fun v => by simp [seen], initOutput, stillDistances, high⟩
  obtain ⟨t, tree, actual, treeRun, finalReady, treeBound, minimum, floyd, base, count, pathsBase,
    resultReal, resultNatural, words⟩ :=
    primComponentTreeBlock_correct initFrame (primPrefix_initial root neededRoot) rural.2.2.1 rfl markReady
  let finish := relocateState initializePrimArraysBlock.length (relocateState primSupportScanBlock.length
    (relocateState markPrimTargetBlock.length t))
  have run := seedRun.append (supportRun.append (markRun.append treeRun))
  have ticks : (10 * n + 5 * I.graph.q + 23) + ((15 * I.graph.q + 2) + ((11 * n + 4) +
      (28 * n ^ 3 + 22 * n ^ 2 + 37 * n + 4))) =
      28 * n ^ 3 + 22 * n ^ 2 + 58 * n + 20 * I.graph.q + 33 := by ring
  have budget := (Nat.add_le_add_left (Nat.add_le_add_left
    (Nat.add_le_add_left treeBound (11 * n + 4)) (15 * I.graph.q + 2)) (10 * n + 5 * I.graph.q + 23)).trans_eq ticks
  have finalFloyd : FloydFrame n rows matrix finish := floyd.preserved (fun _ _ _ => rfl) rfl
  refine ⟨finish, tree, _, by simpa only [primFromLabelsBlock] using run, finalReady, budget,
    minimum, finalFloyd, base, count,
    pathsBase.trans ((markFixed 26 (by decide) (by decide) (by decide)).trans
      ((supportFixed 26 (by decide)).trans seed.nextBase)), ?_, ?_, ?_, words⟩
  · intro k earlier
    exact (resultNatural k earlier).trans
      ((belowVisits k (earlier.trans_le ((Nat.le_add_right _ _).trans labelsBeforeVisits))).trans
        (beforeSupport k (earlier.trans_le (Nat.le_add_right _ _))))
  · intro p
    exact (congrFun resultReal _).trans (stillDistances p)
  · intro e
    change t.rm e.val = I.graph.weight e
    rw [resultReal, storedReal, Function.update_of_ne (Nat.ne_of_lt
      (e.isLt.trans_le (weightsFit.trans (Nat.le_add_right _ _))))]
    exact weightInput e

end VehicleRoutingSurvey.Routing
end RppSource_PrimFromLabels

/-! runtime/PrimAfterPaths.lean -/
section RppSource_PrimAfterPaths
namespace VehicleRoutingSurvey.Routing

def minimumTreeAfterPathsBlock : List ArithmeticInstruction :=
  appendBlock requiredComponentsAfterPathsBlock primFromLabelsBlock

/-- Classify the required components and select their minimum-cost connecting
tree. The shortest-path pointers and the input records remain available for
expanding the output pairs into traversals. -/
theorem minimumTreeAfterPathsBlock_correct {I : Service} {rows matrix next : ℕ}
    {s : ArithmeticState} (rural : Rural I) (requiredLinks : I.links.Nonempty)
    (frame : FloydFrame I.graph.n rows matrix s) (nextAt : s.nr 26 = next)
    (input : ∀ k < 2 + 3 * I.graph.q, s.nm k = (ruralNatInput I)[k]?.getD 0)
    (inputBefore : 2 + 3 * I.graph.q ≤ next) (rowsBefore : rows + I.graph.n ≤ next)
    (weightsBefore : I.graph.q ≤ matrix)
    (weights : ∀ e : Fin I.graph.q, s.rm e.val = I.graph.weight e)
    (distances : ∀ p : PrimPair I, s.rm (matrix + primPairOffset p) = distance I.graph p.1 p.2)
    (entry : s.pc = 0) (running : s.halted = false) :
    ∃ (t : ArithmeticState) (tree : List (PrimPair I)) (steps output : ℕ),
      BlockRuns minimumTreeAfterPathsBlock steps s t ∧ t.halted = false ∧
      steps ≤ 40 * I.graph.n ^ 3 + 41 * I.graph.n ^ 2 + 68 * I.graph.n + 35 * I.graph.q + 50 ∧
      MinimumComponentTree I tree ∧ FloydFrame I.graph.n rows matrix t ∧
      t.nr 34 = output ∧ t.nr 35 = tree.length ∧ t.nr 26 = next ∧
      next + I.graph.n ^ 2 ≤ output ∧
      (∀ k < next + I.graph.n ^ 2, t.nm k = s.nm k) ∧
      (∀ p : PrimPair I, t.rm (matrix + primPairOffset p) = distance I.graph p.1 p.2) ∧
      (∀ e : Fin I.graph.q, t.rm e.val = I.graph.weight e) ∧
      ∀ i : Fin tree.length,
        t.nm (output + 2 * i.val) = (tree.get i).1.val ∧
        t.nm (output + 2 * i.val + 1) = (tree.get i).2.val := by
  let n := I.graph.n
  let bits := next + n ^ 2
  let labels := bits + n ^ 2
  obtain ⟨labeled, labelRun, labelReady, labelFrame, labelReal, _, labelKeeps, classes⟩ :=
    requiredComponentsAfterPathsBlock_correct frame rural.1.1 nextAt input inputBefore rowsBefore entry running
  let primStart := {labeled with pc := 0}
  have rowsFit : rows + n ≤ labels :=
    (rowsBefore.trans (Nat.le_add_right _ _)).trans (Nat.le_add_right _ _)
  have inputFit : 2 + 3 * I.graph.q ≤ labels :=
    (inputBefore.trans (Nat.le_add_right _ _)).trans (Nat.le_add_right _ _)
  have primInput (k : ℕ) (hk : k < 2 + 3 * I.graph.q) :
      primStart.nm k = (ruralNatInput I)[k]?.getD 0 :=
    (labelKeeps k (hk.trans_le (inputBefore.trans (Nat.le_add_right _ _)))).trans (input k hk)
  have primWeights (e : Fin I.graph.q) : primStart.rm e.val = I.graph.weight e :=
    (congrFun labelReal e.val).trans (weights e)
  have primDistances (p : PrimPair I) :
      primStart.rm (matrix + primPairOffset p) = distance I.graph p.1 p.2 :=
    (congrFun labelReal _).trans (distances p)
  have primFloyd : FloydFrame n rows matrix primStart := labelFrame.floyd.preserved (fun _ _ _ => rfl) rfl
  obtain ⟨marked, tree, steps, primRun, primReady, stepBound, minimum, primFrame, outputAt,
    countAt, pathsAt, primKeeps, shortest, finalWeights, pairWords⟩ :=
    primFromLabelsBlock_correct (s := primStart) rural requiredLinks primFloyd rfl labelReady
      labelFrame.labelBase labelFrame.bitBase labelFrame.zero rowsFit inputFit weightsBefore
      primInput primWeights primDistances classes
  let layout := adjacentPrimLayout n rows matrix labels rowsFit
  let finish := relocateState requiredComponentsAfterPathsBlock.length marked
  have run := labelRun.append primRun
  have budget : (12 * n ^ 3 + 19 * n ^ 2 + 10 * n + 15 * I.graph.q + 17) + steps ≤
      40 * n ^ 3 + 41 * n ^ 2 + 68 * n + 35 * I.graph.q + 50 := by
    calc
      _ ≤ (12 * n ^ 3 + 19 * n ^ 2 + 10 * n + 15 * I.graph.q + 17) +
          (28 * n ^ 3 + 22 * n ^ 2 + 58 * n + 20 * I.graph.q + 33) :=
        Nat.add_le_add_left stepBound _
      _ = _ := by ring
  have finalFrame : FloydFrame n rows matrix finish := primFrame.preserved (fun _ _ _ => rfl) rfl
  have outputAfterBits : bits ≤ layout.output := by
    change bits ≤ bits + n ^ 2 + n + n + n + n ^ 2
    omega
  refine ⟨finish, tree, _, layout.output, by simpa only [minimumTreeAfterPathsBlock] using run,
    primReady, budget, minimum, finalFrame, outputAt, countAt, pathsAt, outputAfterBits, ?_,
    shortest, finalWeights, pairWords⟩
  intro k hk
  exact (primKeeps k (hk.trans_le (Nat.le_add_right _ _))).trans (labelKeeps k hk)

end VehicleRoutingSurvey.Routing
end RppSource_PrimAfterPaths

/-! runtime/OccurrenceArray.lean -/
section RppSource_OccurrenceArray
namespace VehicleRoutingSurvey.Routing

variable {G : Network}

/-- Consecutive natural cells contain the original link IDs of a list
of edge occurrences. Parallel links and repeated IDs remain distinct
occurrences. -/
def OccurrenceArray {q : ℕ} (memory : ℕ → ℕ) (base : ℕ) (edges : List (Fin q)) : Prop :=
  ∀ i (valid : i < edges.length), memory (base + i) = edges[i].val

theorem OccurrenceArray.append {memory : ℕ → ℕ} {base q : ℕ}
    {first second : List (Fin q)} (left : OccurrenceArray memory base first)
    (right : OccurrenceArray memory (base + first.length) second) :
    OccurrenceArray memory base (first ++ second) := by
  intro i valid
  by_cases old : i < first.length
  · exact (left i old).trans (congrArg Fin.val (List.getElem_append_left' old second))
  · have past : first.length ≤ i := Nat.le_of_not_gt old
    have inside : i - first.length < second.length := by
      simp only [List.length_append] at valid
      omega
    calc
      memory (base + i) = memory (base + first.length + (i - first.length)) := by
        congr 1
        omega
      _ = second[i - first.length].val := right (i - first.length) inside
      _ = ((first ++ second)[i]).val :=
        congrArg Fin.val ((List.getElem_append_right past (h₂ := valid)).symm)

theorem OccurrenceArray.preservedBelow {memory other : ℕ → ℕ} {base bound q : ℕ}
    {edges : List (Fin q)} (array : OccurrenceArray memory base edges)
    (fits : base + edges.length ≤ bound) (below : ∀ a < bound, other a = memory a) :
    OccurrenceArray other base edges := by
  intro i valid
  exact (below _ ((Nat.add_lt_add_left valid _).trans_le fits)).trans (array i valid)

theorem OccurrenceArray.appendStore {memory : ℕ → ℕ} {base q : ℕ}
    {edges : List (Fin q)} (array : OccurrenceArray memory base edges) (edge : Fin q) :
    OccurrenceArray (Function.update memory (base + edges.length) edge.val) base (edges ++ [edge]) := by
  have old : OccurrenceArray (Function.update memory (base + edges.length) edge.val) base edges :=
    array.preservedBelow le_rfl (fun _ valid => Function.update_of_ne (Nat.ne_of_lt valid) _ _)
  apply old.append
  intro i valid
  have zero : i = 0 := by simp at valid; omega
  subst i
  simp

theorem occurrenceArray_ofTraversals {memory : ℕ → ℕ} {base : ℕ} {walk : List (Traversal G)}
    (stored : ∀ i (valid : i < walk.length), memory (base + i) = walk[i].1.val) :
    OccurrenceArray memory base (walk.map Prod.fst) := by
  intro i valid
  have inside : i < walk.length := by simpa using valid
  simpa using stored i inside

end VehicleRoutingSurvey.Routing
end RppSource_OccurrenceArray

/-! runtime/RequiredOccurrences.lean -/
section RppSource_RequiredOccurrences
namespace VehicleRoutingSurvey.Routing

private def readRequiredFlagBlock : List ArithmeticInstruction :=
  [.natLoad 40 39, .natAdd 39 39 6, .natAdd 39 39 6, .natAdd 39 39 6]

private def readRequiredFlagResult (s : ArithmeticState) : ArithmeticState :=
  {s with
    pc := 4
    nr := Function.update (Function.update s.nr 40 (s.nm (s.nr 39))) 39
      (s.nr 39 + s.nr 6 + s.nr 6 + s.nr 6)}

private theorem readRequiredFlag_runs (s : ArithmeticState)
    (entry : s.pc = 0) (running : s.halted = false) :
    BlockRuns readRequiredFlagBlock 4 s (readRequiredFlagResult s) := by
  refine ⟨?_, ?_, rfl⟩
  · intro i less
    interval_cases i <;> simp [readRequiredFlagBlock, arithmeticStep, entry, running,
      Function.iterate_succ_apply']
  · simp [readRequiredFlagBlock, readRequiredFlagResult, arithmeticStep, entry, running,
      Function.iterate_succ_apply', Function.update_idem]

private def appendRequiredId : List ArithmeticInstruction :=
  [.natStore 29 38, .natAdd 29 29 6]

private def appendRequiredIdResult (s : ArithmeticState) : ArithmeticState :=
  {s with
    pc := 2
    nr := Function.update s.nr 29 (s.nr 29 + s.nr 6)
    nm := Function.update s.nm (s.nr 29) (s.nr 38)}

private theorem appendRequiredId_runs (s : ArithmeticState)
    (entry : s.pc = 0) (running : s.halted = false) :
    BlockRuns appendRequiredId 2 s (appendRequiredIdResult s) := by
  refine ⟨?_, ?_, rfl⟩
  · intro i less
    interval_cases i <;> simp [appendRequiredId, arithmeticStep, entry, running,
      Function.iterate_succ_apply']
  · simp [appendRequiredId, appendRequiredIdResult, arithmeticStep, entry, running,
      Function.iterate_succ_apply']

def scanRequiredOccurrenceBlock : List ArithmeticInstruction :=
  appendBlock readRequiredFlagBlock (branchOnUnequal 40 28 appendRequiredId)

private theorem scanRequiredOccurrenceBlock_correct (s : ArithmeticState)
    (entry : s.pc = 0) (running : s.halted = false) (one : s.nr 6 = 1) (zero : s.nr 28 = 0) :
    ∃ t steps, steps ≤ 8 ∧ BlockRuns scanRequiredOccurrenceBlock steps s t ∧
      t.halted = false ∧ t.rm = s.rm ∧
      (∀ r ∉ ([29, 39, 40] : List ℕ), t.nr r = s.nr r) ∧ t.nr 39 = s.nr 39 + 3 ∧
      t.nr 29 = (if s.nm (s.nr 39) = 0 then s.nr 29 else s.nr 29 + 1) ∧
      t.nm = (if s.nm (s.nr 39) = 0 then s.nm else Function.update s.nm (s.nr 29) (s.nr 38)) := by
  let read := {readRequiredFlagResult s with pc := 0}
  have first := readRequiredFlag_runs s entry running
  have fixed (r : ℕ) (notFlag : r ≠ 40) (notCursor : r ≠ 39) : read.nr r = s.nr r := by
    simp [read, readRequiredFlagResult, Function.update_of_ne notFlag, Function.update_of_ne notCursor]
  have flag : read.nr 40 = s.nm (s.nr 39) := by simp [read, readRequiredFlagResult]
  have nextFlag : read.nr 39 = s.nr 39 + 3 := by
    simp [read, readRequiredFlagResult, one, Nat.add_assoc]
  have readZero : read.nr 28 = 0 := (fixed 28 (by decide) (by decide)).trans zero
  by_cases required : s.nm (s.nr 39) = 0
  · let skip := {read with pc := (branchOnUnequal 40 28 appendRequiredId).length}
    have skips : BlockRuns (branchOnUnequal 40 28 appendRequiredId) 2 read skip :=
      branchOnUnequal_skip 40 28 appendRequiredId read rfl running (flag.trans (required.trans readZero.symm))
    refine ⟨relocateState readRequiredFlagBlock.length skip, 6, by decide, first.append skips,
      running, rfl, ?_, nextFlag, ?_, ?_⟩
    · intro r untouched
      exact fixed r (fun eq => untouched (by simp [eq])) (fun eq => untouched (by simp [eq]))
    · change read.nr 29 = (if s.nm (s.nr 39) = 0 then s.nr 29 else s.nr 29 + 1)
      rw [if_pos required]
      exact fixed 29 (by decide) (by decide)
    · simp [required, skip, read, readRequiredFlagResult, relocateState]
  · let push := appendRequiredIdResult read
    have different : read.nr 40 ≠ read.nr 28 := by
      rw [flag, readZero]
      exact required
    have takes : BlockRuns (branchOnUnequal 40 28 appendRequiredId) 4 read (relocateState 3 push) :=
      branchOnUnequal_take 40 28 appendRequiredId (s := read) rfl running different
        (appendRequiredId_runs read rfl running)
    refine ⟨relocateState readRequiredFlagBlock.length (relocateState 3 push), 8, le_rfl,
      first.append takes, running, rfl, ?_, ?_, ?_, ?_⟩
    · intro r untouched
      have not29 : r ≠ 29 := fun eq => untouched (by simp [eq])
      have not39 : r ≠ 39 := fun eq => untouched (by simp [eq])
      have not40 : r ≠ 40 := fun eq => untouched (by simp [eq])
      change Function.update read.nr 29 (read.nr 29 + read.nr 6) r = _
      rw [Function.update_of_ne not29]
      exact fixed r not40 not39
    · simpa [push, appendRequiredIdResult, relocateState] using nextFlag
    · simp [push, appendRequiredIdResult, relocateState, required,
        fixed 29 (by decide) (by decide), fixed 6 (by decide) (by decide), one]
    · simp [push, appendRequiredIdResult, relocateState, read, readRequiredFlagResult, required]

private def initializeOccurrencesBlock : List ArithmeticInstruction :=
  [.natConst 28 0, .natLoad 10 6, .natConst 39 4, .natAdd 29 33 28]

private def initializeOccurrencesResult (s : ArithmeticState) : ArithmeticState :=
  {s with
    pc := 4
    nr := Function.update (Function.update (Function.update (Function.update s.nr 28 0)
      10 (s.nm (s.nr 6))) 39 4) 29 (s.nr 33)}

private theorem initializeOccurrences_runs (s : ArithmeticState)
    (entry : s.pc = 0) (running : s.halted = false) :
    BlockRuns initializeOccurrencesBlock 4 s (initializeOccurrencesResult s) := by
  refine ⟨?_, ?_, rfl⟩
  · intro i less
    interval_cases i <;> simp [initializeOccurrencesBlock, arithmeticStep, entry, running,
      Function.iterate_succ_apply']
  · simp [initializeOccurrencesBlock, initializeOccurrencesResult, arithmeticStep, entry, running,
      Function.iterate_succ_apply']

def requiredOccurrenceBlock : List ArithmeticInstruction :=
  appendBlock initializeOccurrencesBlock (countedLoopFromZero 6 38 10 scanRequiredOccurrenceBlock)

def requiredLinkList (I : Service) : List (Fin I.graph.q) :=
  (List.finRange I.graph.q).filter (fun e => decide (e ∈ I.links))

theorem requiredLinkList_spec (I : Service) :
    (requiredLinkList I).Nodup ∧ (requiredLinkList I).toFinset = I.links := by
  constructor
  · exact (List.nodup_finRange _).filter _
  · ext e
    simp [requiredLinkList, List.mem_finRange]

private def requiredThrough (I : Service) (i : ℕ) : List (Fin I.graph.q) :=
  ((List.finRange I.graph.q).take i).filter (fun e => decide (e ∈ I.links))

private theorem requiredThrough_succ (I : Service) {i : ℕ} (more : i < I.graph.q) :
    requiredThrough I (i + 1) =
      if (⟨i, more⟩ : Fin I.graph.q) ∈ I.links then requiredThrough I i ++ [⟨i, more⟩]
      else requiredThrough I i := by
  have inside : i < (List.finRange I.graph.q).length := by simpa using more
  rw [requiredThrough, List.take_succ_eq_append_getElem inside]
  by_cases chosen : (⟨i, more⟩ : Fin I.graph.q) ∈ I.links <;> simp [requiredThrough, chosen]

def requiredOccurrencePreserved : List ℕ := [3, 4, 5, 6, 26, 33, 34, 35]

private structure RequiredOccurrenceScan (I : Service) (input : ArithmeticState) (i : ℕ)
    (s : ArithmeticState) : Prop where
  entry : s.pc = 0
  running : s.halted = false
  index : s.nr 38 = i
  count : s.nr 10 = I.graph.q
  zero : s.nr 28 = 0
  flagCursor : s.nr 39 = 4 + 3 * i
  outputCursor : s.nr 29 = input.nr 33 + (requiredThrough I i).length
  fixed : ∀ r ∈ requiredOccurrencePreserved, s.nr r = input.nr r
  real : s.rm = input.rm
  low : ∀ a < input.nr 33, s.nm a = input.nm a
  array : OccurrenceArray s.nm (input.nr 33) (requiredThrough I i)

/-- The machine enumerates the required input links once each, in their
input order. The resulting buffer is the base of the Euler occurrence list. -/
theorem requiredOccurrenceBlock_correct {I : Service} {s : ArithmeticState}
    (entry : s.pc = 0) (running : s.halted = false) (one : s.nr 6 = 1)
    (afterInput : 2 + 3 * I.graph.q ≤ s.nr 33)
    (encoded : ∀ a < 2 + 3 * I.graph.q, s.nm a = (ruralNatInput I)[a]?.getD 0) :
    ∃ t steps, BlockRuns requiredOccurrenceBlock steps s t ∧ steps ≤ 11 * I.graph.q + 6 ∧
      t.halted = false ∧ t.nr 28 = 0 ∧ t.nr 29 = s.nr 33 + (requiredLinkList I).length ∧
      (∀ r ∈ requiredOccurrencePreserved, t.nr r = s.nr r) ∧ t.rm = s.rm ∧
      (∀ a < s.nr 33, t.nm a = s.nm a) ∧
      OccurrenceArray t.nm (s.nr 33) (requiredLinkList I) := by
  let setup := initializeOccurrencesResult s
  let start := {setup with pc := 0}
  let inv := RequiredOccurrenceScan I s
  have startCount : s.nm 1 = I.graph.q := by
    rw [encoded 1 (by omega)]
    simp [ruralNatInput]
  have initial : inv 0 {start with pc := 0, nr := Function.update start.nr 38 0} := by
    refine ⟨rfl, running, by simp, ?_, ?_, ?_, ?_, ?_, rfl, fun _ _ => rfl, ?_⟩
    · simp [start, setup, initializeOccurrencesResult, one, startCount]
    · simp [start, setup, initializeOccurrencesResult]
    · simp [start, setup, initializeOccurrencesResult]
    · simp [start, setup, initializeOccurrencesResult, requiredThrough]
    · intro r member
      have distinct (k : ℕ) (changed : k ∈ ([10, 28, 29, 38, 39] : List ℕ)) : r ≠ k := by
        rintro rfl
        simp [requiredOccurrencePreserved] at member
        simp at changed
        omega
      simp [start, setup, initializeOccurrencesResult, Function.update_of_ne (distinct 10 (by decide)),
        Function.update_of_ne (distinct 28 (by decide)), Function.update_of_ne (distinct 29 (by decide)),
        Function.update_of_ne (distinct 38 (by decide)), Function.update_of_ne (distinct 39 (by decide))]
    · intro j possible
      simp [requiredThrough] at possible
  have control (i : ℕ) (m : ArithmeticState) (ok : inv i m) :
      m.pc = 0 ∧ m.halted = false ∧ m.nr 38 = i ∧ m.nr 10 = I.graph.q :=
    ⟨ok.entry, ok.running, ok.index, ok.count⟩
  have step (i : ℕ) (more : i < I.graph.q) (m : ArithmeticState) (ok : inv i m) :
      ∃ t steps, steps ≤ 8 ∧ BlockRuns scanRequiredOccurrenceBlock steps m t ∧
        t.halted = false ∧ inv (i + 1)
          {t with pc := 0, nr := Function.update t.nr 38 (t.nr 38 + t.nr 6)} := by
    let edge : Fin I.graph.q := ⟨i, more⟩
    have mOne : m.nr 6 = 1 := (ok.fixed 6 (by decide)).trans one
    have flagAddr : m.nr 39 = 2 + 3 * edge.val + 2 := by rw [ok.flagCursor]; dsimp [edge]; omega
    have lowFlag : m.nr 39 < 2 + 3 * I.graph.q := by rw [flagAddr]; dsimp [edge]; omega
    have flag : m.nm (m.nr 39) = if edge ∈ I.links then 1 else 0 := by
      rw [ok.low _ (lowFlag.trans_le afterInput), encoded _ lowFlag, flagAddr]
      exact congrArg (fun cell => cell.getD 0)
        (ruralNatInput_link_record I edge (j := 2) (by decide))
    obtain ⟨t, steps, budget, runs, ready, real, unchanged, nextFlag, cursor, memory⟩ :=
      scanRequiredOccurrenceBlock_correct m ok.entry ok.running mOne ok.zero
    have tIndex : t.nr 38 = i := (unchanged 38 (by decide)).trans ok.index
    have tOne : t.nr 6 = 1 := (unchanged 6 (by decide)).trans mOne
    have model : requiredThrough I (i + 1) =
        if edge ∈ I.links then requiredThrough I i ++ [edge] else requiredThrough I i :=
      requiredThrough_succ I more
    refine ⟨t, steps, budget, runs, ready, ?_⟩
    refine ⟨rfl, ready, by simp [tIndex, tOne], ?_, ?_, ?_, ?_, ?_, real.trans ok.real, ?_, ?_⟩
    · simpa using (unchanged 10 (by decide)).trans ok.count
    · simpa using (unchanged 28 (by decide)).trans ok.zero
    · have position : t.nr 39 = 4 + 3 * (i + 1) := by rw [nextFlag, ok.flagCursor]; omega
      simpa using position
    · change t.nr 29 = _
      rw [cursor, flag, model, ok.outputCursor]
      by_cases chosen : edge ∈ I.links <;> simp [chosen, Nat.add_assoc]
    · intro r member
      have notIndex : r ≠ 38 := by rintro rfl; simp [requiredOccurrencePreserved] at member
      have notTouched : r ∉ ([29, 39, 40] : List ℕ) := by
        intro bad
        simp [requiredOccurrencePreserved] at member
        simp at bad
        omega
      exact (Function.update_of_ne notIndex _ _).trans ((unchanged r notTouched).trans (ok.fixed r member))
    · intro a below
      change t.nm a = s.nm a
      rw [memory, flag]
      by_cases chosen : edge ∈ I.links
      · have distinct : a ≠ m.nr 29 := by rw [ok.outputCursor]; omega
        simpa [chosen, Function.update_of_ne distinct] using ok.low a below
      · simpa [chosen] using ok.low a below
    · change OccurrenceArray t.nm (s.nr 33) (requiredThrough I (i + 1))
      rw [memory, flag, model]
      by_cases chosen : edge ∈ I.links
      · simpa [chosen, ok.outputCursor, ok.index, edge] using ok.array.appendStore edge
      · simpa [chosen] using ok.array
  obtain ⟨last, elapsed, done, cap, loop⟩ :=
    countedLoopFromZero_bounded 6 38 10 I.graph.q 8 scanRequiredOccurrenceBlock inv
      (s := start) rfl running initial control step
  have whole : requiredThrough I I.graph.q = requiredLinkList I := by
    simp [requiredThrough, requiredLinkList, List.take_of_length_le]
  have bound : 4 + elapsed ≤ 11 * I.graph.q + 6 := by omega
  obtain ⟨mEntry, mRunning, mIndex, mCount, mZero, mFlag, mCursor, mFixed, mReal, mLow, mArray⟩ := done
  rw [whole] at mCursor mArray
  exact ⟨_, 4 + elapsed, (initializeOccurrences_runs s entry running).append loop, bound, mRunning,
    mZero, mCursor, mFixed, mReal, mLow, mArray⟩

end VehicleRoutingSurvey.Routing
end RppSource_RequiredOccurrences

/-! runtime/FollowLink.lean -/
section RppSource_FollowLink
namespace VehicleRoutingSurvey.Routing

/-- Load the next-edge ID for destination register 7 and source register
9. The next-edge table begins at register 26. The raw link endpoints
are still in the natural input array. -/
def loadNextLinkBlock : List ArithmeticInstruction :=
  [.natAdd 22 3 7, .natLoad 22 22, .natAdd 22 26 22, .natAdd 22 22 9,
    .natLoad 14 22, .natAdd 23 14 14, .natAdd 23 23 14,
    .natAdd 23 23 6, .natAdd 23 23 6, .natLoad 24 23,
    .natAdd 23 23 6, .natLoad 25 23]

private def loadNextLinkResult (s : ArithmeticState) : ArithmeticState :=
  let cell := s.nr 26 + s.nm (s.nr 3 + s.nr 7) + s.nr 9
  let edge := s.nm cell
  let inputCell := edge + edge + edge + s.nr 6 + s.nr 6
  let registers := Function.update (Function.update (Function.update s.nr 22 cell) 14 edge)
    23 inputCell
  {s with
    pc := 12
    nr := Function.update (Function.update (Function.update registers 24 (s.nm inputCell))
      23 (inputCell + s.nr 6))
      25 (s.nm (inputCell + s.nr 6))}

private theorem loadNextLinkBlock_runs (s : ArithmeticState) (entry : s.pc = 0)
    (running : s.halted = false) :
    BlockRuns loadNextLinkBlock 12 s (loadNextLinkResult s) := by
  refine ⟨?_, ?_, rfl⟩
  · intro i inside
    interval_cases i <;> simp [loadNextLinkBlock, arithmeticStep, entry, running,
      Function.iterate_succ_apply']
  · simp [loadNextLinkBlock, loadNextLinkResult, arithmeticStep, entry, running,
      Function.iterate_succ_apply', Function.update_idem]

/-- Orient the loaded undirected link by comparing its tail with the
current vertex. Register 15 gets the direction bit and register 16 gets
the opposite endpoint. Register 28 contains zero. -/
def orientNextLinkBlock : List ArithmeticInstruction :=
  [.natBranch 9 24 1 2, .natBranch 24 9 3 6, .jump 6,
    .natConst 15 1, .natAdd 16 25 28, .jump 9,
    .natConst 15 0, .natAdd 16 24 28, .jump 9]

private def orientNextLinkResult (s : ArithmeticState) : ArithmeticState :=
  {s with
    pc := 9
    nr := Function.update
      (Function.update s.nr 15 (if s.nr 9 = s.nr 24 then 1 else 0))
      16 ((if s.nr 9 = s.nr 24 then s.nr 25 else s.nr 24) + s.nr 28)}

private theorem orientNextLinkBlock_runs (s : ArithmeticState) (entry : s.pc = 0)
    (running : s.halted = false) :
    BlockRuns orientNextLinkBlock 5 s (orientNextLinkResult s) := by
  refine ⟨?_, ?_, rfl⟩
  · intro i inside
    by_cases lower : s.nr 9 ≤ s.nr 24
    · by_cases upper : s.nr 24 ≤ s.nr 9
      · interval_cases i <;> simp [orientNextLinkBlock, arithmeticStep, entry, running,
          Function.iterate_succ_apply', lower, upper]
      · interval_cases i <;> simp [orientNextLinkBlock, arithmeticStep, entry, running,
          Function.iterate_succ_apply', lower, upper]
    · interval_cases i <;> simp [orientNextLinkBlock, arithmeticStep, entry, running,
        Function.iterate_succ_apply', lower]
  · by_cases lower : s.nr 9 ≤ s.nr 24
    · by_cases upper : s.nr 24 ≤ s.nr 9
      · have same := Nat.le_antisymm lower upper
        simp [orientNextLinkBlock, orientNextLinkResult, arithmeticStep, entry, running,
          Function.iterate_succ_apply', lower, upper, same]
      · have different : s.nr 9 ≠ s.nr 24 := fun same => upper same.ge
        simp [orientNextLinkBlock, orientNextLinkResult, arithmeticStep, entry, running,
          Function.iterate_succ_apply', lower, upper, different]
    · have different : s.nr 9 ≠ s.nr 24 := fun same => lower same.le
      simp [orientNextLinkBlock, orientNextLinkResult, arithmeticStep, entry, running,
        Function.iterate_succ_apply', lower, different]

def followNextLinkBlock : List ArithmeticInstruction :=
  appendBlock loadNextLinkBlock orientNextLinkBlock

/-- A shortest-path pointer is decoded in seventeen arithmetic steps.
The nonloop premise ensures the direction is determined by the source. -/
theorem followNextLinkBlock_correct {G : Network} {rowOffsets distanceBase : ℕ}
    {source target : Fin G.n} {step : Traversal G} {s : ArithmeticState}
    (floyd : FloydFrame G.n rowOffsets distanceBase s)
    (sourceReg : s.nr 9 = source.val) (targetReg : s.nr 7 = target.val)
    (zero : s.nr 28 = 0) (entry : s.pc = 0) (running : s.halted = false)
    (parent : s.nm (s.nr 26 + G.n * target.val + source.val) = step.1.val)
    (starts : start G step = source) (nonloop : start G step ≠ finish G step)
    (tailCell : s.nm (2 + 3 * step.1.val) = (G.tail step.1).val)
    (headCell : s.nm (3 + 3 * step.1.val) = (G.head step.1).val) :
    ∃ t, BlockRuns followNextLinkBlock 17 s t ∧ t.halted = false ∧ t.nm = s.nm ∧ t.rm = s.rm ∧
      t.nr 14 = step.1.val ∧ t.nr 15 = (if step.2 then 1 else 0) ∧
      t.nr 16 = (finish G step).val := by
  let read := loadNextLinkResult s
  let oriented := orientNextLinkResult {read with pc := 0}
  have run := (loadNextLinkBlock_runs s entry running).append
    (orientNextLinkBlock_runs {read with pc := 0} rfl running)
  have offset : s.nm (s.nr 3 + s.nr 7) = G.n * target.val := by
    rw [floyd.tableBase, targetReg, floyd.rows _ target.isLt]
  have idReg : read.nr 14 = step.1.val := by
    simp [read, loadNextLinkResult, sourceReg, offset, parent]
  have constTail : step.1.val + step.1.val + step.1.val + 1 + 1 = 2 + 3 * step.1.val := by omega
  have constHead : step.1.val + step.1.val + step.1.val + 1 + 1 + 1 =
      3 + 3 * step.1.val := by omega
  have tailReg : read.nr 24 = (G.tail step.1).val := by
    simp [read, loadNextLinkResult, sourceReg, offset, parent, floyd.one, constTail, tailCell]
  have headReg : read.nr 25 = (G.head step.1).val := by
    simp [read, loadNextLinkResult, sourceReg, offset, parent, floyd.one, constHead, headCell]
  have readSource : read.nr 9 = source.val := by simp [read, loadNextLinkResult, sourceReg]
  have readZero : read.nr 28 = 0 := by simp [read, loadNextLinkResult, zero]
  have output : oriented.nr 15 = (if step.2 then 1 else 0) ∧
      oriented.nr 16 = (finish G step).val := by
    cases dir : step.2 with
    | false =>
      have different : source.val ≠ (G.tail step.1).val := by
        intro same
        apply nonloop
        have headIsSource : G.head step.1 = source := by simpa [start, dir] using starts
        simpa [start, finish, dir, headIsSource] using (Fin.ext same : source = G.tail step.1)
      simp [oriented, orientNextLinkResult, readSource, tailReg, different, readZero, finish, dir]
    | true =>
      have equal : source.val = (G.tail step.1).val := congrArg Fin.val
        (by simpa [start, dir] using starts.symm)
      simp [oriented, orientNextLinkResult, readSource, tailReg, headReg, equal, readZero, finish, dir]
  refine ⟨relocateState loadNextLinkBlock.length oriented, run, running, rfl, rfl, ?_, output.1, output.2⟩
  simpa [oriented, orientNextLinkResult, relocateState] using idReg

theorem followNextLinkBlock_fixed {s t : ArithmeticState}
    (run : BlockRuns followNextLinkBlock 17 s t) (entry : s.pc = 0)
    (running : s.halted = false) (r : ℕ)
    (untouched : r ∉ ([14, 15, 16, 22, 23, 24, 25] : List ℕ)) :
    t.nr r = s.nr r := by
  let read := loadNextLinkResult s
  let out := orientNextLinkResult {read with pc := 0}
  have executes := (loadNextLinkBlock_runs s entry running).append
    (orientNextLinkBlock_runs {read with pc := 0} rfl running)
  have same : t = relocateState loadNextLinkBlock.length out := run.run.symm.trans executes.run
  have different (k : ℕ) (changed : k ∈ ([14, 15, 16, 22, 23, 24, 25] : List ℕ)) :
      r ≠ k := fun eq => untouched (eq.symm ▸ changed)
  rw [same]
  simp [out, read, orientNextLinkResult, loadNextLinkResult, relocateState,
    Function.update_of_ne (different 14 (by decide)), Function.update_of_ne (different 15 (by decide)),
    Function.update_of_ne (different 16 (by decide)), Function.update_of_ne (different 22 (by decide)),
    Function.update_of_ne (different 23 (by decide)), Function.update_of_ne (different 24 (by decide)),
    Function.update_of_ne (different 25 (by decide))]

/-- Append the original link ID to the occurrence array for Euler
traversal, advance its cursor, and advance the current path vertex. -/
def appendNextOccurrenceBlock : List ArithmeticInstruction :=
  [.natStore 29 14, .natAdd 29 29 6, .natAdd 9 16 28]

private def appendNextOccurrenceResult (s : ArithmeticState) : ArithmeticState :=
  {s with
    pc := 3
    nr := Function.update (Function.update s.nr 29 (s.nr 29 + s.nr 6)) 9 (s.nr 16 + s.nr 28)
    nm := Function.update s.nm (s.nr 29) (s.nr 14)}

private theorem appendNextOccurrence_runs (s : ArithmeticState)
    (entry : s.pc = 0) (running : s.halted = false) :
    BlockRuns appendNextOccurrenceBlock 3 s (appendNextOccurrenceResult s) := by
  refine ⟨?_, ?_, rfl⟩
  · intro i less
    interval_cases i <;> simp [appendNextOccurrenceBlock, arithmeticStep, entry, running,
      Function.iterate_succ_apply']
  · simp [appendNextOccurrenceBlock, appendNextOccurrenceResult, arithmeticStep, entry, running,
      Function.iterate_succ_apply']

def followAndAppendOccurrenceBlock : List ArithmeticInstruction :=
  appendBlock followNextLinkBlock appendNextOccurrenceBlock

theorem followAndAppendOccurrenceBlock_correct {s decoded : ArithmeticState}
    (decodes : BlockRuns followNextLinkBlock 17 s decoded)
    (entry : s.pc = 0) (running : s.halted = false) (decodeReady : decoded.halted = false)
    (one : s.nr 6 = 1) (zero : s.nr 28 = 0)
    (decodedMemory : decoded.nm = s.nm) (decodedReal : decoded.rm = s.rm) :
    ∃ t, BlockRuns followAndAppendOccurrenceBlock 20 s t ∧ t.halted = false ∧
      t.nr 9 = decoded.nr 16 ∧ t.nr 29 = s.nr 29 + 1 ∧
      t.nm = Function.update s.nm (s.nr 29) (decoded.nr 14) ∧ t.rm = s.rm ∧
      ∀ r ∈ ([3, 4, 5, 6, 7, 26, 27, 28, 33, 34, 35, 36, 37] : List ℕ), t.nr r = s.nr r := by
  let ready := {decoded with pc := 0}
  let output := appendNextOccurrenceResult ready
  have runs := decodes.append (appendNextOccurrence_runs ready rfl decodeReady)
  have fixed (r : ℕ) (untouched : r ∉ ([14, 15, 16, 22, 23, 24, 25] : List ℕ)) :
      decoded.nr r = s.nr r := followNextLinkBlock_fixed decodes entry running r untouched
  have keepOne : decoded.nr 6 = 1 := (fixed 6 (by decide)).trans one
  have keepZero : decoded.nr 28 = 0 := (fixed 28 (by decide)).trans zero
  have keepCursor : decoded.nr 29 = s.nr 29 := fixed 29 (by decide)
  refine ⟨relocateState followNextLinkBlock.length output, runs, decodeReady, ?_, ?_, ?_, decodedReal, ?_⟩
  · simp [output, ready, appendNextOccurrenceResult, relocateState, keepZero]
  · simp [output, ready, appendNextOccurrenceResult, relocateState, keepOne, keepCursor]
  · simp [output, ready, appendNextOccurrenceResult, relocateState, decodedMemory, keepCursor]
  · intro r present
    have decoderUntouched : r ∉ ([14, 15, 16, 22, 23, 24, 25] : List ℕ) := by
      intro changes
      simp at present changes
      omega
    have noCurrentWrite : r ≠ 9 := by simp at present; omega
    have noCursorWrite : r ≠ 29 := by simp at present; omega
    simp [output, ready, appendNextOccurrenceResult, relocateState,
      Function.update_of_ne noCurrentWrite, Function.update_of_ne noCursorWrite, fixed r decoderUntouched]

end VehicleRoutingSurvey.Routing
end RppSource_FollowLink

/-! runtime/TightWalk.lean -/
section RppSource_TightWalk
namespace VehicleRoutingSurvey.Routing

variable {G : Network}

/-- Read next edges until the destination is reached or the requested
number of pointer steps is exhausted. -/
def followTightPointers (target : Fin G.n) (next : ∀ u, u ≠ target → Traversal G) :
    ℕ → Fin G.n → List (Traversal G)
  | 0, _ => []
  | fuel + 1, u =>
    if done : u = target then [] else
      let edge := next u done
      edge :: followTightPointers target next fuel (finish G edge)

/-- A fuel bound at least the discovery rank is enough to follow the
stored pointers to the destination. The emitted traversals are shortest
and have no repeated vertex. -/
theorem followTightPointers_correct (nonnegative : Nonnegative G)
    (target : Fin G.n) (rank : Fin G.n → ℕ) (next : ∀ u, u ≠ target → Traversal G)
    (starts : ∀ u different, start G (next u different) = u)
    (allowed : ∀ u different, G.directed (next u different).1 = false ∨
      (next u different).2 = true)
    (tight : ∀ u different, tightTraversal G target (next u different))
    (decreases : ∀ u different, rank (finish G (next u different)) < rank u)
    (fuel : ℕ) (u : Fin G.n) (enough : rank u ≤ fuel) :
    let ts := followTightPointers target next fuel u
    ShortestPath G u target ts ∧ ts.length ≤ rank u ∧
      (u :: ts.map (finish G)).Nodup ∧
      (∀ x ∈ u :: ts.map (finish G), rank x ≤ rank u) := by
  have emptyResult : ShortestPath G target target [] ∧
      ([] : List (Traversal G)).length ≤ rank target ∧
      [target].Nodup ∧ (∀ x ∈ [target], rank x ≤ rank target) := by
    exact ⟨⟨rfl, fun ss _ => pathCost_nonnegative nonnegative ss⟩, Nat.zero_le _, by simp, by simp⟩
  induction fuel generalizing u with
  | zero =>
    have atTarget : u = target := by
      by_contra different
      exact (Nat.not_lt_zero _) ((decreases u different).trans_le enough)
    subst u
    exact emptyResult
  | succ fuel ih =>
    by_cases done : u = target
    · subst u
      simpa [followTightPointers] using emptyResult
    · let edge := next u done
      let after := finish G edge
      let tail := followTightPointers target next fuel after
      have lower : rank after < rank u := decreases u done
      have tailFuel : rank after ≤ fuel :=
        Nat.le_of_lt_succ (lower.trans_le enough)
      obtain ⟨shortestTail, tailLength, tailUnique, tailRanks⟩ := ih after tailFuel
      have valid : IsPath G u (edge :: tail) target :=
        ⟨(starts u done).symm, allowed u done, shortestTail.1⟩
      have cost : pathCost G (edge :: tail) = distance G u target := by
        have exactEdge := tight u done
        rw [tightTraversal, starts u done] at exactEdge
        change G.weight edge.1 + pathCost G tail = distance G u target
        exact (congrArg (G.weight edge.1 + ·) (distance_eq_of_shortestPath shortestTail)).symm.trans
          exactEdge.symm
      have shortest : ShortestPath G u target (edge :: tail) :=
        ⟨valid, fun other path => cost.symm ▸ distance_le_pathCost nonnegative path⟩
      have length : (edge :: tail).length ≤ rank u :=
        (Nat.succ_le_succ tailLength).trans lower
      have avoids : u ∉ after :: tail.map (finish G) :=
        fun seen => (Nat.not_le_of_gt lower) (tailRanks u seen)
      simp only [followTightPointers, dif_neg done]
      refine ⟨shortest, length, List.nodup_cons.mpr ⟨avoids, tailUnique⟩, ?_⟩
      intro x seen
      rcases List.mem_cons.mp seen with rfl | inTail
      · exact le_rfl
      · exact (tailRanks x inTail).trans lower.le

/-- Every emitted edge is one looked up by the pointer follower. -/
theorem followTightPointers_uses {target : Fin G.n}
    (next : ∀ u, u ≠ target → Traversal G) (fuel : ℕ) (source : Fin G.n)
    {step : Traversal G} (seen : step ∈ followTightPointers target next fuel source) :
    ∃ u, ∃ different : u ≠ target, step = next u different := by
  induction fuel generalizing source with
  | zero => simp [followTightPointers] at seen
  | succ fuel ih =>
    by_cases done : source = target
    · simp [followTightPointers, done] at seen
    · simp only [followTightPointers, dif_neg done, List.mem_cons] at seen
      rcases seen with rfl | more
      · exact ⟨source, done, rfl⟩
      · exact ih _ more

end VehicleRoutingSurvey.Routing
end RppSource_TightWalk

/-! runtime/PathEmission.lean -/
section RppSource_PathEmission
namespace VehicleRoutingSurvey.Routing

variable {G : Network}

theorem TightStoredRow.shortestPath {target : Fin G.n} {table : DirectLinkTable G}
    {base : ℕ} {memory : ℕ → ℕ} (row : TightStoredRow target table base memory)
    (connected : Connected G) (nonnegative : Nonnegative G) (sound : DirectLinkTableSound table)
    (representative : DirectLinkRepresentatives G (tableChooses table)) (source : Fin G.n) :
    ∃ ts, ShortestPath G source target ts ∧ ts.length < G.n ∧
      ∀ edge ∈ ts, start G edge ≠ target ∧ start G edge ≠ finish G edge ∧
        memory (base + G.n * target.val + (start G edge).val) = edge.1.val := by
  obtain ⟨valid, everySource⟩ := tightSearchAfter_complete connected nonnegative target table sound representative
  let out := tightSearchAfter target table G.n
  let next (u : Fin G.n) (away : u ≠ target) : Traversal G := (row u away).choose
  have specification (u : Fin G.n) (away : u ≠ target) :
      start G (next u away) = u ∧
        (G.directed (next u away).1 = false ∨ (next u away).2 = true) ∧
        tightTraversal G target (next u away) ∧
        memory (base + G.n * target.val + u.val) = (next u away).1.val ∧
        out.rank (finish G (next u away)) < out.rank u :=
    (row u away).choose_spec
  have lengthLE : out.queue.length ≤ G.n := by simpa using valid.unique.length_le_card
  have rankBound : out.rank source < G.n :=
    (valid.ranks source (everySource source)).trans_le lengthLE
  obtain ⟨shortest, length, _, _⟩ := followTightPointers_correct nonnegative target out.rank next
    (fun u h => (specification u h).1) (fun u h => (specification u h).2.1)
    (fun u h => (specification u h).2.2.1) (fun u h => (specification u h).2.2.2.2)
    G.n source rankBound.le
  refine ⟨_, shortest, length.trans_lt rankBound, fun edge used => ?_⟩
  obtain ⟨u, away, rfl⟩ := followTightPointers_uses next G.n source used
  obtain ⟨startAt, _, _, stored, decreases⟩ := specification u away
  refine ⟨startAt.symm ▸ away, ?_, by rwa [startAt]⟩
  intro loop
  have same : finish G (next u away) = u := loop.symm.trans startAt
  rw [same] at decreases
  exact (Nat.lt_irrefl _) decreases

def emitShortestPathBlock : List ArithmeticInstruction :=
  countedLoopFromZero 6 27 5 (branchOnUnequal 9 7 followAndAppendOccurrenceBlock)

def pathEmitFixed : List ℕ := [3, 4, 5, 6, 7, 26, 28, 33, 34, 35, 36, 37]

private structure PathEmitInvariant (before : ArithmeticState) (destination : Fin G.n)
    (chosen : List (Traversal G)) (i : ℕ) (current : ArithmeticState) : Prop where
  entry : current.pc = 0
  running : current.halted = false
  index : current.nr 27 = i
  fixed : ∀ r ∈ pathEmitFixed, current.nr r = before.nr r
  real : current.rm = before.rm
  low : ∀ a < before.nr 29, current.nm a = before.nm a
  path : ∃ (emitted remaining : List (Traversal G)) (vertex : Fin G.n),
    chosen = emitted ++ remaining ∧ IsPath G vertex remaining destination ∧
    current.nr 9 = vertex.val ∧ remaining.length ≤ G.n - i ∧
    current.nr 29 = before.nr 29 + emitted.length ∧
    ∀ j (valid : j < emitted.length), current.nm (before.nr 29 + j) = emitted[j].1.val

private theorem pathEmit_indexPreserves (s : ArithmeticState) (index : ℕ)
    {r : ℕ} (member : r ∈ pathEmitFixed) :
    (Function.update s.nr 27 index) r = s.nr r := by
  have different : r ≠ 27 := by
    rintro rfl
    exact (by decide : 27 ∉ pathEmitFixed) member
  exact Function.update_of_ne different _ _

private theorem encodedOccurrence_append {memory : ℕ → ℕ} {base : ℕ}
    {emitted : List (Traversal G)} (edge : Traversal G)
    (encoded : ∀ j (valid : j < emitted.length), memory (base + j) = emitted[j].1.val) :
    ∀ j (valid : j < (emitted ++ [edge]).length),
      Function.update memory (base + emitted.length) edge.1.val (base + j) =
        ((emitted ++ [edge])[j]).1.val := by
  intro j valid
  by_cases before : j < emitted.length
  · have different : base + j ≠ base + emitted.length :=
      fun eq => (Nat.ne_of_lt before) (Nat.add_left_cancel eq)
    rw [Function.update_of_ne different, encoded j before]
    exact congrArg (fun step : Traversal G => step.1.val) (List.getElem_append_left' before [edge])
  · have final : j = emitted.length := by simp at valid; omega
    subst j
    rw [Function.update_self]
    have last : edge = (emitted ++ [edge])[emitted.length]'(by simp) := by
      simpa using (List.getElem_append_right' emitted (l₂ := [edge]) (i := 0) (by simp))
    exact congrArg (fun step : Traversal G => step.1.val) last

/-- Emit the original link IDs of a shortest path into the occurrence
buffer. The row pointers and original encoded links are kept intact. -/
theorem emitShortestPathBlock_correct {rowOffsets distances : ℕ} {s : ArithmeticState}
    {source target : Fin G.n} {table : DirectLinkTable G}
    (connected : Connected G) (nonnegative : Nonnegative G)
    (sound : DirectLinkTableSound table)
    (representative : DirectLinkRepresentatives G (tableChooses table))
    (row : TightStoredRow target table (s.nr 26) s.nm)
    (frame : FloydFrame G.n rowOffsets distances s)
    (startReg : s.nr 9 = source.val) (targetReg : s.nr 7 = target.val) (zero : s.nr 28 = 0)
    (rowOffsetsBelow : rowOffsets + G.n ≤ s.nr 29)
    (pointerTableBelow : s.nr 26 + G.n * G.n ≤ s.nr 29)
    (inputBelow : 2 + 3 * G.q ≤ s.nr 29)
    (tailCell : ∀ e : Fin G.q, s.nm (2 + 3 * e.val) = (G.tail e).val)
    (headCell : ∀ e : Fin G.q, s.nm (3 + 3 * e.val) = (G.head e).val)
    (entry : s.pc = 0) (running : s.halted = false) :
    ∃ t ts steps, BlockRuns emitShortestPathBlock steps s t ∧
      steps ≤ 1 + (G.n * (22 + 3) + 1) ∧ t.halted = false ∧
      ShortestPath G source target ts ∧ ts.length < G.n ∧ t.nr 9 = target.val ∧
      t.nr 29 = s.nr 29 + ts.length ∧
      (∀ j (valid : j < ts.length), t.nm (s.nr 29 + j) = ts[j].1.val) ∧
      (∀ a < s.nr 29, t.nm a = s.nm a) ∧ t.rm = s.rm ∧
      ∀ r ∈ pathEmitFixed, t.nr r = s.nr r := by
  obtain ⟨ts, shortest, bounded, usedEdges⟩ :=
    row.shortestPath connected nonnegative sound representative source
  let inv := PathEmitInvariant s target ts
  have initial : inv 0 {s with pc := 0, nr := Function.update s.nr 27 0} := by
    refine ⟨rfl, running, by simp, fun r hr => pathEmit_indexPreserves s 0 hr, rfl, fun _ _ => rfl, ?_⟩
    refine ⟨[], ts, source, rfl, shortest.1, ?_, ?_, ?_, ?_⟩
    · simpa using startReg
    · simpa using bounded.le
    · simp
    · intro j impossible
      simp at impossible
  have control (i : ℕ) (m : ArithmeticState) (ok : inv i m) :
      m.pc = 0 ∧ m.halted = false ∧ m.nr 27 = i ∧ m.nr 5 = G.n :=
    ⟨ok.entry, ok.running, ok.index, (ok.fixed 5 (by decide)).trans frame.dimension⟩
  have step (i : ℕ) (more : i < G.n) (m : ArithmeticState) (ok : inv i m) :
      ∃ t steps, steps ≤ 22 ∧
        BlockRuns (branchOnUnequal 9 7 followAndAppendOccurrenceBlock) steps m t ∧
        t.halted = false ∧ inv (i + 1)
          {t with pc := 0, nr := Function.update t.nr 27 (t.nr 27 + t.nr 6)} := by
    obtain ⟨emitted, remaining, vertex, split, walks, atVertex, count, cursor, encoded⟩ := ok.path
    have mOne := (ok.fixed 6 (by decide)).trans frame.one
    have mZero := (ok.fixed 28 (by decide)).trans zero
    have targetAt := (ok.fixed 7 (by decide)).trans targetReg
    cases remaining with
    | nil =>
      have arrived : vertex = target := walks
      have equal : m.nr 9 = m.nr 7 := (atVertex.trans (congrArg Fin.val arrived)).trans targetAt.symm
      let t := {m with pc := (branchOnUnequal 9 7 followAndAppendOccurrenceBlock).length}
      refine ⟨t, 2, by decide, branchOnUnequal_skip 9 7 _ m ok.entry ok.running equal,
        ok.running, ?_⟩
      refine ⟨rfl, ok.running, ?_, ?_, ok.real, ok.low, ?_⟩
      · simp [t, ok.index, mOne]
      · intro r hr
        exact (pathEmit_indexPreserves t _ hr).trans (ok.fixed r hr)
      · refine ⟨emitted, [], vertex, split, walks, ?_, by simp, ?_, encoded⟩
        · simpa [t] using atVertex
        · simpa [t] using cursor
    | cons edge remaining =>
      have used : edge ∈ ts := split.symm ▸ List.mem_append.mpr (.inr List.mem_cons_self)
      obtain ⟨away, nonloop, pointer⟩ := usedEdges edge used
      have starts : start G edge = vertex := walks.1.symm
      have different : m.nr 9 ≠ m.nr 7 := by
        rw [atVertex, targetAt]
        exact fun same => away (starts.trans (Fin.ext same))
      have mFrame : FloydFrame G.n rowOffsets distances m := by
        refine ⟨(ok.fixed 3 (by decide)).trans frame.tableBase,
          (ok.fixed 4 (by decide)).trans frame.matrixBase, (ok.fixed 5 (by decide)).trans frame.dimension,
          mOne, ?_⟩
        intro j hj
        exact (ok.low _ ((Nat.add_lt_add_left hj _).trans_le rowOffsetsBelow)).trans (frame.rows j hj)
      have pointerAddress : s.nr 26 + G.n * target.val + vertex.val < s.nr 29 := by
        have within : G.n * target.val + vertex.val < G.n * G.n := by
          have rowBound : G.n * (target.val + 1) ≤ G.n * G.n :=
            Nat.mul_le_mul_left _ (Nat.succ_le_of_lt target.isLt)
          rw [Nat.mul_succ] at rowBound
          exact (Nat.add_lt_add_left vertex.isLt _).trans_le rowBound
        omega
      have mPointer : m.nm (m.nr 26 + G.n * target.val + vertex.val) = edge.1.val := by
        rw [ok.fixed 26 (by decide), ok.low _ pointerAddress, ← starts]
        exact pointer
      have edgeBelow := edge.1.isLt
      have mTail : m.nm (2 + 3 * edge.1.val) = (G.tail edge.1).val :=
        (ok.low _ (by omega)).trans (tailCell edge.1)
      have mHead : m.nm (3 + 3 * edge.1.val) = (G.head edge.1).val :=
        (ok.low _ (by omega)).trans (headCell edge.1)
      obtain ⟨d, reads, dReady, dNatural, dReal, id, _, vertexNext⟩ :=
        followNextLinkBlock_correct mFrame atVertex targetAt mZero ok.entry ok.running
          mPointer starts nonloop mTail mHead
      obtain ⟨after, appends, ready, nextVertex, nextCursor, writes, real, fixed⟩ :=
        followAndAppendOccurrenceBlock_correct reads ok.entry ok.running dReady
          mOne mZero dNatural dReal
      let t := relocateState 3 after
      have tIndex : t.nr 27 = i := (fixed 27 (by decide)).trans ok.index
      have tOne : t.nr 6 = 1 := (fixed 6 (by decide)).trans mOne
      refine ⟨t, 22, le_rfl, branchOnUnequal_take 9 7 _ ok.entry ok.running different appends,
        ready, ?_⟩
      refine ⟨rfl, ready, ?_, ?_, real.trans ok.real, ?_, ?_⟩
      · simp [t, tIndex, tOne]
      · intro r hr
        exact (pathEmit_indexPreserves t _ hr).trans ((fixed r (by
          simp [pathEmitFixed] at hr
          simp
          omega)).trans (ok.fixed r hr))
      · intro a below
        change after.nm a = s.nm a
        rw [writes, Function.update_of_ne (show a ≠ m.nr 29 by omega)]
        exact ok.low a below
      · refine ⟨emitted ++ [edge], remaining, finish G edge, ?_, walks.2.2, ?_, ?_, ?_, ?_⟩
        · simpa [List.append_assoc] using split
        · simpa [t, relocateState] using nextVertex.trans vertexNext
        · simp at count
          omega
        · simpa [t, relocateState, cursor, Nat.add_assoc] using nextCursor
        · intro j hj
          change after.nm (s.nr 29 + j) = _
          rw [writes, cursor, id]
          exact encodedOccurrence_append edge encoded j hj
  obtain ⟨last, actual, complete, budget, executes⟩ :=
    countedLoopFromZero_bounded 6 27 5 G.n 22
      (branchOnUnequal 9 7 followAndAppendOccurrenceBlock) inv entry running initial control step
  obtain ⟨emitted, remaining, vertex, split, walks, here, count, cursor, encoded⟩ := complete.path
  have empty : remaining = [] :=
    List.length_eq_zero_iff.mp (by simpa using count)
  subst remaining
  have finished : vertex = target := walks
  subst vertex
  have exactEdges : ts = emitted := by simpa using split
  subst emitted
  exact ⟨_, ts, actual, executes, budget, complete.running, shortest, bounded, here, cursor,
    encoded, complete.low, complete.real, complete.fixed⟩

end VehicleRoutingSurvey.Routing
end RppSource_PathEmission

/-! runtime/PairExpansion.lean -/
section RppSource_PairExpansion
namespace VehicleRoutingSurvey.Routing

variable {G : Network}

def ExpansionPairArray (memory : ℕ → ℕ) (base : ℕ)
    (pairs : List (Fin G.n × Fin G.n)) : Prop :=
  ∀ i (valid : i < pairs.length),
    memory (base + 2 * i) = pairs[i].1.val ∧ memory (base + 2 * i + 1) = pairs[i].2.val

private def beginPairCursor : List ArithmeticInstruction := [.natAdd 36 34 28]

private theorem beginPairCursor_runs (s : ArithmeticState) (entry : s.pc = 0)
    (running : s.halted = false) (zero : s.nr 28 = 0) :
    BlockRuns beginPairCursor 1 s {s with pc := 1, nr := Function.update s.nr 36 (s.nr 34)} := by
  refine ⟨?_, ?_, rfl⟩
  · intro i less
    have isZero : i = 0 := by omega
    simp [isZero, entry, beginPairCursor]
  · simp [beginPairCursor, arithmeticStep, entry, running, zero]

private def readExpansionPair : List ArithmeticInstruction :=
  [.natLoad 9 36, .natAdd 36 36 6, .natLoad 7 36, .natAdd 36 36 6]

private theorem readExpansionPair_correct (s : ArithmeticState)
    (entry : s.pc = 0) (running : s.halted = false) (one : s.nr 6 = 1) :
    ∃ t, BlockRuns readExpansionPair 4 s t ∧ t.halted = false ∧ t.nm = s.nm ∧ t.rm = s.rm ∧
      t.nr 9 = s.nm (s.nr 36) ∧ t.nr 7 = s.nm (s.nr 36 + 1) ∧ t.nr 36 = s.nr 36 + 2 ∧
      ∀ r, r ≠ 9 → r ≠ 7 → r ≠ 36 → t.nr r = s.nr r := by
  let t := (arithmeticStep readExpansionPair)^[4] s
  have ready : t.halted = false := by
    simp [t, readExpansionPair, arithmeticStep, entry, running, Function.iterate_succ_apply']
  have exit : t.pc = readExpansionPair.length := by
    simp [t, readExpansionPair, arithmeticStep, entry, running, Function.iterate_succ_apply']
  refine ⟨t, BlockRuns.of_running_exit rfl ready exit, ready, ?_, ?_, ?_, ?_, ?_, ?_⟩
  · simp [t, readExpansionPair, arithmeticStep, entry, running, Function.iterate_succ_apply']
  · simp [t, readExpansionPair, arithmeticStep, entry, running, Function.iterate_succ_apply']
  · simp [t, readExpansionPair, arithmeticStep, entry, running, Function.iterate_succ_apply']
  · simp [t, readExpansionPair, arithmeticStep, entry, running, one, Function.iterate_succ_apply']
  · simp [t, readExpansionPair, arithmeticStep, entry, running, one, Function.iterate_succ_apply', Nat.add_assoc]
  · intro r fromReg toReg cursorReg
    simp [t, readExpansionPair, arithmeticStep, entry, running, Function.iterate_succ_apply',
      Function.update_of_ne fromReg, Function.update_of_ne toReg, Function.update_of_ne cursorReg]

def expandOnePairBlock : List ArithmeticInstruction :=
  appendBlock readExpansionPair emitShortestPathBlock

def expandPairListBlock : List ArithmeticInstruction :=
  appendBlock beginPairCursor (countedLoopFromZero 6 37 35 expandOnePairBlock)

def pairExpansionPreserved : List ℕ := [3, 4, 5, 6, 26, 28, 33, 34, 35]

private structure PairExpansionProgress (input : ArithmeticState) (pairs : List (Fin G.n × Fin G.n))
    (prior : List (Fin G.q)) (i : ℕ) (s : ArithmeticState) : Prop where
  entry : s.pc = 0
  running : s.halted = false
  index : s.nr 37 = i
  pairCursor : s.nr 36 = input.nr 34 + 2 * i
  fixed : ∀ r ∈ pairExpansionPreserved, s.nr r = input.nr r
  real : s.rm = input.rm
  low : ∀ address < input.nr 29, s.nm address = input.nm address
  paths : ∃ walks : List (List (Traversal G)),
    Expands G (pairs.take i) walks ∧ (∀ walk ∈ walks, walk.length < G.n) ∧
    s.nr 29 = input.nr 33 + (prior ++ walks.flatten.map Prod.fst).length ∧
    OccurrenceArray s.nm (input.nr 33) (prior ++ walks.flatten.map Prod.fst)

private theorem occurrencePointerAddressBound (target source : Fin G.n) :
    G.n * target.val + source.val < G.n * G.n := by
  have row : G.n * (target.val + 1) ≤ G.n * G.n :=
    Nat.mul_le_mul_left _ (Nat.succ_le_of_lt target.isLt)
  rw [Nat.mul_succ] at row
  exact (Nat.add_lt_add_left source.isLt _).trans_le row

theorem TightStoredRow.preservedBelow {table : DirectLinkTable G} {target : Fin G.n}
    {old fresh : ℕ → ℕ} {nextBase bound : ℕ} (row : TightStoredRow target table nextBase old)
    (fits : nextBase + G.n * G.n ≤ bound) (copies : ∀ a < bound, fresh a = old a) :
    TightStoredRow target table nextBase fresh := by
  intro source away
  obtain ⟨edge, starts, legal, tight, stored, decreases⟩ := row source away
  have below : nextBase + G.n * target.val + source.val < bound := by
    have within := occurrencePointerAddressBound target source
    omega
  exact ⟨edge, starts, legal, tight, (copies _ below).trans stored, decreases⟩

/-- Expand every encoded pair to a simple shortest path, appending its
link occurrences to the existing array. All source pair cells, raw link
records, and shortest-path pointers remain available below the cursor. -/
theorem expandPairListBlock_correct {rowOffsets distances : ℕ} {s : ArithmeticState}
    {table : DirectLinkTable G} (pairs : List (Fin G.n × Fin G.n)) (prior : List (Fin G.q))
    (connected : Connected G) (nonnegative : Nonnegative G) (frame : FloydFrame G.n rowOffsets distances s)
    (sound : DirectLinkTableSound table)
    (representative : DirectLinkRepresentatives G (tableChooses table))
    (rows : ∀ target, TightStoredRow target table (s.nr 26) s.nm)
    (count : s.nr 35 = pairs.length) (zero : s.nr 28 = 0)
    (initialCursor : s.nr 29 = s.nr 33 + prior.length)
    (encodedPairs : ExpansionPairArray s.nm (s.nr 34) pairs)
    (encodedPrior : OccurrenceArray s.nm (s.nr 33) prior)
    (pairsBelow : s.nr 34 + 2 * pairs.length ≤ s.nr 29)
    (rowsBelow : rowOffsets + G.n ≤ s.nr 29) (pointersBelow : s.nr 26 + G.n * G.n ≤ s.nr 29)
    (inputBelow : 2 + 3 * G.q ≤ s.nr 29)
    (tailCell : ∀ e : Fin G.q, s.nm (2 + 3 * e.val) = (G.tail e).val)
    (headCell : ∀ e : Fin G.q, s.nm (3 + 3 * e.val) = (G.head e).val)
    (entry : s.pc = 0) (running : s.halted = false) :
    ∃ t steps paths, BlockRuns expandPairListBlock steps s t ∧
      steps ≤ pairs.length * (25 * G.n + 9) + 3 ∧ t.halted = false ∧
      Expands G pairs paths ∧ (∀ path ∈ paths, path.length < G.n) ∧
      t.nr 29 = s.nr 33 + (prior ++ paths.flatten.map Prod.fst).length ∧
      OccurrenceArray t.nm (s.nr 33) (prior ++ paths.flatten.map Prod.fst) ∧
      (∀ r ∈ pairExpansionPreserved, t.nr r = s.nr r) ∧ t.rm = s.rm ∧
      ∀ a < s.nr 29, t.nm a = s.nm a := by
  let staged := {s with pc := 0, nr := Function.update s.nr 36 (s.nr 34)}
  let inv := PairExpansionProgress s pairs prior
  have initial : inv 0 {staged with pc := 0, nr := Function.update staged.nr 37 0} := by
    refine ⟨rfl, running, by simp, by simp [staged], ?_, rfl, fun _ _ => rfl, ?_⟩
    · intro r selected
      have notRead : r ≠ 36 := by rintro rfl; simp [pairExpansionPreserved] at selected
      have notCount : r ≠ 37 := by rintro rfl; simp [pairExpansionPreserved] at selected
      simp [staged, Function.update_of_ne notRead, Function.update_of_ne notCount]
    · exact ⟨[], List.Forall₂.nil, by simp, by simpa [staged] using initialCursor,
        by simpa using encodedPrior⟩
  have control (i : ℕ) (m : ArithmeticState) (ok : inv i m) :
      m.pc = 0 ∧ m.halted = false ∧ m.nr 37 = i ∧ m.nr 35 = pairs.length :=
    ⟨ok.entry, ok.running, ok.index, (ok.fixed 35 (by decide)).trans count⟩
  have step (i : ℕ) (more : i < pairs.length) (m : ArithmeticState) (ok : inv i m) :
      ∃ t steps, steps ≤ 25 * G.n + 6 ∧ BlockRuns expandOnePairBlock steps m t ∧
        t.halted = false ∧ inv (i + 1)
          {t with pc := 0, nr := Function.update t.nr 37 (t.nr 37 + t.nr 6)} := by
    obtain ⟨walks, priorPaths, lengthBounds, priorCursor, priorArray⟩ := ok.paths
    let pair := pairs[i]
    have protectedEnd : s.nr 29 ≤ m.nr 29 := by
      rw [initialCursor, priorCursor]
      simp
    have mOne := (ok.fixed 6 (by decide)).trans frame.one
    obtain ⟨read, reads, readReady, readNat, readReal, readSource, readTarget, readCursor, readFixed⟩ :=
      readExpansionPair_correct m ok.entry ok.running mOne
    let routeEntry := {read with pc := 0}
    have readKeeps (r : ℕ) (preserved : r ∈ pairExpansionPreserved) : read.nr r = m.nr r := by
      apply readFixed <;> intro eq <;> simp [pairExpansionPreserved, eq] at preserved
    have readOne := (readKeeps 6 (by decide)).trans mOne
    have readZero := ((readKeeps 28 (by decide)).trans (ok.fixed 28 (by decide))).trans zero
    have currentCursor : read.nr 29 = m.nr 29 := readFixed 29 (by decide) (by decide) (by decide)
    have readBase : read.nr 26 = s.nr 26 := (readKeeps 26 (by decide)).trans (ok.fixed 26 (by decide))
    have sourceBelow : s.nr 34 + 2 * i < s.nr 29 := by omega
    have targetBelow : s.nr 34 + 2 * i + 1 < s.nr 29 := by omega
    have observedSource : read.nr 9 = pair.1.val := by
      rw [readSource, ok.pairCursor, ok.low _ sourceBelow]
      exact (encodedPairs i more).1
    have observedTarget : read.nr 7 = pair.2.val := by
      rw [readTarget, ok.pairCursor, ok.low _ targetBelow]
      exact (encodedPairs i more).2
    have liveFrame : FloydFrame G.n rowOffsets distances routeEntry := by
      refine ⟨((readKeeps 3 (by decide)).trans (ok.fixed 3 (by decide))).trans frame.tableBase,
        ((readKeeps 4 (by decide)).trans (ok.fixed 4 (by decide))).trans frame.matrixBase,
        ((readKeeps 5 (by decide)).trans (ok.fixed 5 (by decide))).trans frame.dimension,
        readOne, ?_⟩
      intro j hj
      change read.nm (rowOffsets + j) = _
      rw [readNat, ok.low _ ((Nat.add_lt_add_left hj _).trans_le rowsBelow)]
      exact frame.rows j hj
    have liveRow : TightStoredRow pair.2 table (routeEntry.nr 26) routeEntry.nm := by
      change TightStoredRow pair.2 table (read.nr 26) read.nm
      rw [readBase, readNat]
      exact (rows pair.2).preservedBelow pointersBelow ok.low
    have liveRowsBelow : rowOffsets + G.n ≤ routeEntry.nr 29 := by
      change _ ≤ read.nr 29
      rw [currentCursor]
      exact rowsBelow.trans protectedEnd
    have livePointersBelow : routeEntry.nr 26 + G.n * G.n ≤ routeEntry.nr 29 := by
      change read.nr 26 + _ ≤ read.nr 29
      rw [readBase, currentCursor]
      exact pointersBelow.trans protectedEnd
    have liveInputBelow : 2 + 3 * G.q ≤ routeEntry.nr 29 := by
      change _ ≤ read.nr 29
      rw [currentCursor]
      exact inputBelow.trans protectedEnd
    have liveTail (e : Fin G.q) : routeEntry.nm (2 + 3 * e.val) = (G.tail e).val := by
      change read.nm _ = _
      have eBelow := e.isLt
      rw [readNat, ok.low _ (by omega)]
      exact tailCell e
    have liveHead (e : Fin G.q) : routeEntry.nm (3 + 3 * e.val) = (G.head e).val := by
      change read.nm _ = _
      have eBelow := e.isLt
      rw [readNat, ok.low _ (by omega)]
      exact headCell e
    obtain ⟨wrote, path, used, expands, usedBound, wroteReady, shortest, pathBound, _, endCursor,
      pathCells, stableInput, wroteReal, preserved⟩ :=
      emitShortestPathBlock_correct connected nonnegative sound representative liveRow liveFrame
        observedSource observedTarget readZero liveRowsBelow livePointersBelow liveInputBelow
        liveTail liveHead rfl readReady
    let t := relocateState readExpansionPair.length wrote
    have keepPairReg (r : ℕ) (present : r ∈ pairExpansionPreserved) : t.nr r = m.nr r := by
      exact (preserved r (by simp [pairExpansionPreserved, pathEmitFixed] at present ⊢; omega)).trans
        (readKeeps r present)
    have oneOut : t.nr 6 = 1 := (keepPairReg 6 (by decide)).trans mOne
    have indexOut : t.nr 37 = i := (preserved 37 (by decide)).trans
      ((readFixed 37 (by decide) (by decide) (by decide)).trans ok.index)
    have sourceMem (address : ℕ) (earlier : address < m.nr 29) : t.nm address = m.nm address := by
      have beforeWrite : address < routeEntry.nr 29 := by
        change address < read.nr 29
        rwa [currentCursor]
      exact (stableInput address beforeWrite).trans (congrFun readNat address)
    have past : OccurrenceArray t.nm (s.nr 33) (prior ++ walks.flatten.map Prod.fst) :=
      priorArray.preservedBelow (by rw [priorCursor]) sourceMem
    have new : OccurrenceArray t.nm (s.nr 33 + (prior ++ walks.flatten.map Prod.fst).length)
        (path.map Prod.fst) := by
      have atCursor : routeEntry.nr 29 = s.nr 33 + (prior ++ walks.flatten.map Prod.fst).length :=
        currentCursor.trans priorCursor
      change OccurrenceArray wrote.nm _ _
      have stored := occurrenceArray_ofTraversals pathCells
      rwa [atCursor] at stored
    have combined := past.append new
    have nextPaths : Expands G (pairs.take (i + 1)) (walks ++ [path]) := by
      rw [List.take_succ_eq_append_getElem more]
      exact List.rel_append priorPaths (List.Forall₂.cons shortest List.Forall₂.nil)
    have bound : 4 + used ≤ 25 * G.n + 6 := by omega
    refine ⟨t, 4 + used, bound, reads.append expands, wroteReady, ?_⟩
    refine ⟨rfl, wroteReady, by simp [t, indexOut, oneOut], ?_, ?_,
      wroteReal.trans (readReal.trans ok.real), ?_, ?_⟩
    · have pairAdvance : t.nr 36 = s.nr 34 + 2 * (i + 1) := by
        have observed : t.nr 36 = read.nr 36 := preserved 36 (by decide)
        rw [observed, readCursor, ok.pairCursor]
        omega
      simpa [t] using pairAdvance
    · intro r present
      have noReset : r ≠ 37 := by rintro rfl; simp [pairExpansionPreserved] at present
      exact (Function.update_of_ne noReset _ _).trans ((keepPairReg r present).trans (ok.fixed r present))
    · intro address below
      exact (sourceMem address (below.trans_le protectedEnd)).trans (ok.low address below)
    · refine ⟨walks ++ [path], nextPaths, ?_, ?_, ?_⟩
      · intro previous included
        rcases List.mem_append.mp included with earlier | last
        · exact lengthBounds previous earlier
        · exact (List.mem_singleton.mp last).symm ▸ pathBound
      · change wrote.nr 29 = _
        simpa [routeEntry, currentCursor, priorCursor, List.flatten_append,
          List.map_append, List.append_assoc, Nat.add_assoc] using endCursor
      · simpa [List.flatten_append, List.map_append, List.append_assoc] using combined
  obtain ⟨last, elapsed, done, cap, executes⟩ :=
    countedLoopFromZero_bounded 6 37 35 pairs.length (25 * G.n + 6) expandOnePairBlock inv
      (s := staged) rfl running initial control step
  obtain ⟨walks, pathProof, pathBounds, cursor, array⟩ := done.paths
  have setup := beginPairCursor_runs s entry running zero
  have totalBound : 1 + elapsed ≤ pairs.length * (25 * G.n + 9) + 3 := by
    rw [show 25 * G.n + 6 + 3 = 25 * G.n + 9 by omega] at cap
    omega
  exact ⟨_, 1 + elapsed, walks, setup.append executes, totalBound, done.running,
    by simpa using pathProof, pathBounds, cursor, array, done.fixed, done.real, done.low⟩

end VehicleRoutingSurvey.Routing
end RppSource_PairExpansion

/-! runtime/ConnectorOccurrences.lean -/
section RppSource_ConnectorOccurrences
namespace VehicleRoutingSurvey.Routing

def connectorOccurrencesBlock : List ArithmeticInstruction :=
  appendBlock requiredOccurrenceBlock expandPairListBlock

/-- Produce the base and expanded connector occurrences before parity
is computed. The tree pair list is supplied by the preceding stage. -/
theorem connectorOccurrencesBlock_correct {I : Service} {rowOffsets distances : ℕ}
    {table : DirectLinkTable I.graph} {s : ArithmeticState}
    (pairs : List (Fin I.graph.n × Fin I.graph.n)) (rural : Rural I)
    (frame : FloydFrame I.graph.n rowOffsets distances s)
    (sound : DirectLinkTableSound table)
    (representative : DirectLinkRepresentatives I.graph (tableChooses table))
    (rows : ∀ target, TightStoredRow target table (s.nr 26) s.nm)
    (count : s.nr 35 = pairs.length)
    (encodedPairs : ExpansionPairArray s.nm (s.nr 34) pairs)
    (rawInput : ∀ a < 2 + 3 * I.graph.q, s.nm a = (ruralNatInput I)[a]?.getD 0)
    (pairBound : s.nr 34 + 2 * pairs.length ≤ s.nr 33)
    (rowBound : rowOffsets + I.graph.n ≤ s.nr 33)
    (pointerBound : s.nr 26 + I.graph.n * I.graph.n ≤ s.nr 33)
    (rawBound : 2 + 3 * I.graph.q ≤ s.nr 33)
    (entry : s.pc = 0) (running : s.halted = false) :
    ∃ t steps paths, BlockRuns connectorOccurrencesBlock steps s t ∧
      steps ≤ 11 * I.graph.q + pairs.length * (25 * I.graph.n + 9) + 9 ∧
      t.halted = false ∧ Expands I.graph pairs paths ∧
      (∀ path ∈ paths, path.length < I.graph.n) ∧
      t.nr 28 = 0 ∧ t.nr 29 = s.nr 33 + (requiredLinkList I ++ paths.flatten.map Prod.fst).length ∧
      OccurrenceArray t.nm (s.nr 33) (requiredLinkList I ++ paths.flatten.map Prod.fst) ∧
      (∀ r ∈ pairExpansionPreserved, r ≠ 28 → t.nr r = s.nr r) ∧
      t.rm = s.rm ∧ ∀ a < s.nr 33, t.nm a = s.nm a := by
  obtain ⟨b, scans, baseRun, baseBound, baseReady, zero, cursor, fixed, real, early, baseArray⟩ :=
    requiredOccurrenceBlock_correct entry running frame.one rawBound rawInput
  let expandEntry := {b with pc := 0}
  have liveFrame : FloydFrame I.graph.n rowOffsets distances expandEntry := by
    refine ⟨(fixed 3 (by decide)).trans frame.tableBase, (fixed 4 (by decide)).trans frame.matrixBase,
      (fixed 5 (by decide)).trans frame.dimension, (fixed 6 (by decide)).trans frame.one, ?_⟩
    intro j hj
    exact (early _ ((Nat.add_lt_add_left hj _).trans_le rowBound)).trans (frame.rows j hj)
  have liveRows (target : Fin I.graph.n) :
      TightStoredRow target table (expandEntry.nr 26) expandEntry.nm := by
    change TightStoredRow target table (b.nr 26) b.nm
    rw [fixed 26 (by decide)]
    exact (rows target).preservedBelow pointerBound early
  have cursorStart : expandEntry.nr 29 = expandEntry.nr 33 + (requiredLinkList I).length := by
    change b.nr 29 = b.nr 33 + _
    rwa [fixed 33 (by decide)]
  have pairInput : ExpansionPairArray expandEntry.nm (expandEntry.nr 34) pairs := by
    change ExpansionPairArray b.nm (b.nr 34) pairs
    rw [fixed 34 (by decide)]
    intro i hi
    exact ⟨(early _ (by omega)).trans (encodedPairs i hi).1,
      (early _ (by omega)).trans (encodedPairs i hi).2⟩
  have prior : OccurrenceArray expandEntry.nm (expandEntry.nr 33) (requiredLinkList I) := by
    change OccurrenceArray b.nm (b.nr 33) _
    rwa [fixed 33 (by decide)]
  have startAfter : s.nr 33 ≤ expandEntry.nr 29 := by change _ ≤ b.nr 29; rw [cursor]; omega
  have pairsBelow : expandEntry.nr 34 + 2 * pairs.length ≤ expandEntry.nr 29 := by
    change b.nr 34 + _ ≤ b.nr 29
    rw [fixed 34 (by decide)]
    exact pairBound.trans startAfter
  have pointersBelow : expandEntry.nr 26 + I.graph.n * I.graph.n ≤ expandEntry.nr 29 := by
    change b.nr 26 + _ ≤ b.nr 29
    rw [fixed 26 (by decide)]
    exact pointerBound.trans startAfter
  have keptRaw : ∀ a < 2 + 3 * I.graph.q, expandEntry.nm a = (ruralNatInput I)[a]?.getD 0 :=
    fun a ha => (early a (ha.trans_le rawBound)).trans (rawInput a ha)
  obtain ⟨p, expands, paths, pathRun, pathCost, ready, valid, pathLen, finalCursor,
      finalArray, finalFixed, finalReal, finalEarly⟩ :=
    expandPairListBlock_correct pairs (requiredLinkList I) rural.1 rural.2.1 liveFrame sound
      representative liveRows ((fixed 35 (by decide)).trans count) zero cursorStart pairInput prior
      pairsBelow (rowBound.trans startAfter) pointersBelow (rawBound.trans startAfter)
      (fun edge => (ruralInputs_preserveLinkEndpoints keptRaw edge).1)
      (fun edge => (ruralInputs_preserveLinkEndpoints keptRaw edge).2) rfl baseReady
  let final := relocateState requiredOccurrenceBlock.length p
  have completed := baseRun.append pathRun
  refine ⟨final, scans + expands, paths, completed, by omega, ready, valid, pathLen,
    (finalFixed 28 (by decide)).trans zero, ?_, ?_, ?_, finalReal.trans real, ?_⟩
  · change p.nr 29 = _
    have original := finalCursor
    change p.nr 29 = b.nr 33 + _ at original
    rwa [fixed 33 (by decide)] at original
  · change OccurrenceArray p.nm (s.nr 33) _
    have original := finalArray
    change OccurrenceArray p.nm (b.nr 33) _ at original
    rwa [fixed 33 (by decide)] at original
  · intro r hr notZero
    have original : r ∈ requiredOccurrencePreserved := by
      simp [pairExpansionPreserved] at hr
      simp [requiredOccurrencePreserved]
      omega
    exact (finalFixed r hr).trans (fixed r original)
  · exact fun a ha => (finalEarly a (ha.trans_le startAfter)).trans (early a ha)

end VehicleRoutingSurvey.Routing
end RppSource_ConnectorOccurrences

/-! matching/WeightedCacheRAM.lean -/
section RppSource_WeightedCacheRAM
namespace VehicleRoutingSurvey.Routing

/-- Merge one least-slack candidate into a cache cell. Natural register 0 is the new edge
identifier, and register 1 is the current one. Zero means empty. Real registers 0 and 1
carry their slacks. An equal-slack edge keeps the earlier representative. -/
def mergeSlackEntryBlock : List ArithmeticInstruction :=
  [.natConst 2 0, .natBranch 0 2 7 2, .natBranch 1 2 4 3, .realBranch 1 0 7 4,
    .natAdd 1 0 2, .realConst 2 0, .realAdd 1 0 2]

def mergeSlackEntryTakesCandidate (s : ArithmeticState) : Prop :=
  s.nr 0 ≠ 0 ∧ (s.nr 1 = 0 ∨ s.rr 0 < s.rr 1)

private theorem mergeSlackEntryBlock_absent (s : ArithmeticState) (entry : s.pc = 0)
    (running : s.halted = false) (absent : s.nr 0 = 0) :
    (arithmeticStep mergeSlackEntryBlock)^[2] s = {s with pc := 7, nr := Function.update s.nr 2 0} := by
  simp [mergeSlackEntryBlock, arithmeticStep, Function.iterate_succ_apply', entry, running, absent]

private theorem mergeSlackEntryBlock_empty (s : ArithmeticState) (entry : s.pc = 0)
    (running : s.halted = false) (available : s.nr 0 ≠ 0) (empty : s.nr 1 = 0) :
    (arithmeticStep mergeSlackEntryBlock)^[6] s =
      {s with
        pc := 7
        nr := Function.update (Function.update s.nr 2 0) 1 (s.nr 0)
        rr := Function.update (Function.update s.rr 2 0) 1 (s.rr 0)} := by
  simp [mergeSlackEntryBlock, arithmeticStep, Function.iterate_succ_apply', entry, running, available, empty]

private theorem mergeSlackEntryBlock_keep (s : ArithmeticState) (entry : s.pc = 0)
    (running : s.halted = false) (available : s.nr 0 ≠ 0) (occupied : s.nr 1 ≠ 0)
    (noBetter : s.rr 1 ≤ s.rr 0) :
    (arithmeticStep mergeSlackEntryBlock)^[4] s = {s with pc := 7, nr := Function.update s.nr 2 0} := by
  simp [mergeSlackEntryBlock, arithmeticStep, Function.iterate_succ_apply', entry, running, available, occupied,
    noBetter]

private theorem mergeSlackEntryBlock_replace (s : ArithmeticState) (entry : s.pc = 0)
    (running : s.halted = false) (available : s.nr 0 ≠ 0) (occupied : s.nr 1 ≠ 0)
    (better : s.rr 0 < s.rr 1) :
    (arithmeticStep mergeSlackEntryBlock)^[7] s =
      {s with
        pc := 7
        nr := Function.update (Function.update s.nr 2 0) 1 (s.nr 0)
        rr := Function.update (Function.update s.rr 2 0) 1 (s.rr 0)} := by
  simp [mergeSlackEntryBlock, arithmeticStep, Function.iterate_succ_apply', entry, running, available, occupied,
    not_le.mpr better]

/-- One cache comparison uses at most seven instructions, with the remaining memory intact. -/
theorem mergeSlackEntryBlock_spec (s : ArithmeticState) (entry : s.pc = 0) (running : s.halted = false) :
    ∃ steps ≤ 7, let result := (arithmeticStep mergeSlackEntryBlock)^[steps] s
      BlockRuns mergeSlackEntryBlock steps s result ∧
      (mergeSlackEntryTakesCandidate s → result.nr 1 = s.nr 0 ∧ result.rr 1 = s.rr 0) ∧
      (¬ mergeSlackEntryTakesCandidate s → result.nr 1 = s.nr 1 ∧ result.rr 1 = s.rr 1) ∧
      result.nm = s.nm ∧ result.rm = s.rm := by
  classical
  by_cases absent : s.nr 0 = 0
  · refine ⟨2, by decide, ?_⟩
    rw [mergeSlackEntryBlock_absent s entry running absent]
    exact ⟨BlockRuns.of_running_exit (mergeSlackEntryBlock_absent s entry running absent) running rfl,
      by simp [mergeSlackEntryTakesCandidate, absent]⟩
  by_cases empty : s.nr 1 = 0
  · refine ⟨6, by decide, ?_⟩
    rw [mergeSlackEntryBlock_empty s entry running absent empty]
    exact ⟨BlockRuns.of_running_exit (mergeSlackEntryBlock_empty s entry running absent empty) running rfl,
      by simp [mergeSlackEntryTakesCandidate, absent, empty]⟩
  by_cases better : s.rr 0 < s.rr 1
  · refine ⟨7, by decide, ?_⟩
    rw [mergeSlackEntryBlock_replace s entry running absent empty better]
    exact ⟨BlockRuns.of_running_exit (mergeSlackEntryBlock_replace s entry running absent empty better) running rfl,
      by simp [mergeSlackEntryTakesCandidate, absent, empty, better]⟩
  · refine ⟨4, by decide, ?_⟩
    rw [mergeSlackEntryBlock_keep s entry running absent empty (le_of_not_gt better)]
    exact ⟨BlockRuns.of_running_exit (mergeSlackEntryBlock_keep s entry running absent empty (le_of_not_gt better)) running rfl,
      by simp [mergeSlackEntryTakesCandidate, absent, empty, better]⟩

end VehicleRoutingSurvey.Routing
end RppSource_WeightedCacheRAM

/-! matching/WeightedDeltaRAM.lean -/
section RppSource_WeightedDeltaRAM
namespace VehicleRoutingSurvey.Routing

/-- Real registers 0 and 3 contain slack and rate. Divide for a rising constraint, or
clear the candidate edge identifier for a constraint that imposes no upper bound. -/
def prepareDualBoundBlock : List ArithmeticInstruction :=
  [.realConst 4 0, .realBranch 3 4 2 4, .natConst 0 0, .jump 6, .realDiv 0 0 3, .jump 6]

private noncomputable def preparedDualBound (s : ArithmeticState) : ArithmeticState :=
  let initial := {s with pc := 6, rr := Function.update s.rr 4 0}
  if s.rr 3 ≤ 0 then {initial with nr := Function.update initial.nr 0 0}
  else {initial with rr := Function.update initial.rr 0 (s.rr 0 / s.rr 3)}

private theorem prepareDualBoundBlock_spec (s : ArithmeticState) (entry : s.pc = 0)
    (running : s.halted = false) : BlockRuns prepareDualBoundBlock 4 s (preparedDualBound s) := by
  classical
  have instructionResult : (arithmeticStep prepareDualBoundBlock)^[4] s = preparedDualBound s := by
    by_cases nonpositive : s.rr 3 ≤ 0 <;>
      simp [prepareDualBoundBlock, arithmeticStep, Function.iterate_succ_apply', entry, running,
        preparedDualBound, nonpositive]
  apply BlockRuns.of_running_exit instructionResult
  · by_cases nonpositive : s.rr 3 ≤ 0 <;> simp [preparedDualBound, nonpositive, running]
  · by_cases nonpositive : s.rr 3 ≤ 0 <;> simp [preparedDualBound, nonpositive, prepareDualBoundBlock]

def mergeDualBoundBlock : List ArithmeticInstruction := appendBlock prepareDualBoundBlock mergeSlackEntryBlock

def mergeDualBoundTakesCandidate (s : ArithmeticState) : Prop :=
  s.nr 0 ≠ 0 ∧ 0 < s.rr 3 ∧ (s.nr 1 = 0 ∨ s.rr 0 / s.rr 3 < s.rr 1)

/-- A candidate is normalized to its slack divided by its positive rate and compared to
the previous minimum in at most eleven instructions. -/
theorem mergeDualBoundBlock_spec (s : ArithmeticState) (entry : s.pc = 0) (running : s.halted = false) :
    ∃ steps ≤ 11, let result := (arithmeticStep mergeDualBoundBlock)^[steps] s
      BlockRuns mergeDualBoundBlock steps s result ∧
      (mergeDualBoundTakesCandidate s → result.nr 1 = s.nr 0 ∧ result.rr 1 = s.rr 0 / s.rr 3) ∧
      (¬mergeDualBoundTakesCandidate s → result.nr 1 = s.nr 1 ∧ result.rr 1 = s.rr 1) ∧
      result.nm = s.nm ∧ result.rm = s.rm := by
  classical
  let middle := {preparedDualBound s with pc := 0}
  have middleLive : middle.halted = false := by
    by_cases nonpositive : s.rr 3 ≤ 0 <;> simp [middle, preparedDualBound, nonpositive, running]
  have unchanged : middle.nr 1 = s.nr 1 ∧ middle.rr 1 = s.rr 1 ∧ middle.nm = s.nm ∧ middle.rm = s.rm := by
    by_cases nonpositive : s.rr 3 ≤ 0 <;> simp [middle, preparedDualBound, nonpositive]
  have equivalent : mergeSlackEntryTakesCandidate middle ↔ mergeDualBoundTakesCandidate s := by
    by_cases nonpositive : s.rr 3 ≤ 0
    · simp [middle, preparedDualBound, mergeSlackEntryTakesCandidate, mergeDualBoundTakesCandidate,
        nonpositive, not_lt_of_ge nonpositive]
    · simp [middle, preparedDualBound, mergeSlackEntryTakesCandidate, mergeDualBoundTakesCandidate,
        nonpositive, lt_of_not_ge nonpositive]
  obtain ⟨steps, short, compared, chosen, kept, natMem, realMem⟩ := mergeSlackEntryBlock_spec middle rfl middleLive
  have joined := BlockRuns.append (prepareDualBoundBlock_spec s entry running) compared
  refine ⟨4 + steps, by omega, ?_⟩
  dsimp only
  rw [mergeDualBoundBlock, joined.run]
  refine ⟨joined, ?_, ?_, natMem.trans unchanged.2.2.1, realMem.trans unchanged.2.2.2⟩
  · intro take
    have found := chosen (equivalent.mpr take)
    have positive : 0 < s.rr 3 := take.2.1
    have registers : middle.nr 0 = s.nr 0 ∧ middle.rr 0 = s.rr 0 / s.rr 3 := by
      simp [middle, preparedDualBound, not_le.mpr positive]
    exact ⟨found.1.trans registers.1, found.2.trans registers.2⟩
  · intro skip
    have found := kept (fun take => skip (equivalent.mp take))
    exact ⟨found.1.trans unchanged.1, found.2.trans unchanged.2.1⟩

end VehicleRoutingSurvey.Routing
end RppSource_WeightedDeltaRAM

/-! matching/WeightedReadDeltaRAM.lean -/
section RppSource_WeightedReadDeltaRAM
namespace VehicleRoutingSurvey.Routing

def naturalDestination : ArithmeticInstruction → ℕ
  | .natAdd dst _ _ | .natSub dst _ _ | .natConst dst _ | .natLoad dst _ => dst
  | _ => 0

private theorem arithmeticStep_keeps_register {p : List ArithmeticInstruction}
    {s : ArithmeticState} {r : ℕ} (otherWrites : ∀ ins ∈ p, naturalDestination ins ≠ r) :
    (arithmeticStep p s).nr r = s.nr r := by
  by_cases halted : s.halted = true
  · simp [arithmeticStep, halted]
  cases fetch : p[s.pc]? with
  | none => simp [arithmeticStep, halted, fetch]
  | some ins =>
    have writes := otherWrites ins (List.mem_of_getElem? fetch)
    cases ins <;> simp (disch := omega) [arithmeticStep, halted, fetch, naturalDestination] at writes ⊢

theorem arithmeticRun_keeps_register {p : List ArithmeticInstruction}
    {r : ℕ} (otherWrites : ∀ ins ∈ p, naturalDestination ins ≠ r) (s : ArithmeticState) (steps : ℕ) :
    ((arithmeticStep p)^[steps] s).nr r = s.nr r := by
  induction steps with
  | zero => rfl
  | succ k ih =>
    rw [Function.iterate_succ_apply', arithmeticStep_keeps_register otherWrites, ih]

theorem arithmeticRun_keeps_high_register {p : List ArithmeticInstruction}
    {r : ℕ} (lowWrites : ∀ ins ∈ p, naturalDestination ins < r) (s : ArithmeticState) (steps : ℕ) :
    ((arithmeticStep p)^[steps] s).nr r = s.nr r := by
  exact arithmeticRun_keeps_register (fun ins h => (lowWrites ins h).ne) s steps

theorem naturalDestination_ne_of_list {p : List ArithmeticInstruction} {r : ℕ}
    (written : List ℕ) (checked : p.all (fun ins => decide (naturalDestination ins ∈ written)) = true)
    (away : r ∉ written) : ∀ ins ∈ p, naturalDestination ins ≠ r := by
  intro ins present same
  apply away
  exact same ▸ of_decide_eq_true (List.all_eq_true.mp checked ins present)

theorem arithmeticRun_keeps_from_destination_list {p : List ArithmeticInstruction} {r : ℕ}
    (written : List ℕ) (checked : p.all (fun ins => decide (naturalDestination ins ∈ written)) = true)
    (away : r ∉ written) (s : ArithmeticState) (steps : ℕ) :
    ((arithmeticStep p)^[steps] s).nr r = s.nr r :=
  arithmeticRun_keeps_register (naturalDestination_ne_of_list written checked away) s steps

def realDestination : ArithmeticInstruction → ℕ
  | .realConst dst _ | .realAdd dst _ _ | .realSub dst _ _ | .realMul dst _ _
  | .realDiv dst _ _ | .realLoad dst _ => dst
  | _ => 0

private theorem arithmeticStep_keeps_real_register {p : List ArithmeticInstruction}
    {s : ArithmeticState} {r : ℕ} (otherWrites : ∀ ins ∈ p, realDestination ins ≠ r) :
    (arithmeticStep p s).rr r = s.rr r := by
  by_cases halted : s.halted = true
  · simp [arithmeticStep, halted]
  cases fetch : p[s.pc]? with
  | none => simp [arithmeticStep, halted, fetch]
  | some ins =>
    have writes := otherWrites ins (List.mem_of_getElem? fetch)
    cases ins <;> simp (disch := omega) [arithmeticStep, halted, fetch, realDestination] at writes ⊢

theorem arithmeticRun_keeps_real_from_destination_list {p : List ArithmeticInstruction} {r : ℕ}
    (written : List ℕ) (checked : p.all (fun ins => decide (realDestination ins ∈ written)) = true)
    (away : r ∉ written) (s : ArithmeticState) (steps : ℕ) :
    ((arithmeticStep p)^[steps] s).rr r = s.rr r := by
  have avoids : ∀ ins ∈ p, realDestination ins ≠ r := by
    intro ins present same
    apply away
    exact same ▸ of_decide_eq_true (List.all_eq_true.mp checked ins present)
  induction steps with
  | zero => rfl
  | succ k ih => rw [Function.iterate_succ_apply', arithmeticStep_keeps_real_register avoids, ih]

@[simp] theorem naturalDestination_relocate (offset : ℕ) (ins : ArithmeticInstruction) :
    naturalDestination (relocateInstruction offset ins) = naturalDestination ins := by
  cases ins <;> rfl

theorem forall_naturalDestination_append (p : ℕ → Prop) (a b : List ArithmeticInstruction) :
    (∀ ins ∈ appendBlock a b, p (naturalDestination ins)) ↔
      (∀ ins ∈ a, p (naturalDestination ins)) ∧ ∀ ins ∈ b, p (naturalDestination ins) := by
  simp only [appendBlock, List.forall_mem_append, List.forall_mem_map, naturalDestination_relocate]

theorem forall_naturalDestination_counted (p : ℕ → Prop) (one index limit : ℕ)
    (body : List ArithmeticInstruction) :
    (∀ ins ∈ countedLoop one index limit body, p (naturalDestination ins)) ↔
      p 0 ∧ p index ∧ ∀ ins ∈ body, p (naturalDestination ins) := by
  simp only [countedLoop, List.forall_mem_append, List.forall_mem_map, naturalDestination_relocate]
  simp [naturalDestination, and_assoc, and_left_comm, and_comm]

theorem forall_naturalDestination_countedFromZero (p : ℕ → Prop) (one index limit : ℕ)
    (body : List ArithmeticInstruction) :
    (∀ ins ∈ countedLoopFromZero one index limit body, p (naturalDestination ins)) ↔
      p 0 ∧ p index ∧ ∀ ins ∈ body, p (naturalDestination ins) := by
  simp only [countedLoopFromZero, forall_naturalDestination_append, forall_naturalDestination_counted]
  simp [naturalDestination, and_assoc, and_left_comm, and_comm]

theorem forall_naturalDestination_unlessEqual (p : ℕ → Prop) (x y : ℕ)
    (body : List ArithmeticInstruction) :
    (∀ ins ∈ branchOnUnequal x y body, p (naturalDestination ins)) ↔
      p 0 ∧ ∀ ins ∈ body, p (naturalDestination ins) := by
  change (∀ ins ∈ [.natBranch x y 1 2, .natBranch y x (3 + body.length) 3, .jump 3] ++
      body.map (relocateInstruction 3), p (naturalDestination ins)) ↔ _
  simp only [List.forall_mem_append, List.forall_mem_map, naturalDestination_relocate]
  simp [naturalDestination]

theorem no_halt_from_running {p : List ArithmeticInstruction} {s : ArithmeticState} {steps : ℕ}
    (running : s.halted = false) (safe : ∀ k < steps, ((arithmeticStep p)^[k] s).pc < p.length)
    (notHalt : ArithmeticInstruction.halt ∉ p) : ((arithmeticStep p)^[steps] s).halted = false := by
  induction steps with
  | zero => exact running
  | succ k ih =>
    let before := (arithmeticStep p)^[k] s
    have entry : before.pc < p.length := safe k (Nat.lt_succ_self k)
    have live : before.halted = false := ih (fun j earlier => safe j (earlier.trans (Nat.lt_succ_self k)))
    have fetch : p[before.pc]? = some p[before.pc] := List.getElem?_eq_getElem entry
    have selected : p[before.pc] ∈ p := List.getElem_mem entry
    rw [Function.iterate_succ_apply']
    change (arithmeticStep p before).halted = false
    generalize eq : p[before.pc] = instr at fetch selected
    cases instr <;> simp [arithmeticStep, live, fetch, notHalt] at selected ⊢

private theorem mergeDualBoundBlock_low_writes (r : ℕ) (high : 3 ≤ r) :
    ∀ ins ∈ mergeDualBoundBlock, naturalDestination ins < r := by
  simp [mergeDualBoundBlock, appendBlock, prepareDualBoundBlock, mergeSlackEntryBlock,
    relocateInstruction, naturalDestination] <;> omega

private theorem mergeDualBoundBlock_no_halt : ArithmeticInstruction.halt ∉ mergeDualBoundBlock := by
  simp [mergeDualBoundBlock, appendBlock, prepareDualBoundBlock, mergeSlackEntryBlock, relocateInstruction]

/-- Read one cached event. Natural registers 3, 4, and 5 address the identifier, slack, and
rate arrays. Register 7 is the current index. The identifier is zero for an empty slot. -/
def readDualBoundBlock : List ArithmeticInstruction :=
  [.natAdd 6 3 7, .natLoad 0 6, .natAdd 6 4 7, .realLoad 0 6, .natAdd 6 5 7, .realLoad 3 6]

private def dualBoundReadState (s : ArithmeticState) : ArithmeticState :=
  let idAddress := s.nr 3 + s.nr 7
  let slackAddress := s.nr 4 + s.nr 7
  let rateAddress := s.nr 5 + s.nr 7
  {s with
    pc := 6
    nr := Function.update (Function.update (Function.update (Function.update s.nr 6 idAddress)
      0 (s.nm idAddress)) 6 slackAddress) 6 rateAddress
    rr := Function.update (Function.update s.rr 0 (s.rm slackAddress)) 3 (s.rm rateAddress)}

private theorem readDualBoundBlock_spec (s : ArithmeticState) (entry : s.pc = 0) (running : s.halted = false) :
    BlockRuns readDualBoundBlock 6 s (dualBoundReadState s) := by
  apply BlockRuns.of_running_exit
  · simp [dualBoundReadState, arithmeticStep, readDualBoundBlock, Function.iterate_succ_apply', entry, running]
  · exact running
  · rfl

def considerDualBoundBlock : List ArithmeticInstruction := appendBlock readDualBoundBlock mergeDualBoundBlock

def considerDualBoundTakesCandidate (s : ArithmeticState) : Prop :=
  s.nm (s.nr 3 + s.nr 7) ≠ 0 ∧ 0 < s.rm (s.nr 5 + s.nr 7) ∧
    (s.nr 1 = 0 ∨ s.rm (s.nr 4 + s.nr 7) / s.rm (s.nr 5 + s.nr 7) < s.rr 1)

/-- Read and consider one cached event in at most seventeen instructions. -/
theorem considerDualBoundBlock_spec (s : ArithmeticState) (entry : s.pc = 0) (running : s.halted = false) :
    ∃ steps ≤ 17, let result := (arithmeticStep considerDualBoundBlock)^[steps] s
      BlockRuns considerDualBoundBlock steps s result ∧ result.halted = false ∧
      (considerDualBoundTakesCandidate s → result.nr 1 = s.nm (s.nr 3 + s.nr 7) ∧
        result.rr 1 = s.rm (s.nr 4 + s.nr 7) / s.rm (s.nr 5 + s.nr 7)) ∧
      (¬considerDualBoundTakesCandidate s → result.nr 1 = s.nr 1 ∧ result.rr 1 = s.rr 1) ∧
      result.nm = s.nm ∧ result.rm = s.rm ∧ ∀ r, 3 ≤ r → r ≠ 6 → result.nr r = s.nr r := by
  let middle := {dualBoundReadState s with pc := 0}
  have takes : mergeDualBoundTakesCandidate middle ↔ considerDualBoundTakesCandidate s := by
    simp [middle, dualBoundReadState, mergeDualBoundTakesCandidate, considerDualBoundTakesCandidate]
  obtain ⟨steps, bounded, merged, chosen, kept, natMem, realMem⟩ := mergeDualBoundBlock_spec middle rfl running
  have joined := BlockRuns.append (readDualBoundBlock_spec s entry running) merged
  have staysLive := no_halt_from_running (s := middle) running merged.inside mergeDualBoundBlock_no_halt
  refine ⟨6 + steps, by omega, ?_⟩
  dsimp only
  rw [considerDualBoundBlock, joined.run]
  refine ⟨joined, staysLive, ?_, ?_, natMem, realMem, ?_⟩
  · intro h
    simpa [middle, dualBoundReadState, relocateState] using chosen (takes.mpr h)
  · intro h
    simpa [middle, dualBoundReadState, relocateState] using kept (fun yes => h (takes.mp yes))
  · intro r high away
    have nonzero : r ≠ 0 := by omega
    have fixed := arithmeticRun_keeps_high_register (mergeDualBoundBlock_low_writes r high) middle steps
    simpa [middle, dualBoundReadState, relocateState, away, nonzero] using fixed

end VehicleRoutingSurvey.Routing
end RppSource_WeightedReadDeltaRAM

/-! runtime/PrimToOccurrences.lean -/
section RppSource_PrimToOccurrences
namespace VehicleRoutingSurvey.Routing

/-- Reserve the matching pair array immediately after the tree pairs.
The occurrence buffer begins after its capacity of two cells per vertex. -/
def allocateOccurrenceBufferBlock : List ArithmeticInstruction :=
  [.natAdd 0 35 35, .natAdd 106 34 0, .natAdd 0 5 5, .natAdd 33 106 0]

theorem allocateOccurrenceBufferBlock_correct (s : ArithmeticState)
    (entry : s.pc = 0) (running : s.halted = false) :
    ∃ t, BlockRuns allocateOccurrenceBufferBlock 4 s t ∧ t.halted = false ∧
      t.nr 106 = s.nr 34 + 2 * s.nr 35 ∧ t.nr 33 = t.nr 106 + 2 * s.nr 5 ∧
      t.nm = s.nm ∧ t.rm = s.rm ∧
      ∀ r, r ≠ 0 → r ≠ 33 → r ≠ 106 → t.nr r = s.nr r := by
  let t := (arithmeticStep allocateOccurrenceBufferBlock)^[4] s
  have ready : t.halted = false := by
    simp [t, allocateOccurrenceBufferBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
  have exit : t.pc = allocateOccurrenceBufferBlock.length := by
    simp [t, allocateOccurrenceBufferBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
  refine ⟨t, BlockRuns.of_running_exit rfl ready exit, ready, ?_, ?_, ?_, ?_, ?_⟩
  · simp [t, allocateOccurrenceBufferBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
    omega
  · simp [t, allocateOccurrenceBufferBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
    omega
  · simp [t, allocateOccurrenceBufferBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
  · simp [t, allocateOccurrenceBufferBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
  · intro r scratch base reserve
    simp [t, allocateOccurrenceBufferBlock, arithmeticStep, entry, running, Function.iterate_succ_apply',
      Function.update_of_ne scratch, Function.update_of_ne base, Function.update_of_ne reserve]

private theorem connectorOccurrenceDestinationsBelowReservation :
    ∀ ins ∈ connectorOccurrencesBlock, naturalDestination ins < 106 := by
  have checked :
      connectorOccurrencesBlock.all (fun ins => decide (naturalDestination ins < 106)) = true := by
    decide
  exact fun ins found => of_decide_eq_true (List.all_eq_true.mp checked ins found)

def minimumTreeOccurrencesBlock : List ArithmeticInstruction :=
  appendBlock (appendBlock minimumTreeAfterPathsBlock allocateOccurrenceBufferBlock)
    connectorOccurrencesBlock

/-- From the stored all-pairs paths, compute the minimum component tree
and the exact base-plus-connector occurrence array. The result is ready
for degree parity and retains space for the later matching pairs. -/
theorem minimumTreeOccurrencesBlock_correct {I : Service} {rows matrix next : ℕ}
    {table : DirectLinkTable I.graph} {s : ArithmeticState}
    (rural : Rural I) (requiredLinks : I.links.Nonempty)
    (frame : FloydFrame I.graph.n rows matrix s) (nextAt : s.nr 26 = next)
    (sound : DirectLinkTableSound table)
    (representative : DirectLinkRepresentatives I.graph (tableChooses table))
    (pathRows : ∀ target, TightStoredRow target table next s.nm)
    (raw : ∀ k < 2 + 3 * I.graph.q, s.nm k = (ruralNatInput I)[k]?.getD 0)
    (inputBefore : 2 + 3 * I.graph.q ≤ next) (rowsBefore : rows + I.graph.n ≤ next)
    (weightsBefore : I.graph.q ≤ matrix)
    (weights : ∀ e : Fin I.graph.q, s.rm e.val = I.graph.weight e)
    (distances : ∀ p : PrimPair I, s.rm (matrix + primPairOffset p) = distance I.graph p.1 p.2)
    (entry : s.pc = 0) (running : s.halted = false) :
    ∃ (t : ArithmeticState) (tree : List (PrimPair I))
      (paths : List (List (Traversal I.graph))) (steps : ℕ),
      BlockRuns minimumTreeOccurrencesBlock steps s t ∧ t.halted = false ∧
      steps ≤ 300 * (I.graph.n ^ 3 + I.graph.q) ∧
      MinimumComponentTree I tree ∧ Expands I.graph tree paths ∧
      (∀ path ∈ paths, path.length < I.graph.n) ∧
      FloydFrame I.graph.n rows matrix t ∧ t.nr 26 = next ∧ t.nr 28 = 0 ∧
      next + I.graph.n ^ 2 ≤ t.nr 106 ∧ t.nr 33 = t.nr 106 + 2 * I.graph.n ∧
      t.nr 29 = t.nr 33 + (requiredLinkList I ++ paths.flatten.map Prod.fst).length ∧
      OccurrenceArray t.nm (t.nr 33) (requiredLinkList I ++ paths.flatten.map Prod.fst) ∧
      (∀ k < next + I.graph.n ^ 2, t.nm k = s.nm k) ∧
      (∀ p : PrimPair I, t.rm (matrix + primPairOffset p) = distance I.graph p.1 p.2) ∧
      ∀ e : Fin I.graph.q, t.rm e.val = I.graph.weight e := by
  obtain ⟨m, tree, primSteps, output, prim, mReady, primBound, minimum, mFrame,
      outputAt, countAt, pathsAt, outputAfterPaths, mNatural, mDistances, mWeights, pairWords⟩ :=
    minimumTreeAfterPathsBlock_correct rural requiredLinks frame nextAt raw inputBefore rowsBefore
      weightsBefore weights distances entry running
  obtain ⟨a, alloc, aReady, reserved, occurrenceBase, aNat, aReal, aFixed⟩ :=
    allocateOccurrenceBufferBlock_correct {m with pc := 0} rfl mReady
  let allocated := relocateState minimumTreeAfterPathsBlock.length a
  let expansionEntry := {allocated with pc := 0}
  have fixed (r : ℕ) (nonScratch : r ≠ 0) (nonBase : r ≠ 33) (nonReserved : r ≠ 106) :
      expansionEntry.nr r = m.nr r := aFixed r nonScratch nonBase nonReserved
  have copied (address : ℕ) (below : address < next + I.graph.n ^ 2) :
      expansionEntry.nm address = s.nm address :=
    (congrFun aNat address).trans (mNatural address below)
  have aFrame : FloydFrame I.graph.n rows matrix expansionEntry :=
    mFrame.preserved (fun r hlo hhi => fixed r (by omega) (by omega) (by omega)) aNat
  have livePaths (target : Fin I.graph.n) :
      TightStoredRow target table (expansionEntry.nr 26) expansionEntry.nm := by
    have atPaths := (fixed 26 (by decide) (by decide) (by decide)).trans pathsAt
    rw [atPaths]
    refine (pathRows target).preservedBelow le_rfl fun address below => ?_
    exact copied address (by simpa [pow_two] using below)
  have pairAt := (fixed 34 (by decide) (by decide) (by decide)).trans outputAt
  have pairCount := (fixed 35 (by decide) (by decide) (by decide)).trans countAt
  have pairArray : ExpansionPairArray expansionEntry.nm (expansionEntry.nr 34) tree := by
    rw [pairAt]
    intro j hj
    change a.nm _ = _ ∧ a.nm _ = _
    rw [aNat]
    exact pairWords ⟨j, hj⟩
  have liveRaw (address : ℕ) (below : address < 2 + 3 * I.graph.q) :
      expansionEntry.nm address = (ruralNatInput I)[address]?.getD 0 :=
    (copied address (below.trans_le (inputBefore.trans (Nat.le_add_right _ _)))).trans (raw address below)
  have afterPaths : next + I.graph.n ^ 2 ≤ expansionEntry.nr 33 := by
    change next + I.graph.n ^ 2 ≤ a.nr 33
    rw [occurrenceBase, reserved, outputAt]
    omega
  have pairBound : expansionEntry.nr 34 + 2 * tree.length ≤ expansionEntry.nr 33 := by
    change expansionEntry.nr 34 + _ ≤ a.nr 33
    rw [pairAt, occurrenceBase, reserved, outputAt, countAt]
    omega
  have pointerBound : expansionEntry.nr 26 + I.graph.n * I.graph.n ≤ expansionEntry.nr 33 := by
    rw [(fixed 26 (by decide) (by decide) (by decide)).trans pathsAt]
    simpa [pow_two] using afterPaths
  obtain ⟨p, pathSteps, paths, expand, expandBound, ready, expands, pathLengths, zero, cursor,
      array, pFixed, pReal, pNat⟩ :=
    connectorOccurrencesBlock_correct tree rural aFrame sound representative livePaths pairCount
      pairArray liveRaw pairBound (rowsBefore.trans ((Nat.le_add_right _ _).trans afterPaths)) pointerBound
      (inputBefore.trans ((Nat.le_add_right _ _).trans afterPaths)) rfl aReady
  let final := relocateState
    (appendBlock minimumTreeAfterPathsBlock allocateOccurrenceBufferBlock).length p
  have sameReservation : p.nr 106 = a.nr 106 := by
    rw [← expand.run]
    exact arithmeticRun_keeps_high_register connectorOccurrenceDestinationsBelowReservation
      expansionEntry pathSteps
  have finalBase : p.nr 33 = a.nr 33 := pFixed 33 (by decide) (by decide)
  have finalRows : FloydFrame I.graph.n rows matrix final := by
    refine ⟨(pFixed 3 (by decide) (by decide)).trans aFrame.tableBase,
      (pFixed 4 (by decide) (by decide)).trans aFrame.matrixBase,
      (pFixed 5 (by decide) (by decide)).trans aFrame.dimension,
      (pFixed 6 (by decide) (by decide)).trans aFrame.one, ?_⟩
    intro j hj
    exact (pNat _ ((Nat.add_lt_add_left hj _).trans_le
      (rowsBefore.trans ((Nat.le_add_right _ _).trans afterPaths)))).trans (aFrame.rows j hj)
  have countBound : tree.length ≤ I.graph.n := (componentTree_length_lt minimum.1).le
  have product : tree.length * (25 * I.graph.n + 9) ≤ 25 * I.graph.n ^ 2 + 9 * I.graph.n := by
    calc
      _ ≤ I.graph.n * (25 * I.graph.n + 9) := Nat.mul_le_mul_right _ countBound
      _ = _ := by ring
  have square : I.graph.n ^ 2 ≤ I.graph.n ^ 3 := by
    calc
      _ = I.graph.n ^ 2 * 1 := (Nat.mul_one _).symm
      _ ≤ I.graph.n ^ 2 * I.graph.n := Nat.mul_le_mul_left _ rural.1.1
      _ = _ := (pow_succ _ 2).symm
  have vertexBound : I.graph.n ≤ I.graph.n ^ 3 :=
    (by simpa only [pow_two, Nat.mul_one] using Nat.mul_le_mul_left I.graph.n rural.1.1 :
      I.graph.n ≤ I.graph.n ^ 2).trans square
  have cube : 0 < I.graph.n ^ 3 := pow_pos rural.1.1 _
  have bound : primSteps + 4 + pathSteps ≤ 300 * (I.graph.n ^ 3 + I.graph.q) := by omega
  refine ⟨final, tree, paths, _, (prim.append alloc).append expand, ready, bound, minimum, expands,
    pathLengths, finalRows, (pFixed 26 (by decide) (by decide)).trans
      ((fixed 26 (by decide) (by decide) (by decide)).trans pathsAt), zero, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
  · change _ ≤ p.nr 106
    rw [sameReservation, reserved, outputAt]
    omega
  · change p.nr 33 = p.nr 106 + _
    rw [finalBase, sameReservation, occurrenceBase]
    exact congrArg (fun n => a.nr 106 + 2 * n) mFrame.dimension
  · change p.nr 29 = p.nr 33 + _
    rwa [finalBase]
  · change OccurrenceArray p.nm (p.nr 33) _
    rwa [finalBase]
  · intro address below
    exact (pNat address (below.trans_le afterPaths)).trans (copied address below)
  · intro pair
    exact (congrFun (pReal.trans aReal) _).trans (mDistances pair)
  · intro edge
    exact (congrFun (pReal.trans aReal) edge.val).trans (mWeights edge)

end VehicleRoutingSurvey.Routing
end RppSource_PrimToOccurrences

/-! runtime/RawToOccurrences.lean -/
section RppSource_RawToOccurrences
namespace VehicleRoutingSurvey.Routing

def rawToConnectorOccurrencesBlock : List ArithmeticInstruction :=
  appendBlock apspFromRawInputBlock minimumTreeOccurrencesBlock

/-- Compute the required and connector occurrences from the exact
encoded nonempty rural-postman input. This is the checkpoint at which
the odd degrees are computed. -/
theorem rawToConnectorOccurrencesBlock_correct {I : Service}
    (rural : Rural I) (required : I.links.Nonempty) :
    let n := I.graph.n
    let q := I.graph.q
    let rowOffsets := 2 + 3 * q
    let next := rowOffsets + n + n * n + n + n
    let start := arithmeticInput (ruralNatInput I) (ruralRealInput I)
    ∃ (t : ArithmeticState) (table : DirectLinkTable I.graph)
      (tree : List (PrimPair I)) (paths : List (List (Traversal I.graph))) (steps : ℕ),
      BlockRuns rawToConnectorOccurrencesBlock steps start t ∧ t.halted = false ∧
      steps ≤ 500 * (n ^ 3 + q) ∧
      MinimumComponentTree I tree ∧ Expands I.graph tree paths ∧
      (∀ path ∈ paths, path.length < n) ∧ FloydFrame n rowOffsets q t ∧
      t.nr 26 = next ∧ t.nr 28 = 0 ∧ next + n ^ 2 ≤ t.nr 106 ∧
      t.nr 33 = t.nr 106 + 2 * n ∧
      t.nr 29 = t.nr 33 + (requiredLinkList I ++ paths.flatten.map Prod.fst).length ∧
      OccurrenceArray t.nm (t.nr 33) (requiredLinkList I ++ paths.flatten.map Prod.fst) ∧
      DirectLinkTableSound table ∧ DirectLinkRepresentatives I.graph (tableChooses table) ∧
      (∀ target, TightStoredRow target table next t.nm) ∧
      (∀ a < 2 + 3 * q, t.nm a = (ruralNatInput I)[a]?.getD 0) ∧
      (∀ p : PrimPair I, t.rm (q + primPairOffset p) = distance I.graph p.1 p.2) ∧
      ∀ edge : Fin q, t.rm edge.val = I.graph.weight edge := by
  let n := I.graph.n
  let q := I.graph.q
  let rowOffsets := 2 + 3 * q
  let next := rowOffsets + n + n * n + n + n
  obtain ⟨a, table, pathsRun, aReady, aFrame, aNext, input, sound, representative, distanceData,
      weights, rows⟩ := apspFromRawInputBlock_correct rural
  let entry := {a with pc := 0}
  have inputFrame : FloydFrame n rowOffsets q entry :=
    aFrame.preserved (fun _ _ _ => rfl) rfl
  have inputBefore : 2 + 3 * q ≤ next := by dsimp [next, rowOffsets]; omega
  have rowsBefore : rowOffsets + n ≤ next := by dsimp [next]; omega
  have distancePairs (pair : PrimPair I) :
      entry.rm (q + primPairOffset pair) = distance I.graph pair.1 pair.2 := by
    change a.rm _ = _
    simpa [primPairOffset, Nat.add_assoc] using distanceData pair.1 pair.2
  obtain ⟨b, tree, paths, steps, occurrencesRun, bReady, occurrenceBound, minimum, expands,
      short, bFrame, bNext, zero, reserved, occurrenceBase, cursor, occurrences, retained,
      distances, linkWeights⟩ := minimumTreeOccurrencesBlock_correct rural required inputFrame aNext
        sound representative rows input inputBefore rowsBefore le_rfl weights distancePairs rfl aReady
  let final := relocateState apspFromRawInputBlock.length b
  have finalFrame : FloydFrame n rowOffsets q final :=
    bFrame.preserved (fun _ _ _ => rfl) rfl
  have allRows (target : Fin n) : TightStoredRow target table next final.nm := by
    change TightStoredRow target table next b.nm
    exact (rows target).preservedBelow le_rfl
      (fun address below => retained address (by simpa [pow_two] using below))
  have inputCells (address : ℕ) (bound : address < 2 + 3 * q) :
      final.nm address = (ruralNatInput I)[address]?.getD 0 :=
    (retained address (bound.trans_le (inputBefore.trans (Nat.le_add_right _ _)))).trans
      (input address bound)
  have square : n ^ 2 ≤ n ^ 3 := by
    calc
      _ = n ^ 2 * 1 := (Nat.mul_one _).symm
      _ ≤ n ^ 2 * n := Nat.mul_le_mul_left _ rural.1.1
      _ = _ := (pow_succ _ 2).symm
  have vertexBound : n ≤ n ^ 3 :=
    (by simpa only [pow_two, Nat.mul_one] using Nat.mul_le_mul_left n rural.1.1 : n ≤ n ^ 2).trans square
  have positive : 0 < n ^ 3 := pow_pos rural.1.1 _
  have runtime : (49 * n ^ 3 + 24 * n ^ 2 + 36 * n + 33 * q + 38) + steps ≤
      500 * (n ^ 3 + q) := by
    change steps ≤ 300 * (n ^ 3 + q) at occurrenceBound
    omega
  exact ⟨final, table, tree, paths, _, pathsRun.append occurrencesRun, bReady, runtime,
    minimum, expands, short, finalFrame, bNext, zero, reserved, occurrenceBase,
    cursor, occurrences, sound, representative, allRows, inputCells, distances, linkWeights⟩

end VehicleRoutingSurvey.Routing
end RppSource_RawToOccurrences

/-! runtime/EulerAdjacency.lean -/
section RppSource_EulerAdjacency
namespace VehicleRoutingSurvey.Routing

/-- A dart stores the next incident dart, both endpoints, the address of
the occurrence's shared activity bit, and the original traversal code. -/
def insertEulerDartMemory (m : ℕ → ℕ) (head dart source target activity link direction : ℕ) :
    ℕ → ℕ :=
  let m := Function.update m dart (m head)
  let m := Function.update m head dart
  let m := Function.update m (dart + 1) source
  let m := Function.update m (dart + 2) target
  let m := Function.update m (dart + 3) activity
  let m := Function.update m (dart + 4) link
  Function.update m (dart + 5) direction

/-- Prepend one dart to its source vertex's incident list. Register 6
supplies one. Registers 7, 8, 9, 11, 12, 13, 14 hold the head-table base,
source, dart address, target, activity address, link, and direction. -/
def insertEulerDartCell : List ArithmeticInstruction :=
  [.natAdd 0 7 8, .natLoad 2 0, .natStore 9 2, .natStore 0 9,
   .natAdd 0 9 6, .natStore 0 8, .natAdd 0 0 6, .natStore 0 11,
   .natAdd 0 0 6, .natStore 0 12, .natAdd 0 0 6, .natStore 0 13,
   .natAdd 0 0 6, .natStore 0 14]

theorem insertEulerDartCell_correct {s : ArithmeticState} (entry : s.pc = 0)
    (running : s.halted = false) (one : s.nr 6 = 1) :
    ∃ t, BlockRuns insertEulerDartCell 14 s t ∧ t.halted = false ∧
      t.rm = s.rm ∧ t.rr = s.rr ∧ (∀ r, r ≠ 0 → r ≠ 2 → t.nr r = s.nr r) ∧
      t.nm = insertEulerDartMemory s.nm (s.nr 7 + s.nr 8) (s.nr 9)
        (s.nr 8) (s.nr 11) (s.nr 12) (s.nr 13) (s.nr 14) := by
  let t := {s with
    pc := 14
    nr := Function.update (Function.update (Function.update s.nr 0 (s.nr 7 + s.nr 8))
      2 (s.nm (s.nr 7 + s.nr 8))) 0 (s.nr 9 + 5)
    nm := insertEulerDartMemory s.nm (s.nr 7 + s.nr 8) (s.nr 9)
      (s.nr 8) (s.nr 11) (s.nr 12) (s.nr 13) (s.nr 14)}
  refine ⟨t, ⟨?_, ?_, rfl⟩, running, rfl, rfl, ?_, rfl⟩
  · intro j bound
    interval_cases j <;>
      simp [insertEulerDartCell, arithmeticStep, entry, running, Function.iterate_succ_apply']
  · simp [insertEulerDartCell, arithmeticStep, entry, running, one,
      Function.iterate_succ_apply', insertEulerDartMemory, t, Nat.add_assoc, Function.update_idem]
  · intro r other0 other2
    simp [t, Function.update_of_ne other0, Function.update_of_ne other2]


end VehicleRoutingSurvey.Routing
end RppSource_EulerAdjacency

/-! runtime/EulerBuildOccurrence.lean -/
section RppSource_EulerBuildOccurrence
set_option linter.unusedSimpArgs false

namespace VehicleRoutingSurvey.Routing

/-- Construct the two incident darts for one occurrence of an original link.
The occurrence IDs and dart cursor run downward, so prepending the darts
leaves each list in the order used by `EulerOccurrences.initial`. -/
def prepareEulerOccurrenceBlock : List ArithmeticInstruction :=
  [.natSub 20 20 6, .natSub 21 21 22,
   .natAdd 0 23 20, .natLoad 13 0,
   .natAdd 0 13 13, .natAdd 0 0 13, .natAdd 0 0 24,
   .natLoad 11 0, .natAdd 0 0 6, .natLoad 8 0,
   .natAdd 12 25 20, .natStore 12 6, .natAdd 9 21 10, .natConst 14 0]

structure EulerOccurrenceOperands where
  index : ℕ
  dart : ℕ
  link : ℕ
  tail : ℕ
  head : ℕ
  activity : ℕ

def EulerOccurrenceOperands.read (s : ArithmeticState) : EulerOccurrenceOperands :=
  let index := s.nr 20 - 1
  let link := s.nm (s.nr 23 + index)
  let inputOffset := link + link + link + 2
  ⟨index, s.nr 21 - 12, link, s.nm inputOffset, s.nm (inputOffset + 1), s.nr 25 + index⟩

def eulerOccurrencePreserved : List ℕ := [6, 7, 10, 17, 18, 22, 23, 24, 25, 26, 27, 28]

theorem prepareEulerOccurrenceBlock_correct {s : ArithmeticState}
    (entry : s.pc = 0) (running : s.halted = false)
    (one : s.nr 6 = 1) (zero : s.nr 10 = 0) (width : s.nr 22 = 12) (two : s.nr 24 = 2) :
    let e := EulerOccurrenceOperands.read s
    ∃ t, BlockRuns prepareEulerOccurrenceBlock 14 s t ∧ t.halted = false ∧
      t.rm = s.rm ∧ t.rr = s.rr ∧
      (∀ r ∈ eulerOccurrencePreserved, t.nr r = s.nr r) ∧
      t.nr 20 = e.index ∧ t.nr 21 = e.dart ∧
      t.nr 8 = e.head ∧ t.nr 11 = e.tail ∧ t.nr 9 = e.dart ∧
      t.nr 12 = e.activity ∧ t.nr 13 = e.link ∧ t.nr 14 = 0 ∧
      t.nm = Function.update s.nm e.activity 1 := by
  let t := (arithmeticStep prepareEulerOccurrenceBlock)^[14] s
  let e := EulerOccurrenceOperands.read s
  have ready : t.halted = false := by
    simp [t, prepareEulerOccurrenceBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
  have exit : t.pc = prepareEulerOccurrenceBlock.length := by
    simp [t, prepareEulerOccurrenceBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
  refine ⟨t, BlockRuns.of_running_exit rfl ready exit, ready, ?_⟩
  simp [t, e, prepareEulerOccurrenceBlock, EulerOccurrenceOperands.read, eulerOccurrencePreserved,
    arithmeticStep, entry, running, one, zero, width, two, Function.iterate_succ_apply',
    or_imp, forall_and]

/-- Swap the endpoints and advance six cells to the forward dart. -/
def switchEulerDartBlock : List ArithmeticInstruction :=
  [.natAdd 0 8 10, .natAdd 8 11 10, .natAdd 11 0 10, .natAdd 9 9 26, .natAdd 14 6 10]

theorem switchEulerDartBlock_correct {s : ArithmeticState}
    (entry : s.pc = 0) (running : s.halted = false)
    (one : s.nr 6 = 1) (zero : s.nr 10 = 0) (halfWidth : s.nr 26 = 6) :
    ∃ t, BlockRuns switchEulerDartBlock 5 s t ∧ t.halted = false ∧
      t.nm = s.nm ∧ t.rm = s.rm ∧ t.rr = s.rr ∧
      (∀ r ∈ eulerOccurrencePreserved, t.nr r = s.nr r) ∧
      t.nr 8 = s.nr 11 ∧ t.nr 11 = s.nr 8 ∧ t.nr 9 = s.nr 9 + 6 ∧
      t.nr 12 = s.nr 12 ∧ t.nr 13 = s.nr 13 ∧ t.nr 14 = 1 ∧
      t.nr 20 = s.nr 20 ∧ t.nr 21 = s.nr 21 := by
  let t := (arithmeticStep switchEulerDartBlock)^[5] s
  have ready : t.halted = false := by
    simp [t, switchEulerDartBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
  have exit : t.pc = switchEulerDartBlock.length := by
    simp [t, switchEulerDartBlock, arithmeticStep, entry, running, Function.iterate_succ_apply']
  refine ⟨t, BlockRuns.of_running_exit rfl ready exit, ready, ?_⟩
  simp [t, switchEulerDartBlock, eulerOccurrencePreserved, arithmeticStep, entry, running,
    one, zero, halfWidth, Function.iterate_succ_apply', or_imp, forall_and]

def buildEulerOccurrenceBlock : List ArithmeticInstruction :=
  appendBlock (appendBlock (appendBlock prepareEulerOccurrenceBlock insertEulerDartCell)
    switchEulerDartBlock) insertEulerDartCell

def EulerOccurrenceOperands.write (e : EulerOccurrenceOperands) (heads : ℕ) (memory : ℕ → ℕ) : ℕ → ℕ :=
  let memory := Function.update memory e.activity 1
  let memory := insertEulerDartMemory memory (heads + e.head) e.dart e.head e.tail e.activity e.link 0
  insertEulerDartMemory memory (heads + e.tail) (e.dart + 6) e.tail e.head e.activity e.link 1

/-- Install both darts and the shared live flag in a fixed number of steps. -/
theorem buildEulerOccurrenceBlock_correct {s : ArithmeticState}
    (entry : s.pc = 0) (running : s.halted = false)
    (one : s.nr 6 = 1) (zero : s.nr 10 = 0) (width : s.nr 22 = 12)
    (two : s.nr 24 = 2) (halfWidth : s.nr 26 = 6) :
    let e := EulerOccurrenceOperands.read s
    ∃ t, BlockRuns buildEulerOccurrenceBlock 47 s t ∧ t.halted = false ∧
      t.rm = s.rm ∧ t.rr = s.rr ∧
      (∀ r ∈ eulerOccurrencePreserved, t.nr r = s.nr r) ∧
      t.nr 20 = e.index ∧ t.nr 21 = e.dart ∧ t.nm = e.write (s.nr 7) s.nm := by
  let e := EulerOccurrenceOperands.read s
  obtain ⟨prep, prepRun, prepReady, prepRm, prepRr, prepKeeps, prepIndex, prepCursor,
    prepSource, prepTarget, prepDart, prepFlag, prepLink, prepDirection, prepMem⟩ :=
    prepareEulerOccurrenceBlock_correct entry running one zero width two
  obtain ⟨back, backRun, backReady, backRm, backRr, backKeeps, backMem⟩ :=
    insertEulerDartCell_correct (s := {prep with pc := 0}) rfl prepReady
      ((prepKeeps 6 (by decide)).trans one)
  have backFixed (r) (hr : r ∈ eulerOccurrencePreserved) : back.nr r = s.nr r := by
    have shows0 : r ≠ 0 := by rintro rfl; simp [eulerOccurrencePreserved] at hr
    have shows2 : r ≠ 2 := by rintro rfl; simp [eulerOccurrencePreserved] at hr
    exact (backKeeps r shows0 shows2).trans (prepKeeps r hr)
  obtain ⟨turn, turnRun, turnReady, turnMem, turnRm, turnRr, turnKeeps, turnSource, turnTarget,
    turnDart, turnFlag, turnLink, turnDirection, turnIndex, turnCursor⟩ :=
    switchEulerDartBlock_correct (s := {back with pc := 0}) rfl backReady
      ((backFixed 6 (by decide)).trans one) ((backFixed 10 (by decide)).trans zero)
      ((backFixed 26 (by decide)).trans halfWidth)
  have turnFixed (r) (hr : r ∈ eulerOccurrencePreserved) : turn.nr r = s.nr r :=
    (turnKeeps r hr).trans (backFixed r hr)
  obtain ⟨forward, forwardRun, forwardReady, forwardRm, forwardRr, forwardKeeps, forwardMem⟩ :=
    insertEulerDartCell_correct (s := {turn with pc := 0}) rfl turnReady
      ((turnFixed 6 (by decide)).trans one)
  have forwardFixed (r) (hr : r ∈ eulerOccurrencePreserved) : forward.nr r = s.nr r := by
    have shows0 : r ≠ 0 := by rintro rfl; simp [eulerOccurrencePreserved] at hr
    have shows2 : r ≠ 2 := by rintro rfl; simp [eulerOccurrencePreserved] at hr
    exact (forwardKeeps r shows0 shows2).trans (turnFixed r hr)
  have run := ((prepRun.append backRun).append turnRun).append forwardRun
  refine ⟨_, run, forwardReady, forwardRm.trans (turnRm.trans (backRm.trans prepRm)),
    forwardRr.trans (turnRr.trans (backRr.trans prepRr)), forwardFixed, ?_, ?_, ?_⟩
  · exact (forwardKeeps 20 (by decide) (by decide)).trans
      (turnIndex.trans ((backKeeps 20 (by decide) (by decide)).trans prepIndex))
  · exact (forwardKeeps 21 (by decide) (by decide)).trans
      (turnCursor.trans ((backKeeps 21 (by decide) (by decide)).trans prepCursor))
  · have backMemory : back.nm =
        insertEulerDartMemory (Function.update s.nm e.activity 1)
          (s.nr 7 + e.head) e.dart e.head e.tail e.activity e.link 0 := by
      simpa only [prepMem, prepKeeps 7 (by decide), prepSource, prepTarget, prepDart, prepFlag,
        prepLink, prepDirection] using backMem
    have backSource := (backKeeps 8 (by decide) (by decide)).trans prepSource
    have backTarget := (backKeeps 11 (by decide) (by decide)).trans prepTarget
    have backDart := (backKeeps 9 (by decide) (by decide)).trans prepDart
    have backFlag := (backKeeps 12 (by decide) (by decide)).trans prepFlag
    have backLink := (backKeeps 13 (by decide) (by decide)).trans prepLink
    change forward.nm = e.write (s.nr 7) s.nm
    simpa only [e, EulerOccurrenceOperands.write, turnMem, backMemory, turnFixed 7 (by decide),
      turnSource, turnTarget, turnDart, turnFlag, turnLink, turnDirection, backSource, backTarget,
      backDart, backFlag, backLink] using forwardMem


end VehicleRoutingSurvey.Routing
end RppSource_EulerBuildOccurrence

/-! runtime/EulerBuildLoop.lean -/
section RppSource_EulerBuildLoop
namespace VehicleRoutingSurvey.Routing

structure EulerBuildView where
  remaining : ℕ
  dartCursor : ℕ
  memory : ℕ → ℕ

def EulerBuildView.read (s : ArithmeticState) : EulerBuildView :=
  ⟨s.nr 20, s.nr 21, s.nm⟩

def EulerBuildView.next (heads input flags : ℕ) (view : EulerBuildView) : EulerBuildView :=
  let index := view.remaining - 1
  let link := view.memory (input + index)
  let endpoints := link + link + link + 2
  let e : EulerOccurrenceOperands :=
    ⟨index, view.dartCursor - 12, link, view.memory endpoints, view.memory (endpoints + 1),
      flags + index⟩
  ⟨e.index, e.dart, e.write heads view.memory⟩

def buildEulerOccurrencesBlock : List ArithmeticInstruction :=
  countedLoopFromZero 6 17 18 buildEulerOccurrenceBlock

def eulerBuildFixed : List ℕ := [6, 7, 10, 18, 22, 23, 24, 25, 26, 27, 28]

private structure EulerBuildLoopInvariant (s : ArithmeticState) (i : ℕ)
    (m : ArithmeticState) : Prop where
  entry : m.pc = 0
  running : m.halted = false
  index : m.nr 17 = i
  fixed : ∀ r ∈ eulerBuildFixed, m.nr r = s.nr r
  realMemory : m.rm = s.rm
  realRegisters : m.rr = s.rr
  view : EulerBuildView.read m =
    (EulerBuildView.next (s.nr 7) (s.nr 23) (s.nr 25))^[i] (EulerBuildView.read s)

theorem buildEulerOccurrencesBlock_correct {s : ArithmeticState}
    (entry : s.pc = 0) (running : s.halted = false)
    (one : s.nr 6 = 1) (zero : s.nr 10 = 0) (width : s.nr 22 = 12)
    (two : s.nr 24 = 2) (halfWidth : s.nr 26 = 6) :
    ∃ t, BlockRuns buildEulerOccurrencesBlock (1 + (s.nr 18 * 50 + 1)) s t ∧
      t.halted = false ∧ t.rm = s.rm ∧ t.rr = s.rr ∧
      (∀ r ∈ eulerBuildFixed, t.nr r = s.nr r) ∧
      EulerBuildView.read t =
        (EulerBuildView.next (s.nr 7) (s.nr 23) (s.nr 25))^[s.nr 18] (EulerBuildView.read s) := by
  have initial : EulerBuildLoopInvariant s 0 {s with pc := 0, nr := Function.update s.nr 17 0} := by
    refine ⟨rfl, running, by simp, ?_, rfl, rfl, by simp [EulerBuildView.read]⟩
    intro r present
    have distinct : r ≠ 17 := by rintro rfl; simp [eulerBuildFixed] at present
    exact Function.update_of_ne distinct _ _
  have control (i) (m : ArithmeticState) (inv : EulerBuildLoopInvariant s i m) :
      m.pc = 0 ∧ m.halted = false ∧ m.nr 17 = i ∧ m.nr 18 = s.nr 18 :=
    ⟨inv.entry, inv.running, inv.index, inv.fixed 18 (by decide)⟩
  have iterate (i : ℕ) (_ : i < s.nr 18) (m : ArithmeticState) (inv : EulerBuildLoopInvariant s i m) :
      ∃ t, BlockRuns buildEulerOccurrenceBlock 47 m t ∧ t.halted = false ∧
        EulerBuildLoopInvariant s (i + 1)
          {t with pc := 0, nr := Function.update t.nr 17 (t.nr 17 + t.nr 6)} := by
    obtain ⟨t, run, ready, rm, rr, stable, count, address, memory⟩ :=
      buildEulerOccurrenceBlock_correct inv.entry inv.running
        ((inv.fixed 6 (by decide)).trans one) ((inv.fixed 10 (by decide)).trans zero)
        ((inv.fixed 22 (by decide)).trans width) ((inv.fixed 24 (by decide)).trans two)
        ((inv.fixed 26 (by decide)).trans halfWidth)
    have index := (stable 17 (by decide)).trans inv.index
    have increment := ((stable 6 (by decide)).trans (inv.fixed 6 (by decide))).trans one
    refine ⟨t, run, ready, ⟨rfl, ready, by simp [index, increment], ?_, rm.trans inv.realMemory,
      rr.trans inv.realRegisters, ?_⟩⟩
    · intro r present
      have distinct : r ≠ 17 := by rintro rfl; simp [eulerBuildFixed] at present
      exact (Function.update_of_ne distinct _ _).trans
        ((stable r (by simp [eulerBuildFixed, eulerOccurrencePreserved] at present ⊢; tauto)).trans
          (inv.fixed r present))
    · have nextView : EulerBuildView.read t =
          (EulerBuildView.read m).next (s.nr 7) (s.nr 23) (s.nr 25) := by
        have heads := inv.fixed 7 (by decide)
        have input := inv.fixed 23 (by decide)
        have flags := inv.fixed 25 (by decide)
        simp [EulerBuildView.read, EulerBuildView.next, EulerOccurrenceOperands.read, count, address,
          memory, heads, input, flags]
      rw [inv.view] at nextView
      simpa [EulerBuildView.read, Function.iterate_succ_apply'] using nextView
  obtain ⟨last, inv, run⟩ := countedLoopFromZero_correct 6 17 18 (s.nr 18) 47
    buildEulerOccurrenceBlock (EulerBuildLoopInvariant s) entry running initial control iterate
  exact ⟨_, run, inv.running, inv.realMemory, inv.realRegisters, inv.fixed, inv.view⟩


end VehicleRoutingSurvey.Routing
end RppSource_EulerBuildLoop

Source
J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity of vehicle routing and scheduling problems (1979), Table 3, printed p. 5. https://ir.cwi.nl/pub/9658/9658D.pdf

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me