The first two weeks of february: boring.

At work I write code for a translator between two exotic languages. (working on translators seems to be interesting when the languages involved are themselves interesting; these ones are not: they are big and clunky) I have just finished migrating the code to smart pointers. You can't imagine how boring it can be! The good points are:

• Now I have an acceptable grasp of who owns who.
• Three lurking bugs where found because of the use of smart pointers.

In order to keep my sanity I had to do something different. And since I haven't had enough time to work on an article (Vali will kill me) I took some breaks while at work to think about interesting problems. One of them camed from the OCaml mailing list from the author of the Felix programming language. After some discussion we found a solution. The final answer was given by Pascal Zimmer but I did had a good contribution. Anyway, let's move on to the problem. You are given a set of assignments that should be performed in parallel. The variables involved are taken from the set X={xi with i=0,N-1} and the assignments have the form: xi = f(Xi), Xi included in X The problem is to output a list of as few as possible sequential assignments that have the same effect. You can use temporaries. For example an instance of the problem is:

x = y
y = x

with solution

t <- x
x <- y
y <- t

Another instance is:

a = b+c
b = c
c = a+b

with solution:

t <- c
c <- a+b
a <- b+t
b <- t

It is easy to see that the number of necessary sequential assignments is at most twice the number of parallel assignments but... finding the minimum turns out to be an NP problem. Since I don't want to spoil it for you I'll write the solution in a few days.