[rswann]

Hi, first time poster. How you all doing?

I'm working on an assignment in which we are given a single line of - or o characters (12 of them).

A "-" represents an empty hole and a "o" represents a peg-filled hole. Pegs can be removed by jumping over other pegs, but only if they have an empty hole to jump into, like so...

oo- <- the first o can jump over the second, which removes the second, and into the empty hole.
o-o <- neither can jump
-oo <- the second o can jump over the first, which removes the first, and into the empty hole.

It's basically like drafts, but you can only move if you are jumping over another peg, and you can move both left and right.

I have to find the minimum number of pegs that can be left. I am having problems working this out. I emailed my tutor as we were given no hints on how to accomplish this, and he said that a brute-force search is feasible as the input size is not that great. I then worked on some pseudocode which looked like this:

count = number of o's;
for (int i = 0; i < size of the array; i++){
	 if (token[i] == "-"){
		  i++;
	 }
	 else if(token[i] == token [i+1]){
		  if(token[i+2] == "-"){
			   token[i+2] = "o";
			   count--;
			   i += 3;
		  }
		  else{
			   i += 3;
		  }
	 }
}

but then realised that this is only going to run UP the line and never down. I am confused at what I should do to rectify this. Has anyone worked on a problem similar to this before? Can they please give me advice or help?

Thank-you!

[LaFayette]

So for every peg (you have left) you have to consider two possibilities. It might be able jump right (and remove the peg to the right) or left (and remove the peg to the left), and then you have to reconsider the problems for the instance in which the the right peg was removed and the one where the left one was (recursive calls?).

This post has been edited by LaFayette: 06 October 2009 - 03:35 AM

[rswann]

You know, I had a feeling this was to do with recursion. I even looked over the Towers of Hanoi problem a few moments ago! I can't seem to get my head around recursion though. Can you please give me an example of how this recursion would work?

[LaFayette]

something like this (without any counting and base cases):

pegCount(arrayOfPegs) {
        while arrayOfPegs not empty {
                take next peg p.
                if p can jump over p_left {
                        create ArrayOfPegs1 with p in right place and p_left removed
                        pegCount(arrayOfPegs1)
                if p can jump over p_right {
                        create ArrayOfPegs2 with p in right place and p_right removed
                        pegCount(arrayOfPegs2)
          }
          remove p from arrayOfPegs.
}

edit: In the above it looks like the collection of pegs and the actual peg-hole-line is in the same datastructure (arrayOfPegs). They could be, but perhaps shouldnt.

This post has been edited by LaFayette: 06 October 2009 - 04:01 AM

[rswann]

thank-you, i will look at your example and also look into recursions a bit more then see what I can come up with.

I'm not great with data structures, even after spending a whole course on them! I'll still give it a go though, of course.

edit: I wonder if this might be a bit too complicated for me actually. I need to learn this though.

This post has been edited by rswann: 06 October 2009 - 04:04 AM

[rswann]

I've been working on this but am just at a loss for what to do. My programming skills aren't the best. I'm trying to make canJumpLeft and canJumpRight method but I'm just hopeless. Can anyone show me how I can go about doing this? I've tried

public boolean canJumpLeft(String[] s, String p){
			if(s[p] == "o"){
				if(s[p-1] == "o" && s[p-2] == "-"){
					return true;
				}
			}
			return false;
}

but I am of course getting errors because it is wrong.

edit: I know I should also check to make sure that I don't get an ArrayOutOfBounds exception...

This post has been edited by rswann: 06 October 2009 - 07:49 PM