I have a sequence of characters xxxxxx
(with xk
and k > 0
)
My goal is to transform this sentence into a dutch flag, that is to say :
xxx -> RWB
xxxx -> RWBB
xxxxx -> RWWBB
xxxxxx -> RRWWBB
with R <= W <= B
All solutions that I have found, have a very high complexity.
What is an efficient approach to build a Turing machine using only one tape and one head/cursor?
How about dividing the task into subtasks like:
EDIT:
Here's another approach: you say you've seen algorithms that start with the colors present (out of order). So all you really need is a way to put the colors in (out of order)...