When you first encounter larger programs, it seems
difficult to know where to start. Problems like 1.5
have a number of components, and organizing your
solution may be difficult. Here are some suggestions.
Have a plan: Design from top down
Break down the work into chunks
Build from the bottom up, checking as you go
Find a way around road blocks
Start simple, and get clever when things work
Save your work
I sat down yesterday and wrote up a solution.
Though I understand the problem, I face the
same difficulties getting this to work that
anyone else does.
Have a plan: Design from top down
I started with a plan: there would be an object
holding an array of sets that could be used
by the backtracking. To get solve the problem,
I would need to
Be able to read in one set
Be able to read in a file of sets
Perform BackTracking
Break down the work into chunks
I started with the short term goal of writing
a class to hold one set, and being able to
perform the operations I would need on the
set. Without much thought, these include
Construct an empty set
Construct a set from a description
Display a set
Manipulate sets
Shift
Test for intersection
Add and subtract sets
Copy sets
As the program expanded, I might find
that I needed additional operations.
But it is pretty clear that a good representation
of a set is needed.
Build from the bottom up, checking as you go
Once I had a plan for the set representation,
many of these methods were easy to write.
The constructor based on a string was the
most difficult. To be able to test the
other attributes, I quickly wrote a
constructor that took a string, and
simply added the digits it saw. Thus
it would take the string
"{1, 2, 3"}
and get the right set, but it would create
the same set for
{123}
or
{132}
or
1-1%1...2!!!3(232}[3]
The simple constructor was quick to write, and
allowed me to make progress on other fronts.
This has limited utility: I can only use this to
solve a problem with 1..9 integers. However,
this is a start, and I could use this to test my
function to display sets, and even test the
backtracking for simpler cases.
Find a way around road blocks
Once I had a basic scheme to read a
set, it should have been easy to write
a routine to read a set of sets.
But for a long time, I had trouble converting
the first line of the file into an integer.
I was attempting to use some Java functions,
and I still haven't made that work.
Without the right number, of course,
you can't really get very far. Rather than
let this stop me, I did the following
// Latest attempt to read from file
numInts = .....
System.out.println(numInts); // Echo print results
numInts = 12;
That is, I knew that the right answer for the file
I was using was 12, and I hotwired the result to
match. This allowed me to use a single
edit/compile/test run to test multiple things
at once. While your habits may be more orderly
than mine, I would encourage you to find a
way around each obstacle that presents itself.
If you cannot get the data in from the file, can
you feed in a good data set by hand? If you
cannot get readInt to work, is there another way?
Often some problem will be clearer in the morning,
or after you have had a chance to compare notes
with the mailing list. If you work smart, you
can work around many of these problems.
Start simple, and get clever when things work
My early version in the Backtracking function
was quite conservative: I would copy sets and
modify the copy rather than modify the set
directly. I started with something designed
to be easy to debug: since I had a copy of
the original and the manipulated set,
it would be easier to see what had gone wrong.
I'm currently trying to solve a larger challenge
set. I constructed it to have a solution, but my
program hasn't found it yet. Now that I know
my solution works, I can focus on making it
more efficient by removing copies, simplifying
tests, etc. It is easier to make a working
program efficient than to write an efficient
program from scratch. The flip side of this
is that if you need to start with a good design:
you cannot make a silk purse from a sow's
ear.
Save your work
I strongly suggest that you develop some
kind of "source control". This can be
as simple as making backup copies of
working source, or as complex as a
RCS or ClearCase source control.
One goal is to have a backup when you
make a mistake at 2AM and wipe out
your current copy of the program.
Another goal is to have source that
you can take ideas from.
- jeff parker
PS Here is the test case I am working
on at present. I find this much more
challenging than the challenge set.
I designed this to have a solution, but
have only checked this by hand.
27
{1, 6, 15}
{1, 5, 10}
{1, 3, 9}
{1, 10, 17}
{1, 9, 19}
{1, 6, 10}
{1, 9, 13}
{1, 9, 14}
{1, 10, 19}
