The Zelda Rupees Problem

Play First, Then Read

Plato is tossing rupees into a forest clearing, and they don’t stay long. Click the field, then move Pot with the arrow keys or WASD, and grab what you can before they fade. Green is worth 1, blue is worth 5, and red is worth 20. Flame is already playing - it’s the same believable AI from Dungeons Without End, and it doesn’t wait for you. Reset puts both counters back at zero.

Man, I love games. The classics, the old Nintendo games. I love them so much I make strategy guides out of them. I recreate them, and I make new ones. And I’ve decorated my office with a lot of gaming elements, characters and posters. And I even find a way to use them for my work. So while I’m working on mortgage and title product systems today, I sneak in games where I can - as an interview problem.

I grew up playing Zelda in the early 90s, oblivious to how obscure the game was, with its mistranslated hints, and to how much I adored it. Not until much later, in retrospect, did I really realize how much I loved these old games. Zelda has grown up a lot since then, into fully immersive 3D games, and Link has roles in the rest of Nintendo’s gaming ecosystem now too, as a racer in Mario Kart, and with his own hack-n-slash in Hyrule Warriors. Like Zelda, I’ve grown a lot too. My interview problem is one way I pay tribute to the classics, and not only to Link and the game itself, but to its developers, who had to work under such heavy constraint - namely, 8 bits.

It is impressive to me that developers in the 80s and 90s used assembly to make these games. They had real constraints, and that forced real creativity. I’ll write about that one day, as it’s something I strongly believe in - our expansive resources today make us a bit uncreative. Developers back then had to use a lot of creativity, and I feel we miss a lot of that today.

Link can only carry 255 rupees. And that’s both a business and an engineering decision. 255 is recognizable as the limit for 8 bits: 2 raised to the 8th power is 256, and counting from zero, that takes you up to 255. In binary, it’s eight ones, 11111111, every bit switched on. And unsigned, at that, meaning it could use all 8 bits for a positive number. It’s a business limitation because that’s what they wanted, and 255 rupees is all you really needed to experience what the game offered.

It’s more recognizable as an engineering limitation, because it meant you only needed a single place in memory - one byte - to store the number of rupees. Any more than that, and you needed a ninth bit, which really means a second byte, and extra code to carry from one byte into the next. The NES could do it, but not directly: its processor worked on one byte at a time. Dragon Warrior went to the trouble for its gold, which tops out at 65,535, two full bytes. Zelda didn’t need to.

Yet still, many games could show higher numbers. Notably, in Super Mario Bros., the score could reach many 9s, far more than 255 itself. The question, and therefore the crux of the interview problem, was then: how could that be possible on an 8-bit system? The answer isn’t all that clever - it’s in fact an account of how we count at all in base ten: a fixed, positional numbering system.

History of Counting

History lesson time! I learned this one in a History of Math class during college. Counting wasn’t always as trivial as it seems today. Roman numerals are the ones most people recognize, and they don’t count the way we count today. An X next to an X meant you add two tens together to get 20. We don’t mimic this today by writing “1010” and taking it to mean 20.

The oldest way to count is barely a system at all: tally marks. One scratch per sheep. It works fine for a small flock, and terribly for anything bigger.

The Egyptians did better. They had a symbol for each power of ten - a stroke for 1, a hobble for 10, a coil of rope for 100, a lotus flower for 1,000, and on up - and they drew as many of each as they needed. So it was base ten, sort of, but with no positions. 123 was one coil, two hobbles, and three strokes, and you could shuffle them around and still have 123. The Romans worked much the same way, with letters instead of pictures, plus the later twist of subtracting a small letter placed before a big one: IV for 4. Neither system was much good for arithmetic. The real work happened on an abacus or a counting board, and the numerals just wrote the answer down.

The Babylonians, close to 4,000 years ago, had the earliest positional system we know of. Their digits were built from just two wedge marks pressed into clay, and where a digit sat told you what it was worth. But they counted in base 60, which is why we still have 60 seconds in a minute and 60 minutes in an hour. And they had no zero. An empty place was just a gap in the clay, and much later a placeholder of two slanted wedges, but never at the end of a number. So 1 and 60 were written exactly the same, and you worked out which one was meant from context. Imagine a loan amount written that way. The Maya, on the other side of the world, got there on their own, in base 20, with a real zero drawn as a shell.

The system we use today comes from India: nine digits, plus a zero that held its place like any other digit. By 628, the mathematician Brahmagupta was writing rules for zero as a number in its own right - what you get when you subtract a number from itself. From there, it traveled. In 9th-century Baghdad, al-Khwarizmi wrote a book on calculating with the Hindu numerals, and when it was translated into Latin, his name came along as Algoritmi. That’s where we get the word algorithm. Then in 1202, Fibonacci - yes, the sequence guy - published Liber Abaci and pitched the new numerals to European merchants.

The business world, as it tends to, took its time. In 1299, the money changers’ guild of Florence ordered its members to write their account books out in plain words, not “by abacus,” a rule usually read as keeping the new numerals out of the books because they were too easy to alter. It took a few more centuries for positional numbers to win the ledger.

And so with a fixed position system, the paramount mechanic is that each position is exponentially accumulated by its base, and then added. So 123 becomes 1 × 10² + 2 × 10¹ + 3 × 10⁰, which is 100 + 20 + 3. Binary is the same trick in base 2: 11111111 is 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1, which is our 255. If you know this, you know the most important piece of solving the Zelda Rupees Problem.

Why Zelda Rupees

I asked candidates to implement the solution in simple C#, on an online notepad that could compile and run the code. Nothing fancy, just the method and a basic test of language proficiency. I never enjoyed, nor do I agree with, the complex problems that larger companies like Facebook, Microsoft, and Google like to ask. You don’t use those solutions at work, and you likely never will need anything so deeply complex. That is for researchers working at the forefront of knowledge: for the sake of knowledge and publications, not for the sake of some business seeking to earn profitable income. The world doesn’t buy complexity, but it asks for it in a niche corner. That corner then, over time, leaks to the business world slowly, when the world decides it is ready to adopt it. Just like the numbering system in the 1200s.

And then again, the world doesn’t need a solution to the Zelda Rupees Problem, either. And the company you’re interviewing for doesn’t need it either. That was never the point. I didn’t need anyone to know about the raw solution, or about 8-bit limitations at all. I could tell you all of that as backstory. In fact, if you were able to solve it in spite of not knowing anything at all about it, it told me more about you than the ones who already knew the problem. That’s what’s wrong with LeetCode-style problems: the ones who can solve them likely have already solved them before. I care more about the way you think, the questions you ask, and how you might work well with me to make our time together more enjoyable than I do your raw ability.

You see, that’s sometimes more powerful than brute strength at coding and engineering. Realize we are all here to make a living, to earn a salary and work together. Ultimately, to have fun while we do it. Not to make family or be each other’s best buddies, but because we are brought together by a common goal and a common company. My goals are not the company’s goals, and that’s fine. But I fit in fine, because I’m willing to work on the company’s goals and also my own at the same time. That is cultural fit, and I have a much harder time gauging that than I do your technical proficiency. In the age of AI, the technical proficiency part is even less of a concern, and that is fine, because I never cared that much about it to begin with. Feature-rich IDEs already took care of a lot of coding patterns for you, like the auto-imports you could never remember to write by hand on a notepad. AI does even more of it now, and that’s a good thing. I would never expect you to reiterate what the tool could already do for you. That is just redundant.

Zelda Rupees was a fun problem we could both talk through, and for an hour, we could have fun together, just two perfect strangers working on the same, very simple problem. And so one of my objectives in giving an interview was to ease the mind of the candidate. Relax. You won’t work as stressed as you are now, and I’m not trying to be your gatekeeper. I’m not here to grade and nitpick every detail in my little notebook. That is something I struggle with myself when I’m on the opposite side of the table. Ironically, the most employable skill is the one we are all the least good at, and just as equally, the one we will use the least in our lives: the ability to interview well. And if that doesn’t suck, I don’t know what does.

The Problem

Link can only carry 255 rupees. What if we wanted to remove that limitation and allow him to pick up more, and hold up to 999 rupees? If we are limited to 8 bits, how might we philosophically implement that?

When we realize the solution is not just one piece of information to store, but three, then we can begin to solve it. We hold the 1s, the 10s, and the 100s. 999 rupees means a 9 in each of these three registers of information. In C#, I only cared to see this as three different regular integers. They didn’t need to be short or byte data types. I was fine with 32-bit integers, for the sake of simplicity.

Get the current amount to display as a single number on the screen. And then implement a routine that can “pick up” an additional, variable rupee amount. The getter was simpler: return Hundreds * 100 + Tens * 10 + Ones. The setter to add more rupees was more complex. There’s the case of overflow to handle, for example, when the ones overflow 9, and you need to carry it over to the 10s. And then there’s the case of overflow at the 100s too, and we must stay at 999.

That’s how Super Mario Bros. gets its many 9s, by the way. It keeps its score one decimal digit to a byte, none of them ever holding more than a 9, with a carry from each into the next. And it’s how the counters in the game at the top of this post keep theirs: hundreds, tens, and ones, stopping at 999.

public class RupeeWallet
{
    public int Hundreds { get; set; }

    public int Tens { get; set; }

    public int Ones { get; set; }

    public int GetRupeeTotal()
    {
        return Hundreds*100 + Tens*10 + Ones;
    }

    public void PickupCoin(int rupeeValue)
    {
        var incHundreds = rupeeValue / 100;
        var incTens = (rupeeValue / 10) % 10;
        var incOnes = (rupeeValue) % 10;

        Ones += incOnes;
        if (Ones > 9)
        {
            incTens += 1;
            Ones -= 10;
        }

        Tens += incTens;
        if (Tens > 9)
        {
            incHundreds += 1;
            Tens -= 10;
        }

        Hundreds += incHundreds;
        if (Hundreds > 9)
        {
            Hundreds = 9;
            Tens = 9;
            Ones = 9;
        }
    }
}

The Problem, in Another Place

Another way I’ve run into this problem is with some of the games I’ve built in the past. Whenever a game had a running score, I wanted to display that score. But I wanted to display that score with a custom graphic for each number. So I had ten files: one for each of the numbers. Hand drawn and digitized.

To get the game to properly use my numbering system, you guessed it, it was the same Zelda Rupees Problem all over again. If my game could show up to 999,999,999, then I had to divide by 100 million, then by 10 million, and so on, keeping the remainder each time, to find out the digit in each place. That told me which file to use to draw the number, and if I was smart about it, it wasn’t even ten files. It was just one larger numerical sprite sheet. If I wanted to draw the “six,” then I had to move over to the sixth column of the sprite sheet and render from there. Column six, counting from zero, like any good programmer.

A Little Fun at Work

You’d think this was a problem that’d work really well at a gaming company. But it worked really well for me, more so than I could’ve thought, even for a mortgage company that would do nothing with gaming. I still sometimes secretly dream of sneaking in a small easter egg one day. A small little playable game of sorts, like the Google T-Rex running game.

I think gaming is one way we can bring fun with us to the workplace in small, professional, and warming ways. If we’re all here to work and slave for the company, we’re never happy, and that’s not something I can get behind. But if we all work together, and make each other’s lives a little happier, then that’s a culture I can enjoy.

If you haven’t tried it yet, go try and implement the Zelda Rupees Problem yourself, today. It’s about as difficult as FizzBuzz or the Fibonacci sequence, but if you’re like me, and you remember and have a fond love for the classics, then maybe you’ll enjoy the Zelda Rupees Problem better.