TopCoder games

Consider the following problems (from topcoder):

• Partition an integer multiset in as few parts as possible such that the sum of each part is at most 20. The multiset has at most 10 elements, each between 1 and 10 (inclusive).
• How many maximal cliques are there in a graph with at most 20 nodes?
• How many integers less than N whose decimal representation does not contain three consecutive equal digits are there?
• Two players play with two custom dice: they have six faces but the values are integers between 1 and 100 inclusive. The first player throws his dice A times, and the second player throws his dice B times (1 <= A, B <= 200). The one with the greatest sum wins. Given A, B and the numbers written on dice faces find the win probabilities.

What do they have in common?

Each can be solved using multiple alternative strategies. But what struck me recently is the fact that all can be solved mechanically by viewing them as games. I knew that before. I was amazed, however, how long it took me to recognize that a large portion of topcoder problems are game problems.

How do you solve a game problem mechanically?

You begin by identifying state and legal moves. Then you assign values to states and decide how to compute the value of a state from the values of subsequent states, i.e. you decide how to combine values. And you're done. All you need is a recursive function that takes a state and outputs the value.

Not really. Sometimes speed is good. To that purpose you memoize the function (remember chess programs' "hash tables"?). Also you may need to exploit symmetries by normalizing the state representation; if you do this it should be the first thing to do in your function, before even checking the cache. Another way to speed things is to avoid some calls completely; this can be done for certain modes of combining values and some classic ways are branch-and-bound and alpha-beta prunning. But this later type of optimizations are seldom possible/needed in topcoder problems.

Now try to do that for the problems above.

Progress

A while back I quoted an advice of Floyd on how to improve as a programmer. Now it's time for Knuth's advice.

[...] we should make use of the idea of limited resources in our education. We can all benefit by doing occasional "toy" programs, when artificial restrictions are set up, so that we are forced to push our abilities to the limit. We shouldn't live in the lap of luxury all the time, since that tends to make us lethargic. The art of tackling miniproblems with all our energy will sharpen our talents for the real problems, and the experience will help us get more pleasure from our accomplishments on less restricted equipment.

Now, that sounds like a good reason to learn Haskell :). (That's half a joke, but half it ain't). Lest you think that Knuth wants you to spend all your time solving miniproblems:

[...] I especially enjoy writing programs which do the greatest good, in some sense. There are many senses in which a program can be "good", of course. In the first place, it's especially good to have a program that works correctly. Secondly it is often good to have a program that won't be hard to change, when the time for adaptation arises. Both of these goals are achieved when the program is easily readable and understandable to a person who knows the appropriate language. Another important way for a production program to be good is for it to intereact gracefully with its users. [...] Another important aspect of program quality is the efficiency with which the computer's resources are actually being used. I am sorry to say that many people nowadays [1974] are condemning program efficiency, telling us that it is in bad taste. [...] premature optimization is the root of all evil (or at least most of it) in programming.