Распечатка процесса рекурсивной проблемы возврата

Question

Мне дали задание для школы:

Вам дали головоломку, состоящую из ряда квадратов, каждый из которых содержит целое число, например:

6 , 4, 1, 3, 3, 1, 4, 1, 1, 0

Жирным числом на начальном квадрате является маркер, который может перемещаться на другие квадраты вдоль ряда. На каждом шаге головоломки вы можете перемещать маркер на число квадратов, обозначенных целым числом в квадрате, который он в данный момент занимает. Маркер может двигаться влево или вправо по ряду, но не может проходить мимо любого конца. Цель головоломки - переместить маркер в 0 в дальнем конце ряда.

Программа проверяет индекс, на котором вы в данный момент находитесь, и перемещает количество квадратов влево или вправо на основе целого числа этого индекса в массиве. Он решает это на основе границ массива, если он не может переместить требуемое количество квадратов влево, он переместится вправо и наоборот. В этой программе первый ход должен быть на 6 вправо, поскольку он не может сдвинуть 6 пробелов влево, не выходя за пределы. Затем он должен переместиться на 4 влево, поскольку он не может переместиться на 4 вправо, и он продолжается таким образом.

У меня все работает, и печать процесса заслуживает дополнительной оценки. У меня есть процесс печати, но он вышел из строя.

вот мой код:

def self.solvable(start, board)

     return false if start>= board.length || start<0
     return false if @@infinite[start] == -1
     return true if board[start] == 0

     @@infinite[start] = -1

     if solvable(board[start] + start, board)
          puts "Shifted right " + board[start].to_s + " spaces, from index " + start.to_s + " to index " + (board[start] + start).to_s
          return true
     else
          puts "Shifted left " + board[start].to_s + " spaces, from index " + start.to_s + " to index " + (start - board[start]).to_s
     end       
     return solvable(start - board[start], board)
end

print "Enter an array of numbers: "
input = gets.chomp!

board = input.each_char.map(&:to_i)
@@infinite = input.each_char.map(&:to_i)
puts solvable(0, board)

Я не понимаю, как сделать вывод кода в более логичном порядке, печатая 6 пробелов справа, 4 пробела слева и т. Д. c. .. вместо текущего выхода, который является:

Сдвиг влево на 4 пробела, от индекса 6 до индекса 2

Сдвиг влево на 3 пробела, от индекса 3 до индекса 0

Смещенные левые 1 пробелы, от индекса 2 до индекса 1

Смещенные левые 1 пробелы, от индекса 5 до индекса 4

Смещенные правые 1 пробелы, от индекса 8 до индекса 9

Смещено вправо на 1 пробел, от индекса 7 до индекса 8

Смещено вправо на 3 пробела, от индекса 4 до индекса 7

Смещено вправо на 4 пробела, от индекса 1 до индекса 5

Смещено вправо на 6 пробелов, от индекса 0 до индекса 6

Answer 1

Предположение

Я предполагаю, что игра начинается в позиции 0. Каждый ход увеличивает или уменьшает позицию на целую величину. Цель состоит в том, чтобы вернуться в положение 0 после того, как был сделан первый ход.

Нам дан массив arr целых чисел и отображение позиций в индексы массива. Для позиции p индекс arr задается как p % arr.size.

Если мы находимся в позиции p, мы получаем, что значение может переместиться в позицию p + n или p - n, где

n = arr[p % arr.size]

Для приведенного примера:

arr = [6, 4, 1, 3, 3, 1, 4, 1, 1, 0]

(arr.size #=> 10) и p изначально ноль,

n = arr[0 % 10]
  #=> arr[0] => 6

, поэтому мы можем перейти в положение + 6 или -6. Если мы перейдем к +6, мы вычислим

n = arr[6 % 10]
  #=> 4

, поэтому мы можем перейти в положение 6+4 #=> 10 или 6-4 #=> 2. Если мы перейдем к -6, мы вычислим

n = arr[-6 % 10]
  #=> 3

, поэтому мы можем перейти в положение -6-3 #=> -9 или -6+3 #=> -3.

Обратите внимание, что arr[9] #=> 0 может рассматриваться как поглощающее состояние .

код

Метод, который я выбрал для использования, является рекурсивным.

def onward_to_zero(arr, pos=0)
  n = arr[pos % arr.size]
  return [] if n.zero?
  return [-n] if (pos-n).zero?
  return [n] if (pos+n).zero?
  if rand < 0.5
    rv = onward_to_zero(arr, pos-n)
    return [-n] + rv unless rv.empty?
    rv = onward_to_zero(arr, pos+n)
    return [n] + rv unless rv.empty?
  else
    rv = onward_to_zero(arr, pos+n)
    return [n] + rv unless rv.empty?
    rv = onward_to_zero(arr, pos-n)
    return [-n] + rv unless rv.empty?
  end
  []
end

Я считаю, что это возможно Докажи, что всегда есть путь к нулю, но я не придумал доказательства.

Примеры

arr = [6, 4, 1, 3, 3, 1, 4, 1, 1, 0]

onward_to_zero(arr)
  #=>       [-6, 3, 1, -1, 1, -1, -1, 4]
  # pos % 10  0  4  7   8  7   8   7  6    
  # pos->  0 -6 -3 -2  -3 -2  -3  -4  0

arr = [3, 2, 4, 1, 3, 6, 2]

onward_to_zero(arr)
  #=>    [3, -1, 4, 2, 2, 1, -3, 2, -1, -4, -6, -2, 3]
  # pos-> 3   2  6  8 10 11   8 10   9   5   -1 -3  0

arr = [3, 3]

onward_to_zero(arr)
  #=>    [-3, 3]
  # pos-> -3  0

arr = [7, 26, 33, 18, 7, 13]
onward_to_zero(arr)
  #=>     [-7, -13,  7, 13]
  # pos->  -7  -20 -13   0

Обсуждение

Обратите внимание, что if rand < 0.5 заставляет меня задуматься о сокращении позиции до ее увеличения примерно в половину времени. Если бы я всегда рассматривал уменьшение до увеличения или наоборот, я мог бы легко получить слишком большой уровень стека ошибка.

Однако даже с этим механизмом вероятности метод дает довольно разнообразные результаты и все равно может привести к слишком глубокой ошибке на уровне стека . Вот результаты, которые я получил, выполнив первый пример 10 раз.

[6, -4, 1, -3] 
[-6, 3, 1, -1, -1, 4] 
[6, 4, 6, 4, 6, 4, 6, 4, 6,..., -1, -1, 4] (824 elements) 
[6, 4, -6, -3, 4, 1, -4, -1,..., -4, 1, -3] (386 elements) 
[-6, 3, 1, -1, -1, 4] 
[-6, -3, 4, 1, 4] 
[-6, 3, 1, -1, 1, -1, -1, 4] 
[-6, -3, -4, -1, -4, 1, -3, 6, 4, 6, 4] 
[-6, -3, -4, 1, -1, -1, -4, -1, 4, 1, 4, 6, 4]
[-6, 3, -1, 4]