Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

How to find cheapest path through an array

recursion java

This topic has been archived. This means that you cannot reply to this topic.
5 replies to this topic

#1 stacker9752

stacker9752

    CC Lurker

  • New Member
  • Pip
  • 3 posts

Posted 18 October 2015 - 12:52 PM

Hi there! This is my first post so bare with me :). I am currently working a question that involves recursion and its getting tough for me to wrap this one around my head. 

 

The question:    The game of “Jump It” consists of a board with n positive integers in a row except for the first column, which always contains zero. These numbers represent the cost to enter each column. Here is a sample game board where the length is 5:

0, 1, 3, 4, 1
The object of the game is to move from the first column to the last column in the lowest total cost. The number in each column represents the cost to enter that column. You always start the game in the first column and have two types of moves. You can either move to the adjacent column or jump over the adjacent column to land two columns over. The cost of a game is the sum of the costs of the visited columns.

 

In the case above the cheapest way would be to jump to index 2 (value 3) then jump to index 4 (value1) for a total cost =4

How can i recursively work through this problem to find the cheapest way no matter how large the game board is. 



#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts

Posted 18 October 2015 - 01:54 PM

This may sound like a strange question, but why do you want to solve this with recursion?

 

I would approach this by having a couple of parallel arrays where you indicate the cost to get to that location, and the path you would arrive there from to get that lowest cost. The result would be the following:

 

To enter:      0, 1, 3, 4, 1

Net Cost:     0, 1, 3, 5, 4

Come from: 0, 0, 0, 1, 2

Then you can work backwards (maybe the recursion step comes in here? but you can build your output string non-recursively so no need...) to determine your path: so you get to index 4 from index 2 from index 0.


Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 stacker9752

stacker9752

    CC Lurker

  • New Member
  • Pip
  • 3 posts

Posted 18 October 2015 - 02:36 PM

assignment guidelines says it MUST be recursive. Really appreciate the insight! So all i need is the lowest cost! I dont need to output the path taken what-so-ever. Just the lowest cost it can take to get to the end of the array so my output for 0,1,3,4,1 would be 4 because i can jump to 3 then jump to 1.


Edited by stacker9752, 18 October 2015 - 02:39 PM.


#4 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts

Posted 19 October 2015 - 04:42 AM

Okay, here's a way to do it "recursively": The total cost of entering the current node = cost entry of current node + min(total costs of previous 2 nodes)


Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#5 stacker9752

stacker9752

    CC Lurker

  • New Member
  • Pip
  • 3 posts

Posted 19 October 2015 - 05:42 AM

I am very close but something is off! any ideas? 
 

public int play() throws BadInputException {
    if (ValidArray[0] != 0) {
        throw new BadInputException();
    }
    return minimumCost(0, ValidArray);
}

private static int minimumCost(int cell, int cost[]) {
    if (cell >= count) {
        return 0;
    }
    int jump = cost[cell] + minimumCost(cell + 2, cost);
    int move = cost[cell] + minimumCost(cell + 1, cost);

    if (move < jump) {
        cell += 1;
        System.out.printf("Move to cell %d.\n", cell);
        return move;
    } else {
        cell += 2;
        System.out.printf("Jump to cell %d.\n", cell);
        return jump;
    }
}
 
validarray is my game board and count is the length of validarray.

Edited by dargueta, 21 October 2015 - 07:05 PM.
Added code formatting.


#6 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts

Posted 19 October 2015 - 09:24 AM

Can you provide some sample inputs and outputs, since we don't have code that can be compiled?


Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/