Stream: helpdesk (published)

Topic: ✔ Convert forest to list


view this post on Zulip 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.

view this post on Zulip 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

view this post on Zulip Notification Bot (Jan 25 2023 at 17:52):

Júlio Hoffimann has marked this topic as resolved.


Last updated: Nov 22 2024 at 04:41 UTC