Dutch national flag on a Turing Machine
-
28-09-2019 - |
Question
I have a sequence of characters xxxxxx (with x^k and k > 0) My goal is to transform this sentence into a dutch flag, that is to say :
xxxxx -> RRWWBB xxxx -> RWBB
with R <= W <= B
All solutions that I have found, have a very high complexity. Do you have any hint/clue to help to me build a Turing machine using only one tape and one head/cursor?
Solution
How about dividing the task into subtasks like:
- Change the last X to B.
- Change the last X to W.
- Change the first X to R.
- 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)...
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow