Information currency
Computing with coins, gems, and crowns
If you recall from last post, the victorious hero received a large treasure chest. In it are gems, jewels, and coins which the hero must now count and organize. Don’t worry — this won’t be a lecture on accounting. This is a thinly disguised metaphor for understanding an important concept in computer science.
Let us say our nameless hero holds in their hands three pennies (3P) and two quarters (2Q). How should they calculate the total value? The answer may seem obvious but think very precisely and explicitly how the hero should do it. You can’t just add 3P and 2Q directly to get 5P+Q or something silly like that. Each value must be converted into cents individually and then the cents must be added up. Since a penny and a cent are the same thing, 3P is trivially converted into three cents (3C). A quarter is equal to twenty-five cents, so two quarters converts to fifty cents (50C). Add the two amounts up to get the total: 3C + 50C = 53C
Again, you may find it pretty obvious, but we’ve taken this simple case and used it to derive rules about how to add together any coins, even ones that aren’t intuitively easy to add together. Let’s use this idea in a more complex situation. Now the hero has a new set of coins, three in total: five three-cent silvers (5S), four nickels (4N), and thirteen half-cents (13H). If you’re curious, three-cent silvers and half-cents are archaic, obsolete U.S. coins. This one is harder to do mentally, so let’s write each step down:
- 5S = 5 * 3C = 15C (five three-cent silvers equals five coins worth three cents each, totaling fifteen cents)
- 4N = 4 * 5C = 20C (four nickels equals four coins worth five cents each, totaling twenty cents)
- 13H = 13 * 0.5C = 6.5C (thirteen half-cents equals thirteen coins worth half of a cent each, totaling six and a half cents)
- 15C + 20C + 6.5C = 41.5C (fifteen cents plus twenty cents plus six and a half cents equals forty-one and a half cents)
Note how the equations and the sentences look different but say equivalent information; they are different representations of the same concept. You could call the process centifying: it turns a collection of various types of coins into their equivalent in cents. So, centify 5S, 4N, 13H produces 41.5C, just like it did above. You could even add this word to the hero’s vocabulary to make it more intuitive. “Hero, centify these coins.”
The hero also found gems and jewels, including a crown. The crown has several slots for gems but unlike in George XII of Georgia’s crown shown above, none of this crown’s slots are filled. You could say the five slots look like this:
_ _ _ _ _
Then the hero inserts two amethysts (A) symmetrically:
_ A _ A _
Then two rubies (R):
R A _ A R
And finally, a diamond (D) in the center:
R A D A R
What a nice palindrome of jewels for the crown. So nice, in fact, that you present it to the local warlord as a sign of fealty. Unfortunately the warlord turns out to have very particular aesthetic tastes and won’t take the crown in its current state. He very much likes the gems embedded in the crown but has his own crown, a family heirloom, that he wants to move to gems to. The warlord’s crown looks like this:
S _ _ _ _ _ S
S stands for sapphire. How should the hero move the gems to the new crown? The end result should certainly look like this:
S R A D A R S
But how do we tell the hero? As with adventuring, the hero has a limited vocabulary when it comes to arranging gems. Specifically, they can accept only two instructions:
- Remove gem x: the hero removes the gem in the xth spot in the hero’s crown
- Add gem to spot x: the hero adds the just removed gem to the xth spot in the warlord’s crown
A limited selection of commands, perhaps, but it is enough to do the job. There’s one catch, however. The left-most spot on both crowns is the 0th spot. So the spots on the crowns look like this:
Hero’s crown: 0 1 2 3 4
Warlord’s crown: 0 1 2 3 4 5 6
Note that even though both crowns use spots 0 to 4, the two crowns have different spots. To put it another way, spot 0 in the hero’s crown is not spot 0 in the warlord’s crown — they just share the same number because they’re in the same relative position. Spots in the warlord’s crown are marked in italics while spots in the hero’s are not. Take your time and lay out the instructions you want to give to the hero. The goal here is precision, not speed — the warlord does not easily forgive mistakes, especially those involving his family heirlooms. When you’re done, compare your answer to this one:
- Remove gem 0
- Add gem to spot 1
- Remove gem 1
- Add gem to spot 2
- Remove gem 2
- Add gem to spot 3
- Remove gem 3
- Add gem to spot 4
- Remove gem 4
- Add gem to spot 5
Every gem in the hero’s crown gets moved to the right one spot when inserted into the warlord’s crown. In other words, a gem originally in spot x moves to spot x + 1. Now that we understand how the gems move in a general way, we can use some instructions I didn’t mention the hero has:
- For all gems x, y: the hero performs y for all gems; the instruction y can use x to identify the spot of the gem
- x then y: the hero performs x then y
Let me give you an example of how this works and then I’ll explain it in more detail. You can replace all ten instructions above with just this one:
- For all gems x, Remove gem x then Add gem to spot x + 1
Let’s examine the first part, For all gems x. This instruction tells the hero to perform an action for all gems in their crown. To refer to the gem the hero is currently manipulating, you can use x. In other words, any instruction you put after this part is performed five times, once per gem. For the left-most gem, x is 0. For the next gem, x is 1. And so forth.
The next part, Remove gem x then Add gem to spot x + 1, is really two instructions disguised as one. x then y tells the hero to perform x and then perform y. This may sound silly since you could normally write the two instructions on two separate lines for the same effect. However, it is useful to allow two instructions on one line in the case of For all gems x, y, since y leaves room for only one instruction.
To explain the next part in more detail, Remove gem x removes the gem in spot x. then glues this instruction to the next one, Add gem to spot x + 1. This instruction kind of cheats since I never claimed the hero can add (as they must to compute x + 1) but let’s give them the benefit of the doubt; they did receive excellent grades at the Hero Academy. So this final instruction adds the gem previously removed from spot x in the hero’s crown and places it in spot x + 1 in the warlord’s crown. It helps to remember that spot x in the hero’s crown is not spot x in the warlord’s crown; the numbers refer to positions within a single crown, so different crowns can both have spots 0, 1, etc.
If you’re not quite sure why all of this works, try swapping x with an actual number:
- Remove gem 0 then Add gem to spot 0 + 1
0 + 1 = 1, so the gem in spot 0 moves to spot 1. Swapping x with 1, 2, 3, and 4, you can see how the rest of the gems fit into place. The nice part about using For all gems x is that it works no matter how many gems there are; the instruction can tell the hero how to move a million gems into the right spots, as long as the gem placement follows some pattern (like x + 1).
The conclusion is that the hero successfully transposed the gems to the warlord’s crown, thereby gaining favor within the local tribe. They’ve been promoted to the official tribal hero, a posh sinecure involving many rituals and procedures but no real danger. Will the hero return to actual adventuring or waste away into a flabby bureaucrat? Find out next time!
Image credit: penny, three-cent silver, half-cent, crown
