The Kangaroo Problem

Quot homines, tot sententiae; suus cuique mos.
There are as many opinions as there are people. To each his own.

—Terence, Phormio 454

Though I code with the tongues of men and of angels, but have not love, I have become sounding brass or a clanging cymbal.

—I Corinthians 13:1 (adapted)

The concept of “good code” can be controversial—as much as, I suppose, the concept of “good” anything. What makes something good? Obviously, different people will have different answers. But perhaps that makes it more imporant than ever for me to answer that question for myself.

So what makes “good code”? This post will discuss a few ideas.

Warning: For an example I’ll be looking at the HackerRank Kangaroo Problem. I will be discussing solutions to the problem. (In fact, I’ll be discussing several solutions.) If you don’t want the solution spoiled for you, stop reading here. You’ve been warned…

The Kangaroo Problem

Here’s the setup, as desribed on HackerRank:

You are choreographing a circus show with various animals. For one act, you are given two kangaroos on a number line ready to jump in the positive direction (i.e, toward positive infinity).

• The first kangaroo starts at location and moves at a rate of meters per jump.
• The second kangaroo starts at location and moves at a rate of meters per jump.

You have to figure out a way to get both kangaroos at the same location at the same time as part of the show. If it is possible, return YES, otherwise return NO.

Function Description

Complete the function kangaroo in the editor below. It should return 'YES' if they reach the same position at the same time, or 'NO' if they don't.

kangaroo has the following parameters:

• x1, v1: integers, starting position and jump distance for kangaroo 1
• x2, v2: integers, starting position and jump distance for kangaroo 2

Constraints

• 0 ≤ x1 < x2 ≤ 10,000
• 1 ≤ v1 ≤ 10,000
• 1 ≤ v2 ≤ 10,000

A bit contrived, but no less a puzzle. Let’s see if we can work out a solution in JavaScript, and at the same time develop a standard by which we can evaluate our code.

Good code works.

The minimum requirement for code is that it works. Code that doesn’t work certainly can’t be called “good.”

But what does it mean for code to work? To answer this question I have to have a precise understanding of what it is I want my code to do. I need to have a defined goal. That goal may change over time—and my definition of “good code” will change along with it.

Thankfully, HackerRank is very clear about what it means for our solution to the Kangaroo Problem to work:

1. Our solution should take the form of a function that accepts four parameters called x1, v1, x2, and v2.
2. The function should return the string ‘YES’ if and only if it is possible for the two kangaroos to land in the same spot at the same point in time.
3. The function should return the string ‘NO’ if it is impossible for them to land in the same spot.

In addition to these goals defined by HackerRank, there is one more particular to our case:

4. The function must meet conditions 1-3 for every test case provided by HackerRank.

After all, this is how HackerRank itself determines success. It calls our function on a series of values. If the function returns the right value for each test case, then it deems us successful and awards us a handful of those coveted Hackos.

One approach to the problem is to loop through all the possible kangaroo positions and test whether they are in the same spot at any point. But how many times should we loop? Surely we’ll have an answer after 10,000 iterations. (Surely the kangaroos will be tired enough after 10,000 jumps to take a break!)

function kangaroo(x1, v1, x2, v2) {
    // A 'good' solution
    let result = 'NO';
    for (let i = 0; i < 10000 && result == 'NO'; i++) {
        if (x1 + v1 * i == x2 + v2 * i) {
            result = 'YES';
        }
    }
    return result;
}

Does this code work? Let’s check our specs:

• It's a function.
• It returns the string 'YES' if and only if it is possible for the two kangaroos to land in the same spot at the same point in time.
• It returns the string 'NO' if they will never, ever land in the same spot.
• It satisfies these conditions for every test case provided by HackerRank.

Yes, we’ve met all our goals. If we test our function with all of HackerRank’s test cases, we succeed every time. According to our definition, we’ve produced some good code.

Better code is easy to interpret.

But what does our function really do? It’s probably not too difficult to explain it at the moment, since we just wrote it. It loops 10,000 times, and each time it checks… Wait, what does it check? Inside the loop we have this conditional expression:

x1 + v1 * i == x2 + v2 * i

If we think for a second, we might be able to remember that this line calculates the current position of each kangaroo as the sum of its initial location plus the product of its jump-size multiplied by the number of jumps it’s made at this point. It then compares these calculations together to see if they are in the same location. To us it may be (fairly) clear, but would it be clear to someone else who was reading our code?

And even if it makes perfect sense to us right now, what will we do when we come back to this code in ten weeks or ten days (or ten minutes!) and this line seems a little more obscure?

To me, this is the line between good code and better code. Good code may work, but better code works in a way that is clear and easy to interpret. Good code may get the job done for me, but better code is useful for others as well. (If you’re in doubt about the limitations of merely good code, just check out any minified JavaScript file.)

Our solution to the Kangaroo Problem is short, but we’ve already seen how at least one line is pretty hard to read. What can we do to make it clearer?

One option is to add comments that explain the tricky bits, but I have an even better idea.

Wouldn’t it be great if we could just replace the complicated if-statement with a description, in English, of what condition it’s checking? We can do that if we replace the condition with a function call:

function kangaroo(x1, v1, x2, v2) {
    // A 'better' solution
    
    let kangaroosAreInTheSameSpot = function(jumpNumber) {
        // Calculates the position of the kangaroos after
        // a given number of jumps and tests for equality.
        return (x1 + v1 * jumpNumber == x2 + v2 * jumpNumber);
    }

    let result = 'NO';
    for (let i = 0; i < 10000 && result == 'NO'; i++) {
        if (kangaroosAreInTheSameSpot(i)) {
            result = 'YES';
        }
    }
    return result;
}

All we have done is refactor the logic of the condition into its own function. We gave that function the very descriptive name of kangaroosAreInTheSameSpot. The effect is that our if-statement reads like natural English.

Just imagine for a moment returning to this code after a year and trying to make sense of it. How much easier will it be to interpret this solution, compared to our first, “good” attempt!¹

Can code be “best”?

But I think we can do more to improve our merely “good” solution. It contains a loop that runs 10,000 times—but why 10,000? Why not 100 times, or 1 million? The truth is that we assumed that any kangaroo would be tired out after 10,000 jumps, and so that’s how many times we looped. This happened to work for us; all of the HackerRank test cases were successful. But there was nothing in the setup of the problem that told us we would only have to account for 10,000 jumps. What if a super-kangaroo came along that could jump 1 million times in a row without breaking a sweat? Our solution might not work.

This leads us to the concept not of “good” code or “better” code, but of the best code. For code to be “best” does not mean that it can’t be improved. All code is the product of a human author and will express the limitations of that author. Pobody’s nerfect. Not to mention the fact that the requirements of code may change over time. Since we’re evaluating code according to the extent to which it solves a problem, when that problem changes, even the best code must be changed along with it.

So what does it mean for code to be best?

The best code is clever.

The best code not only solves the current problem, but attempts to anticipate other problems that are likely to arise. In the case of the Kangaroo Problem, we might imagine a super-kangaroo that can jump more than 10,000 times. How can we improve our solution so that it isn’t limited to 10,000 jumps—or to any arbitrary number of jumps?

When I first encountered this problem, I asked myself how I could break it into smaller pieces that could be solved more easily. For example, I knew that it would be easy to test whether the kangaroos were in the same position at the start, before they had many any jumps, because their starting positions are passed in as parameters.

From there, I realized I could call my kangaroo function recursively, updating the values of x1 and x2 each time. A recursive solution starts with a “base case” that defines the situation when a solution has been found. The base case is followed by the recursive case, which calls the same function again with different values.

function kangaroo(x1, v1, x2, v2) {
    // A 'best' solution with recursion
    
    // BASE CASE:
    // If the kangaroos are on the same spot, then we found a solution
    if (x1 == x2) return 'YES';

    // RECURSIVE CASE:
    // Update x1 and x2 and call kangaroo() again.
    x1 += v1;
    x2 += v2;
    return kangaroo(x1, v1, x2, v2);
}

This is a start, but we’re not quite there yet. If the kangaroos ever land in the same spot, this solution will find it. But if there is no solution—if the kangaroos will never, ever land in the same spot—then our function will keep running forever… or until it overflows the stack. That’s not what we want. We need to add a few more base cases to check whether we have enough information to determine that, no, the kangaroos will never land in the same spot.

function kangaroo(x1, v1, x2, v2) {
    // A 'best' solution with recursion
    
    // BASE CASE 1: Success
    // If the kangaroos are on the same spot, then we found a solution
    if (x1 == x2) return 'YES';

    // BASE CASE 2: Failure
    // If the 1st kangaroo has jumped ahead of the 2nd kangaroo,
    // then they'll never land on the same spot.
    if (x1 > x2) return 'NO';

    // BASE CASE 3: Failure
    // If Kangaroo 2 is going faster than Kangaroo 1,
    // then they'll never land on the same spot.
    if (v2 > v1) return 'NO';

    // BASE CASE 4: Failure
    // If the kangaroos have the same velocity
    // (and they're not on the same spot already)
    // then they'll never land on the same spot.
    if (v1 == v2) return 'NO';

    // RECURSIVE CASE:
    // Update x1 and x2 and call kangaroo() again.
    x1 += v1;
    x2 += v2;
    return kangaroo(x1, v1, x2, v2);
}

There are three situations that indicate, at any point, that the kangaroos will never land in the same spot. First, since the problem setup says Kangaroo 2 always starts out ahead of Kangaroo 1, we know that they should stay that way until they land in the same spot (if they ever do). If Kangaroo 1 is ever ahead of Kangaroo 2, then it’s jumped over her buddy, who will never catch up to her.

Second, if the 2nd kangaroo is moving faster than the first, then the first will never be able to catch up to her, and they’ll never land together.

Third, if the kangaroos are jumping at the same velocity, they’ll always be moving in parallel and will never intersect.

The strength of this solution is its cleverness. It employed a technique (recursion) that transformed it from a particular solution (limited to 10,000 jumps) to a general solution (theoretically unlimited).

That’s what I mean by clever. A clever solution leverages the inherent strength of our computer’s processor to perform a feat that would be much too difficult for any human. Making someone solve this problem by hand using recursion would probably violate the Geneva Convention. It would drive anyone insane. But our processor is actually very good at this sort of task and doesn’t shy away from finite recursion. Asking the code to do something that it’s very good at doing is what makes this a clever solution.

The best code is simple.

I am not afraid to admit that I like to be clever. 😉 And here is where I describe the most important lesson I learned from the Kangaroo Problem. The best code may be clever, but the best code is also simple.

When I told my husband about my clever solution to the Kangaroo Problem, he blinked once, grabbed a stack of Post-It notes, and began scribbling. A minute later he showed me his solution—consisting of just one if-else-statement. No recursion. Not even a loop.

Sheepishly, I typed it into HackerRank and ran the tests. They all checked out. He had instantly replaced my 28-line solution, which had a complexity of O(n), with one smaller by a factor of 4 with a complexity of O(1). The booger.

Here is what he wrote:

function kangaroo(x1, v1, x2, v2) {    
    if (v1 < v2 || (x2 - x1) % (v1 - v2) !== 0) {
        return 'NO';
    } else {
        return 'YES';
    }
}

He explained that the straightforward solution to the problem is to use a system of equations. We know that the position of the first kangaroo is equal to x1 + v1 * n, where n is the number of jumps it has made. Similarly, the position of the second kangaroo is equal to x2 + v2 * n. If we set these expressions equal to one another, we can not only determine whether they will intersect, but when and at what location. So let’s do some algebra:

1. x1 + v1 * n = x2 + v2 * n (Set the expressions equal to each other.)
2. (v1 * n) - (v2 * n) = x2 - x1 (Move the n terms to the same side.)
3. n * (v1 - v2) = x2 - x1 (Factor out the n terms.)
4. n = (x2 - x1) / (v1 - v2) (Divide each side by v1 - v2.)

As long as n is a positive integer, then we know right off the bat that the kangaroos will land in the same spot at some point. n is positive as long as v1 < v2. That’s what the first logical condition in the if-statement above is checking. If v1 < v2, then we can return ‘NO’.

The second logical condition is checking that n evaluates to an integer. After all, it doesn’t make much sense to talk about the kangaroos being in the same spot after 1.37 jumps, right? It only works if they intersect at a whole number value of n. So if (x2 - x2) divides into (v1 - v2) with a remainder other than zero, then we should return ‘NO’.

Otherwise, n evaluates to a positive integer, so the answer is ‘YES’. The kangaroos will intersect.

Balancing the bests

Ultimately, code is “good enough” if it accomplishes the desired goal, regardless of how it does that. But “good enough” code isn’t exactly code I’d be eager to Slack to my friends or post to my blog. 😉 Better code accomplishes the desired goal in a way that is easy to interpret, so that others can understand what it is doing and how it is doing it—and so that I’m not left scratching my head when I return to it after a while.

But writing the best code requires a balance between simple and clever. Our first solution to the Kangaroo Problem was simple; all it did was loop 10,000 times. But it wasn’t clever enough to handle other likely situations, such as a super-kangaroo that can jump 1 million times. Our final solution strikes a balance between clever and simple. It’s clever enough to work for any number of jumps, but it’s so simple that it doesn’t even use a loop.

Striking that balance is what’s going to be the challenge for me. But at least now I’ll always know exactly where my kangaroos are…

1. Of course, just because I have a function called kangaroosAreInTheSamePlace doesn’t mean that it actually checks whether the kangaroos are in the same spot. But that does at least make it clear that this was my intention and that’s what the if-statement is supposed to be doing. ↩