CODEWITHSUNDEEP
pythonlisttreeflatten
sten
sten

Reputation: 7476

Flatten repeatable-tree

I have a tree-like structure in List of Lists. I want to flatten it out.

 [[[[2, 1], [1, 2]], [[1, 2], [2, 1]]], [[[1, 2], [2, 1]], [[2, 1], [1, 2]]]]

Here are the rules , on the lowest level two two-item lists are combined in such a way that the middle numbers that are shared between the two lists are squashed/joined like this :

 [2, 1], [1, 2] => 212
 [1, 2], [2, 1] => 121

This will result in four - 3 element lists. In this second operation the middle 2 numbers between the two list are squashed.

 212 121 , 121 212  => 2121 , 1212 => 21212

In the next step the middle 3 numbers are squashed/joined ... and so on in the same manner.

Btw you don't need to do any checks it is guaranteed that the middle-numbers are always repeated i.e. match.

Every higher level would add one more new number to the overall sequence. Also any numbers can be used, here we have used only 1 and 2 for simplicity.

any ideas.

If you have solution in python, but other languages are welcome too. But in general I'm looking for the idea. Still testing it, but this does seem to do the work :

def squash(self, lst1, lst2):
    return lst1 + [lst2[-1]]

def unroll(self, lol):
    print lol
    if isinstance(lol[0], int) : return lol
    if isinstance(lol[0][0], int) : return self.squash(lol[0], lol[1])
    rv = [ self.unroll(lol[0]) , self.unroll(lol[1]) ]
    return self.unroll( rv )

Any simplification welcome ...

Upvotes: 3

Views: 88

Answers (1)

Ohjeah
Ohjeah

Reputation: 1307

This assumes the input of squash is always a list with 2 elements.

def isiter(x):
    try:
        iter(x)
        return True
    except TypeError:
        return False

def squash(x):
    if isiter(x[0][0]):
        return squash([squash(y) for y in x])
    else:
        return x[0] + x[1][-1:]

Upvotes: 1

Related Questions