Puzzle 1

package org.ebberson.puzzles;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class PuzzleSolver {
	private final List<Integer> values;
	private final List<List<Integer>> buckets;
 
	/**
	 * Creates the puzzle solver.
	 * 
	 * @param values array of initial values
	 * @param bucketCount number of buckets in the games
	 */
	public PuzzleSolver(int[] values, int bucketCount) {
		this.values = new ArrayList<Integer>(values.length);
		this.buckets = new ArrayList<List<Integer>>(bucketCount);
 
		for (int i = 0; i < values.length; i++) {
			this.values.add(values[i]);
		}
 
		for (int i = 0; i < bucketCount; i++) {
			this.buckets.add(new ArrayList<Integer>());
		}
 
		bestGuess();
		optimize();
		printResults();
	}
 
 
	/**
	 * Initializes the buckets with a 'best guess'.
	 * 
	 * In descending order, adds a value to the bucket with the lowest sum.
	 */
	private void bestGuess() {
		Collections.sort(values);
		Collections.reverse(values);
 
		for (Integer i : values) {
			getLowestBucket().add(i);
		}
	}
 
 
	/**
	 * Optimizes the distribution by looking at pairs of numbers that 
	 * can be swapped to improve the total score.
	 */
	private void optimize() {
		for (List<Integer> bucket : buckets) {
			Collections.sort(bucket);
		}
 
		for (int i = 0; i < buckets.size() - 1; i++) {
			for (int j = i + 1; j < buckets.size(); j++) {
				optimize(buckets.get(i), buckets.get(j));
			}
		}
	}
 
 
	/**
	 * Optimizes the distribution by looking at pairs of numbers that 
	 * can be swapped to improve the total score.
	 * 
	 * @param bucket1
	 * @param bucket2
	 */
	private void optimize(List<Integer> bucket1, List<Integer> bucket2) {
		long bestScore = score();
 
		for (int i1 = 0; i1 < bucket1.size(); i1++) {
			for (int i2 = 0; i2 < bucket2.size(); i2++) {
				swap(bucket1, i1, bucket2, i2);
 
				if (score() > bestScore) {
					swap(bucket1, i1, bucket2, i2);
				}
			}
		}
	}
 
 
	/**
	 * Swaps values from two different buckets.
	 * 
	 * @param bucket1
	 * @param index1
	 * @param bucket2
	 * @param index2
	 */
	private void swap(List<Integer> bucket1, int index1, List<Integer> bucket2, int index2) {
		int temp = bucket1.get(index1);
		bucket1.set(index1, bucket2.get(index2));
		bucket2.set(index2, temp);
	}
 
 
	/**
	 * Returns the bucket with the lowest current sum.
	 * 
	 * @return
	 */
	private List<Integer> getLowestBucket() {
		List<Integer> lowestBucket = null;
		int lowestSum = Integer.MAX_VALUE;
 
		for (List<Integer> bucket : buckets) {
			int sum = sum(bucket);
			if (sum < lowestSum) {
				lowestBucket = bucket;
				lowestSum = sum;
			}
		}
 
		return lowestBucket;
	}
 
 
	/**
	 * Calculates the sum of a bucket.
	 * 
	 * @param bucket
	 * @return
	 */
	private int sum(List<Integer> bucket) {
		int sum = 0;
 
		for (Integer i : bucket) {
			sum += i;
		}
 
		return sum;
	}
 
 
	/**
	 * Calculates the total score.
	 * 
	 * @return
	 */
	private long score() {
		int n = buckets.size();
		int[] temp = new int[n];
 
		for (int i = 0; i < n; i++) {
			temp[i] = sum(buckets.get(i));
		}
 
		long sum = 0;
 
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				int delta = temp[i] - temp[j];
				sum += delta * delta;
			}
		}
 
		return sum;
	}
 
 
	/**
	 * Prints the results.
	 */
	private void printResults() {
		System.out.println("Final score: " + score());
 
		int i = 1;
 
		for (List<Integer> bucket : buckets) {
			System.out.print("Bucket " + i + " (" + sum(bucket) + "): ");
			Collections.sort(bucket);
			print(bucket);
			System.out.println();
			i++;
		}
	}
 
 
	/**
	 * Prints list of integers with proper comma usage.
	 * 
	 * @param bucket
	 */
	private void print(List<Integer> bucket) {
		boolean first = true;
 
		for (Integer i : bucket) {
			if (!first) {
				System.out.print(", ");
			}
 
			System.out.print(i);
			first = false;
		}
	}
 
	public static void main(String[] args) {
		int[] values = { 23, 43, 12, 54, 7, 3, 5, 10, 54, 55, 26, 9, 9, 43, 54, 1, 8, 6, 38, 33 };
		int bucketCount = 4;
		new PuzzleSolver(values, bucketCount);
	}
}