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.

You can also directly jump from from the initial cell(first cell) past the end of the array if they are integers to the right of that cell.

E.g 

`[6, 1, 1]` is winnable

`[6]` is **not** winnable

Note: You can **not** jump from the last cell!

`[1, 1, 3]` is **not** winnable

## -----

Your task is to complete the function `canJump()`  that determines if a given game is winnable.

### More Examples

``` javascript
canJump([5]) //=> false
canJump([2, 5]) //=> true
canJump([3, 0, 2, 3]) //=> true (3 to 2 then past end of array)
canJump([4, 1, 2, 0, 1]) //=> false
canJump([5, 0, 0, 0]) //=> true
canJump([1, 1]) //=> false
```

Source: codewars | Difficulty: EASY
Tags: Data structures

Game theory

Starter code: def can_jump(arr):
	

Solutions:
def can_jump(arr):
	if arr[0] == 0 or len(arr) == 1:
		return False
	if arr[0] >= len(arr):
		return True
	for jump in range(1, arr[0] + 1):
		if can_jump(arr[jump:]):
			return True
	return False


def can_jump(arr):
	last = len(arr)
	for i in reversed(range(len(arr) - 1)):
		if arr[i] >= last - i:
			last = i
	return not last


from functools import lru_cache

def can_jump(arr):

	@lru_cache(maxsize=None)
	def rec(i):
		if i >= len(arr) - 1:
			return i >= len(arr)
		return any((rec(i + j) for j in range(1, arr[i] + 1)))
	return rec(0)


def can_jump(arr):
	length = len(arr)
	i = length - 2
	while i >= 0:
		if arr[i] + i >= length:
			length = i
		i -= 1
	return length == 0


def can_jump(lst):
	l = len(lst)
	for i in range(l - 2, -1, -1):
		if lst[i] >= l - i:
			l = i
	return l == 0


def can_jump(arr):
	x = len(arr) - 1
	p = []
	i = 0
	j = arr[i]
	n = i + j
	if not x or not arr[0]:
		return False
	while True:
		if x < n:
			return True
		while j and (n == x or not arr[n]):
			j -= 1
			n = i + j
		if not j:
			if not p:
				return False
			j = p.pop()
			i -= j
			j -= 1
			continue
		p.append(j)
		i += j
		j = arr[i]
		n = i + j


def can_jump(arr, i=0):
	return i >= len(arr) or (i < len(arr) - 1 and arr[i] and any((can_jump(arr, i + j) for j in range(1, arr[i] + 1))))


def can_jump(arr):
	if len(arr) <= 1 or arr[0] == 0:
		return False
	if arr[0] >= len(arr):
		return True
	return any((can_jump(arr[i + 1:]) for i in range(arr[0])))


def can_jump(lst):
	(p, l) = (lst[0], len(lst))
	if l == 1:
		return False
	if p >= l:
		return True
	for i in range(1, p + 1):
		if lst[i] and can_jump(lst[i:]):
			return True
	return False


def can_jump(A):
	z = len(A)
	for i in range(z - 1)[::-1]:
		z = (z, i)[z <= i + A[i]]
	return z == 0