`swap::regroup` fails on complicated reorderings

[tangentstorm]

The plan_regroup function makes a plan for moving variables into place.

The "plan" is just a hashmap of variables that need to be moved, and the position into which they should go. Unfortunately, it is not a very good plan.

The problem is this algorithm was designed for the simple needs of the swap solver: moving a set of variables up to the top. But now that we have reorder_by_force, which can generate a completely new ordering, it's quite possible to request orderings that the current algorithm can't solve for.

Basically, this algorithm needs to be reworked. In the meantime, it's still possible to achieve any ordering you want, simply by iteratively bringing the variables you want to the top. Start by passing [{everything else},{z}] to reorder, then `[{everything else},{y},{z}], until you have all your variables in individual hash sets.

I hope to fix this soon. I'm mostly putting this here in case anyone runs into the problem before it's fixed.

[tangentstorm]

There's a grok chat here with a working animation of the algorithm we want.
https://grok.com/chat/92f54565-20c3-4bfa-bd47-69f5765129fa

[tangentstorm]

old behavior

In the current implementation, regroup takes a Vec<Set>, because it is mainly used to substitute one BDD for a variable in another BDD, and the two input BDDs may have overlapping variables in different orders, and we don't really care what order they wind up in as long as they're both the same.

The current implementation calls plan_regroup once to make a "plan", which is actually just a mapping of variables to final positions. Then it runs a swarm, and every time a worker initializes, we call next_regroup_task to figure out the next incremental swap, working from the plan.

This worked fine for the swap solver (where the variable is always replaced by a bdd of 3 variables) but it fails in the general reordering mechanism required by the python binding.

what needs to change

First, the groups should be analyzed and the "plan" (which is really a goal) should be changed to a simple Vec<VID>, and then we could call a new function called reorder(goal: Vec<VID>).

For the swap solver, this would probably mean reordering the smaller one so no two variables ever have to cross each other in the bigger one for them to match, then reorder the bigger one to put those variables at the top)

The reorder function would still spawn a swarm, and still feed it row-swapping tasks incrementally based on an incremental planning function, but this function would be the new algorithm produced by grok:

function* reorderPlan() {
    while (!arraysEqual(currentOrder, targetOrder)) {
        let swaps = [];
        let tempLocked = new Set(locked);
        for (let i = 0; i < NUM_ITEMS - 1; i++) {
            if (!tempLocked.has(i) && !tempLocked.has(i + 1)) {
                const itemA = currentOrder[i];
                const itemB = currentOrder[i + 1];
                const targetA = targetOrder.findIndex(t => t.id === itemA.id);
                const targetB = targetOrder.findIndex(t => t.id === itemB.id);

                const dirA = i < targetA ? 'down' : (i > targetA ? 'up' : 'stay');
                const dirB = i + 1 < targetB ? 'down' : (i + 1 > targetB ? 'up' : 'stay');
                const distA = Math.abs(i - targetA);
                const distB = Math.abs(i + 1 - targetB);

                if (dirA !== dirB || (dirA === 'stay' && dirB !== 'stay') || (dirB === 'stay' && dirA !== 'stay')) {
                    const newOrder = [...currentOrder];
                    [newOrder[i], newOrder[i + 1]] = [newOrder[i + 1], newOrder[i]];
                    const newDistA = Math.abs(i + 1 - targetA);
                    const newDistB = Math.abs(i - targetB);
                    const oldTotalDist = distA + distB;
                    const newTotalDist = newDistA + newDistB;

                    if (newTotalDist < oldTotalDist || (dirA === 'stay' && newDistB < distB) || (dirB === 'stay' && newDistA < distA)) {
                        swaps.push([i, i + 1]);
                        tempLocked.add(i);
                        tempLocked.add(i + 1);
                    }
                }
            }
        }
        yield swaps;
    }
    log("Sorting complete!");
}

Here is a rust translation generated by claude 4:

#[derive(Debug, PartialEq, Eq)]
enum Mv { UP, DN, OK }

fn plan_regroup(vids:&[VID], groups:&[HashSet<VID>])->HashMap<VID,usize> {
  // Direct translation of the JavaScript algorithm from algo-final.js
  let mut plan = HashMap::new();

  // if only one group, there's nothing to do:
  if groups.len() == 1 && groups[0].len() == vids.len() { return plan }

  // Build target position mapping from groups (bottom-to-top)
  let mut vid_to_target: HashMap<VID, usize> = HashMap::new();
  let mut target_pos = 0;
  for group in groups {
    for &vid in group {
      vid_to_target.insert(vid, target_pos);
      target_pos += 1;
    }
  }

  // Simple greedy algorithm - direct translation from JavaScript
  for i in 0..vids.len().saturating_sub(1) {
    let vid_a = vids[i];
    let vid_b = vids[i + 1];

    if let (Some(&target_a), Some(&target_b)) = (vid_to_target.get(&vid_a), vid_to_target.get(&vid_b)) {
      // Calculate current distances (absolute difference)
      let dist_a = if i > target_a { i - target_a } else { target_a - i };
      let dist_b = if i + 1 > target_b { i + 1 - target_b } else { target_b - (i + 1) };

      // Calculate distances after swap
      let new_dist_a = if i + 1 > target_a { i + 1 - target_a } else { target_a - (i + 1) };
      let new_dist_b = if i > target_b { i - target_b } else { target_b - i };

      // Apply the same heuristic as JavaScript: swap if it reduces total distance
      let old_total = dist_a + dist_b;
      let new_total = new_dist_a + new_dist_b;

      // Also check direction-based conditions like the JavaScript version
      let dir_a = if i < target_a { Mv::DN } else if i > target_a { Mv::UP } else { Mv::OK };
      let dir_b = if i + 1 < target_b { Mv::DN } else if i + 1 > target_b { Mv::UP } else { Mv::OK };

      // JavaScript condition: different directions OR one stays while other moves
      let should_consider = dir_a != dir_b ||
                           (dir_a == Mv::OK && dir_b != Mv::OK) ||
                           (dir_b == Mv::OK && dir_a != Mv::OK);

      if should_consider && (new_total < old_total ||
                            (dir_a == Mv::OK && new_dist_b < dist_b) ||
                            (dir_b == Mv::OK && new_dist_a < dist_a)) {
        // Mark both variables as needing to move to their target positions
        if i != target_a { plan.insert(vid_a, target_a); }
        if (i + 1) != target_b { plan.insert(vid_b, target_b); }
      }
    }
  }

  plan
}

This gives some insight into what's happening, but it does seem to have dropped the lock variable ,which is quite important for planning.

If this were a single threaded procedure, it would be trivial (just sort the rows by their target position). The complexity comes because swaps happen in parallel, and therefore require locking, and locked items can't move past each other... And also we have no idea how long each swap will take: some are fast, some are slow. It all depends on the graph we're dealing with.

[copilot-swe-agent]

@tangentstorm Unfortunately I hit an unexpected error while trying to work on issue #12. I've automatically reported this to GitHub.

You can ask me to try again later by unassigning and then reassigning the issue to me again.

If you want to contact GitHub about this error, please mention the following identifier so they can better serve you: 5e39b606-df5b-482f-a38c-8946fb9f39a3

Sorry for the inconvenience!