Stream: helpdesk (published)

Topic: Convert forest to list

Júlio Hoffimann (Jan 24 2023 at 17:32):

I am stuck with a simple recursion algorithm, and would appreciate any help.

Suppose we are given a data structure like

input = [(1,[(2,[(4,[])]),(3,[])]),  (5,[(6,[])])]

This data structure represents a forest of trees of geometries:

20230124_141753.jpg

I would like to convert this structure into a new structure:

output = [(1,[2,3]), (4,[]), (5,[6])]

that emphasizes the parity of the circles.

Namely, the circle 1 is odd and has inner circles 2 and 3 that are even, the circle 5 is odd and has inner circle 6 that is even, and the circle 4 is odd again without inner circles:

20230124_142342.jpg

Can you write a simple function that takes the input above and produces the desired output? I spent the whole morning trying to write it down, but my brain is not working today.

Júlio Hoffimann (Jan 25 2023 at 15:54):

Nothing like a good night of sleep :ok:

Here is a solution with breadth-first-search:

answer(input) = mapreduce(bfs, vcat, input)

function bfs(root)
  record(node) = (first(node), first.(last(node)))

  visited = []
  frontier = [root]
  while !isempty(frontier)
    node = popfirst!(frontier)

    seen = false
    for vnode in visited
      if first(node) ∈ last(vnode)
        seen = true
        break
      end
    end

    if !seen
      push!(visited, record(node))
    end

    for child in last(node)
      push!(frontier, child)
    end
  end

  visited
end

Last updated: Oct 02 2023 at 04:34 UTC