Google foobar, part ii: stashing bunnies

This post is the second installment of the foobar challenge series. You can read the first one to learn more about foobar and see what sort of intro problems the challenge presents if you don't want any real spoilers.

WARNING: Obviously, MAJOR spoilers ahead, for the problems themselves and possible solutions or hints. Even if you're attempting one of these and feel completely stuck, give it another go before reading the rest. Keep reading only if you don't mind getting spoiled!

Problem statement

Okay, so this one is about stashing bunnies. Bunnies? Well, anything that's fuzzy and warm and you can assign an ID to.

Assume you have a bunch of bunnies stashed in a corner, represented by their ID numbers, revealing the order you stacked them in:

We want to figure out what the ID of the bunny is given a pair of coordinates \((x, y)\), where \(x\) is the distance from the leftmost wall and \(y\) the distance from the floor. For example, the bunny with ID \(1\) is at \((1, 1)\), the one with ID \(8\) is at \((2, 3)\) and so on.

@@@@@@@@@@

@@@@@@@@@@

SECOND WARNING: If you want to solve this yourself, STOP HERE! Anything past this point is a spoiler of some part of figuring out the solution, or of the solution itself. You've been warned!

@@@@@@@@@@

@@@@@@@@@@

First ideas

A naive solution to this could be to simply construct this thing as a 2D array, and index into it to get the answer immediately. Of course that wouldn't be very interesting, so the challenge prevents us from doing so by setting the max values of \(x\) and \(y\) to a considerably large number (something like \(100{,}000\) if I remember correctly). While you might be able to get away with constructing the solution like this here, I haven't tried it and I think it's more fun to find a solution that doesn't need that anyway.

So... where do we start? Well, as always it's a good idea to start looking for patterns in the numbers, so let's start by writing down the first few coordinates, ordered by the ID they point to: $$ \begin{matrix} (1, 1) & \rightarrow & 1 \\ (1, 2) & \rightarrow & 2 \\ (2, 1) & \rightarrow & 3 \\ (1, 3) & \rightarrow & 4 \\ (2, 2) & \rightarrow & 5 \\ (3, 1) & \rightarrow & 6 \\ (1, 4) & \rightarrow & 7 \\ (2, 3) & \rightarrow & 8 \\ (3, 2) & \rightarrow & 9 \\ (4, 1) & \rightarrow & 10 \\ & \ldots & \\ \end{matrix} $$

See a pattern? I'll try to describe what came to me first, and it's okay if it's kind of wishy-washy and not clearly formulated yet, we will get to a more formal version later.

What I first observed when writing those down is that you always seem to come back to a \((1, M)\) pair, then some other pairs, then \((M, 1)\), and then \((1, M + 1)\). For example, you have the pair \((1, 4)\), then some other pairs, then \((4, 1)\), and then \((1, 5)\) immediately after.

The second thing I observed was that those intermediate pairs between \((1, M)\) and \((M, 1)\) were kind of stepping through the values between \(1\) and \(M\). More specifically, the value of the \(x\) coordinate increments until it reaches \(M\), and the value of the \(y\) coordinate decrements until it reaches \(1\). So, finally, the sequence is: $$ \begin{matrix} ( & 1 & , & M & ) \\ ( & 2 & , & M - 1 & ) \\ ( & 3 & , & M - 2 & ) \\ & & \ldots & & \\ ( & M - 2 & , & 3 & ) \\ ( & M - 1 & , & 2 & ) \\ ( & M & , & 1 & ) \\ ( & 1 & , & M + 1 & ) \\ & & \ldots & & \\ \end{matrix} $$

Great, but.. what ID is associated to \((1, M)\), how does this get us anywhere? Well, at this point we could pretty much solve this by iterating on this sequence until we reach the given coordinate pair.

I don't love this solution; sure, maybe there's some clever dynamic programming trick we could use to optimize this, but basically if we're given \((100{,}000,\ 100{,}000)\) we're screwed: we'd have to go through literally every other ID before we find that one. There's also another problem: our sequence algorithm gets us IDs in the same order as the one they're put in the stash, so diagonally! This means that we will only get the pair \((M, M)\) if it's in the diagonal of \((1, N) \ldots (N, 1)\), but of course \(M \leq N\). If the max value of \(x\) and \(y\) was \(4\), we would never be able to get \((M, M)\) for any \(M \gt 2\).

NOTE: if you don't get why that is, think that the diagonal containing \((2, 2)\) ends at \((3, 1)\). This means that the next diagonal starts at \((1, 4)\), but it doesn't contain an \((M, M)\) pair (you can convince yourself by writing down the entire diagonal). The diagonal after that one, \((1, 5)\), does contain \((3, 3)\), but as you can clearly tell \((1, 5)\) is out-of-bounds, because for this example we said that the max value of \(x\) and \(y\) is \(4\).

Looking for more patterns

We can do much better than this. The next idea I had was to look at what IDs were associated with coordinates of the form \((1, M)\), for different values of \(M\): $$ \begin{matrix} (1, 1) & \rightarrow & 1 \\ (1, 2) & \rightarrow & 2 \\ (1, 3) & \rightarrow & 4 \\ (1, 4) & \rightarrow & 7 \\ (1, 5) & \rightarrow & 11 \\ & \ldots & \\ \end{matrix} $$

Let's forget about the pairs of any \(x\) and \(y\) and focus on the \((1, M)\) pairs for a moment: reducing a problem by adding a constraint like this often makes it easier to find a partial solution to the original problem, and then by removing the constraint we can start to build a complete solution.

When I got to this point while solving, I was trying to find a sort of law for the sequence of IDs (\(1, 2, 4, 7, 11, \ldots\)) or for the relationship of the ID and \(M\), the \(y\) coordinate. Maybe there is one, but I didn't find it, and I came up with another idea instead: what if we thought of every \((1, M)\) pair as the beginning of a group? In that case, the ID of the beginning of a group would basically be the number of IDs below it, plus one (since IDs start at 1). The first group is \(G_1 = \{(1, 1), \ldots, (1, 1)\}\) group, which contains a single element (\(G_1 = \{(1, 1)\}\)), so the ID of the first element of the second group is \(|G_1| + 1 = 1 + 1 = 2\).

Let's do another example, to convince ourselves: group 2 has 2 elements, with \(G_2 = \{(1, 2), (2, 1)\}\), so we can say that \((1, 3)\) will have an ID of \(|G_1| + |G_2| + 1 = 1 + 2 + 1 = 4\), which is indeed the case.

So, for a given group leader pair \((1, M)\), we have two things to figure out in order to be able to find its ID:

• Which group it is in;
• How many elements are below/before it.

The first one is easy: \((1, M)\) is the first element of the \(M\)-th group! The second one is more complicated. I mean, we can sort of answer the question by saying the number of elements below \(M\) is the sum of the sizes of the groups \(1\) through \(M - 1\), but of course that's not the complete answer. It does simplify things though: now we only need to find how many elements are in a given group \(M\). Well... if you think of it, the groups we've been talking about are simply the diagonals!

So, this question is actually trivial: group \(M\) has \(M\) elements! Now we can start assembling our answer.

Every pair \((1, M)\) has an ID of \(\left(\sum_{i = 1}^{M - 1} |G_i|\right) + 1\), which is equal to \((1 + 2 + \ldots + (M - 1)) + 1\).

That's great! We now know the ID of every group leader pair. How can we solve the general problem of finding the ID of any \((x, y)\) pair? Well, all we have to do at this point is figure out two things:

• Which group \((x, y)\) belongs to;
• What is its offset from the group leader.

The first one is easy to figure out if we remember how we obtained the sequence of each group: increment \(x\) until \(M\), decrement \(y\) until \(1\). Since we're incrementing \(x\) and decrementing \(y\) at the same time, that means that their sum is constant, so no matter which \((x, y)\) we land on in the sequence, \(x + y\) will give us the same value (for \(G_3\) for instance, \(1 + 3 = 2 + 2 = 3 + 1\)). But what's that sum? Well, since the group leader of group \(M\) is \((1, M)\), the sum is simply \(M + 1\). That's the answer to the first question: \((x, y)\) belongs to group \(x + y - 1\).

The second question is also easy to answer if we look at the patterns, again: since we are looking for an offset from \((1, M)\), and the sequence pattern is formed by incrementing \(x\), all we have to do is look at \(x\). For the first element of the group \(x\) will be \(1\), for the second \(2\) and so on. So, to get the offset from the group leader for any given \((x, y)\) pair, we simply calculate \(x - 1\).

Solution

Let's put everything together. For a given pair \((x, y)\), belonging to group \(x + y - 1\), the ID is: $$ \textrm{(ID of group leader of}\ x + y - 1\textrm{)} + \textrm{(offset from group leader of}\ x + y - 1\textrm{)} $$

Expanding on that, we have: $$ (\textrm{(number of elements before}\ x + y - 1\textrm{)} + 1) + (x - 1) $$

And by expanding further, we get: $$ \left(\left(\sum_{i = 1}^{x + y - 2} i\right) + 1\right) + (x - 1) $$

With a bit of simplifying, we finally get: $$ \left(\sum_{i = 1}^{x + y - 2} i\right) + x $$

If we want to be even cooler and pretend we actually know some basic math, we can simplify it further since \(\sum_{i = 1}^{N} i = \frac{N(N + 1)}{2}\). So the final formula actually is: $$ \mathrm{ID}(x, y) = \frac{(x + y - 2)(x + y - 1)}{2} + x $$

Okay, that's cool and all, but does it work? Let's test our formula on a couple of pairs: $$ \mathrm{ID}(2, 3) = \frac{(2 + 3 - 2)(2 + 3 - 1)}{2} + 2 = 8 $$

Nice! And another one: $$ \mathrm{ID}(4, 2) = \frac{(4 + 2 - 2)(4 + 2 - 1)}{2} + 4 = 14 $$

Woo! The formula seems to be correct!

This is great because, since it's a closed-form solution, the time complexity will be \(O(1)\) (or, in layman's terms, really frickin' fast). Let's implement it in code:

def solution(x, y):
    return (x + y - 2) * (x + y - 1) // 2 + x

And that's it!