Find algorithm: Bear jumping/walking over traps

Find algorithm: Bear jumping/walking over traps
0

#1

Hello,

So I’ve have the following problem to solve:

Let’s take an animal, here a bear. The bear is placed at position 0 on a straight line of length L (0, 1, 2, …, L-1). There are several traps on the line indicated by the array traps[]. The bear can walk from position i to position i+1, or he can jump from position i to position i+J. J is the number of position he can jump during one single jump. The bear can always jump excactly J positions, not less not more.
The task is to find the furthest distance the bear can move without getting into a trap!

So here’s an example:

L = 15
J = 4
traps = {4, 6, 8, 11, 13, 14}
-> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

The bear can move maximum to position 10.
It first moves to 1, then jumps to 5, jumps again to 9 and then finally moves 1 further to 10.
It can’t move from 9 to 13 as there is a trap, neither from 2 to 6, etc.

Is there an algorithm that finds the furthest distance the bear can get? And how does it work?
I was thinking of an algorithm that uses recursion or maybe using dynamic programming?


#2

Firstly, welcome to the forums.

While we are primarily here to help people with their Free Code Camp progress, we are open to people on other paths, too. Some of what you are asking is pretty trivial in the Free Code Camp context, so you might find that if you’re not getting the instruction and material you need in your current studies, the FCC curriculum will really help you get started. At a modest guess I’d say investing a 4-5 hours working through the curriculum here will really pay off. You can find the curriculum at https://freecodecamp.org.

With your current questions, we don’t have enough context to know what you already know or don’t know, so it is impossible to guide you without just telling you the answer (which we won’t do).

It is pretty typical on here for people to share a codepen / jsfiddle example of what they have tried so that anyone helping has more of an idea of what help is actually helpful.

Please provide some example of what you’ve tried and I’m sure you’ll get more help.

Happy coding :slight_smile:

(Hahaha @randelldawson is too slow)