This is an exam question I couldn't solve and I need to solve it because I can face it in my next exam again ( and it decides whether you get a D or an A).
The problem:
"Two robots R1 and R2 carry boxes around a factory. R1 can carry 1 or 3 or 5 boxes at once, whereas R2 can carry 2 or 4 boxes at once. If there are 34 boxes, write a C# program that finds every movement combination of robot R1 and R2 carrying all the boxes. The movements occur in such a way that one robot may move after the other one (R1 gets the boxes, carries them in the required destination, and then R2 can go next). Also show which combination allows carrying all the boxes with minimal movement.
Possible combination: (R1=5,R2=4), (R1=3,R2=4), (R1=3,R2=2), (R1=3,R2=2), (R1=3,R2=2), (R1=1,R2=2)"
The problem is that I don't even know where to start. I wrote some possible combinations hoping that I might get a clue to start somewhere. I tried a program, but it didn't work (printed the numbers of boxes until the number of boxes after being taken from the robots was not negative: boxes-(r1+r2)>=0, which is one specific case out of every possible combination)
I found a program from an older student who sent me the following windows form code:
private void button1_Click(object sender, EventArgs e)
{
int Min = 34;
string stMin = "";
for(int i1=0;i1<=34;i1++)
for (int i2 = 0; i2 <= 34; i2++)
for (int i3 = 0; i3 <= 34; i3++)
for (int j1 = 0; j1 <= 34; j1++)
for (int j2 = 0; j2 <= 34; j2++)
for (int j3 = 0; j3 <= 34; j3++)
{
if (i1 * 3 + i2 * 4 + i3 * 5 + j1 * 1 + j2 * 2 + j3 * 3 == 34 && i1 > 0 && i2 > 0 && i3 > 0 && j1 > 0 && j2 > 0 && j3 > 0 && (i1 + i2 + i3 == j1 + j2 + j3))
{
if(i1+i2+i3+j1+j2+j3<Min)
{
Min = i1 + i2 + i3 + j1 + j2 + j3;
stMin = "R1 =>" + i1 + " x 3, " + i2 + " x 4 " + i3 + " x 5 " + "R2 =>" + j1
+ " x 1 " + j2 + " x 2 " + j3 + " x 3 ";
}
string st = "R1 =>" + i1 + " x 3, " + i2 + " x 4 " + i3 + " x 5 " + "R2 =>" + j1
+ " x 1 " + j2 + " x 2 " + j3 + " x 3 ";
listBox1.Items.Add(st);
}
listBox1.Items.Add("==========Min=========");
listBox1.Items.Add(stMin);
}
}
I analyzed it for 3 days but I don't know how this code works. Asked him for explanation but he says it's not his code, doesn't remember where he got it nor knows if it even works. I also asked friends and colleagues but no one knows how to solve it.
I would appreciate if someone could give me an idea or a piece of code to start with the solution (writing the full code would be great, and no I won't copy paste it into my exam, I will look up to understand every step of the code).
Side info: I am a novice programmer. My professor taugh us basic stuff like reading input from users, using loops and creating classes. My self-learning didn't reach such a complex problem, so please explain your solution as deep and specific as possible.
Well, since you are still curious let's solve the probem.
It is a classic one and as usual the first thing is to be very clear about the conditions:
The are these possible combination: (R1=5,R2=4), (R1=3,R2=4), (R1=3,R2=2), (R1=3,R2=2), (R1=3,R2=2), (R1=1,R2=2)
The starting box count is 34
This implies that we are done when all boxes are gone and also that we are on an invalid combination of moves if we have 1 or 2 boxes left, since these can't be moved by any of our combinations.
Let's next create a nice data structure to hold the allowed combinations so we can use it in a loop; let's call those 'full moves':
Dictionary<string, int> fullMoves = new Dictionary<string, int>();
We will store the moves as strings and will also store the total count of boxes moved by each combination..
Next we need to fill the data structure:
for (int i = 1; i <= 5; i += 2)
for (int j = 2; j <= 4; j += 2)
fullMoves.Add(i + "-" + j + " ", i + j);
Test this with the debugger to see that is works!
Now let's get down to business: We need a function to do the real work.
As I have explained in my comments this is a typical problem for a recursive solution. All the choices create a tree of paths to take (i.e. sequences of full moves) and trees (almost) always call for a recursive aproach. It will call itself over and over again, passing out the current state of affairs until is is done, i.e. has reached a 'halting condition'.
The abstract goal is this:
Here is a piece of code that does just that. It passes on both a list of current paths and of correct solutions found so far. Also the new path and the count of boxes still left.
void moveBoxes(int count, string curMove, List<string> curMoveList, List<string> solutions)
{
// test for halting conditions:
// 1) count == 0: we're done with this solution
if (count == 0)
{
solutions.Add(curMove);
return;
}
// 2) less than three boxes: invalid solution:
else if (count < 3)
{
curMoveList.Remove(curMove);
return;
}
// keep moving..:
foreach (string cm in curMoveList)
foreach (string k in fullMoves.Keys)
{
int bc = count - fullMoves[k];
moveBoxes( bc, curMove + k, curMoveList, solutions );
}
}
You can see that is is rather short. This is one feature often found in recursive solution. Another is that it takes a little practice to wrap your head around. Look here for a simpler example, which collects TextBoxes from nested containers in a form!
Let's put it to the test! Here is a testbed that runs the code for a number of box numbers and writes out to the console how many solutions you get for each starting number. The solution for the last starting number (34) is also written out to a TextBox.
List<string> solutions = new List<string>();
List<string> curMoveList = new List<string>();
for (int ccc = 10; ccc <= 34; ccc++)
{
solutions = new List<string>();
curMoveList = new List<string>();
int count = ccc;
curMoveList.Add("");
moveBoxes(count, "", curMoveList, solutions);
Console.WriteLine(ccc + " boxes can be moved in " + solutions.Count + " ways.\r\n");
}
StringBuilder sb = new StringBuilder();
foreach (string s in solutions) sb.Append(s.Length / 5 + " moves: " + s + "\r\n");
textBox1.Text = sb.ToString();
Here is the console output:
10 boxes can be moved in 8 ways.
11 boxes can be moved in 6 ways.
12 boxes can be moved in 11 ways.
13 boxes can be moved in 18 ways.
14 boxes can be moved in 16 ways.
15 boxes can be moved in 36 ways.
16 boxes can be moved in 36 ways.
17 boxes can be moved in 58 ways.
18 boxes can be moved in 86 ways.
19 boxes can be moved in 98 ways.
20 boxes can be moved in 172 ways.
21 boxes can be moved in 201 ways.
22 boxes can be moved in 304 ways.
23 boxes can be moved in 432 ways.
24 boxes can be moved in 549 ways.
25 boxes can be moved in 856 ways.
26 boxes can be moved in 1088 ways.
27 boxes can be moved in 1587 ways.
28 boxes can be moved in 2220 ways.
29 boxes can be moved in 2966 ways.
30 boxes can be moved in 4364 ways.
31 boxes can be moved in 5798 ways.
32 boxes can be moved in 8284 ways.
33 boxes can be moved in 11529 ways.
34 boxes can be moved in 15760 ways.
Maje sure to collect the output in a Stringbuilder; creating 15k strings is expensive and adding them directly to a TextBox take a real long time..
Bonus* questions: