019: Magic Squares and Sequences

/*

  Magic sequence problem in Picat.

  http://www.dcs.st-and.ac.uk/~ianm/CSPLib/prob/prob019/spec.html
  """
  A magic sequence of length n is a sequence of integers x0 . . xn-1 between 
  0 and n-1, such that for all i in 0 to n-1, the number i occurs exactly xi 
  times in the sequence. For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence 
  since 0 occurs 6 times in it, 1 occurs twice, ...


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

*/

% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

import cp.

main => go.

go =>
        magic_sequence(400,Sequence),
        writeln(Sequence).


go2 =>
        foreach(N in 4..40)
           if magic_sequence(N,Sequence) then
              writeln(Sequence)
           else 
              writeln('No solution')
           end
        end.


scalar_product(A, X) = Product => 
   Product #= sum([S : I in 1..A.length, S #= A[I]*X[I]]).


magic_sequence(N, Sequence) =>

        writef("\n%d: ",N),

        Sequence = new_list(N),
        Sequence :: 0..N-1,


        % Note: I would like to use global_cardinality/2 instead 
        %       but didn't get it right.
        foreach(I in 0..N-1) count(I,Sequence,#=,Sequence[I+1]) end,


        N #= sum(Sequence),
        Integers = [ I : I in 0..N-1],
        N = scalar_product(Integers, Sequence),
        solve([ff], Sequence).