Help with a simple algorithm

[Baddox]

My Java2 class is usually a breeze and often even a joke, but for some reason I am having trouble this week with what should be a simple algorithm. What we're doing is taking a list (an array actually) of integers and determining a minimum score for "jumping" through the numbers. The first (left-most) number is always 0, and we must move to the last (right-most) number by either moving one number to the right, or "jumping" over one number and landing two numbers to the right. Any number we land on gets added to the score. When we land on the last number, it gets added as well. Our algorithm must, given the array of numbers, return the best (minimum) possible score. For example, given the numbers:

0 3 80 6 57 10 ,

the best solution is 19, because we land on the underlined numbers:

0 3 80 6 57 10 .

This one's easy to figure out just by looking at it, but for larger lists I'm having trouble finding an algorithm. I don't need help with any of the coding, just the algorithm itself to solve the puzzle. The instructor provided some other lists with the solutions given to help test our code:

0 98 7 44 25 3 5 85 46 4 answer is 87

0 57 59 83 9 42 70 answer is 138

0 20 49 96 53 7 43 77 answer is 186

0 24 17 15 61 49 61 8 65 43 26 99 7 57 97 50 93 6 82 52 answer is 330

[daemonSiege]

this is a pretty simple solution to the problem. there are probably more efficient ways to solve it, but my guess is that you just need one that works.

ok so you are given an array [a b c d e f g h].

The first thing you must do is make the first element the current value. [ {a} b c d e f g h]

Next you will compare b and c. If c < b you will always make c the new current value and add c to the count.

[a b {c} d e f g h]

If b > c then you will need some more comparisons. you will need to compare b + d and c + e

If (c + e) < (b + d) you will make c the new current value and add c to the count

Else you will make b the new current value and add b to the count

Follow this procedure recursively until the entire list is scanned and return the count.

You will also need to add a way to deal with the end of the array since you won't always be able to compare indexes outside the array

Hope this helps and let me know if you have any more trouble or if you find a problem with the algorithm

[g-ram]

If b > c then you will need some more comparisons. you will need to compare b + d and c + e

If (c + e) < (b + d) you will make c the new current value and add c to the count

Else you will make b the new current value and add b to the count

I was going to post something along the lines of your post but right before i posted i realized that i was missing that part and I didn't feel like solving it but yea. thats how I would do it too.

I even wrote up the code for it and will post it if you guys want..

[daemonSiege]

I was going to post something along the lines of your post but right before i posted i realized that i was missing that part and I didn't feel like solving it but yea. thats how I would do it too.

I even wrote up the code for it and will post it if you guys want..

did u write it in java? i wrote a version of it in scheme just to make sure it worked. but yea go ahead and post it

[Baddox]

I believe daemonSiege's solution is correct. I haven't quite coded it all yet, but in pseudo-pseudo code, it's roughly this:

if (counter == a.length - 1 || counter == a.length - 2 || counter == a.length - 3)
        {
            return score + last item in array;
        }
else
        {
            return score + Math.min(jumpIt(a, counter + 1), jumpIt(a, counter + 2));
        }

The if part handles the last 3 items in the array. The else opens up two recursive executions (which of course in turn potentially open up two more recursive executions). Score is just the integer variable keeping track of the sum. I haven't worked enough on it yet, because right now my code is iterating through all the recursions, but isn't totalling the sum, it's just returning the last number from the array. If anyone can explain how to get the sum working I would appreciate it.

[daemonSiege]

Score is just the integer variable keeping track of the sum. I haven't worked enough on it yet, because right now my code is iterating through all the recursions, but isn't totalling the sum, it's just returning the last number from the array. If anyone can explain how to get the sum working I would appreciate it.

There are 2 ways to accomplish this.

The first would be to have a base case and then use deferred operaitons (linear recursion)

For example, the base case would return 0

And the recursion would be something like Score + recursive call

A better way to solve this would be to create a state variable and add it to the parameters. (tail recursion)

For example, your function definition would be something like function(array, current, score)

Then the next recursive call would look something like function(array, (current + 1), (score + array[current]))

This approach is preferred because i believe java optimizes for tail recursion since only one function call is kept on the stack

This is probably pretty confusing if your not familiar with the concept so let me know if u need a better explaination

[g-ram]

Here it is in java. (I even took time to document it!! :) )

EDIT: Finally got it right :)

public static int recurse(int[] a, int x)
    {
    //a: the array your looking for
    //x: your location in the array
        if (x == a.length -1) // base case (end of the array)
            return a[x];
        else if (x >= a.length - 3) // if one or two spots away from the end of the array add current value + end value
            return a[x] + a[a.length - 1];
        else
        {
            if (a[x + 1] > a[x + 2])  // if "b" is greater than "c" we make "c" the current value
               return recurse(a, x + 2) + a[x];
            else
            {
                if (x == a.length - 4) //if it's only 3 away from the end, we can't use x+4...
                {
                    if (a[x + 2] + a[x + 3] < a[x + 1] + a[x + 3]) // so we use x+3 instead (while doing the same thing)
                        return recurse(a, x + 2) + a[x];
                    else                                           // same thing here
                        return recurse(a, x + 1) + a[x];
                }
                else
                {
                    if (a[x + 2] + a[x + 4] < a[x + 1] + a[x + 3]) // if (c + e) < (b + d) we make c the current value
                        return recurse(a, x + 2) + a[x];
                    else                                          //Otherwise, make b the current value
                        return recurse(a, x + 1) + a[x];

                }
            }
        }
    }

[Baddox]

public static int jumpIt(int[] a, int counter)
    {
        int score = 0;
        if (counter == a.length - 1 || counter == a.length-2 || counter==a.length-3)
        {
            cost += a[a.length-1];
            return score;
        }
        else
        {

            return score + Math.min(jumpIt(a, counter + 1), jumpIt(a, counter + 2));
        }
    }

This is my current code, which is obviously not right, because it just returns the last number in each array. It is however, obviously reaching the else statement multiple times before getting to the if part. I'm just getting lost in the way the recursion is operating, obviously I'm never adding to the cost variable.

[daemonSiege]

This is my current code, which is obviously not right, because it just returns the last number in each array. It is however, obviously reaching the else statement multiple times before getting to the if part. I'm just getting lost in the way the recursion is operating, obviously I'm never adding to the cost variable.

The reason that you are just getting the last number is because of this line...

"int score = 0"

Because of this, everytime you have a recursive call it is resetting the score to 0.

Then the function is just returning 0 + the last number

The easiest way to fix this would be to delete that line,

change "return score" to "return 0",

and change the other return statement to be

return a[counter] + Math.min(jumpIt(a, counter + 1), jumpIt(a, counter + 2));