L14: Algorithms I: Correctness and Efficiency

Puzzle Stations

1. **Best move:** predict the result for jump: 2 legal, dash: 5 legal, and wait: 9 illegal.
2. **Tie rule:** decide which move wins when two scores match, then test that rule.
3. **Empty input:** decide what chooseMove([]) should return.
4. **Invariant check:** name what stays true after each move is checked.

Programming Challenge

Complete the helper. It returns the highest-scoring legal move, keeps the first move when legal moves tie, returns undefined when there is no legal move, and does not modify moves.

type Move = { name: string; score: number; legal: boolean };

function chooseMove(moves: readonly Move[]): Move | undefined {
  // TODO: track the best legal move seen so far.
  // TODO: keep the earlier move when scores tie.
  // TODO: return undefined when no legal move exists.
}

const cases: { moves: readonly Move[]; expectedName: string | undefined }[] = [
  { moves: [], expectedName: undefined },
  {
    moves: [{ name: "jump", score: 2, legal: true }],
    expectedName: "jump",
  },
  {
    moves: [
      { name: "jump", score: 2, legal: true },
      { name: "dash", score: 5, legal: true },
    ],
    expectedName: "dash",
  },
  {
    moves: [
      { name: "jump", score: 5, legal: true },
      { name: "dash", score: 5, legal: true },
    ],
    expectedName: "jump",
  },
  {
    moves: [
      { name: "wait", score: 9, legal: false },
      { name: "dash", score: 4, legal: true },
    ],
    expectedName: "dash",
  },
];

for (const { moves, expectedName } of cases) {
  const before = JSON.stringify(moves);
  const actual = chooseMove(moves);
  if (actual?.name !== expectedName) {
    throw new Error("expected " + expectedName + ", received " + actual?.name);
  }
  if (JSON.stringify(moves) !== before) {
    throw new Error("chooseMove changed its input");
  }
}

Run the five cases after completing the helper. They cover the empty input, single move, later higher score, tie rule, and illegal high-score boundary.

Then state the invariant: after each checked move, the saved answer is the best legal move seen so far.

Common Bugs

• Changing browser UI files before the rule helper is testable.
• Adding state changes inside a function that should be a pure helper.
• Trusting generated code without a small test for the boundary case.

Bonus Puzzles

• Add a tie rule.
• Compare two correct algorithms.
• Ask AI for counterexamples and keep valid ones.