import java.io.*;
import java.util.*;
import java.util.Arrays;
import java.util.Collections;
import org.chocosolver.util.tools.ArrayUtils;
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.solver.constraints.IIntConstraintFactory.*;
import org.chocosolver.solver.constraints.Constraint;
import org.chocosolver.solver.search.strategy.Search;

public class BinPack {

    int[] data;         // the data to be packed
    Model model;        // the model :)
    Solver solver;      // a solver object, to attach variables and constraints
    IntVar inBin[][];   // inBin[i][j] = 1 iff jth number is in ith bin
    IntVar load[];      // load[i] is sum of the numbers in ith bin
    IntVar binUsed[];   // binUsed[i] = 1 iff load[i] > 0
    IntVar totBinsUsed; // total number of bins used
    int c;              // the capacity of each bin
    int n;              // number of items to pack
    int m;              // number of bins you have
    String id;          // an identification for the problem
	
    public BinPack(String fname,int numberOfItems,int numberOfBins,int capacity) throws Exception {
	n           = numberOfItems;
	m           = numberOfBins;
	c           = capacity;
	id          = fname;
	data        = new int[n];
	model       = new Model(id);
	solver      = model.getSolver();
	inBin       = model.intVarMatrix("inBin",m,n,0,1);
	load        = model.intVarArray("load",m,0,c);
	binUsed     = model.intVarArray("binUsed",m,0,1);
	totBinsUsed = model.intVar("totBinsUsed",0,m);

	Scanner sc = new Scanner(new File(fname));
	for (int j=0;j<n;j++) data[j] = sc.nextInt();
	sc.close();

	// EDIT
	//Arrays.sort(data);
	//reverse(data,0,n-1);
	//
	// first fit decreasing
	//

	for (int i=0;i<m;i++)
	    model.scalar(inBin[i],data,"=",load[i]).post();
	// 
	// constrain load[i] to be the scalar product of inBin[i] and data[i]
	//

	for (int i=0;i<m;i++){
	    Constraint c1 = model.arithm(load[i],">",0);
	    Constraint c2 = model.arithm(binUsed[i],"=",1);
	    model.ifThen(c1,c2);
	    model.ifThen(c2,c1);
	}
	// 
	// constrain binUsed[i] to be 1 if and only if there are some
	// items stacked in the ith bin, i.e. load[i] > 0
	//

	for (int i=0;i<n;i++)
	    model.sum(ArrayUtils.getColumn(inBin,i),"=",1).post();
	//
	// constrain a piece of data such that it can only be in one bin at a time!
	// i.e. the sum of a column of the array inBin must be equal to 1,
	//      such that an item/number is in exactly one bin
	// NOTE: inBinT is transpose of inBin
	//

	model.sum(binUsed,"=",totBinsUsed).post();
	//
	// constrain totBinsUsed to be the sum of the binUsed vector
	// we now need to minimise this value
	//

	// EDIT
	//for (int i=0;i<m-1;i++)
        //   model.arithm(load[i],">=",load[i+1]).post();
	//
	// symmetry breaking consistent with first fit decreasing
	// heaviest bins are low index
	//

	// EDIT
	// model.lexChainLessEq(inBin).post();
	//
	// symmetry breaking such that inBin[i] lex< inBin[i+1]
	//
    }

    public void swap(int[] a,int i,int j){
	int temp = a[i]; a[i] = a[j]; a[j] = temp;
    }

    public void reverse(int[] a,int lwb,int upb){
	if (lwb<upb){
	    swap(a,lwb,upb);
	    reverse(a,lwb+1,upb-1);
	}
    }
    
    // solve using value ordering over decision variables
    boolean solve(){
	//solver.setSearch(Search.minDomLBSearch(ArrayUtils.flatten(inBin)));
	//solver.setSearch(Search.minDomUBSearch(ArrayUtils.flatten(inBin)));
	return solver.solve();
    }
    
    public String toString(){
	String s = id + " " + " #items: " + n + 
	          " #bins: " + m + " capacity: " + c + "\n";
	s = s + "#bins used: " +  totBinsUsed.getValue() + "\n";
	int sum = 0;
	for (int j=0;j<n;j++){
	    s = s + data[j] + " ";
	    sum = sum + data[j];
	}
	s = s + "sum: " + sum + "\n";
	for (int i=0;i<m;i++){
	    s = s + "bin[" + i + "] ";
	    for (int j=0;j<n;j++)
		s = s + inBin[i][j].getValue() + " ";
	    s = s + load[i].getValue() + "\n";
	}
	return s;
    }

    public static void main(String[] args) throws FileNotFoundException, IOException, Exception {
	String fname       = args[0];
	int capacity       = Integer.parseInt(args[1]);
	int numberOfItems  = Integer.parseInt(args[2]);    
	int numberOfBins   = Integer.parseInt(args[3]);

	BinPack bp = new BinPack(fname,numberOfItems,numberOfBins,capacity);
	boolean solved = bp.solve(); 
	System.out.println(solved);
	if (solved) System.out.println(bp);
	System.out.println("nodes: " + bp.solver.getMeasures().getNodeCount() +
			   "   cpu: " + bp.solver.getMeasures().getTimeCount());
    }
}