I am trying to process data in a 2D list. I understand that all objects are immutable. My recursive calls are backtracking and state is disappearing. What is the standard approach for dealing with this, when you have no state?
defmodule Euler do
def euler_15() do
grid = create_2d_list(10, 10)
# write out 1's to the first row
grid = write_out_first_row(grid, 0)
grid = write_out_first_column(grid, 0)
fill_out_remainder(grid, 1, 1)
end
def fill_out_remainder(grid, 10, _) do
IO.puts("finale to fill_out_remainder")
end
def write_out_column(grid, row, 10) do
IO.puts("finale! to write out column is running for row: #{row}")
end
def write_out_column(grid, row, col) do
IO.puts("*** write out column is running for column: #{col} and row: #{row}")
IO.puts("Reading from this grid state")
IO.inspect(grid)
cell_above = get_element(grid, row-1, col)
IO.puts("value from column above is: #{cell_above}")
cell_left = get_element(grid, row, col-1)
IO.puts("value from left cell is: #{cell_left}")
grid = set_element(grid,row,col,cell_above+cell_left)
IO.inspect(grid)
write_out_column(grid, row, col+1)
end
def write_out_row(grid, row) do
write_out_column(grid, row, 1)
end
def fill_out_remainder(grid, row_ct, col_ct) do
write_out_row(grid, row_ct)
fill_out_remainder(grid, row_ct + 1, col_ct)
end
def write_out_first_row(grid, 10) do
grid
end
def write_out_first_row(grid, counter) do
grid = set_element(grid, 0, counter, 1)
write_out_first_row(grid, counter + 1)
end
def write_out_first_column(grid, 10) do
grid
end
def write_out_first_column(grid, counter) do
grid = set_element(grid, counter, 0, 1)
write_out_first_column(grid, counter + 1)
end
def create_2d_list(rows, cols) do
for _ <- 1..rows, do: for(_ <- 1..cols, do: nil)
end
def get_element(grid, r, c) do
# first step - extract the row
the_row = Enum.at(grid, r)
# now get the value
Enum.at(the_row,c)
end
def set_element(grid, r, c, new_value) do
# stage 1 - extract the row
the_row = Enum.at(grid, r)
# stage 2 - update the row
the_row = List.replace_at(the_row, c, new_value)
# stage 3 - update the 2d lists row to be changed
# with the updated row
grid = List.replace_at(grid, r, the_row)
grid
end
end
Euler.euler_15()
Euler 15 is a typical dynamic programming problem. Here are my approaches. (All indices are 1-based)
The "standard" way is to make the recursive call take the state along with all other args, and return both the result of that recursion and the updated state.
defmodule Euler do
def euler_15(rows, cols) do
# The first arg is the "state",
# which I prefer to call it "memo".
{routes, _memo} = solve(%{}, rows, cols, 1, 1)
routes
end
# The recursive function should return
# both the number of routes
# and the updated memo.
defp solve(memo, rows, _cols, rows, _j), do: {1, memo}
defp solve(memo, _rows, cols, _i, cols), do: {1, memo}
defp solve(memo, rows, cols, i, j) do
case memo[{i, j}] do
nil ->
{right, memo} = solve(memo, rows, cols, i, j + 1)
{down, memo} = solve(memo, rows, cols, i + 1, j)
routes = right + down
memo = Map.put(memo, {i, j}, routes)
{routes, memo}
routes ->
{routes, memo}
end
end
end
This is my way of solving memoization problems by bringing back the mutability. This is easier to code than V1 and runs faster, too.
defmodule Euler do
def euler_15(rows, cols) do
# Because we are going to use process dictionary as the memo,
# and we don't want to pollute the process dictionary of the caller,
# we just spawn a child process to do all the nasty work.
Task.async(fn ->
solve(rows, cols, 1, 1)
end)
|> Task.await()
end
# The process dictionary is the memo,
# so we don't need to pass in the memo any more.
# We don't need to return the memo, either.
defp solve(rows, _cols, rows, _j), do: 1
defp solve(_rows, cols, _i, cols), do: 1
defp solve(rows, cols, i, j) do
memoized({i, j}, fn ->
right = solve(rows, cols, i, j + 1)
down = solve(rows, cols, i + 1, j)
right + down
end)
end
defp memoized(key, fun) do
case Process.get(key) do
nil ->
val = fun.()
Process.put(key, val)
val
val ->
val
end
end
end
You still need to keep tracking of the updated memo.
defmodule Euler do
def euler_15(rows, cols) do
memo = for i <- 1..rows, into: %{} do
{{i, 1}, 1}
end
memo = for j <- 1..cols, into: memo do
{{1, j}, 1}
end
memo = for i <- 2..rows, j <- 2..cols, reduce: memo do
memo -> Map.put(memo, {i, j}, memo[{i - 1, j}] + memo[{i, j - 1}])
end
memo[{rows, cols}]
end
end