I’m trying to do a very basic union-find (not doing any path compression by rank or size).
def find(dsu, x) do
case Map.get(dsu, x) do
nil ->
{Map.put(dsu, x, x), x}
^x -> {dsu, x}
y ->
{dsu2, p} = find(dsu, y)
{Map.put(dsu2, x, p), p}
end
end
def union(%{} = dsu, x, y) do
{dsu, a} = find(dsu, x)
{dsu, b} = find(dsu, y)
if a == b do
dsu
else
[a,b] = Enum.sort([a,b])
{dsu, c} = find(dsu, a)
Map.put(dsu, b, c)
end
end
The issue I’m having is that after iterating over a set of nodes I have to iterate over all the “parents” a second time because the find function isn’t recursing on those.
@spec num_islands(grid :: [[char]]) :: integer
def num_islands(grid) do
map = LandMap.new(grid)
m = grid |> length() |> Kernel.-(1)
n = hd(grid) |> length() |> Kernel.-(1)
intermediate =
0..m
|> Enum.reduce(%{}, fn x, acc ->
0..n
|> Enum.filter(fn y -> MapSet.member?(map, {x,y}) end)
|> Enum.reduce(acc, fn y, acc2 ->
acc3 = DSU.union(acc2, {x,y}, {x,y})
LandMap.neighbors({x,y}, m, n)
|> Enum.filter(fn coord -> MapSet.member?(map, coord) end)
|> Enum.reduce(acc3, fn neighbor, acc4 -> DSU.union(acc4, neighbor, {x,y}) end)
end)
end)
intermediate
|> Map.values()
|> Enum.reduce(intermediate, fn x, islands ->
case DSU.find(islands, x) do
{^islands, ^x} -> islands
{islands, y} ->
islands
|> Enum.map(fn {k, v} = curr ->
if v == x do
{k, y}
else
curr
end
end)
|> Map.new()
true -> islands
end
end)
|> Map.values()
|> Enum.uniq()
|> Enum.count()
end
If I don’t do the second pass a node that was initially it’s own parent but later linked to others will get updated, but any nodes pointing to it as parent would not be updated. Do I need to track a “parents” map and a “children” map so that I can update any children when a “parent” is updated?
)
