Count Luck

This is clearly a graph traversal problem. As I see it, we must solve two sub-problems:

1. We must find the path from \(M\) to \(*\) (the problem statement guarantees that only a single path from \(M\) to \(*\) exists);
2. we must count how many times Hermione and Ron arrive at a fork in the road.

The first order of business will be to create a graph representation of the forest. If a point is a road, the start, or the portkey, it is a node and it will be represented by a tuple of two usize values representing the point’s \(x\) and \(y\) coordinates. An edge connects two nodes N₁ and N₂ if the two nodes are adjacent, i.e., are left/right or up/down of one another.

With a graph in hand, we can solve (1) by applying a breadth-first search algorithm. BFS will find the shortest path from \(M\) to \(*\). (Because there is only one path, a DFS traversal would also find the shortest path, however I have less experience writing breadth-first traversals, so I’ll use the opportunity to practice a little bit.) We want the result of BFS to be the sequence of points to visit; in the example above, the first element of that sequence is \((2, 7)\), followed by \((2, 8)\), and the last element is \((1, 2)\).

To solve (2), we will use the sequence computed in (1) and basically follow it step-by-step. When we reach a node that has more than one neighbor (excluding the node we came from), we have a fork and Hermione will use her hand there.

The graph data type is defined below. It is a regular Rust struct (product type); it has three fields, the adjacency list (the connections field) and the start and end nodes.

A common practice in Rust is to derive the Debug trait on types; this allows us to print a graph on the console during development.

#[derive(Debug)]
struct Graph {
    start: (usize, usize),
    end: (usize, usize),
    connections: HashMap<(usize, usize), HashSet<(usize, usize)>>
}

We now come to our first big function, read_graph. Because of its size, I will split it into “chunks”: this is not strictly necessary, however it is one of those LP things that I want to experiment with and see if they do aid with comprehension. A chunk is a named snippet of code that we can refer to; they are used primarily to split a long piece of code into understandable parts, and to present the parts in an order that may be easier or more natural to a human.

In the weaved document (which you are likely reading at the moment), a chunk appears in double angle brackets, e.g., <<connect-nodes>>, while in the tangled program they are expanded inline.

The function read_graph receives the dimensions of the scene, reads the description of the scene from stdin, and returns the corresponding graph. Because this is a simple program and because the inputs provided by the HackerRank system are all well-formed, we don’t do extensive error handling. For example, we don’t check that a start and end point exist, and if there are invalid characters in the input, we just panic.

fn read_graph(rows: usize, columns: usize) -> Graph {
    let stdin = io::stdin();
    let mut buf = String::new();
    let mut nodes = HashSet::with_capacity(rows * columns);
    let mut g = Graph {
        start: (0, 0),
        end: (0, 0),
        connections: HashMap::new(),
    };

    <<read-scene>>

    <<connect-nodes>>

    return g;
}

We start by initializing a few local variables:

• stdin and buf are used for reading from the terminal. stdin is a structure that implements the Read trait, which provides the read_line method. This method reads characters up to, and including, the newline character into buf and returns either the number of bytes that were read, or an error. We assume that no errors occur during input.
• g is the graph we want to return. We initialize the coordinates of the start and end nodes to (0, 0). In a program where we cared more about robustness, we’d probably declare those fields as Option<(usize, usize)> and initialize them to None; however, as we mentioned, we don’t expect input without a start or an end, and we therefore keep the types simpler.
• nodes is the set of all the nodes (floor tiles, start and portkey) in the scene. We use this extra local variables rather than storing the information directly in the graph’s HashMap due to Rust’s borrow restrictions (more on this later).

Once the local variables are initialized, we read the whole scene. We will explain in detail how this process works in the next sub-section. At the end of the <<read-scene>> chunk, the start and end fields of g will have been appropriately set. After <<connect-nodes>>, the adjacency list will be populated and we can return g.

Now that we have our Graph data type, and that we have a function to create it from a textual description, it is time to create the traversal function.

(Note: in the preceding section, I split read_graph into three separate, logical chunks. I have decided not to split the bfs function in this section. I want to see how chunk vs. no-chunk affects clarity and comprehension; if you have comments about using chunks, do let me know.)

The bfs function has three logical phases.

Initialization

In this phase, we create two data structures: a queue that contains the nodes to visit (a BFS traversal uses a FIFO structure to determine the next node to visit while a DFS traversal uses a LIFO structure), and a map to keep track of the nodes visited so far and their parent. A parent is represented with an Option type. The start node has no parent and so we represent its lack of a parent in the map with the value None. The parent of the other nodes is Some((x, y)). We begin the procedure, by putting the start node in the queue, and marking it as visited.

Traversal

Our next step is to traverse the whole graph. We iterate until the queue of nodes left to process is empty. We pop the oldest node from the queue and look at its neighbors. If a neighbor has already been visited, we skip it; if a neighbor has yet to be visited, we add it to the queue and record its parent in the map. We could terminate the traversal early by breaking from the loop when we hit the end node, but to keep the code shorter, we have omitted this small optimization.

Path finding

Once the parent map has been populated, finding the path from beginning to end is simple. Starting with the end node, we use the map to find its parent, and then find that parent’s parent, and so on, until we reach the start node. All the while, we push the coordinates of the nodes inside a vector. After the loop, the vector contains the coordinates, but from end to beginning; we reverse the path, and return it.

fn bfs(g: &Graph) -> Vec<(usize, usize)> {
    let mut q = VecDeque::new();
    let mut parent: HashMap<(usize, usize), Option<(usize, usize)>> = HashMap::new();

    q.push_back(g.start);
    parent.insert(g.start, None);

    while !q.is_empty() {
        let curr = q.pop_front().unwrap();

        for neighbor in g.connections.get(&curr).unwrap() {
            if !parent.contains_key(neighbor) {
                parent.insert(*neighbor, Some(curr));
                q.push_back(*neighbor);
            }
        }
    }

    let mut path = Vec::new();
    let mut curr = Some(g.end);
    while let Some(x) = curr {
        path.push(x);
        curr = *(parent.get(&x).unwrap());
    }
    path.reverse();
    return path;
}

We finally get to the last part of the problem, counting how many times Hermione needs to zap her wand for her and Ron to find their way to the portkey. Hermione will use her wand when she and Ron are on a node that has two or more unvisited neighbors. When they are standing on the start node, that means two or more neighbors, and when they are standing on other nodes, that means three or more neighbors (we do not count the node we came from.) Additionally, if Hermione and Ron are standing on the portkey node, she won’t need to zap her wand there, even if there is a fork, because they have reached their destination.

fn count_zaps(g: &Graph, path: &Vec<(usize, usize)>) -> usize {
    let mut zaps = 0;
    for p in path {
        let neighbors = g.connections.get(p).unwrap();
        if *p == g.start && neighbors.len() > 1 {
            zaps += 1;
        } else if *p != g.end && neighbors.len() > 2 {
            zaps += 1;
        }
    }
    return zaps;
}

Last summer, a number of people from my lab at McGill were going on interviews. To practice for those dreaded code challenges, we took problems from sites such as CareerCup and worked as a team to solve them, making sure to act as if we were in front of an interviewer. I remember those moments very fondly: in addition to the wonderful camaraderie of those sessions in front of a blackboard, it was an amazing opportunity to develop problem solving skills, and also solution explaining skills. Everyone who participated were on top of their game and presented their ideas in a clear and logical fashion. We’d sketch out example problems, see how we’d solve them, and try and find the corner cases that were lurking. We’d ask questions about the choice of proper data structures and algorithms, what assumptions we made about the problem, what invariants our solution needed to provide. We’d ask questions about running time, memory usage, we’d poke at details that seemed a little too hand-wavy. It was a very good way to improve as a programmer, and a fantastic way to spend quality time with excellent friends.

I feel that literate programming captures this spirit very well. I have tried my best to write down in the text the ideas that I would want to convey to those lab mates. One advantage of LP over doing it over at the board is that I have more time to think about what I want to say and how I want to say it.

Another obvious advantage of literate programming is how approachable it can make a new code base. We are often thrown into a foreign project, and asked to understand it, which is not always easy if the structure of the program is not documented or if the program is complex. In that context, this core idea of LP that you can open a program at page one, start reading, and begin to understand the program is a powerful one.

I have also found a number of ways by which literate programming was not as good as traditional programming.

Tool support

One of the biggest difficulty during the development of CountLuck was the disconnect between the literate programming document (the org file) and the different programming tools that I’m used to.

• I often forgot to tangle my document after making a change to the code.
• When the Rust compiler reports errors, it (of course) gives the line numbers in the tangled source file, not the org document. It’s harder and longer to locate the cause of an error.
• Useful Emacs features such as find-tag or imenu that I use liberally to navigate in a project don’t work.

I think one of the biggest challenges that literate programming faces if it is to gain wider-spread acceptance is to offer a set of tools that make using LP as convenient as regular programming. (I realize that I have only used one tool, org mode, and haven’t tried noweb or CWEB; maybe they have solutions to those issues.)

Chunks

I don’t know how I feel about chunks. On the one hand, they are great at splitting code into logical parts, and even allowing those parts to come in the order that makes the most sense for the reader. However, I feel that if I use chunks too much, I lose the mental picture of what the function is supposed to look like. Also, when should one use chunks vs. creating a new helper function? I would love to hear arguments for or against chunks.

Project organization

I am not sure how a literate programming project should be organized. Where should the literate program be put? In the src directory or somewhere else? Should the tangled source files be included in version control or should they be considered build artifacts? Should a literate program be a single file (tex.web is a single 25,000 line file) or is splitting encouraged? How does that affect the ability of a team to work together?

Language barrier

I am a native French speaker, and although I don’t have difficulty reading and writing English, it seems that literate programming could make is harder for people who don’t speak English fluently to contribute to a project if they are expected to clearly document the code that they write.

One aspect of this literate program that is not apparent from the weaved document or the tangled program is how I’ve formatted the text inside the org file.

A few weeks ago, I read an old blog post by John Regehr where he suggests making the structure of sentences apparent by using newlines generously. All my sentences are on their own line (or multiple lines if they are long and the right margin) and are separated by a blank line (I use a # to make an org comment to prevent a paragraph break). This definitely makes the source text a little weird to look at, however sentences are a lot easier to move around, I can easily see how long a sentence is, and it’s easier to notice if the same syntactic structure is used or not. In addition, this is friendlier for version control systems like Git since adding or removing a fewof words from a sentence only affects a line or two. If the text was re-filled, the entire paragraph might be in the diff block, thus making the changes harder to spot.

I have found that the hardest part about this style is not writing the text, but rather to avoid the temptation to hit M-q as soon as I hit the period key. (In Emacs, M-q invokes the fill-paragraph command.)