Android App!

• 14 April 2011

After a couple false starts, I've finally gotten around to making an Android application! I've had read through the documentation a couple times before, but never actually got around to doing it. The reason it worked out so well this time was mostly because it was a great bite-sized, interesting project with some guaranteed users (Alex and his friends).

First, some background. Alex and his friends like to play a card game called "Red 10s". I had never heard of this game before meeting them, but it reminds me of a game that we always used to play called "Presidents". "Red 10s" is a 4 player game in which to object is to get rid of all the cards in your hand before everyone on the other team. The interesting thing about the teams is that they aren't always known to the players during the game. Any players with a red 10 in their hand are on one team and the rest are playing against them. This makes for some interesting strategy as you try to figure out who you should be playing with and who you should be trying to screw over.

This game is usually played for money, with the the losers paying the winners some bet (usually starting at $0.10) for each card they have left in their hands. To make things more interesting, the bet can be increased in a few ways:

If someone has both red 10s (so it is 3-on-1), the bet is doubled. In this case the other players don't even know they are playing for double until the round is over.

If the one with two red 10s reveals that he has them, the bet is doubled again (so you are playing for 4 times the bet that round).

If the game ends in a tie, the starting bet is increased by $0.10 for the next round. This keeps increasing until one team or the other wins (the bet can get pretty out of hand in some cases, especially if someone shows red 10s later on). A tie game happens when the teams are 2-on-2 and the finish order is something like: Player A (Team 1), Player B (Team 2), Player C (Team 1), Player D (Team 2).

Because you are always paying different people, the easiest way to keep track of debts is with a 4x4 grid. However, the payouts at the end get very confusing and complicated if you were to just pay the values on the grid. You can almost always simplify the payment a bit so that there are as few payments as possible (see below). This isn't terribly difficult to do, but it is a bit of a pain and somewhat error-prone. This was the main reason it was decided that an Android app would be useful.

An example of a payment grid:

And the simplified table:

These tables are laid out as row owes column, so you can verify that it is correct by summing the rows and columns and comparing. For example, A owes $1 ($0.30 to B and $0.70 to C), but is owed $0.60 ($0.10 from B and $0.50 from C), so he owes a net of $0.40. This is the same as the simplified table. You'll see that this holds true for each player, even though they may be paying it out to different people than they originally owed.

I found the simplest way to approach this problem was to treat the table as a graph, with each player as a node and each debt as a directed edge (an edge from A to B means A owes B). The graph for the example above looks like:

Once we are looking at the problem like this, we can see that the easiest way to simplify the graph is to find money that "flows through" intermediate nodes and send it straight to the destination instead. For example, we might notice that B owes C $1.60, and C owes D $0.40, and simplify this to say that B owes D $0.40 more (so $1.30) and B now only owes C $1.20. It we keep doing these simplifications, we will end up with a graph in which no node has both incoming edges and outgoing edges, which will be as simple as possible.

and eventually...

While this is a relatively simple graph problem, I still found it interesting and fun to implement.

The app is fairly simple, but it works well. The main screen features a large grid of buttons that when pressed increment the debt for that space. There are buttons to increase the base bet and double the bet, but my favorite feature was the undo system. Undo systems are a standard feature in just about everything nowadays, but I had never implemented one before. It was an interesting challenge and I was pretty happy with my implementation in the end. Here's some shots of the app in action:

The Android intent system makes it very easy send data to other applications to do things with. For example, clicking the "Send" button here will open up a chooser that you can use to send the results to any application that can send data (like the Messaging app, or a mail app, or anything really). Really useful for sending the results out to everyone.

If you want to give the app a shot, you can download the most recent version here.

• Previous: Voting
• Next: The Great Update of 2011