/* 

  Largest number divisible by its digits (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Largest_number_divisible_by_its_digits
  """
  Task

  Find the largest base 10 integer whose digits are all different, and is evenly 
  divisible by each of its individual digits.


  These numbers are also known as Lynch-Bell numbers, numbers n such that the 
  (base ten) digits are all different (and do not include zero) and n is divisible 
  by each of its individual digits.


  Example

  135   is evenly divisible by   1,   3,   and   5.

  Note that the digit zero (0) can not be in the number as integer division by zero is undefined.

  The digits must all be unique so a base ten number will have at most 9 digits.

  Feel free to use analytics and clever algorithms to reduce the search space your example needs 
  to visit, but it must do an actual search. (Don't just feed it the answer and verify it is correct.)


  Stretch goal

  Do the same thing for hexadecimal. 
  """

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

*/

import cp.


main => go.


% Base 10:9867312  0.957s 
go ?=>
  maxof(largest_number_divisible_by_its_digits(10, N),N),
  % largest_number_divisible_by_its_digits2(10, N),
  println(N),
  nl.
go => true.


% Base 16: ???s
go2 ?=>
  maxof(largest_number_divisible_by_its_digits(16, N10),N10),
  println(N),
  println(hex=to_radix_string(N,16)),
  nl.
go2 => true.

% Another approach
% 1.197s for base 10
go3 ?=>
  garbage_collect(300_000_000),
  Base = 16,
  M = Base-1,
  member(Len,1..M),
  L = 1..M,
  X = new_list(Len),
  X :: L,
  X[1] #= M,
  to_num(X,Base,N),  
  foreach(I in 2..Len)
    N mod X[I] #= 0
  end,
  all_different(X),
  solve(X),
  println(X=to_radix_string(N,Base)),
  fail.
go3 => true.

largest_number_divisible_by_its_digits(Base, N) =>
  M = Base-1,
  member(Len,1..M),
  X = new_list(Len),
  X :: 1..M,
  N :: 1**(M-1)..M**M-1,

  all_different(X),
  to_num(X,Base,N),

  X[1] #= M,

  foreach(I in 1..Len)
    N mod X[I] #= 0
  end,

  solve($[ffd,updown,max(N)],X),
  println(Base=X=to_radix_string(N,Base)).


% Another approach
largest_number_divisible_by_its_digits2(Base, N) =>
  M = Base-1,
  X = new_list(M),
  X :: 0..M,
  
  N :: 0..M**M-1,

  all_different_except_0(X),
  to_num(X,Base,N),
  
  foreach(I in 1..M)
    X[I] #> 0 #=> N mod X[I] #= 0
  end,

  % collect 0s to the left
  % foreach(I in 2..M)
  %   X[I] #= 0 #=> X[I-1] #= 0
  % end,
  
  println([x=X,n=N]),
  solve($[ff,split,max(N)],X),
  println([x=X,n=N]).


%
% converts a number Num to/from a list of integer List given a base Base
%
to_num(List, Base, Num) =>
   Len = length(List),
   Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).