minimum array jumps to reach the end

[darshanghorpade]

For a given array of integers, reach to the end of the array from the 0th index with minimum number of moves. Moves possible at each index:

Move from index i to index (i+1)
Move from index i to index (i-1)
Move from index i to index j, if a[i] == a[j]

Input
The first line of each test case contains a single integer T denoting the number of test cases. Each test consists of two lines. First line denotes N the number of elements in the array. Second line contains N space separated integers.

Output
For each test case, output a single line containing minimum number of moves possible

Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 20
1 ≤ Ai ≤ 105
Example
Input:
2
6
1 2 3 4 5 6
11
2 3 5 1 4 3 2 6 7 8 4

Output:
5
4

[Dani]

Move from index i to index (i+1)

I haven't looked at C++ in forever, but if you are at array[i] then can you just move to the next one by doing array[++i]?? My assumption would be that ++i would first increment i, and then trieve the array element at the incremented index.

Move from index i to index (i-1)

So then to go from index i to index i - 1 I suppose would be array[--i]?

Move from index i to index j, if a[i] == a[j]

Does that mean that we need to loop through all the elements in the array checking if they have the same value as a[i], so that we can find the value of j?

The first line of each test case contains a single integer T denoting the number of test cases. Each test consists of two lines. First line denotes N the number of elements in the array. Second line contains N space separated integers.

Sorry, I have no clue what this means? What test case is being referred to? Is this homework assignment a continuation of something that was explained in class? I don't understand what the contraints are. What is T, N, and Ai?

[chuckc]

I’m with Dani on this, it seems like something from the assignment is missing. Maybe the purpose is to get students familiar with using arrays. It would be interesting to see what the instructor considers a good solution.

[darshanghorpade]

T is the number of test cases
N is the size of an array and
Ai is an array element
If you look at input format you will get it

[Dani]

Oh, I see. So you know that there is an array A that has n elements in it. So that means the indexes of the array are from 0 to n-1.

Now you are beginning at the head of the array, element A[0]. Your goal is to get to array element A[n-1].

But, like a game of chess, you need to do it in as few moves possible, and the only moves you're capable of doing are:

• Moving to the next element
• Moving to the previous element
• Swapping with another element that has the same value as the element you're on

Sooooo ... let's forget about code for a moment. Have you come up with an algorithm to achieve this?

Obviously the brute force way is to just keep moving to the next element, from index 0 to index, n - 1 times, until you get to the end of the array. But that isn't efficient at all.

So, here's a thought. Let's say our array looks like this:

5.   2.   6.   9.   4.   4.   6.    1.

So the algorithm that I would use is:

• We start at the first element in the array (A[0]) and we see that it's value is 5. We know we can jump ahead if there are any other elements that also have a value of 5. Because our goal is to get to the end of the array as quick as possible, let's start at the end of the array, and work backwards, and see if we can find another 5. So 1? 6? 4? 4? 9? 6? 2? Nope, we're back where we started, so let's move on.
• We move on to the next element, A[1] with a value of 2. Let's work backwards again and see if we can get there: 1? 6? 4? 4? 9? 6? Nope, we're back where we started, so let's move on.
• We move on to the next element, A[2] with a value of 6. Our goal is to jump ahead to the end. So 1? Nope. 6? Yes!! We found another 6, meaning we can jump ahead all the way to there. So now we can move from A[2] all the way to A[6]. But there are 8 elements in the array, meaning we need to get to A[7].
• Let's move one piece to the right to A[7]. Now we're at the end.

Of course, this algorithm relies on the fact that we can snoop at the entire array even if we can't move our "game piece" any way other than those 3 ways. Sort of like a game of chess where you can see the whole chess board but you can only move in a limited number of ways.

If this algorithm makes sense to you, why don't you try coding it up and see where you get stuck, and then I can help you from there.

[JamesCherrill]

Consider the array
1 2 3 4 5 2 6 7 8 3
your algorithm will find the 2 and jump, missing the better solution jumping on 3.
you need to continue searching; your first jump solution is just the best so far.
Of course there may be multiple jumps on different numbers as part of the optimum solution, so you'll want a recursive tree search to find the optimum. But your algorithm will greatly reduce the size of the tree.

[Dani]

Thanks JamesCherrill! I wasn't thinking it through. I guess I was more focused on how the assignment says one of the 3 moves you can make is the ability to move backwards. If you're able to "see" the entire array at all times, why would you ever need the ability to move backwards? I feel like we're still misunderstanding the complete assignment.

But you're right. This assignment is probably meant to be an exercise on writing a recursive search algorithm.

[chuckc]

Thank you darshanghorpade, and Dani, for sharing thoughts on this exercise. It is good to stretch one’s thinking with challenges that go beyond routine analysis and programming.

[JamesCherrill]

Backwards step? Consider 1 x x x 3 1 x x x3
Shortest solution requires the back step from 1 to 3

[Fifth Horseman]

The input may be described as an array, but you'll actually solve the assignment by treating it as a graph.
Each index i has a 1-length route to i+1 and i-1, as well as a 1-length route to any j located ahead of itself that has the same value.
Create a NxN 2D array, populate it with the route lengths and apply Djikstra's Algorithm to find the shortest path from the first to last node.