Solitaire Meets Number Theory

First off, when I say solitaire, I don't mean the game that everyone calls "Solitaire". That's Klondike. Solitaire refers to any card game that can be played by just one person. The solitaire game I'll be talking about here is called Pyramid. The rules are pretty simple: first, you lay out cards in a pyramid of 7 rows (first 1 card, then 2, then 3, etc). The goal is to remove all the cards from the pyramid, and you can only remove cards in pairs that add up to 13 (where A = 1, J = 11, Q = 12, and K = 13). So, for example, you can remove an A and a Q, 6 and 7, 5 and 8, or a K by itself. You can also only remove cards that aren't covered by other cards. You can see in the image how each card is covered directly by two others, plus a bunch more farther below

If you get stuck, you can draw cards one at a time from the rest of the deck, called the Stack. So, that's all well and good, but what on earth does math have to do with this? Read on, dear reader.



Since I'm not in a CS class right now, I figured I needed some sort of project so I didn't get rusty at coding, so I decided to work up an implementation of Pyramid. It's nowhere near done yet, but I ran into an interesting problem today. First, for those of you who aren't exactly CS majors, the most you need to know about programming is that a simple list of numbers is the most basic way to store data possible. Makes sense, right? But this is a pyramid, how do I make it into a list? Simple, I just store the cards in order, top to bottom and left to right. So, based on the picture above, the list would be (2, J, 9, K, 3, J, 4, 7, 7, J, etc).

Now, as I started programming the game, I discovered that I needed a quick way to tell whether any given card in the list was covered or not, and to do that, I needed to be able to know what level of the pyramid that card was on. That's not a simple task. You might be able to see the pattern when the list is small, but what if the list is bigger - would you be able to tell quickly where, say, the 47th card in the list is? Me neither. So, I needed a more algorithmic way of doing it, i.e. an efficient procedure, rather than just counting. What if we don't worry about specific cards, and instead think just about the place in the list (in computer science, you start counting at 0, so the first list element is the "0th" element. Don't worry about it too much). So, now our pyramid looks like this.
                 0
              1    2
           3    4    5
        6    7    8    9
    10  11  12  13  14

And so on. Now, for the mathematicians in the audience, do you recognize the numbers along the left edge? If they kept going, you'd get 15, 21, 28, 36, and so on. These are known as the triangular numbers, because they arise from the same triangle pattern I just made. Alright, so what good is that? Basically, the most challenging part of finding whether a card from my list is covered is finding out what level of the list it's on. Luckily for me, there was a neat little formula on the Wikipedia page for triangular numbers:

Alright, so what does this mean? If x is a triangular number, then finding n will tell you which triangular number it is. So, for x = 10, n = (-1+sqrt(81))/2 = (-1+9)/2 = 8/2 = 4, which means that 10 is triangular number #4, which agrees with the triangle above (remember, we start counting at 0). But then, what good does this formula do us if x isn't triangular? Remember, most of the time I want to know what level some arbitrary number is on. It turns out that this equation is well-behaved enough that if x is between triangular numbers n and n+1, then the result of the equation is also between n and n+1. So, let's look at an example: 13. Plugging it in, you get n = (-1+sqrt(105))/2 = 4.6. So, 13 is between levels 4 and 5, i.e. it's on level 4, which is true! Hooray!

Of course, I've glossed over some minor details, and just knowing which level a card is on doesn't answer the question of whether it's covered or not, but this math was the central difficulty behind this task. So there you have it: a type of number known to the Ancient Greeks being used to solve a distinctly 21st century problem. This is why I enjoy programming.