Learning Rust: Programming The Pick-Up Sticks Game

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:

1. Emacs 28.0.50 with emacspeak 52.0.
2. Package eglot for managing the project with an LSP server.
3. Rust Language Server (RLS) as the LSP server.
4. Package company for completion.
5. Package yasnippet for code templates.
6. Package rust-mode for Rust editing smarts.
7. Package racer for additional cross-referencing and
   documentation support.
8. 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:

1. This is a two-player game and the game starts with \(n\) sticks.
2. The first player can pick at most \(n-1\) sticks.
3. Assume a player picks \(k\) sticks. At the subsequent turn, opponent
   can pick at most \(2 * k\) sticks.
4. 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:

1. If the number of sticks at the start is a Fibonacci number, ask
   the opponent to play first.
2. At each turn, force the opponent toward the closest Fibonacci number.
3. 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\).
4. 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.

7 Closing Thoughts

1. The computing environment I now have is far more sophisticated
   than what I had in 1987.
2. Today, I have interactive completion, source-code
   cross-references, on-the-fly access to documentation, and a fully
   accessible book where I can look up things whenever I want.
3. In 1987, I did most of my thinking and problem-solving in my
   dorm-room with no computer to hand. When ready with the solution,
   I made a few notes in Braille using a pocket-slate and stylus,
   then went to the computer room with a volunteer reader and typed
   up the program, with the student volunteer providing high-quality
   interactive spoken feedback.
4. Interestingly, I think it took me less time from memory to
   implement the solution in 1987 — perhaps this is time shrinking
   with number of years passed.
5. Either way, the primary take-away is that it pays to analyse a
   problem before one actually starts writing code. Writing code is
   always fun, and today, even more so given the excellent array of
   tools — but unless one focuses on the problem at hand, one can
   spend a lot of time sharpening one's pencils as opposed to
   writing something useful.

Viewing Data Records As Forms: Old Is Gold!

1 Executive Summary

Given a file containing data records made up of multiple fields, you
can easily view them using Emacs' forms library.

2 Background: BBC Program Listings

I use Perl utility get_player to fetch details of BBC Radio
programs. When I was using this frequently, I had installed package
iplayer.el from Melpa — that package presented the data as a
nicely organized Org document. Time passed, and I somehow stopped
using it, until … last week. Then I discovered that package
iplayer on Melpa hadn't been updated in a few years, and worse had
broken because package org no longer includes now obsoleted
sub-module orgstruct.

3 Task: Viewing BBC Program Listings

When I realized package iplayer was broken, I tried to make up for
its loss for a few days by using shell-level utilities like cut. But
then I missed the convenience of being able to work with the data with
all of Emacs' power and was initially tempted to write a new package
— after all, how hard is it to take a record, split it into fields
and display it in a desired form? Fortunately, I remembered another of
my favorite edicts from the creator of Perl (Larry Wall)

Lazy Programmer Is A Good Programmer

At the same time I had a strong sense of dejavu — in the early daysa
of Emacspeak (approx 1995), I remembered demonstrating the power of
Emacs to manipulate and display data records by using file
/etc/passwd as an example.

4 The Free Solution

So the completely free (AKA zero-work) solution I used was to leverage
Emacs' built-in forms library — the solution
as created
in
get-iplayer.el is below:

(setq forms-read-only t)
(setq forms-file (expand-file-name "~/.get_iplayer/radio.cache"))
(setq forms-number-of-fields 16)
(setq forms-field-sep "|")
(setq forms-format-list
      (list
       "Id: "  1 "\t" "Name: " 3 "\n"
       "Episode: " 4 "\t" "Description: "  12 "\n"))

With the above in place, you can:

1. M-x forms-find-file RET get-iplayer.el
2. This displays one record at a time as specified by forms-format-list.
3. You can search through records etc.