Hackbright Code Challenges

Monkey River Crossing

« Back to Homepage

Monkey River Crossing

Whiteboard

Harder

Challenge

Medium

Concepts

Logic, Lists

Download

monkey.zip

Solution

Monkey River Crossing: Solution


../_images/monkey.jpg

In this problem, a monkey is trying to jump across a certain distance across a river, using stones in the river to break his jumps into sections. The stones are evenly spread across the river.

However, the monkey can only jump N number of stones-lengths at a time.

As an added piece of complexity, the water level is decreasing with each hour, and as the water level gets lower, more stones emerge for the monkey to use to cross the river.

For example, imagine a river like this:

digraph monkeydiag { rankdir=LR river -> midnight -> "2 am" -> "1 am" -> "3 am" -> "6 am" -> "9 am" -> shore river [label="R I V E R" shape="rect"] shore [label="S H O R E" shape="rect"] }

  • If our monkey can only jump one stone at a time, it couldn’t get across the river until 9 am (since it has to use every stone, and the last stone isn’t available until 9 am.

  • If our monkey can jump 2 stones at a time, the earliest landing time is 6 am. It could jump: midnight to 2 am to 1 am to 3 am to 6 am to the shore.

  • If our monkey can jump 3 stones at a time, the earliest landing time is 3 am. It could jump: midnight to 3 am to the shore.

  • If our monkey can jump 4 stones at time, the earliest landing time is 1 am. It could jump: 1 am to the shore.

Our problem is, given a river and the number of jumps the monkey can make, to calculate the earliest arrival time, like those examples.

Data Structure

The stone timing data can be stored as a list. For example, this list:

[ 1, 2, 5, 0, 3, 4 ]

Would mean:

  • one stone at 1 am

  • one stone at 2 am

  • one stone at 5 am

  • one stone at midnight

  • one stone at 3 am

  • one stone at 4 am

Important: stone times are unique. A time will never be used more than once.

So, for the above array, at time t, the stones would emerge as the following:

t     RIVER (* stone, - no stone)
-     ---------------------------
0     [ -  -  -  *  -  -  ]
1     [ *  -  -  *  -  -  ]
2     [ *  *  -  *  -  -  ]
3     [ *  *  -  *  *  -  ]
4     [ *  *  -  *  *  *  ]
4     [ *  *  *  *  *  *  ]

Write a function that given the stones in the river as represented above, and the number of stones the monkey is able to jump, the soonest time t that the monkey would be able to make it across the river.

The code should work like this:

>>> earliest_arrival(3, [1, 2, 3, 0])
1

>>> earliest_arrival(2, [1, 2, 3, 0])
2

>>> earliest_arrival(3, [1, 4, 0, 2, 3, 5])
2

>>> earliest_arrival(5, [5, 2, 3, 8, 9, 99, 4, 0])
3

We’ve created a stub for earliest_arrival. Implement it.