The Tower of Hanoi

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 cargo is installed on your system via rustup.
  • Create a new package called hanoi to 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

Link to GitHub branch.

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 = 7

P1: Printed Moves

Link to GitHub branch.

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 = 15

We 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

Link to GitHub branch.

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 out

That’s all for today, folks! 🖖

Time Management Toolbox

One of the things people talk to me about commonly is how to manage their time. Over the years, I have accumulated a bunch of pithy equations that characterize this skill, which I now present to you as the one and only time management toolbox.

Eq 1: “Time” \approx “Currency”

This is a common saying, but not applied as commonly as it ought to be. Consider the fact that spending your time is equivalent to spending your money…but worse — because you have a limited supply of it. The motives here aren’t simply selfish; just as you want to generate the most value from your time, so too does whoever signs your paycheck. Time is your greatest asset, so use it wisely. And remember, you can use it like currency: spend it to help someone and generate goodwill.

Eq 2: “Urgent” \neq “Important”

People sometimes have a tendency to confuse the urgent (tasks right in front of you) with the important, but it is important to distinguish between the two, as you can see in the table below. If you think about it, there are many tasks that are urgent (or appear to be) — but don’t fall into the trap of pursuing these tasks unless they are also important.

Urgent vs Important

Eq 3: “I don’t have time” \Rightarrow “This is not a priority”

In this talk, Laura Vanderkam points out that every minute you spend is your choice. Whenever you are tempted to say that you don’t have time to do something that you think is important, try saying instead that it is not a priority. All of a sudden, you realize that you are making a conscious choice to deprioritize something important, which also means you can choose differently by elevating its priority and dropping something else instead.

Eq 4: “Prioritize Task” \equiv “Deprioritize Everything Else”

One of the tricks I have found useful to employ is to ruthlessly deprioritize and discard any task with the slightest chance of being unimportant. Rather than asking whether something is or could be important, instead ask the opposite. Create a vacuum that you then have no choice but to fill up with your important tasks. I often surprise myself when I pick up an obviously important task and ask, “What’s the worst that could happen if I dropped this?” and the answer turns out to be, “Not much”. 🤷‍♂️

Eq 5: “My Time” > “Your Time”

Not everyone’s time is equal, and if you want to leverage your time effectively, consider your time to be more important than everyone else’s by default. In case this sounds selfish, remember that every other person with this skill is doing the same thing themselves! In any case, don’t be shy about demanding time from others, and don’t take it personally if you are refused. When you are mentoring someone, remember that an hour spent trying and failing is more valuable to the student than an hour you spend teaching them. Provide guidance, then get out of the way.

Eq 6: “Out of Sight” \simeq “Out of Mind”

Things that are right in front of us not only seem urgent, they also make us forget the things that aren’t in front of us. The antidote? Write down your important tasks and goals on post-it notes and stick them on your computer monitor. Or keep a list of things you consider important, that you are forced to look at every day, maybe several times each day.

Eq 7: “High Throughput” + “Low Latency”

If you focus exclusive quality time on a task, you can make a signficant dent in it. On the other hand, this may prevent you from shepherding other important tasks that would have benefited from quick action to move them along or course-correct. If you allow yourself to be driven solely by incoming tasks and events, you lose the ability to spend dedicated quality time on any particular task, and the overhead of context-switching becomes too much. Obviously, there is a happy balance between these two ends of the spectrum, but it is important to recognize that you need both kinds. Personally, I prefer to spend early mornings on longer tasks that require deep focus, and handle interrupts, follow-ups and meetings during the remainder of the day.

That’s all for today, folks! 🖖

Offsite Guide

What is an offsite?

An offsite is a team-building exercise designed to bring together the core members of a team into a single room over an extended period time (usually 2-3 days). Offsites are structured to offer participants a respite from daily tasks, distractions and context-switches, instead allowing them to spend focused time with the rest of the team. With the right set of activities and facilitation, offsite participants are able to gradually develop a full appreciation of diverse perspectives and align on the fundamental problem that they want to solve as a team.

Do I need to be thinking about arranging an offsite for my team?

If your team is in its formative stages, it may be facing a lot of ambiguity regarding its charter and boundaries. Getting together at this stage is very useful for understanding the team’s mission, sharing and digesting lessons learned from the past, establishing guiding principles for the team to operate against, and agreeing upon the goals to be achieved. Similarly, an offsite is useful when your team is embarking upon a major new initiative, or if it has recently expanded or turned-over significantly.

Who should participate in the offsite?

Anyone who contributes to the day-to-day decisions of the team or helps set direction for the team should participate in the offsite. It is often helpful to limit the group size to approximately 10, so everyone can actively participate in the session. All participants should be physically and mentally present for the entire duration of the offsite.

Is an offsite the same as a sprint planning session?

No, sprint planning and retrospective sessions are usually far more time-constrained and help define tactical goals for the team, whereas offsites tend to be more strategic in nature and help define the team’s charter. Offsites typically benefit from novelty (such as a change in location and pace) and tend to encourage out-of-the-box thinking. Festina lente – make haste slowly – may be a good motto for an offsite.

What should my team be looking to gain from the offsite?

Typically, your team should be looking to achieve the following goals from an offsite: (a) get clarity on why the team exists, what its charter is, and who its customers are, (b) get a deep understanding of customers’ pain points and unmet needs, (c) align on what the most important problems are and agree on a strategy for solving them, (d) celebrate the team’s successes and acknowledge its failures, and finally (e) establish an environment where every individual is encouraged to speak freely and their voice is heard.

Planning an Offsite

Participation — Perhaps the most challenging aspect of the offsite is getting everyone into the room in the first place. Create a concrete agenda and communicate it to the team, so they see the value in it. Speak to each participant individually and make sure they have cleared out their calendar and get their commitment to be present, both physically and mentally, for the full duration of the offsite. Participants may want to “step out” to go to other meetings in the middle of the day – prevent this at all costs! Make sure everyone is able to attend in person for the full duration, even if it means traveling from another location for some participants.

Environment — Often underestimated in its influence, the environment around the team plays a role in the quality of the discussion and the receptiveness of the team to new ideas and challenges to status quo. Most importantly, the environment of the offsite should offer a change of scenery from day-to-day work – hotel conference rooms and resorts work well, or even a different office building with a distinct floor plan. Go for large spaces to broaden your horizons and think creatively (there is a reason artists prefer coffee shops and lofts). Open up the windows and bring in the light to keep the energy in the room positive and refreshing. Start early when the mind is fresh.

Agenda — Create an agenda for each day on the previous evening. Take into account the critical discussions and action items from the prior session if it is a multi-day offsite. At the start of each day, put down the agenda on the whiteboard or project it onto the screen for everyone to see. Ask each participant what they are looking to get out of the time spent and make sure it gets added to the list of topics to discuss. But everything said and done, the agenda merely serves as a guide and forcing function for discussion; it is not an end unto itself. Change the agenda – or discard it altogether – if you discover more important topics during the day.

Equipment — Make sure the conference room has the right tools (check on the day before to confirm). Make sure there is a projector and audio/video equipment that is functional. There is a lot of value in sharing a screen with the entire team showing the action items, priorities and notes. (On a side note, it is not unusual for everyone to agree on an action item but fail to agree on what the action item meant once it was written up precisely on the screen for everyone to read.) Don’t let your action items and decisions be lost or diluted because you failed to write it down clearly while it was being discussed.

Engagement — Write down and share a set of ground rules at the start of the offsite. Enforce a strict “no laptops” policy for anyone in the room – all individuals must close their laptops unless they are taking pertinent notes. There is arguably nothing more discouraging in such a session than to watch individuals physically in the same room but mentally elsewhere. Get everyone to sit at the table, and not on the sidelines, acting as observers. Identify activities that everyone can participate in and contribute. No one in the room should feel disengaged from the conversation. Normally, not everyone is eager to participate, so they must be assigned stuff to do. Some of the best discussions are had when the team breaks off as individuals, performs some activity (such as writing up some bullet points or paragraphs on customer pain points) and then comes back to share it with the group. This provides the right “melting pot” environment for ideas to come together and patterns to emerge. Most importantly, it also helps the quieter voices to be heard and disagreements to come out into the open.

Food — Nothing good can come of working on an empty stomach. Get lunch ordered ahead of time so the team can sit down and eat together, and perhaps continue the discussion in a more relaxed setting. Keep the energy level up – take a break or pick a different topic of discussion if the team is getting tired out.

Guiding Principles

1. Work backwards from the customer. Work backwards from the customer problem that you are trying to solve. Even when you are faced with operational issues and organizational challenges, frame the problem and its resolution in terms of the value it provides to real customers. Keeping your sights on the customer ensures that as a team you are externally focused rather than internally focused and always continue to generate value for your customers. By recognizing this value, the team is able to align on its charter and purpose of its existence.

2. Avoid groupthink. In the desire to be heard, it is easy to fall into the trap of expressing one’s opinion loudly and forcefully to the extent that it suppresses alternate opinions. In the interest of social cohesion, others may choose to simply agree with the idea or may fail to elaborate on dissenting views. For the team to make decisions that they can fully stand behind, it is important to encourage every individual to put forth their thoughts clearly (without reference to others’ opinions) and for others to actively listen to what they have to say.

3. Speak up. As an owner, every member of the team has a responsibility to speak up when they believe that they team is making a wrong decision or is heading towards a pitfall that they see coming. Rather than staying silent to avoid conflict, the individual must step forward to convey their own experience and understanding to the rest of the team. A decision may be arrived at where some members disagree and commit to the decision – but only after the point has been conveyed and understood by the others.

4. Measure progress. When it comes to setting goals for the team, the hard part is to make the goal measurable. With a measurable goal, anyone can objectively see how much progress has been made towards the goal. Until the measurement for the goal has been discussed and agreed upon, it cannot be considered a valid goal. Attempting to do otherwise results in goals that are not actionable, later resulting in confusion across the team and stakeholders.

5. Break constraints. Innovation and speed arise directly from a willingness to evaluate and break constraints. It is common for the team to see constraints as simply ‘the way things are’ instead of situations that can be intentionally altered. If you continue to operate within the existing framework of constraints, you are forced to move at the same slow speed as always; by consciously putting an effort into recognizing, evaluating and breaking such constraints, you unlock innovation and are able to move much faster towards your goals. Seemingly unsurmountable barriers vanish and you discover simpler and speedier ways to achieve what you originally assumed was impossible.

6. Create two-way doors. Decisions can be made much faster when you recognize that most decisions are two-way doors (that is, easily reversible). Teams sometimes spend a lot of time debating options endlessly and failing to reach consensus. Usually, though, there are more points of agreement than disagreement, and everyone has the same higher-level goal in mind. Once you recognize this, it is easy to see that most decisions are in fact two-way doors, and it is more important to make a decision, commit to it and move forward, rather than over-index on making the right decision all the time.

7. Take control of your own destiny. It is common to have dependencies on people and groups outside the team, both internal and external to the organization. In a situation where the team is blocked on dependencies, it is important that the team acts immediately to find innovative ways to unblock itself, or eliminate the dependency altogether. Only when the team ‘takes control of its own destiny’ is it able to accelerate towards its goals.

That’s all for today, folks! 🖖