Dutch national flag problem: Difference between revisions
Line 1,019: | Line 1,019: | ||
def dutch? |
def dutch? |
||
return true if length < 2 |
return true if length < 2 |
||
Values[self[0]] < Values[self[1]] && slice( |
Values[self[0]] < Values[self[1]] && slice(1..-1).dutch? |
||
end |
end |
||
Revision as of 02:43, 27 September 2012
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)
Ada
<lang Ada>with Ada.Text_IO, Ada.Numerics.Discrete_Random, Ada.Command_Line;
procedure Dutch_National_Flag is
type Colour_Type is (Red, White, Blue);
Number: Positive range 2 .. Positive'Last := Positive'Value(Ada.Command_Line.Argument(1)); -- no sorting if the Number of balls is less than 2
type Balls is array(1 .. Number) of Colour_Type;
function Is_Sorted(B: Balls) return Boolean is -- checks if balls are in order begin for I in Balls'First .. Balls'Last-1 loop if B(I) > B(I+1) then return False; end if; end loop; return True; end Is_Sorted;
function Random_Balls return Balls is -- generates an array of random balls, ensuring they are not in order package Random_Colour is new Ada.Numerics.Discrete_Random(Colour_Type); Gen: Random_Colour.Generator; B: Balls; begin Random_Colour.Reset(Gen); loop for I in Balls'Range loop B(I) := Random_Colour.Random(Gen); end loop; exit when (not Is_Sorted(B)); -- ... ensuring they are not in order end loop; return B; end Random_Balls;
procedure Print(Message: String; B: Balls) is begin Ada.Text_IO.Put(Message); for I in B'Range loop Ada.Text_IO.Put(Colour_Type'Image(B(I))); if I < B'Last then Ada.Text_IO.Put(", "); else Ada.Text_IO.New_Line; end if; end loop; end Print;
procedure Sort(Bls: in out Balls) is -- sort Bls in O(1) time
Cnt: array(Colour_Type) of Natural := (Red => 0, White => 0, Blue => 0); Col: Colour_Type;
procedure Move_Colour_To_Top(Bls: in out Balls; Colour: Colour_Type; Start: Positive; Count: Natural) is This: Positive := Start; Tmp: Colour_Type; begin for N in Start .. Start+Count-1 loop while Bls(This) /= Colour loop This := This + 1; end loop; -- This is the first index >= N with B(This) = Colour Tmp := Bls(N); Bls(N) := Bls(This); Bls(This) := Tmp; -- swap This := This + 1; end loop; end Move_Colour_To_Top;
begin for Ball in Balls'Range loop -- count how often each colour is found Col := Bls(Ball); Cnt(Col) := Cnt(Col) + 1; end loop; Move_Colour_To_Top(Bls, Red, Start => 1, Count => Cnt(Red)); Move_Colour_To_Top(Bls, White, Start => 1+Cnt(Red), Count => Cnt(White)); -- all the remaining balls are blue end Sort;
A: Balls := Random_Balls;
begin
Print("Original Order: ", A);
pragma Assert(not Is_Sorted(A)); -- Check if A is unsorted
Sort(A); -- A = ((Red**Cnt(Red)= & (White**Cnt(White)) & (Blue**Cnt(Blue)))
pragma Assert(Is_Sorted(A)); -- Check if A is actually sorted
Print("After Sorting: ", A);
end Dutch_National_Flag;</lang>
- Output:
>./dutch_national_flag 5 Original Order: RED, RED, BLUE, RED, BLUE After Sorting: RED, RED, RED, BLUE, BLUE >./dutch_national_flag 5 Original Order: BLUE, RED, RED, WHITE, RED After Sorting: RED, RED, RED, WHITE, BLUE >./dutch_national_flag 7 Original Order: WHITE, WHITE, BLUE, WHITE, BLUE, BLUE, WHITE After Sorting: WHITE, WHITE, WHITE, WHITE, BLUE, BLUE, BLUE
C++
<lang cpp>#include <algorithm>
- include <iostream>
// Dutch national flag problem template <typename BidIt, typename T> void dnf_partition(BidIt first, BidIt last, const T& low, const T& high) {
for (BidIt next = first; next != last; ) { if (*next < low) { std::iter_swap(first++, next++); } else if (!(*next < high)) { std::iter_swap(next, --last); } else { ++next; } }
}
enum Colors { RED, WHITE, BLUE };
void print(const Colors *balls, size_t size) {
static const char *label[] = { "red", "white", "blue" };
std::cout << "Balls:"; for (size_t i = 0; i < size; ++i) { std::cout << ' ' << label[balls[i]]; } std::cout << "\nSorted: " << std::boolalpha << std::is_sorted(balls, balls + size) << '\n';
}
int main() {
Colors balls[] = { RED, WHITE, BLUE, RED, WHITE, BLUE, RED, WHITE, BLUE };
std::random_shuffle(balls, balls + 9); print(balls, 9);
dnf_partition(balls, balls + 9, WHITE, BLUE); print(balls, 9);
}</lang>
- Output:
Balls: blue white red blue red blue white red white Sorted: false Balls: red red red white white white blue blue blue Sorted: true
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[12] balls; auto colors = [EnumMembers!DutchColors]; do { foreach (i; 0 .. balls.length) balls[i] = colors[uniform(0, $)]; } while (balls[].isSorted());
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]
Erlang
<lang erlang>-module(dutch). -export([random_balls/1, is_dutch/1, dutch/1]).
ball(red) -> 1; ball(white) -> 2; ball(blue) -> 3.
random_ball() -> lists:nth(random:uniform(3), [red, white, blue]).
random_balls(N) -> random_balls(N,[]). random_balls(0,L) -> L; random_balls(N,L) when N > 0 ->
B = random_ball(), random_balls(N-1, [B|L]).
is_dutch([]) -> true; is_dutch([_]) -> true; is_dutch([B|[H|L]]) -> (ball(B) < ball(H)) and is_dutch([H|L]); is_dutch(_) -> false.
dutch(L) -> dutch([],[],[],L).
dutch(R, W, B, []) -> R ++ W ++ B; dutch(R, W, B, [red | L]) -> dutch([red|R], W, B, L); dutch(R, W, B, [white | L]) -> dutch(R, [white|W], B, L); dutch(R, W, B, [blue | L]) -> dutch(R, W, [blue|B], L).</lang>
Sample usage: <lang erlang>main(_) ->
L = random_balls(10), case is_dutch(L) of true -> io:format("The random sequence ~p is already in the order of the Dutch flag!~n", [L]); false -> io:format("The starting random sequence is ~p;~nThe ordered sequence is ~p.~n", [L, dutch(L)]) end.</lang>
Sample output:
The starting random sequence is [white,white,blue,blue,white,red,white,blue, blue,white]; The ordered sequence is [red,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}]
Haskell
With the Color data type we take care that no other values than Red, White and Blue can be used. The "deriving" clause is a key aspect: We want Haskell to make Color automatically an instance of the classes Show, Eq, Ord and Enum. - Show means that Haskell can convert the data constructors Red, White and Blue to text. - Eq means that two values of type Color can be compared for equality, as if they were numbers or characters. - Ord means that one can sort a list of values of type Color according to the order in which the constructors Red, White and Blue were declared. We don't need to check if the order of the colors is right - it just is. - Enum menas that Red, White and Blue are automatically enumerated: every constructor is assigned to an integer.
The function "sort" works with anything that belongs to the Eq and Ord classes. The function "randomRIO" takes a range of two integers to give a random value within the range. We make Color an instance of Enum so that we can give Red, White and Blue as integers to randomRIO and convert the random number back to Red, White or Blue. <lang Haskell>import Data.List (sort) import System.Random (randomRIO) import System.IO.Unsafe (unsafePerformIO)
data Color = Red | White | Blue deriving (Show, Eq, Ord, Enum)
dutch :: [Color] -> [Color] dutch = sort
isDutch :: [Color] -> Bool isDutch x = x == dutch x
randomBalls :: Int -> [Color] randomBalls 0 = [] randomBalls n = toEnum (unsafePerformIO (randomRIO (fromEnum Red,
fromEnum Blue))) : randomBalls (n - 1)
main :: IO () main = do
let a = randomBalls 20 case isDutch a of True -> putStrLn $ "The random sequence " ++ show a ++ " is already in the order of the Dutch national flag!" False -> do putStrLn $ "The starting random sequence is " ++ show a ++ "\n" putStrLn $ "The ordered sequence is " ++ show (dutch a)</lang>
Output:
The starting random sequence is [White,Blue,Blue,Blue,Blue,Blue,Blue,Red,Red, White,White,Blue,White,White,Red,White,Blue,White,Red,Red] The ordered sequence is [Red,Red,Red,Red,Red,White,White,White,White,White, White,White,Blue,Blue,Blue,Blue,Blue,Blue,Blue,Blue]
To understand why Dijsktra was interested in the problem, here's an example showing difficiency of using generic sort: <lang haskell>import Data.List (sort)
inorder n = and $ zipWith (<=) n (tail n) -- or use Data.List.Ordered
mk012 :: Int -> Int -> [Int] -- definitely unordered mk012 n = (++[0]).(2:).map (`mod` 3).take n.frr where -- frr = Fast Rubbish Randoms frr n = r:frr r where r = n * 7 + 13
dutch1 n = (filter (==0) n)++(filter (==1) n)++(filter (==2) n)
dutch2 n = tric [] [] [] n where -- scan list once; it *may* help tric a b c [] = a++b++c tric a b c (x:xs) = case x of 0 -> tric (x:a) b c xs 1 -> tric a (x:b) c xs 2 -> tric a b (x:c) xs
main = do -- 3 methods, comment/uncomment each for speed comparisons -- print $ inorder $ sort s -- O(n log n) -- print $ inorder $ dutch1 s -- O(n) print $ inorder $ dutch2 s -- O(n) where s = mk012 10000000 42</lang>
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>
Logo
<lang logo>; 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</lang>
Test code: <lang>do.while [
make "list random_balls 10
] [dutch? :list]
print (sentence [Start list:] arraytolist :list) print (sentence [Sorted:] arraytolist dutch :list) bye</lang>
Output:
Start list: white blue red red red white blue red red white Sorted: red red red red red white white white blue blue
Mathematica
<lang Mathematica>flagSort[data_List] := Sort[data, If[#1 === RED || #2 === BLUE, True, False] &]</lang>
- Output:
flagSort[{WHITE, RED, RED, WHITE, WHITE, BLUE, WHITE, BLUE, BLUE, WHITE, WHITE, BLUE}] {RED, RED, WHITE, WHITE, WHITE, WHITE, WHITE, WHITE, BLUE, BLUE, BLUE, BLUE}
PARI/GP
A counting sort might be more appropriate here, but that would conceal the details of the sort. <lang parigp>compare(a,b)={
if (a==b, 0 , if(a=="red" || b=="blue", -1, 1) )
}; r(n)=vector(n,i,if(random(3),if(random(2),"red","white"),"blue")); inorder(v)=for(i=2,#v,if(compare(v[i-1],v[i])>0,return(0)));1;
v=r(10); while(inorder(v), v=r(10)); v=vecsort(v,compare); inorder(v)</lang>
Output:
1
Perl 6
Here are five ways to do it, all one liners (apart from the test apparatus). <lang>enum NL <red white blue>; my @colors;
sub how'bout (&this-way) {
sub show { say @colors; say "Ordered: ", [<=] @colors; }
@colors = NL.roll(20); show; this-way; show; say ;
}
say "Using functional sort"; how'bout { @colors = sort *.value, @colors }
say "Using in-place sort"; how'bout { @colors .= sort: *.value }
say "Using a Bag"; how'bout { @colors = red, white, blue Zxx bag(@colors».key)<red white blue> }
say "Using the classify method"; how'bout { @colors = (.list for %(@colors.classify: *.value){0,1,2}) }
say "Using multiple greps"; how'bout { @colors = (.grep(red), .grep(white), .grep(blue) given @colors) }</lang>
- Output:
Using functional sort red red white white red red red red red red red white red white red red red white white white Ordered: False red red red red red red red red red red red red red white white white white white white white Ordered: True Using in-place sort red blue white red white blue white blue red white blue blue blue red white white red blue red blue Ordered: False red red red red red red white white white white white white blue blue blue blue blue blue blue blue Ordered: True Using a Bag red blue blue blue white red white red white blue blue red red red red blue blue red white blue Ordered: False red red red red red red red red white white white white blue blue blue blue blue blue blue blue Ordered: True Using the classify method blue red white blue blue white white red blue red red white red blue white white red blue red white Ordered: False red red red red red red red white white white white white white white blue blue blue blue blue blue Ordered: True Using multiple greps red white blue white white red blue white red white red white white white white white red red blue red Ordered: False red red red red red red red white white white white white white white white white white blue blue blue Ordered: True
PicoLisp
<lang PicoLisp>(def 'Colors
(list (def 'RED 1) (def 'WHITE 2) (def 'BLUE 3) ) )
(let (L (make (do 9 (link (get Colors (rand 1 3))))) S (by val sort L))
(prin "Original balls ") (print L) (prinl (unless (= L S) " not sorted")) (prin "Sorted balls ") (print S) (prinl " are sorted") )</lang>
Output:
Original balls (RED BLUE WHITE BLUE BLUE RED WHITE WHITE WHITE) not sorted Sorted balls (RED RED WHITE WHITE WHITE WHITE BLUE BLUE BLUE) are sorted
Prolog
Works with SWI-Prolog 6.1.11
Prolog spirit
<lang Prolog>dutch_flag(N) :- length(L, N), repeat, maplist(init,L), \+is_dutch_flag(L) , writeln(L), test_sorted(L), sort_dutch_flag(L, TmpFlag), append(TmpFlag, Flag), writeln(Flag), test_sorted(Flag).
sort_dutch_flag([], [[], [], []]).
sort_dutch_flag([blue | T], [R, W, [blue|B]]) :- sort_dutch_flag(T, [R, W, B]).
sort_dutch_flag([red | T], [[red|R], W, B]) :- sort_dutch_flag(T, [R, W, B]).
sort_dutch_flag([white | T], [R, [white | W], B]) :-
sort_dutch_flag(T, [R, W, B]).
init(C) :-
R is random(3),
nth0(R, [blue, red, white], C).
test_sorted(Flag) :-
( is_dutch_flag(Flag)
-> write('it is a dutch flag')
; write('it is not a dutch flag')),
nl,nl.
% First color must be red is_dutch_flag([red | T]) :- is_dutch_flag_red(T).
is_dutch_flag_red([red|T]) :-
is_dutch_flag_red(T);
% second color must be white
T = [white | T1],
is_dutch_flag_white(T1).
is_dutch_flag_white([white | T]) :-
is_dutch_flag_white(T);
% last one must be blue
T = [blue | T1],
is_dutch_flag_blue(T1).
is_dutch_flag_blue([blue | T]) :- is_dutch_flag_blue(T).
is_dutch_flag_blue([]). </lang> Output :
?- dutch_flag(20). [blue,white,white,blue,blue,blue,red,blue,red,blue,blue,blue,white,red,red,blue,blue,red,blue,red] it is not a dutch flag [red,red,red,red,red,red,white,white,white,blue,blue,blue,blue,blue,blue,blue,blue,blue,blue,blue] it is a dutch flag true .
Functional spirit
Use of filters. <lang Prolog>dutch_flag(N) :- length(L, N),
% create the list to sort repeat, maplist(init,L), \+is_dutch_flag(L) , writeln(L), test_sorted(L),
foldl(\X^Y^Z^(Y = [Red, White, Blue], ( X = blue -> append_dl(Blue, [X|U]-U, Blue1), Z = [Red, White, Blue1] ; X = red -> append_dl(Red, [X|U]-U, Red1), Z = [Red1, White, Blue] ; append_dl(White, [X|U]-U, White1), Z = [Red, White1, Blue])), L, [R-R, W-W, B-B], [R1, W1, B1]), append_dl(R1, W1, B1, Flag-[]), write(Flag), nl, test_sorted(Flag).
% append lists in O(1) append_dl(A-B, B-C, A-C). append_dl(A-B, B-C, C-D, A-D).
init(C) :-
R is random(3),
nth0(R, [blue, red, white], C).
test_sorted(Flag) :-
( is_dutch_flag(Flag)
-> write('it is a dutch flag')
; write('it is not a dutch flag')),
nl,nl.
% First color must be red is_dutch_flag([red | T]) :- is_dutch_flag_red(T).
is_dutch_flag_red([red|T]) :-
is_dutch_flag_red(T);
% second color must be white
T = [white | T1],
is_dutch_flag_white(T1).
is_dutch_flag_white([white | T]) :-
is_dutch_flag_white(T);
% last one must be blue
T = [blue | T1],
is_dutch_flag_blue(T1).
is_dutch_flag_blue([blue | T]) :- is_dutch_flag_blue(T).
is_dutch_flag_blue([]). </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
colors as words
This version uses a version of a bin sort with counts, and has been generalized to allow any number of colors.
The REXX solution could've been simplified somewhat by the use of the countstr bif (but older REXX interpreters don't have).
<lang rexx>/*REXX pgm to reorder a set of random colored balls into a correct order*/ /*which is the order of colors on the Dutch flag: red, white, blue. */
parse arg N colors /*get user args from command line*/ if N=',' | N= then N=15 /*use default number of balls. */ 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 /*j*/
say ' sorted ball order:' say space($); say
do k=2 to N /*ensure the balls are in order. */ if wordpos(word($,k),colors)>=wordpos(word($,k-1),colors) then iterate say "The list of sorted balls isn't in proper order!"; exit 13 end /*k*/
say ' sorted ball list has been confirmed as being sorted correctly.' exit /*stick a fork in it, we're done.* /*──────────────────────────────────COUNTWORDS subroutine───────────────*/ countWords: procedure; parse arg ?,hay; s=1
do r=0 until _==0; _=wordpos(?,hay,s); s=_+1; end; return r</lang>
output when using the default input:
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.
colors as letters
<lang rexx>/*REXX pgm to reorder a set of random colored balls into a correct order*/ /*which is the order of colors on the Dutch flag: red, white, blue. */
parse arg N colors . /*get user args from command line*/ if N==',' | N== then N=15 /*use default number of balls. */ if colors= then colors='RWB' /*default: R=red, W=white, B=blue*/ Ncolors=length(colors) /*count the number of colors. */ @=right(colors,1)left(colors,1) /*ensure balls aren't in order. */
do g=3 to N /*generate a random # of balls. */ @=@ || substr(colors,random(1,Ncolors),1) end /*g*/
say 'number of colored balls generated = ' N ; say say 'original ball order:' say @ ; say $=; do j=1 for Ncolors; _=substr(colors,j,1)
#=length(@)-length(space(translate(@,,_),0)) $=$||copies(_,#) end /*j*/
say ' sorted ball order:' say $; say
do k=2 to N /*ensure the balls are in order. */ if pos(substr($,k,1),colors)>=pos(substr($,k-1,1),colors) then iterate say "The list of sorted balls isn't in proper order!"; exit 13 end /*k*/
say ' sorted ball list has been confirmed as being sorted correctly.'
/*stick a fork in it, we're done.*/</lang>
output when using the default input:
number of colored balls generated = 15 original ball order: BRBRRRWRBWRBBBR sorted ball order: RRRRRRRWWBBBBBB sorted ball list has been confirmed as being sorted correctly.
Ruby
<lang ruby>module Dutch
# Could use a class for the balls, but that's a little heavy. # We'll just use symbols.
# List of colors, in order Symbols = [:red, :white, :blue]
# Reverse map from symbol to numeric value Values = Hash[Symbols.each_with_index.to_a]
# Pick a color at random def self.random_ball Symbols[rand 3] end
# But we will use a custom subclass of Array for the list of balls class Balls < Array
# Generate a given-sized list of random balls def self.random(n) self.new(n.times.map { Dutch.random_ball }) end
# Test to see if the list is already in order def dutch? return true if length < 2 Values[self[0]] < Values[self[1]] && slice(1..-1).dutch? end
# Traditional in-place sort def dutch! lo = -1 hi = length i = 0 while i < hi do case self[i] when :red lo += 1 self[lo], self[i] = self[i], self[lo] i += 1 when :white i += 1 when :blue hi -= 1 self[hi], self[i] = self[i], self[hi] end end self end
# Recursive, non-self-modifying version def dutch(acc = { :red => 0, :white => 0, :blue => 0}) return self.class.new( Symbols.map { |c| [c] * acc[c] }.inject(&:+) ) if length == 0 acc[first]+=1 return slice(1..-1).dutch( acc ) end end
end</lang>
Driver/test code: <lang ruby>balls = nil while balls.nil? or balls.dutch? do
balls = Dutch::Balls.random 8
end puts "Start: #{balls}" puts "Sorted: #{balls.dutch}" puts "Intact: #{balls}" puts "In-place: #{balls.dutch!}" puts "Modified: #{balls}"</lang>
Output:
Start: [:red, :blue, :red, :white, :red, :red, :white, :blue] Sorted: [:red, :red, :red, :red, :white, :white, :blue, :blue] Intact: [:red, :blue, :red, :white, :red, :red, :white, :blue] In-place: [:red, :red, :red, :red, :white, :white, :blue, :blue] Modified: [:red, :red, :red, :red, :white, :white, :blue, :blue]
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