Jumping Jack

March 22, 2013

Here is our function to compute the minimum number of steps:

(define (jack n)
  (define (diff-parity? t n)
    (not (= (modulo t 2) (modulo n 2))))
  (let loop ((k 0) (t 0))
    (if (or (< t (abs n)) (diff-parity? t (abs n)))
        (loop (+ k 1) (+ t k 1))
        k)))

The basic idea is to make jumps until you equal or exceed the absolute value of the target, then continue making jumps until the parity of the target and the parity of the counter t are equal, since you can only subtract an even number.

The function that computes the jumps themselves is similar. Once you have passed the target, d is the number you have to subtract.

(define (jacks n)
  (define (diff-parity? t n)
    (not (= (modulo t 2) (modulo n 2))))
  (if (negative? n)
      (map (lambda (x) (- x)) (jacks (- n)))
      (let loop ((k 0) (t 0))
        (if (or (&lt; t n) (diff-parity? t n))
            (loop (+ k 1) (+ t k 1))
            (let loop ((d (/ (- t n) 2)) (xs (range k 0)) (zs (list)))
              (if (null? xs) zs
                (if (<= (car xs) d)
                    (loop (- d (car xs)) (cdr xs) (cons (- (car xs)) zs))
                    (loop d (cdr xs) (cons (car xs) zs)))))))))

It’s easy to check the output by checking that the sum of (jacks n) is equal to n, though I don’t know any easy way to check that the result is minimal. Here’s an example:

> (jack 12)
7
> (jacks 12)
(-1 2 3 4 5 6 -7)

The sum of (-1 2 3 4 5 6 -7) is 12; the signs indicate the direction of the jumps: left, right, right, right, right, right, left.

We used range from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/NVxW2bGK.

About these ads

Pages: 1 2

6 Responses to “Jumping Jack”

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

  2. 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

    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. 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

    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

    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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: