Keeping Tabs
by Tom Temple
17 June 2009
At work we’ve got a snack room and there is a tab on the wall. Attached to it is a pen rather than a pencil as you would expect in a perfect world… Anyway, I’m struck by how inefficiently most people use the space in it, forcing it to be pages and pages long.
All the prices are divisible by five and go from 5c up to $1 with 45, 55, 65, and 95cents all absent. Come up with a scheme for keeping track of the cumulative sum of transactions that doesn’t use a lot of space.
Benchmark: You’ve got enough room for about 80 characters, so you should be able to get at least 160 items before starting another page.
Hard version: You maintain a fixed number strings of {0,1}*. After each transaction (containing potentially multiple items) you may add as many characters to whatever strings you’d like. From these strings you need to be able to construct the sum of the transactions.
You can assume each transaction comes from a finite set with a known probability distribution. Come up with a scheme that minimizes the expected bits per transaction. You’re welcome to make limiting case arguments, but winners are going to be picked at 640 bits.
Jun 23, 12:22 PM
This isn’t the solution but here’s what I actually do: First, I cheat. I have a nickle and a dime hidden in the room, the location of which tell me my balance mod 20.
Given that, I have three tallies t_20, t_40 and t_80. Each consist of strings of {/\X}*. This character set has the nice property that I can retroactively turn either slash into an “X”.
Lets define two functions Strokes(character)=
{(/,1),(\,1),(X,2)} and Value(character)={(/,1),(X,0),(\,-1)}.
Now I overload Strokes(string) and Value(string) as the sums of the character functions over the characters in the string.
Finally, the way I read my balance is
(Strokes(t20)+Strokes(t40)+Value(t80))*80 + Value(t20)*20+Value(t40)*40
Efficiency:
Making 20 takes three strokes, 40,60 take one, and everything else takes floor(price/80) strokes. For me, all of my transactions are in the 1 stroke region.
I could comfortably fit about 320 of these things into the space provided. I could add underline and overline, etc, for higher density, but I’m only working here for 12 weeks.