/* 

  Project Euler #76 in Picat.
  """
  It is possible to write five as a sum in exactly six different ways:

  4 + 1
  3 + 2
  3 + 1 + 1
  2 + 2 + 1
  2 + 1 + 1 + 1
  1 + 1 + 1 + 1 + 1

  How many different ways can one hundred be written as a sum of at 
  least two positive integers?
  """


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

*/

import cp.


main => go.

go ?=>
  euler76a().
go => true.
  
% 0.002s
euler76a =>
  Target = 100,
  Ways = new_list(Target+1),
  bind_vars(Ways,0),
  Ways[1] := 1,
  foreach(I in 2..99)
    foreach(J in I..Target)
       Ways[J+1] := Ways[J+1] + Ways[J-I+1]
    end
  end,
  println(sum(Ways)).

% Too slow (unsurprisingly)
euler76b =>
  println(count_all(e76b(_X))).

e76b(X) =>
  N = 100,
  X = new_list(N-1),
  X :: 0..N-1,
  sum([X[I]*I : I in 1..N-1]) #= 100,
  sum(X) #>= 2,
  solve($[ff,split],X).

% 0.102s
euler76c =>
  C = coins(1..100, 100, 1)-1,
  println(C).

table
coins(Coins, Money, M) = Sum =>
    Sum1 = 0,
    Len = Coins.length,
    if M == Len then
      Sum1 := 1
    else 
       foreach(I in M..Len)
         if Money - Coins[I] == 0 then
            Sum1 := Sum1 + 1
         end,
         if Money - Coins[I] > 0 then
            Sum1 := Sum1 + coins(Coins, Money-Coins[I], I)
         end
       end
    end,
    Sum = Sum1.