# 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`.

```ts
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.