# The Kata
Your task is to transform an input nested list into an hypercube list, which is a special kind of nested list where each level must have the very same size,
This Kata is an exercise on recursion and algorithms. You will need to visualize many aspects of this question to be able to solve it efficiently, as such there is a section on definitions of the terms that will be used in the Kata, make sure to fully understand them before attempting. A naive brute-force-ish answer will most likely fail the tests. There will be tests on  nested lists of dimension and size up to 10. Good luck.


# Definitions
### Nested List
A nested list is a list that may contain either non-list items or more nested lists as items in the list. Here are a few examples of nested lists.

    [[2, 3], 4, 5, 6, [2, [2, 3, 4, 5], 2, 1, 2], [[[[1]]]], []]
    [[[]]]
    [1, 2]
    [[], []]
    [4, 5, 6, 7, [], 2]
    []


- A *basic element* refers to any non-list element of a nested list.


- A nested list's *dimension* is defined as the deepest the list goes.  


- A nested list's *size* is defined as the longest the list or any of its sublists go.  

For example, the *dimension* and *size* of the above nested lists is as follows.

    [[2, 3], 4, 5, 6, [2, [2, 3, 4, 5], 2, 1, 2], [[[[1]]]], []]  # dimension: 5, size: 7
    [[[]]]                                                        # dimension: 3, size: 1
    [1, 2]                                                        # dimension: 1, size: 2
    [[], []]                                                      # dimension: 2, size: 2
    [4, 5, 6, 7, [], 2]                                           # dimension: 2, size: 6
    []                                                            # dimension: 1, size: 0


### Hypercube List
- A `1`-dimensional **hypercube list** of size `n` is a nested list of dimension `1` and size `n`.  


- A `d`-dimensional hypercube list of size `n` is a nested list of dimension `d` and size `n` such that the nested list has `n` elements each of which is a `d - 1`-dimensional hypercube list of size `n`.  


Here are some examples of hypercube lists.

    [1]                                                       # dimension: 1, size: 1
    [[1, 2], [3, 4]]                                          # dimension: 2, size: 2
    [[1, 2, 3], [4, 5, 6], [7, 8, 9]]                         # dimension: 2, size: 3
    [[0]]                                                     # dimension: 2, size: 1
    [[[0, 0], [1, 1]], [[2, 2], [3, 3]]]                      # dimension: 3, size: 2
    [1, 2, 3, 4]                                              # dimension: 1, size: 4
    [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]  # dimension: 2, size: 4


# The Task
Your task is to implement `normalize` which converts any given `nested_list` to be in hypercube format with the same dimension and size as the given nested list, extending and growing with the given `growing_value`. The default growing value is the integer `0`.

### The Algorithm
In most scenarios you will encounter a nested list that does not have the same size throughout. When working on such a list the algorithm should behave as follows.

 * If a hypercube list of dimension 1 needs extra elements, append the required number of growing value elements.
 * If a hypercube list of dimension greater than 1 has a direct basic element as a child, replace it with the required hypercube list with its basic elements all being the replaced item.
 * If a hypercube list of dimension greater than 1 needs extra elements, append the required hypercube list with its basic elements all being the growing value.


Take note of the given example, it will be very helpful in understanding the intricacies of the algorithm.

    >>> normalize(
            [
                [
                    [2, 3, 4],
                    [1, 2],
                    2,
                    [1]
                ],
                [
                    2,
                    [2, 3],
                    1,
                    4,
                    [2, 2, 6, 7]
                ],
                5
            ]
        )
        
Gives the following result.

    [
        [
            [2, 3, 4, 0, 0],
            [1, 2, 0, 0, 0],
            [2, 2, 2, 2, 2],
            [1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0]
        ],
        [
            [2, 2, 2, 2, 2],
            [2, 3, 0, 0, 0],
            [1, 1, 1, 1, 1],
            [4, 4, 4, 4, 4],
            [2, 2, 6, 7, 0]
        ],
        [
            [5, 5, 5, 5, 5],
            [5, 5, 5, 5, 5],
            [5, 5, 5, 5, 5],
            [5, 5, 5, 5, 5],
            [5, 5, 5, 5, 5]
        ],
        [
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0]
        ],
        [
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0]
        ]
    ]


Good luck!

Difficulty: interview

Starter code:

def normalize(nested_list, growing_value=0):
	

Solutions:
from itertools import zip_longest

def normalize(lst, growing=0):
    
    def seeker(lst, d=1):
        yield len(lst), d
        for elt in lst:
            if isinstance(elt,list):
                yield from seeker(elt, d+1)
    
    def grower(lst, d=1):
        return [ grower(o if isinstance(o,list) else [o]*size, d+1)
                    if d != depth else o
                 for o,_ in zip_longest(lst,range(size), fillvalue=growing) ]
                 
    size,depth = map(max, zip(*seeker(lst)))
    return grower(lst)

def H(Q) :
    D,S = 0,len(Q)
    for V in Q :
        if list == type(V) :
            d,s = H(V)
            D,S = max(d,D),max(s,S)
    return 1 + D,S
def W(Q,R,D,S) :
    Q = Q + [R] * (S - len(Q))
    return [W(V if list == type(V) else [V] * S,R,D - 1,S) for V in Q] if D - 1 else Q
normalize = lambda Q,R = 0 : W(Q,R,*H(Q))

def normalize(nested_list: List, growing_value: int = 0) -> List:
    """Convert the given nested list to hypercube format with the given <growing_value> and return it.
    """
    return extend(nested_list, dimension(nested_list), size(nested_list), growing_value)

def extend(nl, dimension, size, growing_value):
    if dimension == 1:
        try: s = len(nl)
        except TypeError: return [nl] * size
        return nl + [growing_value] * (size-s)
    # dimension > 1
    try:
        s = len(nl)
    except TypeError:
        return [extend(nl, dimension-1, size, growing_value)] * size
    else:
        return ([extend(sl, dimension-1, size, growing_value) for sl in nl] +
                [extend(growing_value, dimension-1, size, growing_value)] * (size-s))

def dimension(nested_list):
    try:
        return 1 + max((dimension(l) for l in nested_list), default=0)
    except TypeError:
        return 0

def size(nested_list):
    try:
        d = len(nested_list)
    except TypeError:
        return 0
    return max(d, max((size(l) for l in nested_list), default=0))


def get_dim(obj, _cur_dim: int=0) -> int:
    if not isinstance(obj, list):
        return _cur_dim
    elif len(obj) == 0:
        return _cur_dim + 1

    return max([get_dim(elem, _cur_dim + 1) for elem in obj])


def get_size(obj, _cur_size: int=0) -> int:
    if not isinstance(obj, list) or len(obj) == 0:
        return 0

    return max([len(obj), max([get_size(elem) for elem in obj])])


def _generate_for_value(value, size: int, dim: int):
    if dim == 1:
        return [value] * size

    return [_generate_for_value(value, size, dim - 1)] * size


def _normalize(obj, size: int, dim: int, growing_value: int):
    if not isinstance(obj, list):
        return _generate_for_value(obj, size, dim)

    if len(obj) == 0:
        return _generate_for_value(growing_value, size, dim)

    grow = size - len(obj)
    obj = obj + [growing_value] * grow
    
    if dim == 1:
        return obj

    return [_normalize(elem, size, dim - 1, growing_value) for elem in obj]
        

def normalize(nested_list: List, growing_value: int = 0) -> List:
    """Convert the given nested list to hypercube format with the given <growing_value> and return it.
    """
    size = get_size(nested_list)
    dim = get_dim(nested_list)
    return _normalize(nested_list, size, dim, growing_value)



from itertools import zip_longest


def normalize(nested_list, growing_value=0):
    dimension, size = list(map(max, list(zip(*get_dimension_and_size(nested_list)))))
    return do_normalize(nested_list, dimension, size, growing_value)


def get_dimension_and_size(nested_list, dimension=1):
    yield dimension, len(nested_list)
    for list_item in nested_list:
        if isinstance(list_item, list):
            yield from get_dimension_and_size(list_item, dimension + 1)


def do_normalize(nested_list, dimension, size, growing_value):
    return_list = []

    for list_item, _ in zip_longest(nested_list, list(range(size)), fillvalue=growing_value):
        if dimension > 1:
            list_to_normalize = (
                list_item if isinstance(list_item, list) else [list_item] * size
            )
            return_list.append(
                do_normalize(list_to_normalize, dimension - 1, size, growing_value)
            )
        else:  # dimension == 1
            return_list.append(list_item)

    return return_list




def normalize(nested_list, growing_value=0):
    """Convert the given nested list to hypercube format with the given growing value and return it.
    """
    [dimension, size] = get_dimension_and_size(nested_list)
    return do_normalize(nested_list, dimension, size, growing_value)


def do_normalize(current_elem, dimension, size, growing_value):
    """Convert the given current element to hypercube format with the given dimension, size
        and growing value in a recursive manner.
    """
    is_basic = is_basic_element(current_elem)
    missing_element_count = size - len(current_elem) if not is_basic else size
    current_items = [] if is_basic else current_elem
    fill_value = current_elem if is_basic else growing_value

    return_elem = []
    if dimension > 1:
        for item in current_items:
            return_elem.append(do_normalize(item, dimension - 1, size, growing_value))
        for _ in range(missing_element_count):
            return_elem.append(
                do_normalize(fill_value, dimension - 1, size, growing_value)
            )
    else:  # dimension == 1
        return_elem = list(current_items)
        return_elem.extend(repeat_value(fill_value, missing_element_count))

    return return_elem


def get_dimension_and_size(nested_list, dimension=1):
    """Find out dimension and size for the given nested list
       * A nested list's dimension is defined as the deepest the list goes.
       * A nested list's size is defined as the longest the list or any of its sublists go.
    """
    dimensions = [dimension]
    sizes = [len(nested_list)]
    for list_item in nested_list:
        if not isinstance(list_item, list):
            continue
        [dim, size] = get_dimension_and_size(list_item, dimension + 1)
        dimensions.append(dim)
        sizes.append(size)
    return [max(dimensions), max(sizes)]


def is_basic_element(elem):
    return isinstance(elem, int)


def repeat_value(value, count):
    return [value for _ in range(count)]


def normalize(nested_list, growing_value = 0):

    import copy
    dimension, size = get_params(nested_list)
    hypercube = hypercuber(copy.deepcopy(nested_list), dimension, size, growing_value)
    return hypercube

def hypercuber(lst, dimension, size, grow_val, depth=1):
    
    if len(lst) < size: lst += [grow_val for x in range(size-len(lst))]
    if depth < dimension:
        for i in range(len(lst)):
            if type(lst[i]) == int: lst[i] = [lst[i] for x in range(size)]
            lst[i] = hypercuber(lst[i], dimension, size, grow_val, depth+1)
    return lst

def get_params(lst):
    
    if any([type(elt)==list for elt in lst]):
        dim, size = 0, 1
        sub_params = [get_params(sub) for sub in lst if type(sub)==list]
        return (1 + max([sub[dim] for sub in sub_params]),
                max([len(lst)] + [sub[size] for sub in sub_params]))
    else: return (1, len(lst))


from itertools import zip_longest

def normalize(lst: List, growing: int = 0) -> List:
    """Convert the given nested list to hypercube format with the given <growing_value> and return it.
    """
    
    def seeker(lst, d = 1):
        yield len(lst), d
        for elt in lst:
            if isinstance(elt, list):
                yield from seeker(elt, d + 1)
                
    def grower(lst, d = 1):
        return [ grower(o if isinstance(o, list) else [o] * size, d + 1)
                   if d != depth else o
                 for o, _ in zip_longest(lst, list(range(size)), fillvalue=growing) ]
    
    size, depth = list(map(max, list(zip(*seeker(lst)))))
    return grower(lst)


""" codewars - Hypercube lists """


def longest_len(arr: list):
    """ longst len in a list of list-things """
    list_lens = []
    list_lens.append(len(arr))

    for curr_l in arr:
        if isinstance(curr_l, list):
            list_lens.append(len(curr_l))
            list_lens.append(longest_len(curr_l))
    return max(list_lens) if list_lens else 0


def deepest_depth(arr: list, current_depth: int = 1):
    """ returns the deepest depth """
    depths = []

    for item in arr:
        if isinstance(item, int):
            depths.append(current_depth)
        elif isinstance(item, list):
            depths.append(deepest_depth(item, current_depth + 1))
    return max(depths) if depths else current_depth


def deep_copy(nested_list: list) -> list:
    """ returns a copy """
    res = []
    for item in nested_list:
        if isinstance(item, int):
            res.append(item)
        elif isinstance(item, list):
            res.append(deep_copy(item))
    return res


def normalize(nested_list: list, growing_value: int = 0) -> list:
    """ does tha thing """
    working_list = deep_copy(nested_list)
    target_length = longest_len(working_list)
    target_depth = deepest_depth(working_list)
    extendify(
        working_list,
        target_depth,
        target_length,
        fill_value=growing_value)
    # print(len(working_list))
    return working_list


def extendify(arr: list, target_depth: int, target_length: int,
              depth: int = 1, fill_value: int = 0):
    """ extendifies an arr """

    arr.extend([fill_value] * (target_length - (len(arr))))

    if depth < target_depth:
        for i, current_item in enumerate(arr):
            if isinstance(current_item, int):
                arr[i] = extendify(
                    [],
                    target_depth,
                    target_length,
                    depth + 1,
                    fill_value=current_item)
            elif isinstance(current_item, list):
                arr[i] = extendify(
                    current_item,
                    target_depth,
                    target_length,
                    depth + 1,
                    fill_value=fill_value)
    return arr



def get_size(nested_list: List):
    
    size = len(nested_list)
    rank = 0
    
    for item in nested_list:
        if isinstance(item, list):
            new_size, new_rank = get_size(item)
            size = max(size, new_size)
            rank = max(rank, new_rank)
            
    return size, 1 + rank

def norm_list(item, rank, size, value):
    
    n_list = [item] * size if isinstance(item, int) else item + [value] * (size - len(item))

    rank = rank - 1
    
    if rank > 0:
        for idx in range(len(n_list)):
            n_list[idx] = norm_list(n_list[idx], rank, size, value)
    
    return n_list

def normalize(nested_list: List, growing_value: int = 0) -> List:
    
    size, rank = get_size(nested_list)
    return norm_list(nested_list, rank, size, growing_value)