Assignment 1: Grundy Numbers

Objectives

Introduction

Consider the following variation of Kayles: players can take any single pin, or they can take the outer two of three consecutive pins. For example, if the arrangement at the start of a turn is x.xxxx then the legal moves would leave ..xxxx, x..xxx, x.x.xx, x.xx.x, x.xxx., x..x.x, or x.x.x.. The winner is determined by normal play rules: the first player who cannot move (because there are no pins remaining) loses.

We call this variation of Kayles Kayles-xox. 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-xox 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-xox (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, differing from the input only where pins are removed by the winning move, or "LOSS" if there is no winning move. If there is more than one winning move, select as the output a winning move from the leftmost group that contains a winning move that reduces the group's Grundy number. If there are multiple winning moves in that group, choose the leftmost winning move. If both types of moves are winning moves at that position, then choose the move that removes a single pin.

So that the submission system can use the same build and execute commands regardless of language, you must supply a makefile that creates an executable called Kayles-xox when called with that as the target. For Python and Java, your makefile can create a script that compiles (for Java) and runs your program. For example, 

Kayles-xox:
	echo "#!/bin/bash" > Kayles-xox
	echo "pypy3 kayles.py \"\$$@\"" >> Kayles-xox
	chmod u+x Kayles-xox

You would then submit your source code and the above makefile.

Your code should be efficient – it should be able to compute the first 1000 Grundy numbers in a fraction of a second and determine winning moves for up to 1000 pins with similar speed.

Examples

[jrg94@jaguar cpsc474_kayles]$ ./Kayles-xox grundy 6
[0, 1, 0, 2, 3, 2, 1]
[jrg94@jaguar cpsc474_kayles]$ ./Kayles-xox .x
..
[jrg94@jaguar cpsc474_kayles]$ ./Kayles-xox xxxxxxx.xxxxxxxx..xxxxxxxx.
xxx.xxx.xxxxxxxx..xxxxxxxx.
[jrg94@jaguar cpsc474_kayles]$ ./Kayles-xox xxx.x.xxxx
LOSS