The thread formerly known as "Weekend Coding"


This sort of automagic refactoring/editing wizardry is also easier to pull off in a statically typed language like C++.


The Community Edition has 99% of what you probably would want to do anyway, looking at this comparison:

split this topic #164

A post was merged into an existing topic: Advent of Code


Python’s flickrapi is pretty good. I trimmed my flickr photos down to 1000 using my own criteria rather than SmugMug’s most-recent hammer. It wasn’t so much a script as an interactive python session.


The engine used to make Wargroove is now open source.


So I actually ran into a “real” coding problem at work that activated the Zachtronics area of my brain. It seems so simple on the surface that it should be trivial. There should just be some easy trick to make it happen, especially in Python. Yet, it actually took me like 20 lines and two recursions, and that feels wrong. There should definitely be some easier way to do this. Anyone want to try?

Ok, so there is a tree, but you don’t have to worry about the whole tree. We only have to look at one branch of the tree. We start with a single node and just follow its parents to the root of the tree and we get a single branch, which is now represented as a dictionary like this:

{'a': 1, 'parent': {'a': 2, 'parent': {'a': 3: 'parent': None}}}

For any such given tree branch, remove all the ‘parent’ keys and instead replace them with ‘child’ keys, basically reversing the dictionary so that the root of the tree is the top level dictionary. Preserve all other keys and values on all the dictionaries. In this case, the only other key is ‘a’. This must work for any branch that is within the recursion limit. The correct output for our test case would be:

{'a': 3, 'child': {'a': 2, 'child': {'a': 1, 'child': None}}}

Here is the code I have written to do this that I feel is far from perfect:

    def parent_to_child(tree):

        def recursive_dict_to_stack(rdict):
            stack = []
            parent = rdict.pop('parent', None)
            if parent is not None:
                stack += recursive_dict_to_stack(parent)
            return stack

        stack = recursive_dict_to_stack(tree)

        def stack_to_newtree(stack):
            top = stack.pop()
            if stack:
                top['child'] = stack_to_newtree(stack)
            return top

        return stack_to_newtree(stack)

As you can see I’m basically recursively traversing the branch to push every node onto a stack. Then I peel them off and recursively build a new branch in reverse.

Can you do better?


Don’t bother with recursion.

def invert(tree: dict):
    curr = tree
    stack = []
    while curr is not None and 'parent' in curr:
        curr = curr.pop('parent')
    root = stack.pop()
    curr = root
    while len(stack) > 0:
        curr.pop('parent', None)
        curr['child'] = stack.pop()
        curr = curr['child']

    curr['child'] = None
    return root

Copyright me, all rights reserved


I mean, yeah, that’s good, but it’s basically the same solution, only iterative instead of recursive. You got one loop to fill the stack and one loop to peel it off. I’m looking for a solution that is structurally different.


So not recursive, and not iterative? Some itertools or zip type fancy two liner or something?


Yeah, that’s what I was hoping for. Or at least one loop instead of two.


How about a single recurse?

def invert2(tree, child=None):
    if tree is not None and 'parent' in tree:
        parent = invert2(tree['parent'], tree)
        tree['child'] = child
        tree.pop('parent', None)
        return parent or tree

    return tree