Dutch national flag problem
You are encouraged to solve this task according to the task description, using any language you may know.
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)
D
<lang d>import std.stdio, std.random, std.algorithm, std.traits, std.range;
enum DutchColors : ubyte { red, white, blue }
void dutchFlagSort(DutchColors[] items) pure nothrow {
if (items.length < 1) return;
int lo, mid, hi = items.length - 1;
while (mid <= hi)
final switch (items[mid]) {
case DutchColors.red:
swap(items[lo], items[mid]);
lo++;
mid++;
break;
case DutchColors.white:
mid++;
break;
case DutchColors.blue:
swap(items[mid], items[hi]);
hi--;
break;
}
}
void main() {
DutchColors[] balls;
do {
balls = iota(12)
.map!(_ => [EnumMembers!DutchColors][uniform(0, 3)])()
.array();
} while (balls.isSorted() && balls.length > 1);
writeln("Original Ball order: ", balls);
balls.dutchFlagSort();
writeln("Sorted Ball Order: ", balls);
assert(balls.isSorted(), "Balls not sorted");
}</lang>
- Output:
Original Ball order: [white, red, red, white, white, blue, white, blue, blue, white, white, blue] Sorted Ball Order: [red, red, white, white, white, white, white, white, blue, blue, blue, blue]
Go
<lang go>package main
import (
"fmt" "math/rand" "time"
)
// constants define order of colors in Dutch national flag const (
red = iota white blue nColors
)
// zero object of type is valid red ball. type ball struct {
color int
}
// order of balls based on DNF func (b1 ball) lt(b2 ball) bool {
return b1.color < b2.color
}
// type for arbitrary ordering of balls type ordering []ball
// predicate tells if balls are ordered by DNF func (o ordering) ordered() bool {
var b0 ball
for _, b := range o {
if b.lt(b0) {
return false
}
b0 = b
}
return true
}
func init() {
rand.Seed(time.Now().Unix())
}
// constructor returns new ordering of balls which is randomized but // guaranteed to be not in DNF order. function panics for n < 2. func outOfOrder(n int) ordering {
if n < 2 {
panic(fmt.Sprintf("%d invalid", n))
}
r := make(ordering, n)
for {
for i, _ := range r {
r[i].color = rand.Intn(nColors)
}
if !r.ordered() {
break
}
}
return r
}
// O(n) algorithm // http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/ func (a ordering) sort3() {
lo, mid, hi := 0, 0, len(a)-1
for mid <= hi {
switch a[mid].color {
case red:
a[lo], a[mid] = a[mid], a[lo]
lo++
mid++
case white:
mid++
default:
a[mid], a[hi] = a[hi], a[mid]
hi--
}
}
}
func main() {
f := outOfOrder(12) fmt.Println(f) f.sort3() fmt.Println(f)
}</lang>
- Output:
[{1} {0} {0} {2} {1} {1} {1} {2} {2} {0} {1} {2}]
[{0} {0} {0} {1} {1} {1} {1} {1} {2} {2} {2} {2}]
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 <lang J>b2i=: i2b inv</lang> 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' reverse_index = dict((x,i) for i,x in enumerate(order)) return sorted(items, key=lambda x: reverse_index[x])
def dutch_flag_check(items, order=colours_in_order):
'Return True if each item of items is in the given order' reverse_index = dict((x,i) for i,x in enumerate(order)) order_of_items = [reverse_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 True:
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>from itertools import chain def dutch_flag_sort2(items, order=colours_in_order):
'return summed filter of items using the given order'
return list(chain.from_iterable(filter(lambda c: c==colour, items)
for colour in order))</lang>
Or equivalently using a list comprehension (though perhaps less clear): <lang python>def dutch_flag_sort2(items, order=colours_in_order):
'return summed filter of items using the given order' return [c for colour in order for c in items if c==colour]</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_sort3(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.
Python: Explicit in-place sort
<lang python>import random
colours_in_order = 'Red White Blue'.split()
def dutch_flag_sort(items):
\ In-place sort of list items using the given order. Python idiom is to return None when argument is modified in-place
O(n)? Algorithm from Go language implementation of http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
lo, mid, hi = 0, 0, len(items)-1
while mid <= hi:
colour = items[mid]
if colour == 'Red':
items[lo], items[mid] = items[mid], items[lo]
lo += 1
mid += 1
elif colour == 'White':
mid += 1
else:
items[mid], items[hi] = items[hi], items[mid]
hi -= 1
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)
dutch_flag_sort(balls)
print("Sorted Ball Order:", balls)
assert dutch_flag_check(balls), 'Whoops. Not sorted!'
if __name__ == '__main__':
main()</lang>
Output follows that of the sorting solution above.
REXX
This version uses a bin sort with counts, and has been generalized to allow any number of colors. <lang rexx>/*REXX pgm to reorder a set of random colored balls into a correct order*/ /* (the default correct order is the order of colors on the Dutch flag).*/
parse arg N colors /*get user args from command line*/ if N= then N=15 /*use default number of balls. */ if colors= then colors=space('red white blue') /*use default colors.*/ Ncolors=words(colors) /*count the number of colors. */ @=word(colors,Ncolors) word(colors,1) /*ensure balls aren't in order. */
do g=3 to N /*generate a random # of balls. */
@=@ word(colors,random(1,Ncolors))
end /*g*/
say 'number of colored balls generated = ' N ; say say 'original ball order:' say @ ; say $=
do j=1 for Ncolors
_=word(colors,j)
$=$ copies(_' ',countWords(_,@))
end
say ' sorted ball order:' say space($); say
do j=2 to N /*ensure sorted balls are in order*/ if wordpos(word($,j),colors)>=wordpos(word($,j-1),colors) then iterate say "The list of sorted balls isn't in proper order!"; exit 13 end
say ' sorted ball list has been confirmed as being sorted correctly.' exit /*──────────────────────────────────COUNTWORDS subroutine───────────────*/ countWords: procedure; parse arg ?,hay; s=1
do r=0 until _==0; _=wordpos(?,hay,s); s=_+1; end; return r</lang>
- Output:
number of colored balls generated = 15 original ball order: blue red white white white white red blue white red blue red blue white red sorted ball order: red red red red red white white white white white white blue blue blue blue sorted ball list has been confirmed as being sorted correctly.
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