If I want to color a stick (regarded as a line segment in one-dimensional space) to a desired coloring scheme using brush, how can I make it with the fewest steps?
Notice that, new color will just cover over the olds, and both changing paints and crowhop during brushing will be regarded as causing new steps.
For example, 2 steps are required in the case shown below: (Step 1) brush all the stick with blue and then (Step 2) brush the middle with red.
and there are some other examples:
How can I figure out the minimum step for any given desired coloring scheme, and find a coloring strategy?
Thanks in advance for your help.
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.