from functools import idea clear solution for Tree Walker by veky - python coding challenges

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

from functools import idea solution in Clear category for Tree Walker by veky

from functools import singledispatch

@singledispatch
def count(tree, target): return sum(tree_walker(branch, target) for branch in tree)

@count.register(int)
@count.register(str)
def _(tree, target): return False

@count.register
def _(tree: dict, target): return tree_walker(tree.values(), target)

def tree_walker(tree, target): return tree == target or count(tree, target)

Nov. 30, 2019

Comments:

juestr on Jan. 21, 2020, 10:16 p.m.
Overkill, but educational value. You could replace `count` with a `getchildren` function, this way you get by with simpler direct recursion (and without some non obvious edge cases) in treewalker, and use only half the precious stack space. I don't like the single line def formatting.

veky on Jan. 22, 2020, 6:51 a.m.
I'd really like to see the solution you are referring to. (I'm not quite sure what `children` means in this context. Subtrees?) I agree about your "overkill" assessment, but it's simply because Python is not well-suited for this kind of polymorphism. If I wrote something like: <pre class='brush: python'>contains(tree: int|str, target) = False contains(tree: list|bag, target) = any(tree_walker(branch, target) for branch in tree) contains(tree: dict, target) = contains(tree.values(), target) tree_walker(tree, target) = tree==target or contains(tree, target) </pre> in some language that takes its typing a bit more seriously:-), I'm sure you wouldn't complain about that (and the "single line def formatting" -- these are just expressions anyway). <hr /> Independently, what are the "nonobvious edge cases" you're talking about? This is straightforward induction: base and step, by cases. The only kinda nonobvious thing is the separate "tree==target", but that's because I have to write tree_walker (and not contains) according to a specific interface. That's why I said I'd like to see the solution you're talking about (your solution can't be it, because it has the same distinctions). <hr /> Precious stack space? Are you seriously suggesting that limiting the depth of search to 500 is not ok, while limiting it to 1000 is? :-D Again, that's simply because of Python's lackadaisical treatment of static types, but `pys.recursion_limit *= 2` should take care of that. Multiplicative constants are ignored in most of the computer science anyway. :-]

juestr on Jan. 22, 2020, 10:50 a.m.
It took me a while to convince myself that the recursion is correct. The problem is going deeper with tree.values() in the dict case, if this could lead to false positives in cases like `tree={'a': 1, 'b': 2}, target=[1,2]`. It doesn't, because values() returns a view which a) works like a list in recursion and iteration due to the default case b) does not compare equal to a list even with the same elements. I created a version with direct recursion only, less logic in the helper function, and using 1-line lambdas instead <a href="https://py.checkio.org/mission/tree-walker/publications/juestr/python-3/inspired-by-veky/">here</a>. Of course this is very high level picking on a good & interesting solution already :-)

veky on Jan. 23, 2020, 10:44 a.m.
<blockquote> Of course this is very high level picking on a good & interesting solution already :-) </blockquote> Of course. But it's still interesting. :-) About your example with [1,2], I think I finally understood what's your problem with my solution. Of course, that's an unfortunate mistake: I meant to call `count` in line 11, not `treewalker` (as can be seen from my pseudocode above:). The fact that it wasn't caught is of course explained by your observations, that dictvalues([1,2]) is not the same as [1,2].

juestr on Jan. 23, 2020, 8:28 p.m.
Yes that would explain it. Sometimes I wish we could solve in Haskell for comparison directly.

veky on Jan. 23, 2020, 8:44 p.m.
Yes. :-) @oduvan, how about hs.checkio.org? :-D Haskell has its problems, but it really does take its types seriously. :-]

lisovsky on Feb. 2, 2023, 10:24 p.m.
Something new for me. Thanks!

Rock

0 %

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