Learning Rust: The Pick-Up Sticks Game.

1 Overview

This directory contains an implementation of the Pick Up Sticks game described in my paper Thinking Of Mathematics (Section 5).

It’s an interesting experience writing it in Rust as I learn the language. The original implementation described in my paper was written in 1987 in Fortran-77, and consisted of one single function. Though that style of programming would be frowned upon today and is clearly not advisable for programming in the large, it’s interesting to observe that a more structured implementation as seen in this Rust implementation qrequires a lot more fore-thought with respect to code organization.

2 Programming Environment

here is a short overview of the programming environment used:

Emacs 28.0.50 with emacspeak 52.0.
Package eglot for managing the project with an LSP server.
Rust Language Server (RLS) as the LSP server.
Package company for completion.
Package yasnippet for code templates.
Package rust-mode for Rust editing smarts.
Package racer for additional cross-referencing and documentation support.
Package cargo for cargo integration from inside Emacs.

In the process of setting up my Rust environment, I also speech-enabled Emacs packages rust-mode, racer and cargo for Emacspeak.

3 Books

I downloaded The Rust Programming Language (2018) from Bookshare and it’s what I am still using as I write this. Note that this book is also available in the Rust distribution. The version in the Rust distribution is a little less usable since it’s split into multiple smaller HTML files with each file repeating a lot of navigational boiler-plate at the top.

4 Experience Learning Rust

I usually find that I learn a language better if I write some code as I learn the language. In this instance, I decided to program the pick-up-sticks game — a simple game that I programmed in 1987 for the final class project for CS-101 at IIT-Bombay. Here are the rules of the game:

This is a two-player game and the game starts with $n$ sticks.
The first player can pick at most $n-1$ sticks.
Assume a player picks $k$ sticks. At the subsequent turn, opponent can pick at most $2 * k$ sticks.
The player who is able to clean-up the remaining sticks while adhering to the rules is the winner.

Read Thinking Of Mathematics (Section 5) for a description of an algorithm that is guaranteed to win.

5 The Implementation

Learning Rust’s ownership rules for memory management, and learning to use references the Rust way were some of the things that were unique to this learning experience. Rust has some unique features including declaring lifetimes that are typically needed in more advanced cases; however in my initial attempts, not doing things the Rust way caused compile-time errors that initially guided me toward using and declaring lifetimes. Eventually, all of those declarations became unnecessary. More generally, the Rust compiler turns out to be a very good Rust teacher.

6 Crux Of The Implementation

See module game.rs for the implementation. The core of the implementation is still a handful of lines to implement the winning strategy of:

If the number of sticks at the start is a Fibonacci number, ask the opponent to play first.
At each turn, force the opponent toward the closest Fibonacci number.
Do above while respecting the limit rule, i.e. if you pick $k$ sticks, the opponent can pick up to $2k$ sticks, so never pick $k$ where $3k >= n$.
The result of (3) is to subdivide the game into smaller games when playing with larger values of $n$ — see the while loop in method my_move.