I found this tool in my Grandpa's attic. clear solution for On the same path by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

I found this tool in my Grandpa's attic. solution in Clear category for On the same path by veky

import itertools

def on_same_path(main_tree, pairs):
    def visit(tree):
        root, subtrees = tree
        start = next(step)
        for subtree in subtrees: visit(subtree)
        span[root] = slice(start, next(step))

    step = itertools.count()
    span = {}
    visit(main_tree)

    for a, b in pairs:
        yield (span[a].start < span[b].start) == (span[b].stop < span[a].stop)

Jan. 5, 2020

Comments:

veky on Jan. 5, 2020, 5:17 p.m.
Thanks @Phil15 for the idea!

juestr on Dec. 2, 2021, 5:12 p.m.
That's cool, but I guess it relies on unique node values. Which the examples and tests imply, and maybe graph theory also, but my developer self would have needed it spelled out. :/

veky on Dec. 2, 2021, 5:53 p.m.
I'm not quite sure what you mean... surely if the values are repeated, then "are they on the same path" is not well defined. Moreover, the task text speaks of the values as nodes themselves, so if they are repeated, then we in fact have a cycle and don't have a tree at all.

juestr on Dec. 2, 2021, 6:23 p.m.
I was thinking of trees as data structures which allow this: <pre class='brush: python'> 1 / \ 2 2 / \ 3 4 </pre> I expect you code won't recognize `(2, 3)` as on the same path, because the second `2` branch overwrites `span[2]`. But I think it is safe to assume this was not the intended problem.

veky on Dec. 2, 2021, 6:29 p.m.
Now I understand you, but I think you don't understand me. :-] First, if you consider nodes being fetched by their labels, then "whether 2 and 3 are on the same path" is ambiguous, because what node the label 2 refers to is ambiguous. So the answer "True" is equally correct as the answer "False". Second, if you read the task text carefully, you'll see that it refers to numbers themselves as nodes, not as their labels. That means your structure is in fact <pre class='brush: python'> 1 < > 2 / \ 3 4 </pre> and it is not a tree (it is not even a simple graph) since it has a double edge between nodes 1 and 2.

juestr on Dec. 2, 2021, 9:10 p.m.
Since we are using a nested set tree representation and due to distinct object identities of 1's subtrees in Python I wouldn't accept this interpretation easily. But it's pretty clear I misunderstood the intended task regardless of its clarity, and it's a much more interesting problem your way.

veky on Dec. 3, 2021, 3:44 a.m.
I agree that the paragraph in my post above starting with "Second," is a bit far-fetched, and only comes from literal reading of the task text. However, the one starting with "First," is a real problem with your interpretation. I can as correctly say that nodes labelled 2 and 3 aren't on the same path, as you can say that they are.

Rock

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!