/* 

  A weighing problem in Picat.


  From a (deleted) Stack overflow question
  """
  Coding puzzle from a fortune 100 company recruitment

  everyone I don't know if this is the right place to ask this question but fallowing 
  is the programming challenge I faced and in-fact turned my career upside down. 
  I understand that Stack Overflow is not a place to get my code done. But If 
  anyone could give an idea/concept or a short description on how to solve this 
  problem it would be a big relief for me.

  You are given 7 weights ( 1,3,9,27,81,243) using combination of these weights you 
  should be able to weigh any weight on a weight balance. Example:

   1. If 5 is to be measured then combination would be "9" on one side of balance 
      and "3 and 1" on other side

   2. If 6 is to be measure then combination would be "9" on one side and "3" on other.

   3. Similarly for 7 combination would be "9 and 1" on one side and "3" on 
      other side of balance

    Sample Input

    7

    Sample Output

    First: 3

    Second: 9 1

  NOTE: If one doesn't understand the problem please comment I will 
  further explain in detail
  """

  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 =>
  Num = 7,
  Weights = [1,3,9,27,81,243],
  println(num=Num),
  println(weights=Weights),
  weighing(Weights,Num, X, First,Second),
  println(x=X),
  println(first=First),
  println(second=Second),
  nl.

go2 => 
  Nums = [5,6,7],
  Weights = [1,3,9,27,81,243],
  foreach(Num in Nums)
    println(num=Num),
    println(weights=Weights),
    weighing(Weights,Num, X, First,Second),
    println(x=X),
    println(first=First),
    println(second=Second),
    nl
  end,
  nl.

%
% Which is the largest number that can be weighed?
% This is sum(Weights) of course.
%
go3 => 
  Weights = [1,3,9,27,81,243],
  Max = sum(Weights),
  println(max=Max),
  maxof(weighing(Weights,Num, X, First,Second),Num),
  println(maxNum=Num),
  println(x=X),
  println(first=First),
  println(second=Second),
  nl.

%
% show all possible weighings
%
go4 => 
  Weights = [1,3,9,27,81,243],
  Max = sum(Weights),
  foreach(Num in -Max..Max)
    println(num=Num),
    println(weights=Weights),
    weighing(Weights,Num, X, First,Second),
    println(x=X),
    println(first=First),
    println(second=Second),
    nl
  end,
  nl.


% Check if there are any multiple solutions for any number.
% Answer: No there isn't using the weights [1,3,9,27,81,243].
% For other weights there are plenty, e.g [1,2,4,8,16]
go5 => 
  % Weights = [1,3,9,27,81,243],
  % Weights = [2**I : I in 0..6], % plenty of duplicates for most numbers
  Weights = [[1] ++ [1 + random2() mod 100 : _ in 1..7]].flatten().sort_remove_dups(),
  println(weights=Weights),
  Max = sum(Weights),
  Duplicates = [], % duplicate solutions
  SingleSol = [], % distinct solutions
  ZeroSol = [], % Nums with no solution
  % Just show from 1..Max (negative numbers are symmetric)
  foreach(Num in 1..Max)
    All = findall([X,First,Second], weighing(Weights,Num, X, First,Second)),
    if All.length = 0 then ZeroSol := ZeroSol ++ [Num] end,
    if All.length = 1 then SingleSol := SingleSol ++ [Num] end,
    if All.length > 1 then
      nl,
      println(number_of_solutions=All.length),
      Duplicates := Duplicates ++ [[num=Num,sols=All.length]],
      foreach([X,First,Second] in All) 
        println(num=Num),
        println(weights=Weights),
        println(x=X),
        println(first=First),
        println(second=Second),
        nl
      end
    end
  end,
  println(duplicates=Duplicates),
  println(zeroSol=ZeroSol),
  println(singleSol=SingleSol),
  nl.


weighing(Weights, Num, X,First,Second) => 
  N = Weights.length,

  X = new_list(N),
  X :: -1..1,

  scalar_product(Weights, X,Num),  
  
  solve(X),

  First=[Weights[I] : I in 1..N, X[I] = -1],
  Second=[Weights[I] : I in 1..N, X[I] = 1].