/* 

  Flabbergasted in Picat.

  From Chris Smith's Math Newsletter #561
  """
  ---
  Flabbergasted

  What is the longest sequence you can make from the numbers below?

   1  2  3  4  5  6
   7  8  9 10 11 12
  13 14 15 16 17 18
  19 20 21 22 23 24

  Each number in the sequence must be a factor or multiple of 
  the previous number.
  ---
  
  The challenge? To use the integers from 1 to 24 to create the
  largest string that you can so that the neighbouring numbers
  are either factors or multiplies of each other!

  See if you and your students can beat my _world-record_ of 21 :-) ...
  """

  Also, see
  https://www.transum.org/Software/SW/Starter_of_the_day/starter_May7.ASP


  Note: I interpret this that we can ignore the arrangement of the 
  numbers in the figure and pick any (unique) neighbour from 1..24.


  * Optimal solution (one of them) of length 21
    m = 24
    m = 23
    m = 22
    m = 21
    x = [17,1,15,5,10,20,4,16,8,24,12,6,18,9,3,21,7,14,2,22,11]

  * There are 16 optimal solutions (length 21)
    This has the symmetryt breaking that X[1] < X[21].

    However, there are really just a few (I would say 5) 
    principal solutions since many solutions are identical except 
    for the "spurious" last/first prime with a cheating factor 
    of 1 as the connection.

    x = [9,18,6,12,24,8,16,4,20,10,5,15,3,21,7,14,2,22,11,1,13]
    x = [9,18,6,12,24,8,16,4,20,10,5,15,3,21,7,14,2,22,11,1,17]
    x = [9,18,6,12,24,8,16,4,20,10,5,15,3,21,7,14,2,22,11,1,19]
    x = [9,18,6,12,24,8,16,4,20,10,5,15,3,21,7,14,2,22,11,1,23]

    x = [11,22,2,14,7,21,3,15,5,10,20,4,16,8,24,12,6,18,9,1,13]
    x = [11,22,2,14,7,21,3,15,5,10,20,4,16,8,24,12,6,18,9,1,17]
    x = [11,22,2,14,7,21,3,15,5,10,20,4,16,8,24,12,6,18,9,1,19]
    x = [11,22,2,14,7,21,3,15,5,10,20,4,16,8,24,12,6,18,9,1,23]

    x = [11,22,2,14,7,21,3,9,18,6,12,24,8,16,4,20,10,5,15,1,13]
    x = [11,22,2,14,7,21,3,9,18,6,12,24,8,16,4,20,10,5,15,1,17]
    x = [11,22,2,14,7,21,3,9,18,6,12,24,8,16,4,20,10,5,15,1,19]
    x = [11,22,2,14,7,21,3,9,18,6,12,24,8,16,4,20,10,5,15,1,23]

    x = [13,1,11,22,2,14,7,21,3,9,18,6,12,24,8,16,4,20,10,5,15]

    x = [15,5,10,20,4,16,8,24,12,6,18,9,3,21,7,14,2,22,11,1,17]
    x = [15,5,10,20,4,16,8,24,12,6,18,9,3,21,7,14,2,22,11,1,19]
    x = [15,5,10,20,4,16,8,24,12,6,18,9,3,21,7,14,2,22,11,1,23]


  Or: 32 optimal solutions without symmetry breaking.


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

*/

import cp.
% import sat.
import util.


main => go.

% Find the largest list
go ?=>
  nolog,
  member(Len, 24..-1..2),
  println(len=Len),
  time(flabbergasted(Len,X, Zs)),
  println(x=X),
  println(zs=Zs),
  println(len=[I.to_string : I in X].join.length),
  nl,
  % fail,
  nl.
go => true.

%
% All optimal solutions.
%
go2 ?=>
  nolog,
  Map = get_global_map(),
  Map.put(sols,0),
  Len = 21,
  println(len=Len),
  flabbergasted(Len,X, _Zs),
  println(x=X),
  Map.put(sols,Map.get(sols)+1),
  fail,
  nl.
go2 => println(sols=get_global_map().get(sols)).


flabbergasted(Len,X, Zs) =>
  X = new_list(Len),
  X :: 1..24,
  
  all_distinct(X),
  % all_different(X), % slower

  % symmetry breaking
  X[1] #< X[Len],

  Zs = [],
  foreach(I in 1..Len-1)
    Z :: 1..24,
    (X[I] * Z #= X[I+1] #\/ X[I] #= X[I+1] * Z),
    Zs := Zs ++ [Z]
  end,

  Vars = X ++ Zs,
  solve($[constr,split],Vars).