Deciding on an algorithm for 'Jumping Jack'
algorithm
Solution
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.
Problem
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.