# Jumping Jack

I'd like to present some solutions to the following puzzle that appeared as March 22, 2013 Programming Praxis puzzle.

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.
Design an algorithm that takes an integer *n* and returns a shortest sequence of jumps that Jack can perform to reach *n* along with the length of that sequence.

## Algorithm 1

Brute-force. Perform a breadth-first search through the binary tree of all valid jump/integer summand sequences (0, -1, 1, -1 - 2, -1 + 2, 1 - 2, 1 + 2, ...) and stop when the target sum n is reached.

## Algorithm 2

Brute-force with pruning. Label the nodes of the binary tree with their partial sums and order the nodes of so that the left child is less than the right child (0, -1, 1, -3, -1, -1, 3, ...). Notice that every pair of nodes at the same height with equal partial sums have equal subtrees. Notice also that every pair of nodes at the same height with partial sums of opposite sign have mirror image subtrees. Notice also that flipping the signs/turns of a path with partial sum s yields a path of the same length to -s. So in our breadth-first search, we don't need to search down a node at a given height if we've already discovered a node at the same height with the same magnitude partial sum.

Analyzing the worst-case time complexity of Algorithm 1 or Algorithm 2 requires knowing at what tree height the given number *n* is first discovered.
If you can figure that out, then you probably discovered...

## Algorithm 3

Smart-force.
Find the least integer k such that *t*_{k} : = 1 + 2 + 3 + ... + *k* ≥ *n* and *t*_{k} has the same parity (evenness/oddness) 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 + √(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*, *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* = ∑^{k}_{i = 1}*a*_{i}*i*.
Thus *n* = *t*_{k} − 2*d* = ∑^{k}_{i = 1}*i* − ∑^{k}_{i = 1}2*a*_{i}*i* = ∑^{k}_{i = 1}(1 − 2*a*_{i})*i* and 1 − 2*a*_{i} ∈ − 1, 1.
So the sequence *b*_{i} : = 1 − 2*a*_{i} is a path, and by the minimality of *k*, we have that *b*_{i} is a minimal path.

## Algorithm 3 example

Consider the target number *n* = 12.
According to Algorithm 3, the possibilities for *k* are 5, 6, 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 3 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 ∑^{k}_{i = 1}*a*_{i}*i* for some *a*_{i} ∈ 0, 1.

*Proof*: By induction on *k*.
First, 0 = ∑^{0}_{i = 1}1, the empty sum.
Now suppose the result holds for all *k* − 1 ≥ 0 and let *d* ∈ *A*_{k}.
Repeatedly subtract: *d* = *a*_{k}(*k*) + *r*_{k}, *r*_{k} = *a*_{k − 1}(*k* − 1) + *r*_{k − 1}, ..., choosing each *a*_{i} maximally in 0, 1 and stopping at the first *r*_{j} ∈ *A*_{j} for some *j* < *k*.
Then by the induction hypothesis, *r*_{j} = ∑^{j}_{i = 0}*b*_{i}*i* for some *b*_{i} ∈ 0, 1.
Then *d* = *r*_{j} + ∑^{k}_{i = j + 1}*a*_{k}*i*, as desired.
Conversely, a sum *s* : = ∑^{k}_{i = 1}*a*_{i}*i* for *a*_{i} ∈ 0, 1 satisfies 0 ≤ *s* ≤ ∑^{k}_{i = 1}*i* = *t*_{k}, and so *s* ∈ *A*_{k}.

## Algorithm 3 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* and *O*(*k*) time to use that sum to produce a minimal length sum for *n*.
So *O*(*k*) = *O*(√(*n*)) time all up.

**Why no comments?**
Public comments take too much time to moderate and maintain, time better spent playing outside, but you can still email me private comments by clicking the 'Comment' link above.