Games and Invariants
Loop invariants provide a means to effectively determine the correctness of iterative solutions by
helping one reason about the changes from one iteration to the next.
A loop invariant is a boolean expression that is true each time the
loop condition is evaluated. Typically the boolean expression is composed
of variables used in the loop and evaluated each iteration of the
loop. In particular, the initial establishment of
the truth of the invariant helps determine the proper initial values
of variables used in the loop condition and body. In the loop body, some
statements make the invariant false, and other statements must then
re-establish the invariant so that it is true before the loop condition is
evaluated again.
The general structure of a loop is:
while (!done)
{
// check loop invariant: what is true at every step
// body
// update to maintain invariant
}
Invariants can serve as both aids in recalling the details of an
implementation of a particular algorithm and in the construction of an
algorithm to meet a specification.
You can also use invariants to characterize a variety of iterative processes.
As practice, consider the following puzzles as an
introduction to the use of invariants as a tool for reasoning about a
problem.
Bean Can
You and a friend are given a can containing N black beans and
M white beans initially. The can is emptied according the
following repeated process:
- Select two beans from the can
- If the beans are:
- same color: put a black bean back in the can
- different colors: put a white bean back in the can
The player who chooses the color of the remaining bean wins the game.
Bean Can Algorithm pseudocode (where N represents the number of white beans and M the number of black beans)
while (N + M > 1) do
{
pick 2 beans randomly
if bean1-color == bean2-color then
put-back black bean
else
put-back white bean
}
In order to win, you clearly need to analyze the link between the initial
state and the final state. The key is to identify the invariant that
characterizes the removal process by determining what property is preserved as beans are removed from the can. To help get you started, answer the following questions.
- How does the number of white beans change each turn?
- How does the number of black beans change each turn?
- How does the total bean count change each turn?
- What is the loop invariant?
- What is the the final state for the simple cases where N+M ≤ 3
- Give an overall strategy to determine the final state (the color of
the last bean) from the initial state (N & M)?
N coins
You and a friend have a stack of N coins.
On each person's turn, either 1 or 2 coins can be taken from the stack.
The person who removes the last coin wins. Given N, should you go
first or second? What is the loop invariant?
Hint: Consider the case where N=3
Laser robots
Two laser robots are placed on two opposite corners of a rectangular
city; the first on the south-west corner, and the second on the
north-east corner. The city street map is a grid of horizontal and
vertical roads. The robots move in alternating turns, where each move
is either horizontal (left/right) or vertical (up/down). The goal
of each robot is to have its opponent enter its line of fire
(vertically or horizontally); distance is not a factor. A robot loses when it cannot move without getting shot.
- What is the loop invariant?
- What is the strategy for winning the game?