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}