Júlio Hoffimann (Jan 24 2023 at 17:32): 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:
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:
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
Júlio Hoffimann has marked this topic as resolved.
Last updated: Nov 06 2024 at 04:40 UTC