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

Purposes of this assignment

To teach STM (Software Transactional Memory) in Clojure

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:

Make a small change, or a small number of changes, in the current best solution to try to find a better solution.
- Don't have each agent trying the exact same changes as every other agent! You can avoid this by using some randomness in your approach, or by using the agent's number in some way.
- [Optional] The agent could also try a completely different subset of the numbers. This might be a good thing to do the very first time, or when the current best solution seems "too bad," but most of the time the agent should try small changes.
If the agent's new solution is better than the "official" current best solution,
- Replace the current best solution, and
- Continue trying to improve this solution.
If the new solution is worse that the current best solution,
- Discard this agent's new solution,
- Get a new copy of the "official" current best solution,
- Try to improve that solution.

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.