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

Source: codewars | Difficulty: MEDIUM
Tags: Data structures

Mathematics

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):
	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

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
			elif 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)
			elif 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