-
>
>
>
>
Programming Assignments >
Assignment 1 - Computing Grundy Numbers
Objectives
- to use the Sprague-Grundy Theorem to play a finite, impartial, normal combinatorial game optimally
Introduction
Consider the following variation of Kayles: instead of allowing a move
to remove one or two adjacent pins, a move must always remove two adjacent
pins, except that a single pin with no adjacent pins may be removed,
and a pair of adjacent pins with no pins immediately adjacent on
either side of the pair may
not be removed. The winner is determined by normal play rules: the first
player who cannot move (because there are no pins remaining or only isolated
pairs of pins) loses.
We call this variation of Kayles Kayles.16. It is a finite, impartial,
normal combinatorial game and so can be analyzed using the Sprague-Grundy
Theorem.
Assignment
Write a program that runs in two modes: in the first mode, the first
command-line argument will be the word "grundy" and the second will be
the decimal representation of a non-negative integer $n$ and the output
should be a single line giving the Grundy numbers for a game of Kayles.16
that starts with 0 pins, 1 pin, ..., $n$ pins as a comma-separated list
enclosed in square brackets the a single space after each comma;
in the second mode there will be a single command-line argument that
is a string (possibly empty) of '.' and 'x' characters representing a
position in Kayles.16 (the '.' are removed pins and the 'x' are the remaining
pins). The output should be a single line giving the result of a winning
move if there is one, or "LOSS" if there is no winning move.
If there is more than one winning move, select the winning move to output
that reduces a group's Grundy number and takes pins from as far left
as possible.
Your makefile must create a script called Kayles.16
that runs your program when make
is run with Kayles.16 as the target.
Examples
$ ./Kayles.16 grundy 6
[0, 1, 0, 0, 1, 2, 2]
$ ./Kayles.16 ..xx.
LOSS
$ ./Kayles.16 ..xxx.xxx.
LOSS
$ ./Kayles.16 xxx.xxx.x
xxx.xxx..
$ ./Kayles.16 xxxxxxxxxx
x..xxxxxxx
The Online Encylopedia of Integer Sequences
gives correct Grundy numbers up to $n=102$ (omitting $n=0$) and has a link
to a list of many more in entry A071430.
