# Solver that will return all best paths, not just first
# Parameters:
#   * board - dictionary with interesting spots on board
#   * board_size - total number of spots on board
#   * position - current piece position
#   * steps - previous steps of piece
#   * step_size - how for can piece reach
#   * best_length - what is current best attempt at solving
def solve_recursive(board, board_size, position, steps, step_size, best_length):
    # If we are worse than current best
    if len(steps) > best_length:
        return []

    # If we are not on a free spot then we must follow the ladder or a snake
    if position in board and board[position] != 0:
        return solve_recursive(board, board_size, board[position], steps, step_size, best_length)

    # If we stepped on moose, higher our moving capability
    if position in board and board[position] == 0:
        step_size += 1

    # If we are close to end
    steps_remaining = board_size - position
    if step_size >= steps_remaining:
        current_steps = steps.copy()
        current_steps.append(steps_remaining)
        return [current_steps]

    # Else try all move possibilities
    result = []
    for step in range(1, step_size + 1):
        steps.append(step)  # Try current step
        solutions = solve_recursive(board, board_size, position + step, steps, step_size, best_length)
        steps.pop()  # Remove current step for next try
        score = len(solutions[0]) if len(solutions) > 0 else 0
        if score == best_length and score > 0:  # Solutions are as good as our best
            result.extend(solutions)
        elif score < best_length and score > 0:  # Solutions are better than our best
            result = solutions
            best_length = score
    return result


# Solve Snakes Ladders Mooses Problem
def solve():
    # Define board as a dictionary, all interesting positions are saved as keys,
    # their values are either 0 meaning it is a moose or next position if it is
    # a ladder or a snake. Blank spots are from dictionary omitted.
    board = {
        2: 0, 3: 18, 4: 1, 6: 23,
        11: 0, 14: 0, 15: 30,
        21: 0, 22: 7,
        26: 12, 27: 39, 29: 0,
        34: 49, 35: 19,
        37: 0, 38: 53,
        40: 24, 45: 42,
        48: 32,
        50: 0, 51: 0,
    }

    # We know, that path with 24 steps is possible, let's try to find shorter
    solutions = solve_recursive(board, 55, 0, [], 1, 24)
    print('All solutions:', solutions)

    # From all shortest paths, find the one with highest score
    minimum = sum(solutions[0])
    for solution in solutions[1:]:
        score = sum(solution)
        if score < minimum:
            minimum = score
    return minimum


# Print the result
print('Result:', solve())