Substitute Algorithm: Take the New Straight Road to School

🚲 The Story of the New Straight Road

Meet Ravi, a class seven student who cycles to school every morning. His route is famous in the colony — famous for being ridiculous.

It was never planned. It just grew. Years ago, the direct lane was dug up for pipes, so everyone turned left at the milk booth. Then the shortcut behind the market closed for a wedding hall, so they looped around the pond. Then a stray-dog corner appeared, so they added a detour past the temple. Each turn made sense at the time. Today the dig is finished, the wedding hall has a back gate, the dogs have moved on — but Ravi still rides the full zig-zag: left at the milk booth, around the pond, past the temple, through the cycle stand of the other school, and finally in through his own gate. Twenty-five minutes, eleven turns, and three places where new students always get lost. When his little cousin Anu joined the school last term and asked him to draw the route, Ravi needed a full page and two arrows pointing off the edge of the paper. "Why do we go past the temple?" Anu asked. Ravi opened his mouth, then closed it. He did not actually know anymore. Nobody did. The route had become pure history with pedals.

Then, one Monday, the municipality opens a brand-new straight road. From Ravi's colony gate, it runs directly to the school. Same starting point, same destination — seven minutes, two turns.

Now, here is the question that matters. Should Ravi improve his old route? Maybe trim the temple detour, shave a minute near the pond? No. Patching a zig-zag still leaves a zig-zag. The honest move is to abandon the old route entirely and take the new road. Nothing about his goal changes — leave home, reach school on time. Only the path changes, from a tangle of historical accidents to a simple straight line.

But notice what a careful boy Ravi is. Before switching on a school day, he tests the new road on a Sunday. He rides it once with Anu timing him at the gate. Does it actually reach the school gate? Is it open at 7 a.m., or does the corporation close it for morning cleaning? Does it flood after rain like the pond road does? He even rides it once with his heavy bag, because a road that is fine with an empty basket may feel different with five kilos of books. Only when every check passes does he switch — and then he never looks back. The old route survives only in one place: Anu's hand-drawn map, kept as a souvenir of how silly things used to be.

Code grows zig-zag routes too. A method starts simple, then a bug fix adds a flag, an edge case adds a nested loop, a special customer adds a strange branch. Years later the method works, but the way it works is a tour of historical accidents. When you discover a straight road — a simpler algorithm, a cleaner structure, a well-tested library call — the right move is not to patch the tangle. It is to throw the old body away and put the straight road in its place. That refactoring is called Substitute Algorithm. And Ravi's Sunday test ride? That is your test suite, and it must come first.

🔍 What is Substitute Algorithm?

Substitute Algorithm is the refactoring where you replace the entire body of a method with a different, clearer algorithm that produces the same results. The method's contract — its name, its parameters, what it returns, what callers can observe — stays exactly the same. Only the inside changes.

This makes it an unusual member of the Composing Methods family. Its siblings mostly move code: Extract Method relocates lines into a new function, Replace Method with Method Object relocates a whole computation into a class, Remove Assignments to Parameters renames work onto a local. In all of those, the original logic survives, just in new places. Substitute Algorithm is different: the original logic is deleted. The destination is the same; the road is brand new.

Why would you do something so drastic? Because some implementations are simply not worth improving line by line. A method built from flags, nested loops, manual breaks, and patched-on special cases can be so tangled that each small edit risks breaking it — like Ravi trying to "slightly straighten" the pond loop. When you know a fundamentally simpler approach, rewriting the body in one clean stroke is both easier and safer than ten risky micro-edits, provided the safety rule below is respected.

A naming note from Fowler's books. Unlike some refactorings that were renamed between editions, this one kept its name: it is Substitute Algorithm in both the first (1999) and second (2018) editions of Martin Fowler's Refactoring, and on refactoring.com's catalog. Fowler's own example is famously small — a function that checks names against a hard-coded list of people, rewritten from a chain of repetitive condition checks into a simple collection lookup. The lesson in that tiny example is the big lesson of this whole technique: before substituting, make the method as small as possible, so you are swapping one algorithm, not five.

🕑 When do we need it?

Reach for Substitute Algorithm when one or more of these are true:

1. The mechanics drown the intent. You read the method and see loops, flags, counters, and breaks — but you have to reverse-engineer what it is actually trying to do. When the "what" is simple but the "how" is a puzzle, a substitution that says the "what" directly is a huge win.
2. You found a genuinely better road. Maybe the language gained a feature (Set, find, pattern matching), maybe a well-tested library function does the whole job, maybe you simply learned a better algorithm in class. Hand-rolled code that re-invents a standard operation is a substitution waiting to happen.
3. The old body keeps breeding bugs. If every second bug report traces back to the same method's flag-and-loop bookkeeping, the algorithm itself is the bug factory. Replacing it removes a whole class of future defects, not just today's.
4. Requirements shifted under the algorithm. The old approach was right for the old problem; the problem changed, and the method got patched until it barely fits. A fresh algorithm designed for the current requirement is often shorter than the patches.
5. You just decomposed a Long Method. Substitution is the natural endgame after Extract Method or a method object has broken a monolith into small pieces. Each piece is now small enough that swapping its algorithm is a contained, low-risk change instead of open-heart surgery.

And know the situations where the answer is not yet or no:

• Tests are weak and you cannot strengthen them. Then a substitution is unverifiable. Fix the tests first; that is part of this refactoring, not optional homework.
• The method does many jobs. Decompose first. Substituting a 200-line multi-purpose method wholesale means debugging five swaps at once when something fails.
• Several algorithms must coexist at runtime — for example, different discount rules for different customer tiers. That is the Strategy pattern's job, not a substitution.
• The "better" algorithm is only better on paper. A faster but inscrutable replacement may be a net loss. Clarity is the usual goal; speed is the bonus.

The decision really hangs on two questions — how strong is your safety net, and how big is the clarity win? Place your method on this chart before touching anything:

Notice where the big routeMinutes monster sits — huge clarity gain but weak tests, which means the first job is moving it rightward by writing characterization tests, not rewriting it.

👀 Before and after at a glance

Here is a typical zig-zag in TypeScript. The school van app must answer: which stop on the route is Ravi's stop, and what is its pickup time? The old body grew the usual way — nested loops, a found-flag, and two breaks:

interface Stop {
  name: string;
  pickupTime: string;
}
 
// BEFORE: flags, nested loops, breaks — the mechanics drown the intent
function pickupTimeFor(stops: Stop[], studentStops: string[]): string {
  let found: Stop | null = null;
  for (let i = 0; i < stops.length; i++) {
    for (let j = 0; j < studentStops.length; j++) {
      if (stops[i].name === studentStops[j]) {
        found = stops[i];
        break;
      }
    }
    if (found !== null) {
      break;
    }
  }
  if (found === null) {
    return "NOT-ON-ROUTE";
  }
  return found.pickupTime;
}

What is this method for? Strip away the bookkeeping and the answer is one sentence: return the pickup time of the first stop whose name is in the student's stop list, or a marker if there is none. The new road says exactly that:

// AFTER: the body states the intent directly — and is faster too
function pickupTimeFor(stops: Stop[], studentStops: string[]): string {
  const wanted = new Set(studentStops);
  const stop = stops.find((s) => wanted.has(s.name));
  return stop ? stop.pickupTime : "NOT-ON-ROUTE";
}

Three lines. No flag, no indices, no breaks. A reader gets the intent in one pass. And as a bonus, membership checking through a Set is faster than the inner loop when the lists grow — the straight road is shorter and smoother. Crucially, the contract is untouched: same parameters, same return values, including the "first matching stop wins" rule and the "NOT-ON-ROUTE" marker for no match. Callers cannot tell anything changed — except that nothing new breaks.

College corner: the speed bonus here has a precise name — algorithmic complexity. The old body checks every student stop for every route stop: with n route stops and m student stops, that is up to n×m comparisons, written O(n·m). The new body first builds a hash set in O(m), then checks each route stop with an O(1) average-time lookup, giving O(n + m) overall. For a school van with 10 stops, nobody can feel the difference. But the same shape of code appears in college projects with ten thousand records on each side: O(n·m) is a hundred million comparisons, O(n + m) is twenty thousand operations — the difference between a frozen page and an instant answer. Two honest footnotes your algorithms professor would insist on: hash lookups are O(1) on average (worst cases exist), and the set costs O(m) extra memory — a classic time-versus-space trade. Substitute Algorithm is often exactly this move: swapping a brute-force shape for a better data structure, with tests proving the answers never changed.

🪜 Step-by-step, the safe way

Substitute Algorithm is the refactoring with the highest "silent slip" risk in the beginner's toolkit, because nothing of the old body survives to anchor you. So the steps put almost all the effort before the swap.

Let us walk the van-stop example through the full discipline.

Step 1 — Shrink the method first. Substitution is safest on a small, single-purpose method. If the method also formats messages or saves data, apply Extract Method until the algorithm you want to replace stands alone. Our pickupTimeFor already does one job, so we move on.

Step 2 — Build the safety net. Write tests that capture the contract, especially the edges. For our method, the honest list looks like this:

// Step 2: characterization tests — written BEFORE any new code
describe("pickupTimeFor", () => {
  const stops = [
    { name: "Milk Booth", pickupTime: "07:10" },
    { name: "Pond Road", pickupTime: "07:18" },
    { name: "Temple Gate", pickupTime: "07:25" },
  ];
 
  it("returns the time of a matching stop", () => {
    expect(pickupTimeFor(stops, ["Pond Road"])).toBe("07:18");
  });
 
  it("returns the FIRST route stop when several match", () => {
    // order rule: route order wins, not the order of studentStops
    expect(pickupTimeFor(stops, ["Temple Gate", "Milk Booth"])).toBe("07:10");
  });
 
  it("returns the marker when nothing matches", () => {
    expect(pickupTimeFor(stops, ["Airport"])).toBe("NOT-ON-ROUTE");
  });
 
  it("handles an empty route", () => {
    expect(pickupTimeFor([], ["Milk Booth"])).toBe("NOT-ON-ROUTE");
  });
 
  it("handles an empty student list", () => {
    expect(pickupTimeFor(stops, [])).toBe("NOT-ON-ROUTE");
  });
});

Pause on the second test. It documents a quirk: when both "Temple Gate" and "Milk Booth" match, the old loops return the one that comes first in the route, not first in the student's list. Is that intended? Maybe, maybe not — but callers may rely on it, so the test pins it down. This is the single most valuable minute of the whole refactoring: discovering the tie-breaking rule before the swap instead of in a production bug report.

Run the suite against the old body. All green? The net is ready.

College corner: this style of testing has a formal name — characterization testing (Michael Feathers' term from Working Effectively with Legacy Code), also called golden master testing when you record whole outputs wholesale. The philosophy is unusual: the tests do not assert what the code should do; they assert what it actually does, quirks included, so any change becomes visible. For a swap like this, you can go one level stronger with differential testing: run the old and new algorithms side by side on hundreds of random inputs and assert they always agree — the technique compiler writers use to validate optimizers. Property-based testing libraries (fast-check for TypeScript, Hypothesis for Python, FsCheck for .NET) automate exactly this: you state the property "old(x) equals new(x) for all x," and the library hunts for a counterexample, shrinking any failure to the smallest input that breaks the claim. Ten minutes of property-based comparison catches tie-breaking and empty-input differences that hand-written cases miss.

Step 3 — Write the new algorithm beside the old one. Do not delete anything yet. Add the replacement as a separate function so both roads exist at once:

// Step 3: INTERMEDIATE — both algorithms exist side by side
function pickupTimeForNew(stops: Stop[], studentStops: string[]): string {
  const wanted = new Set(studentStops);
  const stop = stops.find((s) => wanted.has(s.name));
  return stop ? stop.pickupTime : "NOT-ON-ROUTE";
}

If you want extra confidence on a risky swap, point the whole test suite at pickupTimeForNew and run it — or even write a tiny comparison loop that feeds many random inputs to both functions and asserts the answers match. This side-by-side moment is Ravi's Sunday test ride: the old route still exists, so nothing is at stake yet.

Step 4 — Swap in one clean stroke. Replace the old body with the new one, delete the temporary function, and keep the method's signature untouched:

// Step 4: the swap — contract identical, body replaced
function pickupTimeFor(stops: Stop[], studentStops: string[]): string {
  const wanted = new Set(studentStops);
  const stop = stops.find((s) => wanted.has(s.name));
  return stop ? stop.pickupTime : "NOT-ON-ROUTE";
}

Step 5 — Run the entire suite. Every failure here is a behavioral difference between the roads. For each one, ask the key question: was the old behavior contract or accident? If callers depend on it, fix the new algorithm to honor it. If it was an accident nobody wants, keep the new behavior — but change the test deliberately and visibly, ideally in its own commit, so the decision is on record.

Step 6 — Delete the old road for good. Once green, remove any leftover old code, commented-out blocks, or "just in case" copies. Version control remembers the old algorithm forever; your source file should not. Ravi does not keep cycling the pond loop "for backup."

The method passes through five named states on this journey. If you are ever interrupted mid-refactoring, knowing your current state tells you exactly what is safe to do next:

🛣️ A bigger real-life example

Let us put Ravi's whole route into code. The colony's cycling app stores roads as segments, and the old function computes the route from home to school the way the route itself grew — patch by patch, era by era:

interface Segment {
  from: string;
  to: string;
  minutes: number;
  openFrom: number; // hour of day the road opens
}
 
// BEFORE: the algorithm IS the zig-zag — every era of patches still visible
function routeMinutes(segments: Segment[], leaveHour: number): number {
  let total = 0;
  let reachedMilkBooth = false;
  let pondLoopDone = false;
  let templeDetourNeeded = false;
 
  for (let i = 0; i < segments.length; i++) {
    const seg = segments[i];
    if (seg.from === "Home" && seg.to === "MilkBooth") {
      if (seg.openFrom <= leaveHour) {
        total += seg.minutes;
        reachedMilkBooth = true;
      }
    }
    if (reachedMilkBooth && !pondLoopDone) {
      if (seg.from === "MilkBooth" && seg.to === "PondRoad") {
        total += seg.minutes;
        pondLoopDone = true;
        if (seg.minutes > 8) {
          templeDetourNeeded = true; // historical: long pond loop => dog corner => temple
        }
      }
    }
    if (pondLoopDone && templeDetourNeeded) {
      if (seg.from === "PondRoad" && seg.to === "TempleGate") {
        total += seg.minutes;
        templeDetourNeeded = false;
      }
    }
    if (pondLoopDone && !templeDetourNeeded && seg.from === "PondRoad" && seg.to === "School") {
      total += seg.minutes;
      break;
    }
    if (seg.from === "TempleGate" && seg.to === "School") {
      total += seg.minutes;
      break;
    }
  }
  return total;
}

Do not feel bad if your eyes glaze over — that is the point. Three boolean flags encode history, not logic: "the pond loop exists because of the wedding hall," "the temple detour exists because of the dogs." Every bug fix for three years has been another if wedged into this loop. Improving it line by line is hopeless, because its very shape is the zig-zag.

Now the municipality of our codebase opens the straight road. The real requirement today is simple: given the list of road segments, follow the chain from Home to School, adding up the minutes of every segment that is open when Ravi leaves. Said directly:

// AFTER: the algorithm matches today's requirement, not history
function routeMinutes(segments: Segment[], leaveHour: number): number {
  const bySource = new Map(segments.map((s) => [s.from, s]));
  let total = 0;
  let here = "Home";
 
  while (here !== "School") {
    const seg = bySource.get(here);
    if (!seg || seg.openFrom > leaveHour) {
      return 0; // no usable road onward — contract: unreachable means 0
    }
    total += seg.minutes;
    here = seg.to;
  }
  return total;
}

One map, one walk along the chain, one clear rule for closed roads. The flags are gone because the history is gone — the function now expresses the route as data (segments) plus one simple traversal, instead of hard-coding each historical landmark by name. Adding a new stop tomorrow means adding a segment to the data, not a fourth boolean to the code.

And the discipline still applies, even more strongly here, because this swap is bigger than the first one. Before swapping, the characterization tests must pin down the old function's quirks: what does it return when Ravi leaves before the milk-booth road opens? What if the segments come in a strange order? (Look carefully: the old version quietly depended on segment order; the new one does not — that is a behavioral difference the tests must surface, so you can decide on it consciously rather than discover it from an angry caller.)

🐍 The same refactoring in Python

The same swap, in Python, on a small grading helper. The old body checks topper names the long way:

# BEFORE: repetitive condition-chain — a tiny zig-zag
def is_topper(name, toppers_csv):
    found = False
    parts = toppers_csv.split(",")
    for i in range(len(parts)):
        cleaned = parts[i].strip()
        if cleaned != "":
            if cleaned.lower() == name.strip().lower():
                found = True
                break
    if found:
        return True
    return False

The contract: case-insensitive match of a name against a comma-separated topper list, ignoring stray spaces and empty entries. Tests first — empty string, trailing comma, mixed case, name with spaces — and then the straight road:

# AFTER: the body states the contract directly
def is_topper(name, toppers_csv):
    toppers = {p.strip().lower() for p in toppers_csv.split(",") if p.strip()}
    return name.strip().lower() in toppers

Two lines, and each clause maps to one sentence of the contract: build the cleaned set, check membership. Python's comprehensions and in operator make it a wonderful language for this refactoring — very often, the "new algorithm" is simply the standard library doing what the old loop hand-rolled. The same is true of C#'s LINQ (Any, FirstOrDefault, Where) and JavaScript's array methods: a large share of real-world substitutions replace manual loops with a well-tested built-in.

For completeness, the same idiom in C# — the old foreach-with-flag body collapses into one LINQ sentence:

// BEFORE: flag-and-loop
public bool IsTopper(string name, string toppersCsv)
{
    bool found = false;
    foreach (var part in toppersCsv.Split(','))
    {
        var cleaned = part.Trim();
        if (cleaned.Length > 0 && cleaned.Equals(name.Trim(), StringComparison.OrdinalIgnoreCase))
        {
            found = true;
            break;
        }
    }
    return found;
}
 
// AFTER: the library is the straight road
public bool IsTopper(string name, string toppersCsv)
    => toppersCsv.Split(',')
        .Select(p => p.Trim())
        .Where(p => p.Length > 0)
        .Any(p => p.Equals(name.Trim(), StringComparison.OrdinalIgnoreCase));

🛠️ IDE support

There is no "Substitute Algorithm" button in any IDE — no tool can invent a better algorithm for you. But the tooling around the swap is exactly where IDEs shine, and you should lean on all of it:

• Test runners with one-key re-run (Visual Studio Test Explorer, IntelliJ/Rider's runner, VS Code's testing panel, pytest/jest watch modes): the whole discipline depends on running the suite after every move. Watch mode turns "run the tests" from a chore into a heartbeat.
• Coverage tools (dotnet-coverage and Visual Studio's coverage view, IntelliJ's built-in coverage, coverage.py, Istanbul/nyc): before the swap, run coverage on your characterization tests against the old body. Unhit branches are exactly the quirks your net has not pinned down yet — cover them before swapping.
• Extract Method support (all major IDEs): the official step 1. Use the IDE's extraction to shrink the method until the algorithm stands alone, so your swap is small.
• Version control integration: make the swap its own tiny commit, with the tests committed before it. If anything surfaces later, git diff shows the old and new algorithms side by side, and reverting is one command. The IDE's diff viewer is also the best place for a colleague to review a swap, since the whole change is one method body.
• Inline hints and analyzers: ReSharper, Roslyn analyzers, SonarLint, and ESLint frequently suggest substitutions — "convert loop to LINQ expression," "use Array.prototype.find," "simplify conditional." These hints are small, machine-verified Substitute Algorithm moves; accepting one still deserves a test run.

⚖️ Benefits and risks

Read the first risk row twice. Every other refactoring in this series lets you lean partly on the compiler; this one leans almost entirely on tests. Have the tests before you swap — always. That single habit converts Substitute Algorithm from the riskiest basic refactoring into a calm, routine one.

That last row — runtime algorithm choice — deserves a picture, because the practice exercise below will ask you about it. When two roads must both stay open (strict matching for teachers, fuzzy matching for students), you do not substitute one for the other; you put each behind a common interface and let the caller choose. That is the Strategy pattern, and the method-object refactoring from the previous lesson is often the first step toward it:

🧪 Which smells does it cure?

📋 Quick revision box

+--------------------------------------------------------------------+
|            SUBSTITUTE ALGORITHM — REVISION CARD                    |
+--------------------------------------------------------------------+
| Story    : Ravi's zig-zag cycle route vs the new straight road —   |
|            same destination, simpler path. Test-ride on Sunday     |
|            BEFORE switching on a school day.                       |
| What     : keep the method's contract; replace its WHOLE body      |
|            with a clearer/faster algorithm. Move-nothing,          |
|            rewrite-everything.                                     |
| Rule #1  : TESTS FIRST. Characterize the old behavior — edges,     |
|            ordering, tie-breaks, empty inputs — before writing     |
|            one line of the new algorithm.                          |
| Steps    : shrink method -> pin behavior with tests -> write new   |
|            algorithm beside old -> swap in one stroke -> full      |
|            suite -> investigate every diff -> delete old road.     |
| Failures : each red test = old behavior. Decide: contract          |
|            (reproduce it) or accident (change it openly).          |
| Avoid    : weak tests, multi-job methods (decompose first),        |
|            clever-but-unreadable code, runtime algorithm choice    |
|            (that is Strategy).                                     |
+--------------------------------------------------------------------+

✍️ Practice exercise

Your turn to open a straight road. This TypeScript function from a school library app finds the first available copy of a requested book — written, of course, as a zig-zag:

interface BookCopy {
  title: string;
  shelf: string;
  isIssued: boolean;
}
 
function findShelf(copies: BookCopy[], requestedTitles: string[]): string {
  let answer = "";
  let done = false;
  for (let i = 0; i < copies.length; i++) {
    if (!done) {
      for (let j = 0; j < requestedTitles.length; j++) {
        if (copies[i].title === requestedTitles[j]) {
          if (copies[i].isIssued === false) {
            answer = copies[i].shelf;
            done = true;
            break;
          }
        }
      }
    }
  }
  if (done === false) {
    return "NOT-AVAILABLE";
  }
  return answer;
}

Your tasks, in the safe order:

1. State the contract in one sentence. Write it as a comment above the function before touching anything. (Hint: which copy wins when several are available? What happens when the title matches but every copy is issued?)
2. Build the net first. Write at least six characterization tests against the old body: a simple hit, a no-match case, an all-copies-issued case, an empty copies array, an empty requestedTitles array, and — most important — a case with multiple available copies that pins down which one wins. Run them green.
3. Write the straight road beside the old one as findShelfNew, using Set and find like the lesson examples. Run the same tests against it.
4. Swap in one stroke, delete the temporary function, and run the full suite. If any test fails, write one sentence in your notebook: was the old behavior contract or accident, and what did you decide?
5. Delete the old code completely — no commented-out backup. Then check the diff: the entire change should be one method body plus your tests.
6. College corner challenge: state the time complexity of the old body and your new one in Big-O terms, using n for copies and m for requested titles. Then write a ten-line differential test with a property-based library (or a plain loop over random inputs) asserting old and new always agree — and only delete the old body after it passes a thousand cases.
7. Bonus thinking question: suppose the librarian later wants two search rules — strict title match for teachers, fuzzy match for students — selectable at runtime. Why is Substitute Algorithm the wrong tool for that request, and which design pattern is the right one? (Figure 10 is your hint.)

Same destination, simpler path — and a Sunday test ride before every switch. Ride safely.