Fun little algorithms challenge

[fletch to 99]

A monkey is trying to cross a river, that is slowly going down. He wants to cross the river at the earliest possible time. The monkey is able to jump up to k stones.

One assumption can be made: the time it takes the monkey to make jumps between stones in negligible the value of the max stone he must jump to is the time at which he can cross the river.

 

The input looks like this:

r, an array of integers >= -1 representing the time at which the stone becomes available to jump to. If the stone is -1, then there is no stone at that location.

k, an integer > 0 and less than the length of r

 

For example:
r = [6, 3, 0, 1, -1, 4, 7, 2, 5, 1, 3]
k = 3

Time monkey can cross at: 4. This is because the monkey needs to hop on the stone available at time 4 to be able to successfully cross the river.

 

Here is what we want to know:
1. Create an algorithm to find the earliest time the monkey can cross the river. If the monkey cannot cross the river then simply return -1.
2. What is the running time of this algorithm?
3. Is there a faster solution to the problem, if so how would it work?

 

I've got a solution that runs in O(nk) time. If you're interested you can check it out here but I suggest trying before looking! 

[mariushm]

I honestly couldn't understand the problem as written, so I had to google the problem.

 

It would actually help if you'd write it properly:

 

Quote

A frog is trying to get to the other side of the river. Initially on side of the bank (position -1) and wants to get to the other side of the bank (position N).

The frog can jump any distance between 1 and D. If D is less than N, frog cannot jump directly. There are stones to help the frog jump but they will be out of the water only after certain time as water is constantly decreasing. The frog can jump to and from the stones only when the stone is out of water. The stones in the river are described in Array A consisting of N integers. A[K] represents a time when a stone at position K will be out of water. A[K]=-1 means no stone at that position. Goal is to find the earliest time the frog can reach the other bank.

Example D=3, N=6.
A[0]=1

A[1]=-1

A[2]=0

A[3]=2

A[4]=3

A[5]=5

At time 2, 3 stones will be out of water and the frog can jump to the other bank in 3 jumps.

 

Maybe this will help : http://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/13/Slides13.pdf

 

You can also find this problem on Stack Overflow or just by googling "a frog is trying to get to the other side of the river."

 

[fletch to 99]

2 hours ago, mariushm said:

I honestly couldn't understand the problem as written, so I had to google the problem.

 

It would actually help if you'd write it properly:

 

 

Maybe this will help : http://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/13/Slides13.pdf

 

You can also find this problem on Stack Overflow or just by googling "a frog is trying to get to the other side of the river."

 

I'm not trying to solve it, I've already created a solution. I posted the problem for others to try.

[straight_stewie]

@fletch to 99 Can you give more examples of K and R values with the expected output? I'm having trouble figuring the relationship between the K values and the R values.

[fizzlesticks]

r = [6, 3, 0, 5, -1, 4, 7, 2, 5, 1, 3]
k = 2
print(next((ind for ind, m in enumerate([max((lambda y: [s - f for f, s in zip(y, y[1:])])((lambda x: [0] + list(filter(lambda x: x is not False, [j if 0 <= x <= i else False for j, x in enumerate(r)])) + [len(r)])(i))) for i in range(max(r))]) if m <= k), -1))

I think that's correct. I could work the input into the one line but that would just be silly.

[Nineshadow]

Eh, not such an interesting problem.