## Jump!

### February 3, 2017

Jump is a simple one-player game:

You are initially at the first cell of an array of cells containing non-negative integers; at each step you can jump ahead in the array as far as the integer at the current cell, or any smaller number of cells. You win if there is a path that allows you to jump from one cell to another, eventually jumping past the end of the array, otherwise you lose. For instance, if the array contains the integers [2, 0, 3, 5, 0, 0, 3, 0, 0, 3, 1, 0], you can win by jumping from 2, to 3, to 5, to 3, to 3, then past the end of the array.

Your task is to write a program that determines if a given game is winnable. 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

### 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) +   # 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],]
[]
```
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

def initialize(value)
@val = value
@winner = false
end

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

def can_reach_end(start_node)
return true if start_node.winner
false
end

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

can_reach_end(to_jump_graph(cells))
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

def initialize(value)
@val = value
@winner = false
end

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

def can_reach_end(start_node)
return true if start_node.winner