Assignment regarding, dynamic programming. Making my code more efficient?

Question

I've got an assignment regarding dynamic programming. I'm to design an efficient algorithm that does the following: There is a path, covered in spots. The user can move forward to the end of the path using a series of push buttons. There are 3 buttons. One moves you forward 2 spots, one moves you forward 3 spots, one moves you forward 5 spots. The spots on the path are either black or white, and you cannot land on a black spot. The algorithm finds the smallest number of button pushes needed to reach the end (past the last spot, can overshoot it). The user inputs are for "n", the number of spots. And fill the array with n amount of B or W (Black or white). The first spot must be white. Heres what I have so far (Its only meant to be pseudo):

int x = 0
int totalsteps = 0
n = user input
int countAtIndex[n-1] <- Set all values to -1 // I'll do the nitty gritty stuff like this after 
int spots[n-1] = user input

pressButton(totalSteps, x) {
    if(countAtIndex[x] != -1 AND totalsteps >= countAtIndex[x]) {
        FAILED } //Test to see if the value has already been modified (not -1 or not better)
    else
        if (spots[x] = "B") {
            countAtIndex[x] = -2 // Indicator of invalid spot
            FAILED }
        else if (x >= n-5) { // Reached within 5 of the end, press 5 so take a step and win
                GIVE VALUE OF TOTALSTEPS + 1 A SUCCESSFUL SHORTEST OUTPUT 
                FINISH }
        else
            countAtIndex[x] = totalsteps
            pressButton(totalsteps + 1, x+5) //take 5 steps
            pressButton(totalsteps + 1, x+3) //take 3 steps
            pressButton(totalsteps + 1, x+2) //take 2 steps
}

I appreciate this may look quite bad but I hope it comes across okay, I just want to make sure the theory is sound before I write it out better. I'm wondering if this is not the most efficient way of doing this problem. In addition to this, where there are capitals, I'm unsure on how to "Fail" the program, or how to return the "Successful" value. Any help would be greatly appreciated.

I should add incase its unclear, I'm using countAtIndex[] to store the number of moves to get to that index in the path. I.e at position 3 (countAtIndex[2]) could have a value 1, meaning its taken 1 move to get there.

you have the intuition right, your function parameters are right. However you are missing a bit on the implementation. else if (x >= n-5) will run for every solution possible, so it is not true that when that is reached, that is the optimal solution (shortest). The optimal solution is the one from those where totalSteps is minimum. Also unclear how first part works as you don´t show how you update countAtIndex[x]. Note that you can reach same place (x) in different steps (totalsteps) so if you are interested in getting the path you used later on, will need to use countAtIndex[x][totalSteps] — juvian
– juvian, Commented Nov 13, 2018 at 18:31
Hey thanks for the answer. Guess I just wanted to know if my thoughts were sound and not all over the place. I forgot to type in the update for countAtIndex[X] at on the last else statement, but don't know if that affects what you've said much. Gonna revise this over. Thanks again :) — TheButterWorm
– TheButterWorm, Commented Nov 13, 2018 at 19:11
There are always two ways to solve a dynamic programming problem: top-down with memoization, or bottom-up by systematically filling an output array. The one thing they have in common is a recurrence relationship that selects the best answer from 2 or more choices. That concept (choosing the best value for countAtIndex[x]) seems to be absent from your code. As a side note, you seem to have chosen a recursive top-down approach, where my intuition says that a bottom-up iterative solution would be less code. — user3386109
– user3386109, Commented Nov 13, 2018 at 19:14
So my question to you: did the assignment specify that you're supposed to implement a top-down recursive solution with memoization, or are you allowed to choose any implementation that uses dynamic programming? — user3386109
– user3386109, Commented Nov 13, 2018 at 19:43
Any implementation will do, no specifics required. "Describe an efficient algorithm that determines the minimum number of buttons that you need to push in order to win." In addition to this it says "Hint: Use dynamic programming", but thats kind of a given. — TheButterWorm
– TheButterWorm, Commented Nov 13, 2018 at 21:22

user3386109 · Accepted Answer · 2018-11-14 01:03:34Z

I'm converting my comment into an answer since this will be too long for a comment.

There are always two ways to solve a dynamic programming problem: top-down with memoization, or bottom-up by systematically filling an output array. My intuition says that the implementation of the bottom-up approach will be simpler. And my intent with this answer is to provide an example of that approach. I'll leave it as an exercise for the reader to write the formal algorithm, and then implement the algorithm.

So, as an example, let's say that the first 11 elements of the input array are:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B  ...

To solve the problem, we create an output array (aka the DP table), to hold the information we know about the problem. Initially all values in the output array are set to infinity, except for the first element which is set to 0. So the output array looks like this:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - x - x x x - - x -

where - is a black space (not allowed), and x is being used as the symbol for infinity (a spot that's either unreachable, or hasn't been reached yet).

Then we iterate from the beginning of the table, updating entries as we go.

From index 0, we can reach 2 and 5 with one move. We can't move to 3 because that spot is black. So the updated output array looks like this:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - 1 - x 1 x - - x -

Next, we skip index 1 because the spot is black. So we move on to index 2. From 2, we can reach 4,5, and 7. Index 4 hasn't been reached yet, but now can be reached in two moves. The jump from 2 to 5 would reach 5 in two moves. But 5 can already be reached in one move, so we won't change it (this is where the recurrence relation comes in). We can't move to 7 because it's black. So after processing index 2, the output array looks like this:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - 1 - 2 1 x - - x -

After skipping index 3 (black) and processing index 4 (can reach 6 and 9), we have:

index:  0 1 2 3 4 5 6 7 8 9 10 ...
spot:   W B W B W W W B B W B
output: 0 - 1 - 2 1 3 - - 3 -

Processing index 5 won't change anything because 7,8,10 are all black. Index 6 doesn't change anything because 8 is black, 9 can already be reached in three moves, and we aren't showing index 11. Indexes 7 and 8 are skipped because they're black. And all jumps from 9 are into parts of the array that aren't shown.

So if the goal was to reach index 11, the number of moves would be 4, and the possible paths would be 2,4,6,11 or 2,4,9,11. Or if the array continued, we would simply keep iterating through the array, and then check the last five elements of the array to see which has the smallest number of moves.

Hey man thanks a lot for putting it like this. It was hard to see before. I think I've sorted an algorithm with runtime O(n) for this problem.

Collectives™ on Stack Overflow

Assignment regarding, dynamic programming. Making my code more efficient?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related