
The Dutch national flag is composed of three coloured bands in the order:

   red     (top)
   then white,   and
   lastly blue   (at the bottom). 


The problem posed by Edsger Dijkstra is:

Given a number of red, blue and white balls in random order, arrange them in the order of the colours in the Dutch national flag.
When the problem was first posed, Dijkstra then went on to successively refine a solution, minimising the number of swaps and the number of times the colour of a ball needed to determined and restricting the balls to end in an array, ...



Task
 Generate a randomized order of balls ensuring that they are not in the order of the Dutch national flag.
 Sort the balls in a way idiomatic to your language.
 Check the sorted balls are in the order of the Dutch national flag.


C.f.

 Dutch national flag problem
 Probabilistic analysis of algorithms for the Dutch national flag problem by Wei-Mei Chen. (pdf)


; We'll just use words for the balls
make "colors {red white blue}
 
; to get a mapping from colors back to a numeric value,
; we make variables out of the color names (e.g. the variable
; "red" has value "1").
foreach arraytolist :colors [
  make ? #
]
 
; Make a random list of a given size
to random_balls :n
  local "balls
  make "balls array n
  repeat n [
    setitem # :balls pick :colors
  ]
  output :balls
end
 
; Test for Dutchness
to dutch? :array
   output dutchlist? arraytolist :array
end
 
; List is easier than array to test
to dutchlist? :list
  output cond [
    [(less? count :list 2) "true]
    [(greater? thing first :list thing item 2 :list) "false ]
    [else dutchlist? butfirst :list]
  ]
end
 
; But array is better for sorting algorithm
to dutch :array
  local "lo
  make "lo 0
  local "hi
  make "hi sum 1 count :array
  local "i
  make "i 1
  while [:i < :hi] [
    case (item :i :array) [
      [[red]
         make "lo sum :lo 1
         swap :array :lo :i
         make "i sum :i 1
      ]
      [[white]
         make "i sum :i 1
      ]
      [[blue]
         make "hi difference :hi 1
         swap :array :hi :i
      ]
    ]
  ]
  output :array
end
 
; utility routine to swap array elements
to swap :array :a :b
  local "temp
  make "temp item :a :array
  setitem :a :array item :b :array
  setitem :b :array :temp
end