Dutch national flag problem

The Dutch national flag is composed of three coloured bands in the order red then white and lastly blue. 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 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, ...

This task is to

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.

Cf.

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

J

We shall define a routine to convert the values 0 1 2 to ball names:

<lang J>i2b=: {&(;:'red white blue')</lang>

and its inverse

Next, we need a random assortment of balls:

<lang J> BALLS=: i2b ?20#3

  BALLS

┌────┬───┬────┬───┬───┬─────┬─────┬─────┬────┬────┬─────┬────┬────┬───┬────┬───┬─────┬───┬────┬───┐ │blue│red│blue│red│red│white│white│white│blue│blue│white│blue│blue│red│blue│red│white│red│blue│red│ └────┴───┴────┴───┴───┴─────┴─────┴─────┴────┴────┴─────┴────┴────┴───┴────┴───┴─────┴───┴────┴───┘</lang>

And we want to sort them in their canonical order:

<lang J> /:~&.b2i BALLS ┌───┬───┬───┬───┬───┬───┬───┬─────┬─────┬─────┬─────┬─────┬────┬────┬────┬────┬────┬────┬────┬────┐ │red│red│red│red│red│red│red│white│white│white│white│white│blue│blue│blue│blue│blue│blue│blue│blue│ └───┴───┴───┴───┴───┴───┴───┴─────┴─────┴─────┴─────┴─────┴────┴────┴────┴────┴────┴────┴────┴────┘</lang>

Note that if we were not using J's built in sort, we would probably want to use bin sort here.

Anyways, we can test that they are indeed sorted properly:

<lang J> assert@(-: /:~)&b2i /:~&.b2i BALLS</lang>

Python

Python: Sorted

The heart of the idiomatic Dutch sort in python is the call to function sorted in function dutch_flag_sort. <lang python>import random

colours_in_order = 'Red White Blue'.split()

def dutch_flag_sort(items, order=colours_in_order):

   'return sort of items using the given order'
   return sorted(items, key=lambda x: order.index(x))

def dutch_flag_check(items, order=colours_in_order):

   'Return True if each item of items is in the given order'
   order_of_items = [order.index(item) for item in items]
   return all(x <= y for x, y in zip(order_of_items, order_of_items[1:]))

def random_balls(mx=5):

   'Select from 1 to mx balls of each colour, randomly'
   balls = sum(([[colour] * random.randint(1, mx)
                for colour in colours_in_order]), [])
   random.shuffle(balls)
   return balls

def main():

   # Ensure we start unsorted
   while 1:
       balls = random_balls()
       if not dutch_flag_check(balls):
           break
   print("Original Ball order:", balls)
   sorted_balls = dutch_flag_sort(balls)
   print("Sorted Ball Order:", sorted_balls)
   assert dutch_flag_check(sorted_balls), 'Whoops. Not sorted!'

if __name__ == '__main__':

   main()</lang>

Sample output;

Original Ball order: ['Red', 'Red', 'Blue', 'Blue', 'Blue', 'Red', 'Red', 'Red', 'White', 'Blue']
Sorted Ball Order: ['Red', 'Red', 'Red', 'Red', 'Red', 'White', 'Blue', 'Blue', 'Blue', 'Blue']

Python: sum of filters

This follows the critics section of the wikipedia article by using a sum of filters.

Replace the function/function call dutch_flag_sort above, with dutch_flag_sort2 defined as: <lang python>def dutch_flag_sort2(items, order=colours_in_order):

   'return summed filter of items using the given order'
   return sum([list(filter(lambda c: c==colour, items))
               for colour in order], [])</lang>

Output follows that of the sorting solution above.

Python: Construct from ball counts

This reconstructs the correct output by counting how many of each colour their are.

Replace the function/function call dutch_flag_sort above, with dutch_flag_sort3 defined as: <lang python>def dutch_flag_sort2(items, order=colours_in_order):

   'counts each colour to construct flag'
   return sum([[colour] * items.count(colour) for colour in order], [])</lang>

Output follows that of the sorting solution above.

Tcl

This isn't very efficient in terms of the sorting itself (and it happens to use lsearch twice in the comparator!) but it is very simple to write like this. <lang tcl># The comparison function proc dutchflagcompare {a b} {

   set colors {red white blue}
   return [expr {[lsearch $colors $a] - [lsearch $colors $b]}]

}

The test function (evil shimmer of list to string!)

proc isFlagSorted lst {

   expr {![regexp {blue.*(white|red)} $lst] && ![regexp {white.*red} $lst]}

}

A ball generator

proc generateBalls n {

   for {set i 0} {$i<$n} {incr i} {

lappend result [lindex {red white blue} [expr {int(rand()*3)}]]

   }
   return $result

}

Do the challenge with 20 balls

set balls [generateBalls 20] if {[isFlagSorted $balls]} {

   error "already a sorted flag"

} set sorted [lsort -command dutchflagcompare $balls] if {[isFlagSorted $sorted]} {

   puts "Sorted the flag\n$sorted"

} else {

   puts "sort failed\n$sorted"

}</lang>

Output:

Sorted the flag
red red red red red red red white white white white white white white white white blue blue blue blue