Deciding on an algorithm for 'Jumping Jack'

Question

A while back in a programming competition I encountered a puzzling problem, and it has bothered me since. Although I do not remember it verbatim, I will do my best to reproduce it:

Jack starts at 0 on the number line and jumps one unit in either direction. Each successive jump he makes is longer than the previous by 1 unit, and can be made in either direction. Write a program that takes a number and returns the minimum number of jumps Jack makes to reach that number.

I apologise in advance if this is not deemed a good question, or if the title is deemed misleading.

Answer 1

I'd like to elaborate on @supercat's correct and fast solution and describe an algorithm that computes a minimal length sum in addition to computing the length of such a sum.

Algorithm

Find the least integer k such that t_k := 1 + 2 + 3 + ... + k >= |n| and t_k has the same parity as |n|. Then flip the signs of the summands of t_k in a systematic way to total n.

Here are the details. Notice that t_k = k(k + 1)/2, a triangular number. Setting t_k = |n| and solving for k gives the ceiling of (-1 + sqrt(1 + 8|n|))/2. So k equals the ceiling or 1 or 2 plus it, whichever of those three numbers has the same parity as n and is least. Here we're using the fact that the set {t, t + s, t + s + (s + 1)} of three consecutive triangular numbers contains both even and odd numbers for any positive integers t, s. (Simply check all four parity possibilities for t and s.)

To find a minimal length sum for n, first compute d := (t_k - n)/2. Because t_k >= |n| and t_k and n have the same parity, d lies in the set {0, 1, 2, ..., t_k}. Now repeatedly subtract: d = a_k (k) + r_k, r_k = a_{k-1} (k-1) + r_{k-1}, ..., r_2 = a_1 (1) + r_1, choosing each a_i maximally in {0, 1}. By the lemma below, r_1 = 0. So d = sum_{i=1}^k a_i i. Thus n = t_k - 2d = sum_{i=1}^k i - sum_{i=1}^k 2a_i i = sum_{i=1}^k (1 - 2a_i) i and 1 - 2a_i lies in {-1, 1}. So the sequence b_i := 1 - 2a_i is a path, and by the minimality of k, b_i is a minimal path.

Algorithm example

Consider the target number n=12. According to Algorithm 3, the possibilities for k are 5, 6, or 7. The corresponding values of t_k are 15, 21, and 28. Since 28 is the least of these with the same parity as n, we see that k=7. So d = (t_k - n)/2 = 8, which we write as 1 + 7 according to the algorithm. Thus a shortest path to 12 is -1 + 2 + 3 + 4 + 5 + 6 - 7.

I say a shortest path, because shortest paths aren't unique in general. For example, 1 + 2 -3 + 4 - 5 + 6 + 7 also works.

Algorithm correctness

Lemma: Let A_k = {0, 1, 2, ..., t_k}. Then a number lies in A_k if and only if it can be expressed as a sum sum_{i=1}^k a_i i for some sequence a_i in {0, 1}.

Proof: By induction on k. First, 0 = sum_{i=1}^0 1, the empty sum. Now suppose the result holds for all k - 1 >= 0 and suppose a number d lies in A_k. Repeatedly subtract: d = a_k (k) + r_k, r_k = a_{k-1} (k-1) + r_{k-1}, ..., choosing each a_i = 0 or 1 maximally in {0, 1} and stopping when the first r_j lies in A_j for some j < k. Then by the induction hypothesis, r_j = sum_{i=0}^j b_i i for some b_i in {0, 1}. Then d = r_j + sum_{i=j+1}^k a_k i, as desired. Conversely, a sum s := sum_{i=1}^k a_i i for a_i in {0,1} satisfies 0 <= s <= sum_{i}^k i = t_k, and so s lies in A_k.

Algorithm time complexity

Assuming that arithmetic operations are constant time, it takes O(1) time to compute k from n, and hence the length of a minimal path to n. Then it takes O(k) time to find a minimal length sum for d, then O(k) time to use that sum to produce a minimal length sum for n. So O(k) = O(sqrt(n)) time all up.

Answer 2

For any number of jumps, one can easily compute the maximum positive distance the jack could travel. Flipping the polarity of positive jumps totaling any particular value k will cause the jack to end up 2k counts below where it would have otherwise. For any maximum distance t, and any non-negative n of the same parity (even if t is even; odd if t is odd) less than or equal to that distance, it will be possible to find a combination of jumps which totals n. Thus, one need not worry about trees, knapsacks, or any other such things--just whether some number of jumps will be sufficient, and whether it will yield the correct "parity".

Answer 3

The formula for the sum of n consecutive integers is n(n+1)/2. For example 1+2+3+4=10 = 4*5/2=10. This is the minimum number of steps necessary to reach the target number. But there might be overshoot. Say the target is 11. Four jumps will get you to 10 (we just calculated that), but 5 will get you to 5*6/2=15. Now we note only that in the case of 11, we jump back when step size is 2, and we arrive at 11 correctly. We'll deal with overshoot in more detail later. Back to how to calculate the number of jumps in the first place. Our formula is n(n+1)/2 = x where x is the target number. The quadratic equation tells us that the solution to this is

(-1+/-sqrt(-1+8x)))/2

or

(-1-/+(sqrt(9x))/2

The negative "version" will always yield an imaginary number, which is irrelevant here so we have

(sqrt(9x) + 1)/2

Take the ceiling of that number and you have the initial number of jumps necessary.

Overshoot is a bit complicated. In our reaching 11 example, overshoot is 4 (15-11=4), so we just need to make the +2 jump into -2 jump, and that is the place to "stash" the 4 overshoot. However, things are not always so simple: 12 can be reached via -1-2+3+4-5+6+7: it requires 7 steps, not 5 as predicted. The basic observation is that an overshoot must be even, otherwise there is no overshoot/2 step to take. Here's how we find the number of steps for 12

1. Using the above algorithm we find that the minimum number of steps is 5, which gets us to 15
2. Compute the overshoot: we have 3.
3. If overshoot is odd (which it is in this case) try the next number of steps and go back to step 2, until you find an even overshoot. This is your number of steps

For 12 therefore, we try 5 steps, yielding 15 and overshoot of 3. Then we try six steps yielding 21 and an overshoot of 9. Finally we try 7 steps yielding 28 and an overshoot of 16. This is our minimum number of steps. This can probably be computed by a formula, however.