The first problem presented in Concrete Mathematics: A Foundation for Computer Science is The Tower of Hanoi. Although a relatively simple problem, it offers a useful foray into introductory programming with Rust. We are given a tower of n disks, initially stacked in decreasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller. Once we satisfy ourselves that a solution to this problem exists, we can choose to determine the total number of moves T_n required to solve the problem, or an enumerated list of moves constituting this number.
In creating a solution for this, note that we are not pursuing a closed form solution; in essence, the computer has to ‘do the work’ of making each move, recording it in the process. We begin with the simplest possible version of the solution.
Preparation
- Make sure
cargois installed on your system via rustup. - Create a new package called
hanoito run your code.
$ cargo new hanoi
$ cd hanoi//
// src/main.rs
//
use std::io;
use std::io::Write;
/// Solve the Tower of Hanoi problem
fn main() {
let mut num_disks = 0;
let mut num_moves = 0;
get_num_disks(&mut num_disks);
if num_disks >= 0 {
println!("Number of disks = {}", num_disks);
move_disk_set(num_disks, "A", "B", "C", &mut num_moves);
println!("Number of moves = {}", &num_moves);
} else {
println!("Invalid number ({}) of disks!", &num_disks);
}
}
/// Get the number of disks to solve the problem for
///
/// * `k` - Buffer to populate the result in
fn get_num_disks(k: &mut i64) {
let mut buf = String::new();
print!("Enter the number of disks: ");
io::stdout().flush().unwrap();
io::stdin()
.read_line(&mut buf)
.expect("Failed to read input!");
*k = buf
.trim()
.parse::<i64>()
.expect("Failed to parse input as an integer!");
}
/// Move a tower of the given size from source to destination.
///
/// * `num_disks` - Number of disks in the tower
/// * `src` - Label for the source peg
/// * `dst` - Label for the destination peg
/// * `buf` - Label for the peg acting as a buffer
/// * `num_moves` - Number of moves executed so far
fn move_disk_set(
num_disks: i64,
src: &str,
dst: &str,
buf: &str,
num_moves: &mut i64,
) {
match num_disks {
0 => return,
n => {
move_disk_set(n - 1, src, buf, dst, num_moves);
move_disk(num_moves);
move_disk_set(n - 1, buf, dst, src, num_moves);
}
}
}
/// Move a single disk from source to destination.
///
/// * `num_moves` - Number of moves executed so far
fn move_disk(num_moves: &mut i64) {
*num_moves = *num_moves + 1;
}P0: Basic Solution
The output of this program is quite straightforward.
$ cargo run
Compiling hanoi v0.1.0 (/Users/rri/Code/play/hanoi)
Finished dev [unoptimized + debuginfo] target(s) in 0.36s
Running `target/debug/hanoi`
Enter the number of disks: 3
Number of disks = 3
Number of moves = 7P1: Printed Moves
The solution gets a bit more interesting when you print each move on the console, thus giving you a way to see the code in action and verify its output. (For brevity, only the updated functions are shown below.)
Update move_disk to print out the move when it is called.
fn move_disk(num_moves: &mut i64, src: &str, dst: &str) {
*num_moves = *num_moves + 1;
println!("{:>10}: {} -> {}", num_moves, src, dst);
}Update move_disk_set to pass more parameters to move_disk.
fn move_disk_set(
num_disks: i64,
src: &str,
dst: &str,
buf: &str,
num_moves: &mut i64,
) {
match num_disks {
0 => return,
n => {
move_disk_set(n - 1, src, buf, dst, num_moves);
move_disk(num_moves, src, dst);
move_disk_set(n - 1, buf, dst, src, num_moves);
}
}
}The output of the modified program is slightly more involved.
$ cargo run
Compiling hanoi v0.1.0 (/Users/rri/Code/play/hanoi)
Finished dev [unoptimized + debuginfo] target(s) in 0.28s
Running `target/debug/hanoi`
Enter the number of disks: 4
Number of disks = 4
1: A -> C
2: A -> B
3: C -> B
4: A -> C
5: B -> A
6: B -> C
7: A -> C
8: A -> B
9: C -> B
10: C -> A
11: B -> A
12: C -> B
13: A -> C
14: A -> B
15: C -> B
Number of moves = 15We would like to write automated tests for this solution. The need to test software usually forces us to change the structure of the program in certain ways, but this is a good thing as it drives the design of the application to be much more modular. The problem with the solution above is that we can’t really test what output is printed on the console (at least, not easily). We need to modify our program to return a list of moves that we are free to inspect, rather than execute these moves directly. Modular software has this useful property that all effects on the environment external to system under consideration are reified (given a concrete representation), as you see in the next section.
P2: Tested Moves
The basic idea behind reification of effects is to take code that does some work, and represent it in a structure or object that represents the work (instead of actually doing the work). In this case, instead of printing a move on the console, we return a structure that represents a move (complete with source and destination), and leave it up to the consumer of the structure to determine what to do with it. Second, we no longer need to maintain a count of moves, as the count is implied by the size of our move list. Finally, we add a few tests that validate our assumptions. (For brevity, only the updated functions and structures are shown below.)
Define a structure to represent a move.
/// Representation of a 'move' of a disk from one peg to another
struct Move<'a> {
/// Label for the source peg
src: &'a str,
/// Label for the destination peg
dst: &'a str,
}Update the main function to consume and process (print) the moves.
fn main() {
let mut num_disks = 0;
let mut lst_moves: Vec<Move> = Vec::new();
get_num_disks(&mut num_disks);
if num_disks >= 0 {
println!("Number of disks = {}", num_disks);
move_disk_set(num_disks, "A", "B", "C", &mut lst_moves);
println!("Number of moves = {}", lst_moves.len());
for (pos, m) in lst_moves.iter().enumerate() {
println!("{:>10}: {} -> {}", pos + 1, m.src, m.dst);
}
} else {
println!("Invalid number ({}) of disks!", &num_disks);
}
}Update the move_disk function to add to a vector instead of printing the move.
fn move_disk<'a>(
lst_moves: &mut Vec<Move<'a>>,
src: &'a str,
dst: &'a str,
) {
lst_moves.push(Move { src: src, dst: dst });
}Add some tests to satisfy ourselves that the solution works. More interesting and useful tests may be added, of course.
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_nil() {
test_disks(0, 0);
}
#[test]
fn test_one() {
test_disks(1, 1);
}
#[test]
fn test_two() {
test_disks(2, 3);
}
#[test]
fn test_ten() {
test_disks(10, 1023);
}
fn test_disks(num_disks: i64, exp_num_moves: i64) {
let mut lst_moves: Vec<Move> = Vec::new();
move_disk_set(num_disks, "A", "B", "C", &mut lst_moves);
assert_eq!(lst_moves.len() as i64, exp_num_moves);
}
}One of the most interesting things about this code that has insidiously made its way into an otherwise simple example is the notion of lifetimes in Rust. The parameter 'a in the example represents a lifetime, denoting the scope for which the reference parameterized by it is available. The easiest way to think of this is as an extra parameter that gets threaded through whenever the reference is passed along to a function. For instance, the move_disk_set function now needs to be parameterized with 'a, with no other changes. In this case, the actual value of the parameter is inferred to be 'static as we are ultimately starting with string literals ("A", "B", "C").
fn move_disk_set<'a>(
num_disks: i64,
src: &'a str,
dst: &'a str,
buf: &'a str,
lst_moves: &mut Vec<Move<'a>>,
) {
match num_disks {
0 => return,
n => {
move_disk_set(n - 1, src, buf, dst, lst_moves);
move_disk(lst_moves, src, dst);
move_disk_set(n - 1, buf, dst, src, lst_moves);
}
}
}The output of the running the tests are exactly as expected.
$ cargo test
Finished test [unoptimized + debuginfo] target(s) in 0.00s
Running target/debug/deps/hanoi-40e0f0eba95aed0c
running 4 tests
test tests::test_nil ... ok
test tests::test_one ... ok
test tests::test_two ... ok
test tests::test_ten ... ok
test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered outThat’s all for today, folks! 🖖