4

i'm trying to make a recursive method to check if the last number (always 0) in an integer array (with all > 0 integers) is reachable by increasing (or decreasing) the index of the array with the value of the array element of the current index, while staying within the bounds of the array.

example:

say we have the following array, and the start index == 0:

int[] arr = {3, 6, 4, 1, 3, 4, 2, 5, 3, 0};

step 0 : index = 0, value = 3

step 1 : index = 3, value = 1

step 2 : index = 4, value = 3

step 3 : index = 7, value = 5

step 4 : index = 2, value = 4

step 5 : index = 6, value = 2

step 6 : index = 8, value = 3

step 7 : index = 5, value = 4

step 8 : index = 9, value = 0 -- end

my current code: 

        static bool Solveable(int index, int[] arr)
        {
            if (arr[index] == 0)
                return true;
            if (index + arr[index] < arr.Length)
                return Solveable(index + arr[index], arr);
            if (index - arr[index] >= 0)
                return Solveable(index - arr[index], arr);

            return false;
        }

the thing with this is that it will only work with solveable cases, all other cases will result in a stackoverflow exception.

how would i be able to solve this problem WITHOUT using global variables to store previous results?

EDIT:

I can only use the parameters: (int index, int[] arr)

Improve this question
0

5 Answers 5

Reset to default
2

You are correct about stack overflow for unsolvable cases: the recursive code would behave like a dog chasing its own tail until, until it reaches the stack limit.

Fortunately, you can break this infinite recursion by observing that you have at most N steps to reach the end of the array, if you are to reach it at all. Therefore, you could add a third parameter to indicate how many steps you have taken already. If you reach zero before the number of steps passes N, you have a path; otherwise, you don't have a path.

static bool Solveable(int index, int[] arr, int stepsSoFar) {
    if (arr[index] == 0)
        return true;
    if (stepsSoFar > arr.Length)
        return false;
    ...
    // The rest of your code; pass stepsSoFar+1 down to the next level
}

I can only use the two parameters i included in my code snippet

You can mark the indexes that you have visited in the arr itself by placing -1 into them. In order to preserve array's original state, store the old value in a local variable, and set it back into arr before returning:

static bool Solveable(int index, int[] arr) {
    if (arr[index] == 0)
        return true;
    if (arr[index] == -1)
        return false;
    int oldArrAtIndex = arr[index];
    arr[index] = -1;
    try {
        ...
        // The rest of your code
    } finally {
        arr[index] = oldArrAtIndex;
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

i forgot to mention i can only use the two parameters i included in my code snippet, updated the main post.
Would it really be necessary to preserve and replace the old value? If you replace the index you have visited with -1 and then hit -1 value again, wouldn't it be unsolvable?
Dang. Beat me to it. I was just going to propose the -1 solution, too.
@JoonasKoski The reason for restoring the old value is to leave the array in its original state, i.e. make the search non-destructive. The end must be reached in a single "go" anyway, so it's not essential for the search algorithm itself.
@dasblinkenlight thanks for your answer, the part where you pointed out that i should replace already used entries with -1 solved it for me!
|
1

Pass a third argument that tracks the indices you've already traveled. Stop processing if you've already tried the current index.

Also, you may want to make a change to account for travelling in either direction:

var solvable = false;
//...

if (index + arr[index] < arr.Length)
   solvable = Solveable(index + arr[index], arr);
if (!solvable && index - arr[index] >= 0)
   solvable = Solveable(index - arr[index], arr);

return solvable;
Improve this answer

4 Comments

i forgot to mention i can only use the two parameters i included in my code snippet, updated the main post
How contrived. School assignment?
Do the arguments you pass have to be only "int index" and "int[] arr"?
@dasblinkenlight has the right idea in his answer. Mark the array elements you visited with -1 so you don't reprocess them.
1

School assignment or not, lesson on recursion without all the added complexity.

private static void Main()
{
    int[] array = {3, 6, 4, 1, 3, 4, 2, 5, 3, 0};
    Console.WriteLine(IsSolveable(array));
    Console.ReadKey();
}

private static bool IsSolveable(int[] array)
{
    if (array.Length <= 1)
        return false;

    int index = array[0];
    if (index < array.Length && array[index] == 0)
        return true;

    // this is where the recursion magic happens
    return IsSolveable(array.Skip(1).ToArray());
}
Improve this answer

Comments

0

Instead of passing int index, you can pass an array, containing currently visited indexes, and if your next index is contained inside of array of visited, then you just break and return false.

High level idea of code is:

static void Main(string[] args)
{

    int[] arr = { 3, 6, 4, 1, 3, 4, 2, 5, 3, 0 };
    var result = Solveable(new[] {0}, arr);


    Console.WriteLine(result);
    Console.ReadLine();
}

static bool Solveable(int[] path, int[] arr)
{
    var index = path.Last();

    if (arr[index] == 0)
        return true;
    if (index + arr[index] < arr.Length)
    {
        var nextIndex = index + arr[index];
        var nextStepPath = path.Concat(new[] { nextIndex }).ToArray();

        if (path.Contains(nextIndex))
            return false;

        return Solveable(nextStepPath, arr);                                      
    }
    if (index - arr[index] >= 0)
    {
        var nextIndex = index - arr[index];
        var nextStepPath = path.Concat(new[] {nextIndex}).ToArray();

        if (path.Contains(nextIndex))
            return false;

        return Solveable(nextStepPath, arr);
    }

    return false;
}

It need a bit of cleanup, but gives you high-level idea, and makes use of only 2 parameters without introducing classes/structs for your array.

Improve this answer

Comments

0

Here is an algorithm that does not modify the state:

static bool Solveable(int index, int[] arr)
{
    if (arr[index] == 0)
        return true;
    int nextIndex = index + arr[index];
    if (nextIndex < arr.Length)
        return Solveable(nextIndex, arr);
    // Search for a previous index that leads to a different path
    int prevIndex;
    while (true)
    {
        prevIndex = index - arr[index];
        if (prevIndex < 0)
            return false; // Not found, we are done
        if (prevIndex + arr[prevIndex] != index)
            return Solveable(prevIndex, arr); // Process the other path
        index = prevIndex; // Keep searching
    }
}

The essential part is the non recursive back step processing part (see the comments inside the code).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.