Discussion on: Daily Challenge #186 - Jumping Frog

[Craig McIlwrath]

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.