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!
Top comments (2)
Some Elixir using recursion:
My
O(1)
solution in Haskell: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 thanv
(the target value) in the recursive sequencea{n} = a{n-1} + n
. For example, whenv
= 13,n
= 5 becausea{5} = 15
anda{4} = 10
.s
is the terma{n}
.s2
is the terma{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.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 constructs
, it's simply1 + 2 + ... + n
, and ifs - v = 4
, thenv = 1 + 2 + ... + n - 4 = 1 - 2 + ... + n
. The length of this path is equal ton
. This works for any difference, not just 4. The summand that is negated is(s - v) / 2
.If
s2 - v
is even, it's the same as (1) except withs2
andn + 1
, so the path length is equal ton + 1
. This is longer than (1) when both conditions are met, but shorter than (3) when both conditions are met.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 isn + 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.