Transcript Comments on the “Three Piles” Problem

Comments on the “Three Piles”
Problem
29-Mar-16
My timings
Solved 10000 problems of size 5 in 15 milliseconds.
Average time per problem: 0.0015 ms.
Solved 200 problems of size 10 in 16 milliseconds.
Average time per problem: 0.08 ms.
Solved 200 problems of size 15 in 718 milliseconds.
Average time per problem: 3.59 ms.
Solved 200 problems of size 20 in 34719 milliseconds.
Average time per problem: 173.595 ms.
Solved 100 problems of size 25 in 43797 milliseconds.
Average time per problem: 437.97 ms.
Timing graph
General approach


The “Three Piles” problem can be solved by a
backtracking algorithm
Roughly, the algorithm goes like this:

boolean solve(int numbersPlaced) {
if (numbersPlaced== all the numbers)
return true;
for (each pile p) {
if can put the next number, numbersPlaced+1, into pile p {
put it in pile p
if (solve(numbersPlaced+1)) return true
else take the number out again
}
return false
}
Problems with this algorithm


It’s much easier for the programmer if the method
returns a boolean, but the user demands a solution
The method requires some data structures (say, arrays
or stacks) to keep working information in



We can’t set this information up inside a recursive method
We don’t want to hassle the user with extra junk that is only
needed to make the algorithm work
Solution: Provide a facade method to:



Provide a simplified interface to the user
Initialize any needed data structures
Call the “real” recursive method with whatever parameters
are convenient for the programmer, not the user
The facade method

The user wants to do this:



solution = solve(problem)
where solution is some data structure containing your results
In the code below, I called this data structure a “Solution,” but
it might be implemented by (for example) an int[][]
So you do this:

Solution solve(int[] problem) {
Solution solution; // maybe an int[][]
// Create the “Solution” data structure and any other data
// structures and initializations that you need
put problem[0] into your solution pile 0
if (reallySolve(problem, solution, 0, other stuff)) {
return solution;
} else return null; // Much better than returning a bad solution!
}
The real recursive method


boolean reallySolve(problem, solution, nextNumber, ...) {
if nextNumber == problem size, return true**
for each pile p,
if we can put nextNumber into pile p {
put it in the pile
if (reallySolve(problem, solution,
nextNumber+1, ...)) return true;
else take the number back out again
}
}
return false
}
** If some problems may be unsolvable , you should check the
“solution” at this point and return false if it doesn’t work
Backtracking in general


Solution solve(Problem p) {
create object to hold solution;
do any other initializations you need;
if (solve(p, solution, other stuff)) return solution;
else return null;
}
private boolean solve(Problem p, Solution s, other stuff) {
if problem is already solved, return true;
for each of the choices available to you {
make a choice;
if (solve(simpler version of p, s, other stuff)) return true;
else undo this choice; // can sometimes be implicit
}
return false;
}
Summary

The notion of a facade is this:



The code has a complex interface and requires lots of
initializations and global structures
The user wants a simple and easy to use interface
Create a facade to stand between the user and the ugly code
and present a simpler interface
The End