CIS 554 Clojure 3: Equal Piles
Fall 2015, David Matuszek

Purposes of this assignment

General idea of the assignment

The "equal piles" problem is this: Given a large collection of numbers, sort them into two piles, such that the sum of the numbers in the first pile equals the sum of the numbers in the second pile. Equivalently, find a subset of the numbers whose sum is half the total sum. This problem is NP-complete, so there is no known solution that takes less than exponential time.

This assignment will use multiple agents to search for a solution. There are probably more efficient ways to tackle this problem, but the intent here is to use the problem to teach STM.

Detailed specification

Set up the problem

Create a vector of N random numbers, each in the range 1 to M. (Probably good values are N=50, M = 1000000.) You can, if you like, ensure that the sum of all the numbers is even.

Print the total, and half the total, properly labeled. Half the total is your "goal number."

Take about half the numbers, for example the first N/2 numbers, and call this the "current best solution." Print this solution--that is, print the numbers in the solution, the total of those numbers, and the difference between that total and the goal number.

Whenever an agent finds an improvement to this current best solution, save the numbers, the difference between their total and the goal number, and the id of the agent that found this solution. Print these values.

Find better solutions

Create 100 agents, with id numbers 1 to 100, giving each agent a copy of the current best solution. Each agent also needs access to all N numbers and to the goal number, but these won't be changed and don't need to be copies.

Each agent should:

Note that the agents themselves do no printing; all printing is done from the "main" thread.

Stop the program when about 1000 improvements have been made, or when an exact solution is found. Print the best solution.

Due date

Your program is due before 6am Friday, October 9, via Canvas.