# Unflatten a list (Harder than easy)

This is the harder version of Unflatten a list (Easy)

So you have again to build a method, that creates new arrays, that can be flattened!

# Shorter: You have to unflatten a list/an array.

You get an array of integers and have to unflatten it by these rules:
```
- You have to do several runs. The depth is the number of runs, you have to do.
- In every run you have to switch the direction. First run from left, next run from right. Next left...
Every run has these rules:
- You start at the first number (from the direction).
- Take for every number x the remainder of the division by the number of still available elements (from 
  this position!) to have the number for the next decision.
- If the remainder-value is smaller than 3, take this number x (NOT the remainder-Value) direct
  for the new array and continue with the next number.
- If the remainder-value (e.g. 3) is greater than 2, take the next remainder-value-number (e.g. 3)
  elements/numbers (inclusive the number x, NOT the remainder-value) as a sub-array in the new array.
  Continue with the next number/element AFTER this taken elements/numbers.
- Every sub-array in the array is independent and is only one element for the progress on the array. 
  For every sub-array you have to follow the same rules for unflatten it.
  The direction is always the same as the actual run.
```

Sounds complicated? Yeah, thats why, this is the harder version...
Maybe an example will help.

```
 Array: [4, 5, 1, 7, 1] Depth: 2 -> [[ 4, [ 5, 1, 7 ] ], 1]
 
Steps: 
First run: (start from left side!)
1. The first number is 4. The number is smaller than the number of remaining elements, so it is the remainder-value (4 / 5 -> remainder 4).
   So 4 numbers (4, 5, 1, 7) are added as sub-array in the new array.
2. The next number is 1. It is smaller than 3, so the 1 is added direct to the new array.
Now we have --> [[4, 5, 1, 7], 1]

Second run: (start from right side!)
1. The last number (first from other side) is 1. So the 1 is added direct to the new array.
2. The next element is the sub-array. So we use the rules for this.
2a.The last number is 7. There are 4 elements in the array. So for the next decision you have to
   take the remainder from 7 / 4 -> 3. So 3 numbers (5, 1, 7) are added as sub-array in the 
   new array.
2b.Now there is the 4 and only one element last in this array. 4 / 1 -> remainder 0. It is smaller
   than 3. So the 4 is added direct to the new array.
Now we have --> [[ 4, [ 5, 1, 7 ] ], 1]
```

The given array will always contain numbers. There will only be numbers > 0.


Have fun coding it and please don't forget to vote and rank this kata! :-) 

I have created other katas. Have a look if you like coding and challenges.

Difficulty: interview

Starter code:

def unflatten(flat_array, depth):
	

Solutions:
unflatten=lambda m,d,c=0:m if c==d else unflatten(parse(m,[0,1][c&1]),d,c+1)

def parse(ar, lr):
      sub, i = [], [0, len(ar) - 1][lr]
      while 0 <= i < len(ar):
          j, r = ar[i], lr == 1
          if isinstance(j, list):
              sub.append(parse(j, lr))
              i += [1, -1][r]
          else:
              mod = j % len([ar[i:],ar[:i + 1]][r])
              sub.append([j, ar[i:i + (mod * [1, -1][r]):[1, -1][r]][::[1, -1][r]]][mod>=3])
              i += [mod,1][mod<3] * [1,-1][r]
      return sub[::[1, -1][lr]]

def unflatten(arr, depth, isLeft=1):
    lst,it =  [], enumerate(arr if isLeft else reversed(arr))
    for i,x in it:
        if isinstance(x,list):
            lst.append( unflatten(x,1,isLeft) )
            continue
            
        n = x % (len(arr)-i)
        if n < 3:
            lst.append(x)
        else:
            gna = [x] + [next(it)[1] for _ in range(n-1)]
            lst.append(gna if isLeft else gna[::-1])
            
    if not isLeft: lst = lst[::-1]
    
    return lst if depth==1 else unflatten(lst, depth-1, isLeft^1)

import enum


class IterDirection(enum.Enum):
    """ Direction in which we iterate/walk. """
    TowardsRight = 1,
    TowardsLeft = 2


def unflatten(arr, depth):

    def is_iterable(obj):
        try:
            iter(obj)
        except TypeError:
            return False
        else:
            return True

    def walk(arr, direction):
        if direction == IterDirection.TowardsLeft:
            a = arr[::-1]
        else:
            a = list(arr)
        index = 0

        def walk_subarray(subarray):
            if direction == IterDirection.TowardsRight:
                yield list(walk(current_element, direction))
            else:
                yield list(walk(current_element, direction))[::-1]

        while index < len(a):
            current_element = a[index]
            if is_iterable(current_element):
                yield from walk_subarray(current_element)
                index += 1
            else:
                n_elements_left = len(arr[index:])
                remainder = current_element % n_elements_left

                if remainder < 3:
                    yield current_element
                    index += 1
                else:
                    if direction == IterDirection.TowardsLeft:
                        yield a[index: index + remainder][::-1]
                    else:
                        yield a[index: index + remainder]
                    index += remainder

    from itertools import cycle, islice
    directions = (IterDirection.TowardsRight, IterDirection.TowardsLeft)

    arr_copy = list(arr)

    for direction in (islice(cycle(directions), depth)):
        if direction == IterDirection.TowardsLeft:
            arr_copy = list(walk(arr_copy, IterDirection.TowardsLeft))[::-1]
        else:
            arr_copy = list(walk(arr_copy, IterDirection.TowardsRight))
    return arr_copy


def unflatten(flat_array, depth, direction = 1):
    if depth == 0:
        return flat_array
    ind = 0
    array = []
    flat_array = flat_array[::direction]
    while ind < len(flat_array):
        nleft = len(flat_array) - ind
        elem = flat_array[ind]
        if type(flat_array[ind]) is list:
            array.append(unflatten(flat_array[ind], 1, direction))
            ind += 1
        elif elem % nleft < 3:
            array.append(elem)
            ind += 1
        else:
            array.append(flat_array[ind:ind + elem % nleft][::direction])
            ind += elem % nleft
    return unflatten(array[::direction], depth-1, -direction)

def unflatten(flat_array, depth):
    left = True
    i = 0
    new_array = flat_array

    for d in range(depth):
        new_array = unflatten_list(new_array, left, i)
        left = not left
        if left:
            i = 0
        else:
            i = len(new_array) - 1
    return new_array
        
#true = left, false = right
def unflatten_list(array, direction, i):
    new_list = []
    while (direction == True and i < len(array)) or (direction == False and i >= 0):
        elem = array[i]
        if type(elem) == list:
            if direction:
                index = 0
                new_list.append(unflatten_list(elem, direction, index))
                i += 1
            else:
                index = len(elem) - 1
                new_list.insert(0,unflatten_list(elem, direction, index))
                i -= 1
        else:
            if direction:
                residual = elem  % (len(array) - i)
            else:
                residual = elem % (i + 1)
            if residual < 3:
                if direction:
                    new_list.append(elem)
                    i += 1
                else:
                    new_list.insert(0,elem)
                    i -= 1
            else:
                if direction:
                    if(i + residual <= len(array)):
                        new_list.append(array[i:i+residual])
                        i = i + residual
                    else:
                        new_list.append(array[i:])
                        i = len(array)
                else:
                    if(i - residual <= len(array)):
                        new_list.insert(0,array[i - residual + 1: i + 1])
                        i = i - residual
                    else:
                        new_list.insert(0,array[:i+1])
                        i = -1
                    
    return new_list




def unflatten(flat_array, depth):
    r=flat_array
    direction=1
    for d in range(depth):
        r=_unflatten(r,direction)
        direction*=-1
    return r

def _unflatten(flat_array, direction):
    q=flat_array[:]
    r=[]
    while(q):
        if direction>0:
            x=q.pop(0)
        else:
            x=q.pop()
        if type(x)==list:
            if direction>0:
                r.append(_unflatten(x,direction))
            else:
                r.insert(0,_unflatten(x,direction))
        elif x%(len(q)+1)<3:
            if direction>0:
                r.append(x)
            else:
                r.insert(0,x)
        else:
            t=[x]
            for _ in range(x%(len(q)+1)-1):
                if not q:
                    break
                if direction>0:
                    t.append(q.pop(0))
                else:
                    t.append(q.pop())
            if direction>0:
                r.append(t)
            else:
                r.insert(0,t[::-1])
    return r

def unflatten(flat_array, depth, direction=1):
    if depth == 0: return flat_array
    if direction == 1:
      result, j = [], 0
      length = len(flat_array)
      while j < length:
        if isinstance(flat_array[j], list):
          result.append(unflatten(flat_array[j], 1, direction=1))
          j += 1
        else:
          remainder = flat_array[j] % (length - j)
          if remainder < 3:
              result.append(flat_array[j])
              j += 1
          else:
              result.append(flat_array[j:j+remainder])
              j += remainder
      return unflatten(result, depth-1, direction=-1)
    else:
      length = len(flat_array)
      result, j = [], length - 1
      while j >= 0:
        if isinstance(flat_array[j], list):
          result.append(unflatten(flat_array[j], 1, direction=-1))
          j -= 1
        else:
          remainder = flat_array[j] % (j + 1)
          if remainder < 3:
              result.append(flat_array[j])
              j -= 1
          else:
              result.append(flat_array[j-remainder+1:j+1])
              j -= remainder
      return unflatten(result[::-1], depth-1, direction=1)

def unflatten(flat_array, depth):
    right = True
    length = len(flat_array)
    for _ in range(depth):
        flat_array = unflatten_helper(flat_array, right)
        right = not right
    return flat_array
        
        
def unflatten_helper(arr, right):
    newArr = []
    length = len(arr)
    if right:
        i = 0
        while i < length:
            if isinstance(arr[i], list):
                newArr.append(unflatten_helper(arr[i], right))
                i += 1
            else:
                rem = arr[i] % (length - i)
                if rem > 2:
                    newArr.append(arr[i:rem+i])
                    i += rem
                else:
                    newArr.append(arr[i])
                    i += 1
    else:
        i = length - 1
        while i >= 0:
            if isinstance(arr[i], list):
                newArr.append(unflatten_helper(arr[i], right))
                i -= 1
            else:
                rem = arr[i] % (i + 1)
                if rem > 2:
                    newArr.append(arr[i-rem+1:i+1])
                    i -= rem
                else:
                    newArr.append(arr[i])
                    i -= 1
        newArr = newArr[::-1]
    return newArr


def unflatten(flat_array, depth):
    bLeft=True
    for i in range(depth):
        flat_array=oneunflatten(flat_array,bLeft)
        if bLeft==False:
            flat_array=flat_array[::-1]
        bLeft = not bLeft
    return flat_array
    
def oneunflatten(flat_array, bLeft):
    if bLeft:
        arr = flat_array[:]
        for i, v in enumerate(arr):
            if isinstance(v,int):
                if v%(len(arr)-i) > 2:
                    arr[i], arr[i+1:i+v%(len(arr)-i)] = arr[i:i+v%(len(arr)-i)], []
            else:
                arr[i]=oneunflatten(v,bLeft)
        return arr
    else:
        arr = flat_array[::-1]
        for i, v in enumerate(arr):
            if isinstance(v,int):
                if v%(len(arr)-i) > 2:
                    arr[i], arr[i+1:i+v%(len(arr)-i)] = arr[i:i+v%(len(arr)-i)], []
            else:
                arr[i]=oneunflatten(v,bLeft)
        for i, v in enumerate(arr):
            if isinstance(v,int):
                pass
            else:
                arr[i]=arr[i][::-1]
        return arr

def uf_f(arr):
    a, i = [], 0
    while i < len(arr):
        if isinstance(arr[i], list):
            a.append(uf_f(arr[i]))
            i += 1
        else:
            r = arr[i] % (len(arr) - i)
            if r < 3:
                a.append(arr[i])
                i += 1
            else:
                a.append(arr[i: i+r])
                i += r
    return a

def uf_r(arr):
    a, i = [], len(arr) - 1
    while i >= 0:
        if isinstance(arr[i], list):
            a.insert(0, uf_r(arr[i]))
            i -= 1
        else:
            r = arr[i] % (i + 1)
            if r < 3:
                a.insert(0, arr[i])
                i -= 1
            else:
                a.insert(0, arr[i-r+1: i+1])
                i -= r
    return a


def unflatten(array, depth):
    while depth:
        array = uf_f(array)
        depth -= 1
        if depth:
            array = uf_r(array)
            depth -= 1
    return array