Assignment 1: Grundy Numbers

Objectives

Introduction

Consider the following variation of Kayles: the move are restricted so the only time you may take one pin is when it has no adjacent pins, and when you take two pins from a group, you must split that group into two non-empty groups (so you cannot make any moves on groups of 2 or 3 pins). The winner is determined by normal play rules: the first player who cannot move (because there are no pins remaining or only isolated groups of 2 or 3 pins) loses.

We call this variation of Kayles Kayles.14. 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.14 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.14 (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 an executable called Kayles.14. For Python and Java, your makefile can create a script that compiles (for Java) and runs your program when make is run with Kayles.14 as the target. For example, 

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

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

$ ./Kayles.14 grundy 8
[0, 1, 0, 0, 1, 0, 2, 1, 2]
$ ./Kayles.14 .x..xxxx..
LOSS
$ ./Kayles.14 xxxx.xxxx.xxxx
x..x.xxxx.xxxx
$ ./Kayles.14 xxxxxxxx
xxx..xxx
$ ./Kayles.14 xxxxxxxxx
xx..xxxxx

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 A071429.