Как обновить все элементы вложенной карты в эликсире
Я пытаюсь реализовать в Эликсире некоторые алгоритмы генерации лабиринтов из отличной книги Лабиринты для программистов Джеймиса Бака. В императивных языках, таких как Go или V, это проще простого, но с Elixir я застрял.
Лабиринт представляет собой сетку ячеек. Ячейка содержит информацию о том, в каком направлении мы можем двигаться. Он представлен как struct с логическими элементами (north: true или east: false и т. д.). Сетка — это карта, где ключи — это кортежи {col, row}, а значения — Cells. Если mz — лабиринт, mz.grid[{0, 0}] — это ячейка, расположенная в левом верхнем углу.
Одной из основных операций является открытие пути от одной ячейки c1 к другой c2, и в большинстве случаев, если мы можем перейти от c1 к c2, мы также можем перейти от c2 к c1, что означает, что эта операция изменяет обе ячейки. Чтобы реализовать это, у меня есть функция open_to(maze, x, y, direction), которая возвращает кортеж из двух ячеек c1_new и c2_new, где информация о направлении в каждой ячейке была изменена. Затем я могу обновить сетку с помощью Enum.put(maze.grid, {x, y}, c1_new). То же самое для c2_new.
Один из самых простых алгоритмов, алгоритм бинарного дерева, должен посетить все ячейки одну за другой и открыть двунаправленную связь с одним из соседей. Двунаправленный означает, что обе ячейки должны быть обновлены, а вторая ячейка может быть посещена только позже. Я застрял на этом шаге, так как не могу найти, как обновить сетку с ячейками, возвращенными open_to(). Мой псевдокод Эликсира выглядит следующим образом:
def generate(mz) do
Enum.map(mz.grid, fn({{x, y}, c1}) ->
neighbors = [Grid.cell_to(mz, x, y, :north), Grid.cell_to(mz, x, y, :east)]
c2_dir = select_the_neighbor(neighbors) # returns one of :north, :east or nil
# Here! open_to returns the updated cells but what to do with them?
{c1_new, c2_new} = if c2_dir != nil, do: Grid.open_to(mz, x, y, c2_dir)
end)
end
Я считаю, что проблема связана с выбранной мной структурой данных и с тем, как я ее прохожу, но я не могу найти другого пути. Любая помощь приветствуется
Ответы 1
Если я понимаю вопрос, это «как каждый шаг в Enum.map/2 может обновить лабиринт и сделать его видимым друг для друга и для конечного результата?».
Там, где структуры данных в Эликсире неизменяемы, вы не изменяете данные, на которые указывает другая переменная.
В качестве простого примера, помещение пары ключ/значение в карту создает совершенно новую карту:
iex(1)> map = %{a: 3}
%{a: 3}
iex(2)> Map.put(map, :a, 4)
%{a: 4}
iex(3)> map
%{a: 3}
Аналогичным образом Enum.map/2 не предназначен для изменения чего-либо, кроме текущего значения (да и то только в новом списке, а не в исходном). Если вы хотите обновить какое-то значение на основе каждой ячейки, вы можете искать Enum.reduce/3. Он перечисляет такие вещи, как Enum.map/2, но принимает значение или «накопитель». Функция редуктора, которую вы передаете, вызывается с элементом и аккумулятором и должна возвращать обновленное значение аккумулятора. Тогда окончательное значение этого аккумулятора — это то, что возвращается из Enum.reduce/3.
Таким образом, ваш псевдокод может выглядеть примерно так:
def generate(mz) do
# don't use the c1 from enumerating the grid--it could be out of date
# you could also just enumerate the grid coordinates:
# - for x <- 0..width-1, y <- 0..height-1, do: {x, y}
# - Map.keys(mz.grid)
Enum.reduce(mz.grid, mz, fn {{x, y}, _dont_use_this_c1}, mz ->
neighbors = [Grid.cell_to(mz, x, y, :north), Grid.cell_to(mz, x, y, :east)]
if c2_dir = select_the_neighbor(neighbors) do
{c1_new, c2_new} = Grid.open_to(mz, x, y, c2_dir)
mz
|> Map.put({x, y}, c1_new)
|> Map.put(find_x_y(x, y, c2_dir), c2_new)
else
# you have to return a maze, or other iterations will try adding cells to nil
mz
end
end)
end
Спасибо, Бретт. Я не подумал инициализировать аккумулятор со всей структурой, а затем просто обновить его... Умно. Только две детали для потенциальных будущих читателей: 1/аккумулятор должен быть передан в качестве второго аргумента лямбда в
reduceи 2/это аккумулятор, который должен быть возвращен, а неmz. Спасибо за помощь