/* 

  Enigma problem 1570 (Set of cubes)  in Picat.


  From New Scientist:
  http://www.newscientist.com/article/mg20427330.800-enigma-number-1570.html
  """
  04 November 2009 by Richard England
  
  Sets of cubes
  
  1. Find the set of perfect cubes that between them use each of the 
  digits 0 to 9 at least once whose sum is as small as possible. What 
  is the sum of your set of cubes?
  
  2. Find the set of perfect cubes that between them use each of the digits 
  0 to 9 exactly once whose sum is as small as possible. What is the sum 
  of your set of cubes?
  
  In answering either of these questions you may, if you wish, 
  treat 0 as itself being a cube.
  """

  Note: This model handles just the second problem, i.e. where all 
        digits are used exactly once.

  Answer:
    num1 = 1
    num2 = 8
    num3 = 64
    num4 = 205379
    total = 205452
    x = [1, 8, 6, 4, 2, 0, 5, 3, 7, 9]

  There 6 solutions with different number of cubes using all the digits,
  the one with 4 cubes has the smallest total sum (205452):

    numLen = 2
    x = [8,0,2,4,1,3,7,5,6,9]
    ix = [1,2]
    nums = [8,24137569]
    total = 24137577

    x = [8,0,3,2,4,6,1,7,5,9]
    ix = [1,2]
    nums = [8,32461759]
    total = 32461767

    x = [1,2,5,0,4,3,8,9,7,6]
    ix = [1,4]
    nums = [125,438976]
    total = 439101

    x = [5,1,2,0,4,3,8,9,7,6]
    ix = [1,4]
    nums = [512,438976]
    total = 439488

    x = [9,2,6,1,8,0,4,3,5,7]
    ix = [1,5]
    nums = [9261,804357]
    total = 813618

    numLen = 3
    numLen = 4
    x = [1,8,6,4,2,0,5,3,7,9]
    ix = [1,2,3,5]
    nums = [1,8,64,205379]
    total = 205452

  If we allow first cube as 0 and that X[1] == 0 then there are
  10 solutions, i.e. the additional 4 solutions, though neither
  has a total less than the previous optimal solution.

    x = [0,8,2,4,1,3,7,5,6,9]
    ix = [1,2,3]
    nums = [0,8,24137569]
    total = 24137577

    x = [0,8,3,2,4,6,1,7,5,9]
    ix = [1,2,3]
    nums = [0,8,32461759]
    total = 32461767

    x = [0,1,2,5,4,3,8,9,7,6]
    ix = [1,2,5]
    nums = [0,125,438976]
    total = 439101

    x = [0,5,1,2,4,3,8,9,7,6]
    ix = [1,2,5]
    nums = [0,512,438976]
    total = 439488

  
  


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

*/

import cp.


main => go.

go ?=>
  Len = 10, % length of the array
  Base = 10,
  X = new_list(Len),
  X :: 0..9,

  % We have NumLen numbers (cube).
  member(NumLen,1..Len),
  println(numLen=NumLen),
  cubes(Cubes),   
  Nums = new_list(NumLen),  
  Nums :: Cubes,
  
  % indices of the numbers:
  Ix = new_list(NumLen),
  Ix[1] := 1,
  foreach(K in 2..NumLen)
    member(Ix[K],Ix[K-1]+1..Len)
  end,

  all_different(X),
  increasing(Nums),
  increasing(Ix),
    
  % We allow 0 as first digit only if the first cube is 0
  X[1] #= 0 #<=> Nums[1] #= 0,
  % X[1] #= 0, % check for extra solutions.

  Total #= sum(Nums),
  
  % connect cubes to the digits
  foreach(K in 1..NumLen-1)
    to_num([X[I] : I in Ix[K]..Ix[K+1]-1], Base, Nums[K])
  end,
  % last cube
  to_num([X[I] : I in Ix[NumLen]..Len], Base, Nums[NumLen]),

  Vars = X ++ Ix ++ Nums ++ [Total],
  solve([ff,updown],Vars),

  println(x=X),
  println(ix=Ix),
  println(nums=Nums),
  println(total=Total),
  nl,
  flush(stdout),
  fail,
  
  nl.

go => true.

%
% 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]).



%
% Here are cubes between 0^3..1000^3 which just contains unique digits.
%
cubes(Cubes) =>
Cubes = [
0,
1,
8,
27,
64,
125,
216,
512,
729,
1728,
2197,
4096,
4913,
5832,
6859,
9261,
10648,
13824,
19683,
24389,
32768,
42875,
54872,
68921,
205379,
287496,
328509,
389017,
421875,
438976,
592704,
681472,
804357,
912673,
2460375,
3048625,
8365427,
24137569,
26198073,
27543608,
32461759
].