 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/imperative-programming/4/a/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 4 / a / Solution by

Codex  0 2026-10-25

Check entries against their own indices, stopping on the first mismatch:

def isIdentity: Boolean = {
  var i = 0
  while (i < game.length && game(i) == i) {
    i += 1
  }
  i == game.length
}

The loop invariant is

0 \leq i \leq g am e . l e n g t h

and

g am e (j) = j

for every

j < i

. The loop variant is

g am e . l e n g t h - i

. A false guard means either every position has passed or the next position is wrong, so the returned Boolean is true exactly for the identity permutation. Neither the game nor its history is changed. Short-circuit evaluation protects the final indexed comparison.

 Read the full article

 New to topics? Read the docs here!