Flamera Flamera - 1 month ago 28
Java Question

How to try all possible way of traversing Array of integer

I'm new in programming and I'd like some help for an assignment, I only need a little clue to help me getting started (no answer, I only want to get a direction of how to do it then work my way).

The rules of the game : on the initial square is a marker that can move to other squares along the row. At each step in the game, you may move the marker the number of squares indicated by the integer in the square it currently occupies. The marker may move either left or right along the row but may not move past either end.
The goal of the game is to move the marker to the cave, the “0” at the far end of the row. In this configuration, you can solve the game by making the following set of moves:

eg: 2 3 1 2 4 0

first: move of 2 (to the right since it's impossible to go to the left) then: either move 1 to the right or 1 to the left then: if we moved left before: move 3 to the right (cannot go 3 to the left) if we moved right before then it's either 2 to the left or 2 to the right. 2 to the right is the right answer since then the next value is 0.

I must write the program that will try all the possibilities (so using a loop or a recursive I guess?) and return TRUE if there's a solution or FALSE if there are no solution. I had to choose the data structure from a few given by the prof for this assignment and decided to use an Array Based List since the get() is O(1) and it's mainly the only method used once the arraylist is created.

My program is only missing the (static?) method that will evaluate if it's possible or not, I dont need help for the rest of the assignment.
Assume that the ArrayBasedList is already given.

Thanks for your help!


I think your idea about using a recursive method makes a lot of sense. I appreciate you don't want the full answer, so this should just give you an idea:

  1. Make a method (that passes in an integer x of the current position and your list) that returns a boolean.
  2. In the method, check the value of list.get(x).
    1. If it's 0, return true.
    2. If it's -1, return false (more on that later).
  3. Otherwise, store the value in a variable n, replace it with a -1, and return method(x+n) || method(x-n).

What the -1 does is it eventually fills everything in the array with a value that will terminate the program. Otherwise, you could end up with an infinite loop (like if you passed in [1, 2, 4, 2, 3]) with the value going back and forth.

A couple of things to keep in mind:

  1. You'd need to make a new copy of the array every time, so you don't keep overwriting the original array.
  2. You'd need to incorporate a try-catch (or equivalent logic) to make sure you are not trying to measure out of bounds.

If you have any further questions, feel free to ask!