Sometimes a problem pounces upon your brain...

Sometimes a mathematics / computer science problem pounces upon your brain, and takes possession of it for half the day -- at least until you figure out that its general case does have a solution. Then you finally escape its clutches, feeling that you haven't accomplished much; but you've brushed off some dust of that old math/CS knowledge that sometimes gets asked at software development job interviews. So it's not all a waste.

The problem was posted on Facebook by a friend who encountered it in his engineering work.

Suppose you have tasks A, B, and C. Task A occurs n_A times in a given time period, task B occurs n_B times, and task C occurs n_C times. Let's say n_A is 7, n_B is 2, and n_C is 1. The time between any two tasks is the same. Let's call it a unit time interval. These tasks repeat endlessly in a loop. The problem is to arrange the tasks in such a way that the number of time intervals between any two tasks of the same type will be minimized.

It may seem simple, but... it's not.

Ideally, any two A-tasks will be separated by at most ceil((nA + nB + nC) / nA) intervals, any two B-tasks are separated by at most ceil((nA + nB + nC) / nB), and any two C-tasks are separated by at most ceil((nA + nB + nC) / nC) intervals, where ceil() is ceiling, a function that rounds up a number to the nearest integer larger than it.

I came up with an example (or a counterexample, if you will) where it is impossible to find a schedule that satisfies those constraints.

Say task A occurs 19 times in a given time period, task B 13 times, and task C 3 times. Then nA + nB + nC = 35. ceil(35/19) = 2, so A-tasks should be separated by no more than 2 intervals. B-tasks need to be no more than ceil(35/13) = 3 intervals apart. Now, if you put a C-task between two A-tasks, then B-constraint will be violated. Any segment A-A is surrounded by B's, i.e. it will be a subset of B-A-A-B, and those two B's are 3 intervals apart. Put a C in the middle, and B-tasks will be 4 intervals apart. That's greater than ceil(35/13) = 3. If you put a C between A and B-tasks, then A-constraint will be violated, because you'll have a sequence A-C-B, so an A following that sequence will be 3 intervals away from the first A. That's greater than ceil(35/19) = 2.

Of course, there are many combinations of frequencies for which it IS possible to find an optimal schedule, for example 19-11-5. Also, if the numbers are multiples of other numbers, this problem may have additional properties that may make it solvable. Then again, engineers usually don't care about exact solutions, rather than "good enough" approximate solutions. If you require that the number of intervals between two tasks of the same type exceed the optimal only a certain percentage of times, the problem becomes complex enough to be a fodder for master's thesis. I wouldn't be surprised if it has been already solved in the academic literature. I just don't know of a good enough way to search for papers or theses that may have been published on this topic.

Further thoughts: you could map this problem to a graph theory problem. Each task can be a node in a graph, and you would need to find a shortest route for visiting all the nodes -- "shortest" as determined by the costs required to visit each node. This would be the traveling salesman problem, which is NP-complete. But this proves nothing, because this particular problem might map to a special instance of traveling salesman problem that's solvable in polynomial time.

My drafts are a continuum

I don't know if I finished the first draft of my novel. At the beginning of last year I said I was going to, but I don't know. That's because I'm no longer sure what should count as a first draft. The zeroth draft was clear. I had a beginning and an ending, but the middle lacked some chunks. Now all the parts are in place, and in the right order. Finding the right order was nontrivial. Maybe normal writers write a story in a linear fashion, as it develops in time, but that's not me. I write chunks and scenes, and wrack my brain about how to make them fit together. Which one should come before another one? The story can be told in any of the million ways.

I can't help but see stories from a software engineering perspective, not something that develops in time, but as a modular structure that occupies (mental) space. The logical way the modules fit together may not necessarily be the temporal way.

I finally worked out the order in which to string the scenes together. But I also determined I need more scenes with certain characters, because they are more instrumental to the story than I thought before. So can I really say I have Draft 1, or is still Draft 0.5? Or perhaps novel drafts should not be versioned like software releases?

I also have several short (or "short") stories I am working on, all but the newest one completed, and in various states of rewriting. One of them underwent five rewrites -- five completely different variations on the same theme with the same characters, converging on the same finale -- and this is still not the end. I need to figure out how to make the final version shorter. Might I be overthinking this just a tad?

That's the state of my writing for 2011. As far as my programming goes (and I can only speak of spare time projects, not anything I do at work), I'll spare the gentle reader an account of all false starts and stops on my coding endeavors throughout the year. It suffices to say that for the last month I've been trying to get an application I wrote to work on a Windows-hosted website. It is supposed to automate certain tasks on which I spend a lot of time, so it is important to me. To make a long story short, I found out that there are certain incompatibilities between the development environment on my laptop, and my Windows website environment, that can make it impossible to host that application. There are a couple of ways to deal with this, and I don't know which is more viable. It can also be said that when it comes to web hosting, I have champagne tastes on beer budget.