Monomorphic

The Gregorian calendar has been in use since 1582. Among its features is a moderately complicated rule for leap years: if n mod 4 is 0, then n is a leap year. However, if n mod 100 is 0, then n is not a leap year, unless n is a multiple of 400.

In addition, we live in a world with timezones and regional differences in when countries go on and off daylight savings time, if they have such a system. As yet another example of Japanese rationality, Japan does not have a DST system.

Implementing date and time computations correctly can be very hard for computer programmers and is invariably a source of many hidden bugs that may take a long time to discover. Yesterday, a large amount of Sony’s Playstation 3 game consoles stopped working normally.  This was later fixed. There was speculation the error was due to incorrect leap year handling. It wouldn’t be the first time this occurred if this was indeed the reason.

In a software company where I used to work, there would usually be massive troubles every time some country went on or off daylight savings time, or any other time calculation hit a sensitive spot. I’m fairly sure that the world’s software systems, including government, finance, insurance, health care, suffer untold billions of damage every year due to the complexity of the system. Maybe we should simplify it.

I suggest having “years” with 365 x 4 + 1 = 1461 days instead of the usual year for starters. This would move the leap year problem ahead until year 2100, when the next special rule comes in. By that time, software engineering technology should have improved enough that this should no longer be an issue, I hope. If not, we can invent another system by then. Let’s also scrap all daylight savings time everywhere. It’s easy to do and the savings would be huge.

Flood-it, a color filling game. This version was made by Lab Pixies for the iPhone, but many others exist.

There’s a veritable torrent of little games constantly being released for the iPhone. One of the more likable ones is Flood-It, which I’ve been playing recently. The premise is extremely simple: you start off with a grid divided into squares of different, randomized colors. You are given a tool that works a bit like the bucket fill in a picture editor. At each turn, the player chooses a color to fill the grid with, starting from the upper left corner. The monochromatic area slowly grows, and the aim is to fill the entire grid with a single color within a limited number of turns.

A recent analysis showed that finding an optimal solution to games like Flood-It is a NP-hard problem. In addition, deciding whether the game can be solved in n steps for some n is NP-complete. The analysis relies on a reduction of Flood-It to an instance of the SCS problem (shortest common superstring). (It’s important to note that what is NP-complete is deciding whether a particular board can be solved in a certain number of steps, not solving the game with a bounded number of steps. This can be done in polynomial time.) For those who need a summary, ACM Communications had an excellent review of the state of the P/NP problem in September last year.

For a NP-hard problem H, there exists a polynomial time reduction of any problem in NP to H, meaning that if we can solve H in P-time, we can solve any problem in NP in P-time. Many optimization problems in society rely on approximate solutions to difficult problems: routing traffic, assembling DNA sequences from partial subsequences, mathematical theorem proving… On the hypothesis that evolution has turned people into efficient solvers of hard problems (i.e. we have good heuristics in our brains from birth and from experience), we ought to pay people to play these games on their phones, but map real problems into game instances, so that people effectively work while they’re playing. We ought to design games that act as front-ends for real combinatorial problems.

A computer game, as we understand it, can be defined as a very smooth learning curve, and if we only “play” very tricky instances of combinatorial problems, the game would probably present too much of a barrier to new players. So maybe the best way of executing this kind of scheme would be that a majority of all game instances do not represent real problems, but mere training or verification of already solved problems — but every once in a while, a real problem pops up. The player should still get paid though.

A double benefit would be blurring the line between work time and  play time, what is useful and what is useless — I think this line is often artificially constructed. Has technology ever before given us the possibility to literally turn work into play?

Acknowledgements. I am indebted to Christian Sommer for showing me the complexity analysis of Flood-it.

The Flood-It game, easy difficulty setting, with the player having made some progress.