## DEV Community is a community of 891,187 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Daily Challenge #186 - Jumping Frog

### Setup

There is a lonely frog that lives in a pond. Lily-pads are laid out on a coordinate axis atop the pond. The frog can only jump one unit more than the length of the last jump.

With a starting point of 0, reach the target point of `n` using the frog's jumping ability. You can choose to jump forward to backward. Reach the target with the minimal amount of steps.

### Examples

For `n = 2`, the output should be `3`.

```step 1:  0 ->  1  (Jump forward, distance 1)
step 2:  1 -> -1  (Jump backward, distance 2)
step 3: -1 ->  2  (Jump forward, distance 3)```

For `n = 6`, the output should be `3`.

```step 1: 0 -> 1  (Jump forward, distance 1)
step 2: 1 -> 3  (Jump forward, distance 2)
step 3: 3 -> 6  (Jump forward, distance 3)```

### Tests

`n = 1`

`n = 10`

`n = 25`

`n = 100`

`n = 1000`

Good luck!

This challenge comes from myjiinxin2015 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

## Discussion (3) SavagePixie

Some Elixir using recursion:

``````def jump(n), do: jump(n, 1, 1)
def jump(n, step, value)
when rem(value - n, 2) == 0
and value >= n, do: step
def jump(n, step, value), do: jump(n, step + 1, value + step + 1)
`````` My `O(1)` solution in Haskell:

``````jump :: Integral a => a -> a
jump v = let n = ceiling \$ (-1 + sqrt (1 + 8 * (fromIntegral v))) / 2
s = n * (n + 1) `div` 2
s2 = (n + 1) * (n + 2) `div` 2
in  if even (s - v) then n
else if even (s2 - v) then n + 1
else n + 2
``````

I tested this against SavagePixie's solution from 1-10,000 and handwritten tests from 1-36. It passed all those tests. I'll try my best to explain how this works.

The `n` value that is calculated is the 1-indexed index of the first value greater than `v` (the target value) in the recursive sequence `a{n} = a{n-1} + n`. For example, when `v` = 13, `n` = 5 because `a{5} = 15` and `a{4} = 10`.

`s` is the term `a{n}`. `s2` is the term `a{n+1}`.

I determined that there are 3 patterns that will construct a shortest path 3 in different situations, which are represented in the `if` statements.

1. If `s - v` is even, then the target is some even number below a value in the sequence. This is an easy path to construct: to construct `s`, it's simply `1 + 2 + ... + n`, and if `s - v = 4`, then `v = 1 + 2 + ... + n - 4 = 1 - 2 + ... + n`. The length of this path is equal to `n`. This works for any difference, not just 4. The summand that is negated is `(s - v) / 2`.

2. If `s2 - v` is even, it's the same as (1) except with `s2` and `n + 1`, so the path length is equal to `n + 1`. This is longer than (1) when both conditions are met, but shorter than (3) when both conditions are met.

3. In all other cases, a shortest path is to construct a path to `v + 1` and then subtract 1. Subtracting 1 requires 2 operations (ex. 6 - 7 after going to the 5th term). Using 12 as an example, construct the path to 13: `-1 + 2 + 3 + 4 + 5`, then subtract 1: `-1 + 2 + 3 + 4 + 5 + (6 - 7)`. The length is `n + 2`.

I have an intuition of why these are the only three cases, but I can't seem to put it into words right now. Michael Kohl • Edited on

Let's do Reason today, simple recursive version (yes, I stole all variable names from @savagepixie , I'm that lazy):

``````let jump = n => {
let rec jump' = (n, step, value) =>
(value - n) mod 2 == 0 && value >= n ?
step : jump'(n, step + 1, value + step + 1);
jump'(n, 1, 1);
};

``````

The most interesting thing about this for me was that `refmt` turned the pattern match on `true`/`false` i used in `jump'` into a ternary.