/* 

  Dutch national flag problem in Picat.

  http://rosettacode.org/wiki/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. 
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
% import cp.


main => go.


go =>
  _ = random2(), % random seed
  N=21,
  Map = new_map([1=red,2=white,3=blue]),
  [Rand,Sorted] = dutch_random_sort(N,Map,Map.inverse()),
  println('rand  '=Rand),
  println(sorted=Sorted),
  nl.

% generate a random order and ensure it's not already dutch sorted
dutch_random_sort(N,Map,MapInv) = [Rand,Sorted] => 
  Rand = dutch_random1(N,Map),
  Sorted = dutch_sort(Rand,MapInv),
  while (Rand == Sorted)
    println("Randomize again"),
    Rand := dutch_random1(N,Map),
    Sorted := dutch_sort(Rand,MapInv)
  end.

dutch_random1(N,Map) = [Map.get(1+(random() mod Map.map_to_list().length)) : _I in 1..N].

dutch_sort(L,MapInv) = [R : _=R in [MapInv.get(R)=R : R in L].sort()].

inverse(Map) = new_map([V=K : K=V in Map]).