Given a desired coloring scheme for a stick, how can I brush it with the fewest steps?

Solution 1:

Define a portion to be a contiguous section of the stick with the same colour. Denote all the colours by symbols $a,b,c,...$ and the desired colouring by a string using those symbols. Let $S$ denote the starting blank stick and $A,B,C,...$ be symbols used to denote the colour of a portion of the stick, corresponding to the same colours as the lowercase symbols. Now we have the following rules:

$S \to A|B|C|...$ (It doesn't make a difference to paint the entire stick in the first step, because eventually any part unpainted in the first step will be painted over.)

$A \to AB|AC|...|BA|CA|...|ABA|ACA|...$ (We can paint the right/left/middle part of any portion, and we never have to paint across two different portions, otherwise we could have simply enlarged any of the affected portions so that one of its endpoints coincides with the new portion to be painted.)

$A \to a \\ B \to b \\ ...$ (When we are done, we finalize the colours of all portions.)

This is a context-free grammar and can be easily converted into a Chomsky normal form in such a way that the size of the resulting grammar is only a constant factor times that of this grammar. Then we can run the CYK algorithm, which is essentially just a recurrence relation that is based on the fact that each non-terminating step in a Chomsky normal form produces exactly two parts each of which will finally terminate in a non-empty string, and so for any string we can recursively test all possible ways it can be formed because it must be split up into 2 non-empty strings, which can be written as a bottom-up DP algorithm. It is easy to maintain the minimum number of steps needed to get to each substring in the CYK algorithm, and thus we obtain the minimum number of steps needed for the whole string, and as with all DP algorithms we can run a separate back-tracking to recover an optimal (but not necessarily unique) choice at each step.

Of course, it should become clear that we could do the DP directly on the original problem without translating it into a context-free grammar, but sometimes it can be convenient to be able to translate a lot of this kind of problems into the same form.