# 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!

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Data structures

Complete search

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:
	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)
	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:
	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:
			return_list.append(list_item)
	return return_list


def normalize(nested_list, growing_value=0):
	[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):
	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:
		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):
	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))


def longest_len(arr: list):
	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):
	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:
	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:
	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)
	return working_list

def extendify(arr: list, target_depth: int, target_length: int, depth: int=1, fill_value: int=0):
	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)