Learning Rust: The Pick-Up Sticks Game
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.
eglotfor managing the project with an LSP server.
- Rust Language Server (RLS) as the LSP server.
yasnippetfor code templates.
rust-modefor Rust editing smarts.
racerfor additional cross-referencing and
cargofor cargo integration from inside Emacs.
In the process of setting up my Rust environment, I also
speech-enabled Emacs packages
cargo for Emacspeak.
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
6 Crux Of The Implementation
game.rs for the implementation. The core of the
implementation is still a handful of lines to implement the winning
- 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
7 Closing Thoughts
- The computing environment I now have is far more sophisticated
than what I had in 1987.
- 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.
- 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.
- 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.
- 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.