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

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.

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.

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.

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

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