CODEWITHSUNDEEP
algorithmcomplexity-theoryturing-machines
g123k
g123k

Reputation: 3874

Dutch national flag on a Turing Machine

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?

Upvotes: 1

Views: 594

Answers (1)

Beta
Beta

Reputation: 99174

How about dividing the task into subtasks like:

  1. Change the last X to B.
  2. Change the last X to W.
  3. Change the first X to R.
  4. Change BW to WB.

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)...

Upvotes: 1

Related Questions