Крис Пайн Руби ч 10, рекурсия

Question

Я пытался выучить рубин, используя книгу Криса Пайна "Учись программировать". Я на самом деле волновался, просматривая книгу, пока не добрался до главы 10 и использованных примеров. Теперь только эта глава и ее примеры полностью сдули мое волнение, чтобы продолжить эту книгу. В этом примере я совершенно не представляю, как он пытается считать плитки, или почему он использует world [y],[x], когда метод был определен с атрибутом continent_size world, x, y? Я не уверен, как работает рекурсия в этом примере. Может ли кто-то пролить больше света на этот пример относительно того, что автор на самом деле пытается сделать?

M = 'land'
o = 'water'

world = [
  [o,o,o,o,o,M,o,o,o,o,o],
  [o,o,o,o,M,M,o,o,o,o,o],
  [o,o,o,o,o,M,o,o,M,M,o],
  [o,o,o,M,o,M,o,o,o,M,o],
  [o,o,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,M,M,M,M,o,o,o],
  [M,M,M,M,M,M,M,M,M,M,M],
  [o,o,o,M,M,o,M,M,M,o,o],
  [o,o,o,o,o,o,M,M,o,o,o],
  [o,M,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,o,M,o,o,o,o,o]]

def continent_size world, x ,y

  if x < 0 or x > 10 or y < 0 or y > 10
    return 0
  end

  if world[y][x] != 'land'
    return 0
  end

  size = 1
  world [y][x] = 'counted land'

  size = size + continent_size(world, x-1, y-1)
  size = size + continent_size(world, x , y-1)
  size = size + continent_size(world, x+1, y-1)
  size = size + continent_size(world, x-1, y )
  size = size + continent_size(world, x+1, y )
  size = size + continent_size(world, x-1, y+1)
  size = size + continent_size(world, x , y+1)
  size = size + continent_size(world, x+1, y+1)
  size

end

puts continent_size(world, 5, 5)

Answer 1

Это называется заливкой. Что он делает, так это подсчитывает размер всех кусочков "земли", которые связаны с начальной отправной точкой. Обратите внимание, что он не учитывает все символы "земли", а только те, на которые он не может попасть из-за воды.

Заполнение потоком - это форма так называемого поиска в глубину, которая является способом обхода графа (здесь, дискретная "карта"). Это можно резюмировать так:

1. Посетите текущий узел позиции / графика, посчитайте его и отметьте как посещенный
2. Проверьте все подключенные узлы (здесь, что-нибудь вверх, вниз, влево или вправо), если они не посещены и являются наземными, рекурсивно посетите их

Он может делать y, x по следующей причине: логический формат двумерного массива организован сначала по строке, а затем по столбцу. Строка может рассматриваться как ось y, а столбец - как x.

Answer 2

Для чего это стоит, когда я работал над этой проблемой в книге, я также заметил транспонирование x & y, когда мир называется. Я заглянул на сайт Прагматического Программиста, чтобы увидеть, есть ли это в списке ошибок, но это не так.

Я подумал, что это опечатка, и перевернул их на x, y. Код работает в любом случае.

На самом деле это не имеет значения, поскольку начальная точка 5,5 является произвольной, и код будет проверять все восемь плиток вокруг x,y (или y,x) независимо от того, пока не достигнет "края" массива / мира.

Answer 3

Делая несколько шагов назад от других ответов, рекурсия здесь в том, что continent_size называется восемь раз изнутри continent_size,

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

Но... каждый из этих восьми внутренних методов вызывает continent_size еще восемь раз.

И так далее, и так далее.

Это безумие, когда ты думаешь об этом, но когда ты это делаешь, кажется, что ты видишь Матрицу. Хотя очень кратко.

Я наткнулся на этот вопрос в поисках какой-то помощи с битом расширения задачи (как избежать ошибки, если один из ваших "исследователей" упадет с края света).

Я закончил тем, что решил это спасением:

# If it's off the edge of the world, it's as good as water
square = world[y][x] rescue 'o'

if square != 'Land'
  return 0
end

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

Answer 4

Я чувствую себя довольно грязно из-за того, как я решил это, и здесь ищу лучший ответ. Я создал новую переменную E = 'edge' и изменил любой символ, который касался края карты, на E. Затем я добавил этот код в начало метода continent_size:

if world[y][x] == 'edge'
        return 1
    end

Оно работает.:/

Answer 5

Я также заметил транспонирование x и y в коде Pine.
Я думаю, что причина может заключаться в том, что он расположил массив "мир" так, чтобы в каждой строке был один подмассив. Первое число в квадратных скобках после "world" (world[0]) относится к индексу элемента (подмассива) в пределах world. Так как они сложены вертикально, это ваша ось Y. Второе число в скобках (world[0][5]) относится к элементу внутри подмассива. Они идут горизонтально, поэтому второе число относится к вашей оси X. Записывая метод для получения параметра x, затем параметр y позволяет вам вводить начальное местоположение в обычном (x, y) формате, в то время как в методе переменные транспонируются для выполнения задачи. Я думаю. Я полностью новичок в этом, хотя.

Кроме того, если у кого-то есть чистое решение для расширенной версии этого упражнения, где континент "граничит с краем мира", я бы хотел его увидеть

Answer 6

Похоже, что спасательный подход все еще терпит крах, когда на верхнем краю света все в порядке. Простой подход к решению этой проблемы состоит в том, чтобы написать условие, которое проверяет, находится ли какая-либо координата (x,y) за пределами границы (то есть вне 0 или world.length-1), и возвращает 0, если это условие выполнено.

Answer 7

Мне также понадобилось некоторое время, чтобы разобраться в этом примере. Сначала я попытался решить задачу следующим образом:

  if ( world[y] > world[y].length  || world[x] > world[x].length ) || ( world[y] < world[y].length || world[x] < world[x].length )
    return 0 
  end

Но я продолжал получать ошибки "неопределенного метода">"для массива"

Затем я понял, что решение может быть в кондиционировании "x" и "y", если они больше, чем массив (10) или ниже (0):

if x > 10 || x < 0 || y > 10 || y < 0
  return 0
end

Проблема здесь в том, что он работает с определенным размером массивов... если мир больше 10 - программа будет считать каждую "землю", с которой она сталкивается, как 0.

Так что я думаю, что это только половина решения...