Jump!

February 3, 2017

Our solution visits each cell in order:

(define (jump xs)
  (let loop ((reachable 0) (xs xs))
    (if (null? xs) #t
      (let ((next (max (- reachable 1) (car xs))))
        (if (zero? next) #f (loop next (cdr xs)))))))

From any given cell, the maximum reachable position reachable is the greater of one less than the reachable of the previous cell, or the value in the current cell. If reachable goes to 0 before reaching the end of the array, the game is unwinnable. Here are three winnable games and three unwinnable games:

> (jump '(1 3 3 0 0 2 0 4 1 3 0))
#t
> (jump '(2 0 3 5 0 0 3 0 0 6 3))
#t
> (jump '(3 1 4 3 5 0 0 0 3 1 0))
#t
> (jump '(4 4 0 3 0 1 2 2 1 0 0))
#f
> (jump '(3 2 0 1 4 3 1 0 0 0 0))
#f
> (jump '(5 2 0 0 1 0 6 0 0 2 9))
#f

You can run the program at http://ideone.com/aPTEbc.

Advertisements

Pages: 1 2

6 Responses to “Jump!”

  1. 
    (defun winnablep (jumps)
      (labels ((winnable-position-p (position)
                 (when (<= (length jumps) position)
                   (return-from winnablep t))
                 (let ((jumpable (aref jumps position)))
                   (when (zerop jumpable)
                     (return-from winnable-position-p nil))
                   (loop for jump downfrom jumpable to 1
                         if (winnable-position-p (+ position jump))
                           do (return-from winnablep t))
                   nil)))
        (winnable-position-p 0)))
    
    (winnablep #(2 0 3 5 0 0 3 0 0 3 1 0)) ; --> t
    (winnablep #(2 0 3 1 0 0 3 0 0 3 1 0)) ; --> nil
    (winnablep #(1)) ; --> t
    (winnablep #(0)) ; --> nil
    (winnablep #())  ; --> t
    
    
    (defun winnable-path (jumps)
      (labels ((winnable-path-from-position (position)
                 (if (<= (length jumps) position)
                     '(t)
                     (let ((jumpable (aref jumps position)))
                       (if (zerop jumpable)
                           nil
                           (loop for jump downfrom jumpable to 1
                                 for path = (winnable-path-from-position (+ position jump))
                                 if path
                                   do (return (cons jump path))
                                 finally (return nil)))))))
        (winnable-path-from-position 0)))
    
    (winnable-path #(2 0 3 6 0 0 3 0 0 3 1 0)) ; --> (2 1 6 3 t)
    (winnable-path #(2 0 3 5 0 0 3 0 0 3 1 0)) ; --> (2 1 3 3 3 t)
    (winnable-path #(2 0 3 1 0 0 3 0 0 3 1 0)) ; --> nil
    (winnable-path #(1)) ; --> (1 t)
    (winnable-path #(0)) ; --> nil
    (winnable-path #())  ; --> (t)
    
    

    In winnablep, return-from is used to shortcut the exit when the result is known.
    On the other hand, in winnable-path, we use O(log(n)) stack space to avoid allocating O(n) temporary cons cells, and instead we cons the path only once we found it.

  2. Paul said

    Two solutions in Python. The first models the problem as finding the shortest path in a DAG (function dag_sp is omitted). You have to set up the weights for all possible jumps.

    def winnable(jumps):
        'model as shortest path in a DAG and solve'
        n = len(jumps)
        W = {i: {} for i in range(n+1)}
        for label, jump in enumerate(jumps):
            W[label].update({min(label+j+1, n): 1 for j in range(jump)})
        return dag_sp(W, s=0, t=n) < float('inf')
    
    def winnable2(jumps):
        jumps = list(jumps) + [0]  # add entry for target
        reach =  0
        for index, jump in enumerate(jumps):
            if index > reach:
                return False
            reach = max(reach, index + jump)
        return True
    
  3. Globules said

    A Haskell version. If we’re looking at an empty list then either the initial list was empty, which we treat as a win, or we’ve made it to the end of a non-empty list, which is by definition a win. If we ever land on a 0 then we’re on a losing path. Otherwise, if any of the paths within n jumps of our current position is a winner then we’ve won.

    import Data.List (tails)
    
    canWin :: [Int] -> Bool
    canWin []     = True
    canWin (0:_)  = False
    canWin (n:ns) = any canWin $ take n $ tails ns
    
    main :: IO ()
    main = do
      print $ canWin   [2, 0, 3, 5, 0, 0, 3, 0, 0, 3, 1, 0]
      print $ canWin   [2, 0, 3, 0, 1, 0]
      print $ canWin   [3, 2, 1]
      print $ canWin $ [3, 2, 1] ++ [0..]
    
    $ ./jump 
    True
    False
    True
    False
    
  4. Globules said

    Here’s another Haskell program that prints out all winning paths. It has a similar structure to the previous program.

    import Data.List (tails)
    
    allWins :: [Int] -> [[Int]]
    allWins []     = [[]]
    allWins (0:_)  = []
    allWins (n:ns) = concatMap (map (n:) . allWins) $ take n $ tails ns
    
    main :: IO ()
    main = do
      print $ allWins   [2, 0, 3, 5, 0, 0, 3, 0, 0, 3, 1, 0]
      print $ allWins   [2, 0, 3, 0, 1, 0]
      print $ allWins   [3, 2, 1]
      print $ allWins $ [3, 2, 1] ++ [0..]
    
    $ ./jump2 
    [[2,3,5,3,3]]
    []
    [[3,2,1],[3,2],[3,1],[3]]
    []
    
  5. Dan The Man said

    Here is a simple solution in Ruby. It uses the Directed Acyclic Graph approach. The class definition is there for readability only and I could of just as well used a hash.

    class JumpNode
    attr_accessor :val
    attr_accessor :winner
    attr_reader :links

    def initialize(value)
    @val = value
    @links = []
    @winner = false
    end

    def add_link(link)
    @links << link
    end
    end

    def init_graph(cells)
    Array.new(cells.length) { |i| JumpNode.new(cells[i]) }
    end

    def to_jump_graph(cells)
    jump_graph = init_graph(cells)
    jump_graph.each_index do |node_index|
    node = jump_graph[node_index]

    if node.val + node_index >= cells.length
    node.winner = true
    else
    (1..node.val).each { |i| node.add_link(jump_graph[node_index + i]) }
    end
    end
    end

    def can_reach_end(start_node)
    return true if start_node.winner
    return false if start_node.links.empty?
    start_node.links.each { |link| return true if can_reach_end(link) }
    false
    end

    def winnable?(cells)
    return false if cells.nil? || cells.length.zero?

    can_reach_end(to_jump_graph(cells)[0])
    end

    $ irb -r ‘./jump.rb’
    irb(main):001:0> winnable?([2, 0, 3, 5, 0, 0, 3, 0, 0, 3, 1, 0])
    => true
    irb(main):002:0> winnable?([0, 1, 3])
    => false
    irb(main):003:0> winnable?([0, 5, 3, 1, 1])
    => false
    irb(main):004:0> winnable?([1, 0, 3, 1, 1])
    => false
    irb(main):005:0> winnable?([1, 2, 3, 0, 0])
    => true
    irb(main):006:0> winnable?([1, 2, 3, 1, 0])
    => true
    irb(main):007:0> winnable?([1, 2, 0, 1, 0])
    => false
    irb(main):008:0> winnable?([2, 2, 0, 1, 0])
    => false
    irb(main):009:0> winnable?([2, 2, 0, 1, 1])
    => true
    irb(main):010:0> winnable?([2, 2, 0, 1, 6])
    => true
    irb(main):011:0> winnable?([8, 2, 0, 1, 6])
    => true
    irb(main):012:0> winnable?([3, 2, 2, 0, 0])
    => false
    irb(main):013:0> winnable?([3, 2, 2, 0, 1])
    => true

  6. Dan The Man said
    class JumpNode
      attr_accessor :val
      attr_accessor :winner
      attr_reader :links
    
      def initialize(value)
        @val = value
        @links = []
        @winner = false
      end
    
      def add_link(link)
        @links << link
      end
    end
    
    def init_graph(cells)
      Array.new(cells.length) { |i| JumpNode.new(cells[i]) }
    end
    
    def to_jump_graph(cells)
      jump_graph = init_graph(cells)
      jump_graph.each_index do |node_index|
        node = jump_graph[node_index]
    
        if node.val + node_index >= cells.length
          node.winner = true
        else
          (1..node.val).each { |i| node.add_link(jump_graph[node_index + i]) }
        end
      end
    end
    
    def can_reach_end(start_node)
      return true if start_node.winner
      return false if start_node.links.empty?
      start_node.links.each { |link| return true if can_reach_end(link) }
      false
    end
    
    def winnable?(cells)
      return false if cells.nil? || cells.length.zero?
    
      can_reach_end(to_jump_graph(cells)[0])
    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

%d bloggers like this: