Every virtual-DOM framework needs to answer the same question every time a list re-renders: which of the OLD rendered items can be reused (just patched in place, or moved to a new position) versus which are genuinely new or gone? Comparing by array POSITION alone gets this wrong the moment a list reorders (shifting every item down by one looks, positionally, like every single item changed) -- that's exactly why React requires a stable key on list items: the key is what lets the algorithm recognize "this is the SAME logical item, just moved" instead of tearing down and rebuilding everything.

A vnode is a plain dict: {"key": ..., "type": ..., "props": {...}}.

Implement reconcile(old_children, new_children), using React's real single-pass algorithm (this is a simplified version of the keyed-children path in ReactChildFiber.js):

Walk new_children left to right, tracking last_placed_index (the highest old index placed so far, starting at 0). For each new node:

• Key not found in old_children -- brand new item: ("INSERT", key, new_index).
• Key found, but type differs from the old node's -- can't patch a <div> into a <span> in place, so it's a remount: emit BOTH ("DELETE", key, None) and ("INSERT", key, new_index).
• Key found, same type -- compare the matched node's original index (old_index) to last_placed_index:
  • old_index < last_placed_index -- this node has fallen behind something already placed after it: ("MOVE", key, new_index).
  • old_index >= last_placed_index -- already in relative order, no move needed: ("KEEP", key, new_index), and update last_placed_index = old_index.

After the pass, any old_children key that was never matched is a real deletion: append ("DELETE", key, None) for each, in old_children order.

Example

old = [{"key": "a", ...}, {"key": "b", ...}, {"key": "c", ...}]
new = [{"key": "c", ...}, {"key": "a", ...}, {"key": "b", ...}]

reconcile(old, new)
# -> [("KEEP", "c", 0), ("MOVE", "a", 1), ("MOVE", "b", 2)]

Notice this is asymmetric: moving c to the front is "free" (it becomes the new anchor, since nothing has been placed yet), but a and b -- which used to come BEFORE c -- now genuinely have to move after it. This exact asymmetry shows up in real React DevTools profiles of reordered lists.

Constraints

• Process new_children in order; last_placed_index only ever increases (via the KEEP branch).
• A DELETE for an unmatched old key never appears before the pass over new_children is complete.
• Don't sort or reorder the input lists -- the algorithm is a single left-to-right pass.

Real-world grounding

• React's keyed-children reconciliation: packages/react-reconciler/src/ReactChildFiber.js -- see reconcileChildrenArray and the lastPlacedIndex tracking this exercise implements a simplified version of.

Real React additionally diffs and patches props in place for KEEP/MOVE nodes (not just decides reuse-vs-remount) and handles non-keyed children, fragments, and portals -- this exercise implements the core placement decision underneath all of that.