/*

  Hamming numbers in Picat.

  From Rosetta code:
  http://rosettacode.org/wiki/Hamming_numbers
  """
  Hamming numbers are numbers of the form
    H = 2**i * 3**j * 5**k, where  i, j, k >= 0. 

  Hamming numbers are also known as ugly numbers and also 5-smooth numbers 
  (numbers whose prime divisors are less or equal to 5).
  
  Generate the sequence of Hamming numbers, in increasing order. In particular:

   * Show the first twenty Hamming numbers.
   * Show the 1691st Hamming number (the last one below 231).
   * Show the one millionth Hamming number (if the language – or a 
     convenient library – supports arbitrary-precision integers). 
  """


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

*/

import util.
main => go.

go =>

   println("using hamming1/1 (map)"),
   writeln([hamming(I) : I in 1..20]),
   time(writeln(hamming(1691))),
   time(writeln(hamming(1000000))), % about 10s

   garbage_collect(),

   println("using hamming2/1 (array)"),
   writeln([hamming2(I) : I in 1..20]),
   time(writeln(hamming2(1691))),
   time(writeln(hamming2(1000000))), % about 1.5s

   nl.

go2 =>
   writeln(hamming_life(10)),
   nl.


%
% Using map. Slower.
%
hamming(1) = 1.
hamming(2) = 2.
hamming(3) = 3.
hamming(N) = Hamming =>
   writeln($hamming(N)),
   H = new_map(N),
   [Next2, Next3, Next5] = [2,3,5],

   H.put(1,1),
   H.put(4,0),
   H.put(Next2,1),
   H.put(Next3,2),
   H.put(Next5,3),

   I = 0,
   J = 0,
   K = 0,
   M = 1,

   while (M < N) 
      H.put(M, min([Next2,Next3,Next5])),
      if H.get(M) == Next2 then I := I+1, Next2 := 2*H.get(I) end,
      if H.get(M) == Next3 then J := J+1, Next3 := 3*H.get(J) end,
      if H.get(M) == Next5 then K := K+1, Next5 := 5*H.get(K) end,
      M := M + 1
   end,

   HH := H.values(), % adjust for 1-based
   Hamming = HH[N-1].


%
% Using arrays. 
%
hamming2(1) = 1.
hamming2(2) = 2.
hamming2(3) = 3.
hamming2(N) = Hamming2 =>
   writeln($hamming2(N)),
   A = new_array(N),
   [Next2, Next3, Next5] = [2,3,5],

   A[1] := Next2,
   A[2] := Next3,
   A[3] := Next5,

   I = 0,
   J = 0,
   K = 0,
   M = 1,  
   while (M < N) 
      A[M] := min([Next2,Next3,Next5]),
      if A[M] == Next2 then I := I+1, Next2 := 2*A[I] end,
      if A[M] == Next3 then J := J+1, Next3 := 3*A[J] end,
      if A[M] == Next5 then K := K+1, Next5 := 5*A[K] end,
      M := M + 1
   end,
   Hamming2 = A[N-1].
   
% 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36