Very readable and clean. Thank you for sharing.
code-shoily
stevensonmt
My basic understanding is the disjoint sets are useful when you need to know how many unique groups you have in a data set as defined by some connection criteria. So for this problem data points are connected if they are “land” (represented by digit 1) and they share a border. In the “Most Stones Removed” problem the connection is any shared column OR row.
My sense of why it can outperform DFS or BFS in certain situations has to do with not needing to track complete paths and the fact that paths containing cycles are no problem in disjoint sets.
I think I understand this, thanks. (And I also feel a bit frustrated with 2D grids in Elixir b/c so many of the default solutions rely on mutable data stores and access by index. Comes up a lot in Advent of Code.)
@hst337 – Thanks for the great example implementation. Really nice.
1
hst337
2D grids can be represented as :array or just a tuple
For this exact task both DisjointSets and BFS solutions will have the same exact complexity in space and time. DFS solution is not suitable here, since island is a graph, which contains a lot of different trees, thus it can have cycles in it.
1
stevensonmt
lud
In advent of code most of my grids are a map where the key is {x, y} or {x, y, z} and it is very simple to work with.
0