Jumping Jack

March 22, 2013

We have a fun little programming puzzle today; I found it here, but don’t know the original source of the 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. Write a program that takes a number and returns the minimum number of jumps Jack makes to reach that number.

For example, it takes seven jumps to reach 12, first a jump left to -1, then a jump right to 1, a jump right to 4, a jump right to 8, a jump right to 13, a jump right to 19, and a jump left to 12. To go to -12, simply reverse the direction of each jump.

Your task is to write programs that compute the minimum number of steps Jack must take to reach his target and that compute the actual steps. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
6 Comments »

6 Responses to “Jumping Jack”

  1. Programming Praxis – Jumping Jack | Bonsai Code said
    March 22, 2013 at 10:18 AM

    […] today’s Programming Praxis exercise, our goal is to determine the smallest amount of sequential numbers […]

  2. Remco Niemeijer said
    March 22, 2013 at 10:19 AM

    My Haskell solution (see http://bonsaicode.wordpress.com/2013/03/22/programming-praxis-jumping-jack/ for a version with comments):

    import Data.List
import Text.Printf

jack :: Int -> [Int]
jack n = snd $ head
  [ mapAccumR (\r x -> if x <= r then (r-x,-x) else (r,x)) (div (t-n) 2) [1..i]
  | (i,t) <- scanl (\(_,s) x -> (x, s+x)) (0,0) [1..]
  , t >= abs n, mod (t+n) 2 == 0]
  3. YaNan Xu said
    March 24, 2013 at 9:24 PM

    Assume the destiny number is k, the step is n
    we are looking for a minimal value of n that n(n+1) = 2k + 4x where x is the sum of a sub set of [1…n] so x can be any positive integer(no larger than n(n+1)/2)

    import math
    k = 12
    n = int(math.sqrt(2 * k)) + 1
    while (n * (n + 1) – 2 * k) % 4 != 0:
    n += 1
    print n

  4. linesncodez said
    March 25, 2013 at 12:03 AM

    Python – do a breadth first search of possibilities and return the first working solution

    def jumping_jack(n):
    q = [(0,0,[0])]

    while len (q) > 0:
        cur, total, path = q.pop(0)

        cur = cur + 1

        if total + cur == n:
            return path + [cur]
        elif total + cur * -1 == n:
            return path + [cur * -1]
        q.append((cur, total + cur, path + [cur]))
        q.append((cur, total + -1 * cur, path + [cur * -1]))

print jumping_jack(12)
[0, 1, 2, -3, 4, -5, 6, 7]

print len(jumping_jack(12)) - 1
7
  5. mlangc said
    March 31, 2013 at 6:06 PM

    Here is my Ruby solution (note that I’m currently learning Ruby, so feel free to suggest stylistic improvements):

    module JumpingJack

    # Solves the puzzle; to be used like
    # JumpingJack.jump_to(122)
    # => [1, 2, 3, 4, 5, 6, -7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
    def JumpingJack.jump_to(number)
    number >= 0 ? jump_to_positive_number(number) : reverse_sign(jump_to_positive_number(-number))
    end

    private

    # The algorithm works in two steps:
    # – In the first step, we create the shortest array of the form [1, 2, 3, 4, 5, …] so that
    # the sum s of the contained numbers satisfies ‘s – number % 2 == 0’. If ‘s – number == 0’
    # we are done. In any case, the resulting array has exactly the length we are looking for.
    # – In the second step, we adjust the signs of the numbers from the first array so that their
    # sum equals the given number.
    #
    def JumpingJack.jump_to_positive_number(number)
    n = 0
    sum = 0
    ret = []
    loop do
    diff = sum – number
    return ret if diff == 0
    break if diff > 0 && diff % 2 == 0

    n += 1
    sum += n
    ret <= number
    ret[-i] = -val
    break if diff == number
    sum = diff
    end
    end

    ret
    end

    def JumpingJack.reverse_sign(numbers)
    numbers.map { |i| -i }
    end
    end
    [\sourcecode]

  6. mlangc said
    March 31, 2013 at 6:18 PM

    Here is my Ruby solution (this time correctly formatted – please remove the other comment):

    module JumpingJack

    # Solves the puzzle; to be used like 
    # JumpingJack.jump_to(122)
    #  => [1, 2, 3, 4, 5, 6, -7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
    def JumpingJack.jump_to(number)
        number >= 0 ? jump_to_positive_number(number) : reverse_sign(jump_to_positive_number(-number))
    end

    private

    # The algorithm works in two steps:
    #  - In the first step, we create the shortest array of the form 
    #    [1, 2, 3, 4, 5, ...] so that the sum s of the contained numbers 
    #    satisfies 's - number % 2 == 0'. If 's - number == 0' we are done.
    #    In any case, the resulting array has exactly the length we are 
    #    looking for.
    #  - In the second step, we adjust the signs of the numbers from the first
    #    array so that their sum equals the given number.
    #
    def JumpingJack.jump_to_positive_number(number)
        n = 0
        sum = 0
        ret = []
        loop do
            diff = sum - number
            return ret if diff == 0
            break if diff > 0 && diff % 2 ==  0
            
            n += 1
            sum += n
            ret << n
        end

        for i in (1..(ret.length))
            val = ret[-i]
            diff = sum - 2 * val
            if diff >= number
                ret[-i] = -val
                break if diff == number
                sum = diff
            end
        end

        ret
    end

    def JumpingJack.reverse_sign(numbers)
        numbers.map { |i| -i }
    end
end

Leave a comment