# Task

 Your task is to create a `Funnel` data structure. It consists of three basic methods: `fill()`, `drip()` and `toString()/to_s/__str__`. Its maximum capacity is 15 data.
 
 Data should be arranged in an inverted triangle, like this:
 ```
 \1 2 3 4 5/
  \7 8 9 0/
   \4 5 6/
    \2 3/
     \1/
 ```
 The string method should return a multi-line string to display current funnel data arrangement:
   ```python
 funnel = Funnel()
 print(funnel)
  \         /
   \       /
    \     /
     \   /
      \ /
```

 The method `fill()` should accept one or more arguments to fill in the funnel:

  ```python
 funnel = Funnel()
 funnel.fill(1)
 print (funnel)
  \         /
   \       /
    \     /
     \   /
      \1/
 funnel.fill(2)
 print (funnel)
  \         /
   \       /
    \     /
     \2  /
      \1/
 funnel.fill(3)
 print (funnel)
  \         /
   \       /
    \     /
     \2 3/
      \1/
 funnel.fill(4,5)
 print (funnel)
  \         /
   \       /
    \4 5  /
     \2 3/
      \1/
 funnel.fill(6,7,8,9)
 print(funnel)
  \         /
   \7 8 9  /
    \4 5 6/
     \2 3/
      \1/
 ```
  In each row, `fill()` always fill data from left to right.
 
 The method `drip()` should drip the bottom value out of funnel and returns this value:
   ```python
 (continue the example above)
 v = funnel.drip()
 print(v)
 1
 print(funnel)
  \         /
   \  8 9  /
    \7 5 6/
     \4 3/
      \2/
 ```
  
As you can see, the bottom 1 was dripping out. The number above it will fill it's place. The rules to fill are: Select one of the two numbers above it, which bear the "weight" of relatively large. In other words, there are more numbers on this number. Is this a bit hard to understand? Please see the following:
 
```
 In the example above, before the execution of drip(), funnel is:
  \         /
   \7 8 9  /
    \4 5 6/
     \2 3/
      \1/
 ```
 * After drip(), 1 will be dripped out. 
 * We should choose a number between 2 and 3 to fill the place of 1.
 * 2 has 5 numbers on it(4,5,7,8,9). 3 has 4 numbers on it(5,6,8,9)
 * So we choose 2 to fill the place of 1
 * And now, the place of 2 is empty. 
 * We also need choose a number between 4 and 5 to fill the place of 2.
 * 4 has 2 numbers on it(7,8). 5 has 2 numbers on it too(8,9)
 * There are same "weight" on 4 and 5, 
 * In this case, we choose the number on the left
 * So we choose 4 to fill the place of 2
 * And then choose 7 to fill the place of 4
 
Let us continue to `drip()`:
 
   ```python
 funnel.drip()
 print(funnel)
  \         /
   \    9  /
    \7 8 6/
     \5 3/
      \4/
 
 funnel.drip()
 print(funnel)
  \         /
   \       /
    \7 9 6/
     \8 3/
      \5/
 
 funnel.drip()
 print(funnel)
  \         /
   \       /
    \  9 6/
     \7 3/
      \8/
 
 funnel.drip()
 print(funnel)
  \         /
   \       /
    \    6/
     \7 9/
      \3/
 
 funnel.drip()
 print(funnel)
  \         /
   \       /
    \     /
     \7 6/
      \9/
 
 funnel.drip()
 print(funnel)
  \         /
   \       /
    \     /
     \  6/
      \7/
 
 funnel.drip()
 print(funnel)
  \         /
   \       /
    \     /
     \   /
      \6/
 
 funnel.drip()
 print(funnel)
  \         /
   \       /
    \     /
     \   /
      \ /
 ```
  
 When the funnel is empty, drip() will return `null/nil/None`

   
 Another edge case is: When funnel is full, fill() will not change the funnel.
 
 A bit complex...

Difficulty: MEDIUM_HARD

Starter code:
def __init__(self):
	

Solutions:
class Funnel(object):
	SIZE = 5

	def __init__(self):
		self.fun = [[None] * (x + 1) for x in range(self.SIZE)]

	def fill(self, *args):
		genBlanks = ((x, y) for (x, r) in enumerate(self.fun) for (y, v) in enumerate(r) if v is None)
		for (v, (x, y)) in zip(args, genBlanks):
			self.fun[x][y] = v

	def drip(self):
		(y, cnt) = (0, sum((v is not None for row in self.fun for v in row)))
		drop = self.fun[0][0]
		for x in range(self.SIZE - 1):
			left = cnt - sum((self.fun[xx][y + xx - x] is not None for xx in range(x, self.SIZE)))
			right = cnt - sum((self.fun[xx][y] is not None for xx in range(x, self.SIZE)))
			(ySwp, cnt) = (y, left) if left >= right else (y + 1, right)
			self.fun[x][y] = self.fun[x + 1][ySwp]
			y = ySwp
			if not cnt:
				break
		self.fun[x + 1][y] = None
		return drop

	def __str__(self):
		return '\n'.join((f"{' ' * x}\\{' '.join((' ' if v is None else str(v) for v in r))}/" for (x, r) in enumerate(reversed(self.fun))))


class Funnel(object):
	above = ((1, 2), (3, 4), (4, 5), (6, 7), (7, 8), (8, 9), (10, 11), (11, 12), (12, 13), (13, 14))
	weight = (None, (3, 4, 6, 7, 8, 10, 11, 12, 13), (4, 5, 7, 8, 9, 11, 12, 13, 14), (6, 7, 10, 11, 12), (7, 8, 11, 12, 13), (8, 9, 12, 13, 14), (10, 11), (11, 12), (12, 13), (13, 14))

	def __init__(self):
		self.f = [' '] * 15

	def fill(self, *args):
		i = 0
		for x in args:
			while i < 15 and self.f[i] != ' ':
				i += 1
			if i == 15:
				break
			self.f[i] = x

	def drip(self):
		if self.f[0] == ' ':
			return
		helper = lambda i: (self.f[i] != ' ', i < 10 and sum((self.f[j] != ' ' for j in Funnel.weight[i])) + 1)
		(res, self.f[0]) = (self.f[0], ' ')

		def rec(i=0):
			if i < 10 and self.f[i] == ' ':
				j = max(Funnel.above[i], key=helper)
				(self.f[i], self.f[j]) = (self.f[j], ' ')
				rec(j)
		return rec() or res

	def __str__(self):
		return '\\{10} {11} {12} {13} {14}/\n \\{6} {7} {8} {9}/\n  \\{3} {4} {5}/\n   \\{1} {2}/\n    \\{0}/'.format(*self.f)


class Funnel:

	def __init__(self):
		self.funnel = [[' ' for j in range(i + 1)] for i in range(5)]
		self.data = 0

	def fill(self, *args):
		for arg in args:
			if self.data < 15:
				for (indexi, i) in enumerate(self.funnel):
					if ' ' in i:
						self.funnel[indexi][i.index(' ')] = str(arg)
						self.data += 1
						break

	def count_weight_left(self, row, index):
		if self.funnel[row][index] != ' ':
			if row < 4:
				return 1 + self.count_weight_left(row + 1, index)
			else:
				return 1
		return 0

	def count_weight_both(self, row, index):
		if self.funnel[row][index] != ' ':
			if row < 4:
				return 1 + self.count_weight_left(row + 1, index) + self.count_weight_both(row + 1, index + 1)
			else:
				return 1
		return 0

	def drip(self):
		if not self.data:
			return None
		self.data -= 1
		value = int(self.funnel[0][0])
		index = 0
		for row in range(1, 5):
			if self.count_weight_both(row, index) >= self.count_weight_both(row, index + 1):
				self.funnel[row - 1][index] = self.funnel[row][index]
				self.funnel[row][index] = ' '
			else:
				self.funnel[row - 1][index] = self.funnel[row][index + 1]
				index += 1
				self.funnel[row][index] = ' '
		return value

	def __str__(self):
		string = ''
		for (index, i) in enumerate(reversed(self.funnel)):
			string += ' ' * index + '\\' + ' '.join(i) + '/\n'
		return string[:-1]


class Funnel:

	def __init__(self, levels_count=5):
		self.levels_count = levels_count
		self.__levels = [[[] for _ in range(i)] for i in range(1, self.levels_count + 1)]
		self.__curr = [0, 0]

	def __fill_one(self, d):
		curr = self.__get_curr()
		levels = self.__levels
		N = self.levels_count
		if not curr:
			return
		levels[curr[0]][curr[1]] = [d]

	def __get_curr(self):
		curr = None
		for (k, level) in enumerate(self.__levels):
			if [] in level:
				curr = [k, level.index([])]
				break
		return curr

	def fill(self, *args):
		for d in args:
			self.__fill_one(d)

	def drip(self):
		if not self.__levels[0][0]:
			return None
		r = self.__levels[0][0][0]
		self.__levels[0][0] = []
		N = self.levels_count
		hole = [0, 0]
		while hole:
			if hole[0] + 1 >= N:
				break
			a = [hole[0] + 1, hole[1]]
			b = [hole[0] + 1, hole[1] + 1]
			if self.__levels[a[0]][a[1]] == [] and self.__levels[b[0]][b[1]] == []:
				break
			c = max(a, b, key=lambda x: len(self.__get_childs(x[0], x[1])))
			self.__levels[hole[0]][hole[1]] = self.__levels[c[0]][c[1]]
			hole = c
			self.__levels[hole[0]][hole[1]] = []
			self.__curr = hole
		return r

	def __get_childs(self, level_i, list_j):
		N = self.levels_count
		delta = N - level_i
		r = [self.__levels[level_i][list_j]] + [self.__levels[level_i + k][list_j:list_j + k + 1] for k in range(1, delta)]
		r = [v2 for v1 in r for v2 in v1 if v2 != []]
		return r

	def __str__(self):
		N = self.levels_count
		pr = []
		for l in self.__levels:
			t = ' '.join([str(e[0]) if len(e) == 1 else ' ' for e in l])
			n = (2 * N - 1 - len(t)) // 2
			t = ' ' * n + '\\' + t + '/'
			pr.append(t)
		return '\n'.join(pr[::-1])


def check(lst, row, col):
	rows = [i for i in [-1, -2, -3, -4, -5] if i < row - 1]
	idx1 = (row - 1, col)
	val1 = lst[row - 1][col]
	try:
		idx2 = (row - 1, col + 1)
		val2 = lst[row - 1][col + 1]
	except:
		return idx1
	(c1, w) = (0, 2)
	for i in rows:
		for j in range(col, col + w):
			try:
				if lst[i][j] != ' ':
					c1 += 1
			except:
				pass
		w += 1
	(c2, w) = (0, 2)
	for i in rows:
		for j in range(col + 1, col + 1 + w):
			try:
				if lst[i][j] != ' ':
					c2 += 1
			except:
				pass
		w += 1
	if val1 == ' ' and val2 != ' ':
		return idx2
	if val1 != ' ' and val2 == ' ':
		return idx1
	if val1 != ' ' and val2 == ' ':
		return idx1
	if c1 >= c2:
		return idx1
	if c2 > c1:
		return idx2

class Funnel(object):

	def __init__(self):
		self.lst = [[' ', ' ', ' ', ' ', ' '], [' ', ' ', ' ', ' '], [' ', ' ', ' '], [' ', ' '], [' ']]

	def fill(self, *args):
		args = list(args)
		if args != []:
			for i in [-1, -2, -3, -4, -5]:
				c = abs(i)
				x = self.lst[i]
				f = False
				for j in range(c):
					if x[j] == ' ':
						x[j] = args.pop(0)
						if args == []:
							f = True
							break
				self.lst[i] = x
				if f == True:
					break
			return self.lst
		return self.lst

	def drip(self):
		if self.lst[-1][-1] != ' ':
			val = self.lst[-1][-1]
			self.lst[-1][-1] = ' '
			idx = 0
			for i in [-1, -2, -3, -4]:
				res = check(self.lst, i, idx)
				self.lst[i][idx] = self.lst[res[0]][res[1]]
				self.lst[res[0]][res[1]] = ' '
				idx = res[1]
			return val

	def __str__(self):
		res = [' ' * i + '\\' + ' '.join(list(map(str, e))) + '/' for (i, e) in enumerate(self.lst)]
		return '\n'.join(res)


class Funnel(object):

	def __init__(self):
		self.data = [[None] * i for i in range(1, 6)]
		self.number_elements = 0

	def fill(self, *args):
		for new_elem in args:
			added = False
			if self.number_elements < 15:
				for row in self.data:
					for i in range(len(row)):
						if row[i] is None and (not added):
							row[i] = new_elem
							added = True
							self.number_elements += 1

	def get_elem_above(self, row, idx):
		if row >= 5 or self.data[row][idx] is None:
			return []
		return [(row, idx)] + self.get_elem_above(row + 1, idx) + self.get_elem_above(row + 1, idx + 1)

	def get_number_above(self, row, idx):
		return len(set(self.get_elem_above(row, idx)))

	def drip(self):
		node = self.data[0][0]
		self.number_elements -= 1
		current_row = 0
		current_idx = 0
		while current_row <= 4 and self.data[current_row][current_idx] is not None:
			print(self.get_number_above(current_row + 1, current_idx))
			print(self.get_number_above(current_row + 1, current_idx + 1))
			print(current_row, current_idx)
			if self.get_number_above(current_row + 1, current_idx) >= self.get_number_above(current_row + 1, current_idx + 1):
				self.data[current_row][current_idx] = None if current_row == 4 else self.data[current_row + 1][current_idx]
				current_row += 1
			else:
				self.data[current_row][current_idx] = None if current_row == 4 else self.data[current_row + 1][current_idx + 1]
				current_row += 1
				current_idx += 1
		return node

	def __str__(self):
		res = ''
		for (i, row) in enumerate(self.data[::-1]):
			res += ' ' * i + '\\' + ' '.join([str(elem) if elem is not None else ' ' for elem in row]) + '/\n'
		return res[:-1]


from typing import Tuple

class Funnel:

	def __init__(self):
		self.levels = [[None] * (i + 1) for i in reversed(range(5))]

	def __getitem__(self, indexes: Tuple[int, int]):
		(r, c) = indexes
		if 0 <= r < 5 and 0 <= c < 5 - r:
			return self.levels[r][c]

	def fill(self, *args):
		free = ((x, y) for (x, row) in reversed([*enumerate(self.levels)]) for (y, a) in enumerate(row) if a is None)
		for ((x, y), val) in zip(free, args):
			self.levels[x][y] = val

	def above(self, r: int, c: int):
		if r >= 0 and c >= 0 and (self[r, c] is not None):
			yield (r, c)
			for d in range(2):
				if self[r - 1, c + d] is not None:
					yield (r - 1, c + d)
					yield from self.above(r - 1, c + d)

	def drip(self, row: int=4, col: int=0):
		if row >= 0:
			(left, right) = (len({*self.above(row - 1, col + d)}) for d in range(2))
			(self.levels[row][col], val) = (self.drip(row - 1, col + (right > left)), self.levels[row][col])
			return val

	def __str__(self):
		return '\n'.join((f"{' ' * i}\\{' '.join((' ' if x is None else str(x) for x in row))}/" for (i, row) in enumerate(self.levels)))


class Node(object):

	def __init__(self, value=None, left_child=None, right_child=None):
		self.value = None if value is None else str(value)
		self.left_child = left_child
		self.right_child = right_child
		self.visited = False

	def is_empty(self):
		return self.value is None

	def has_value(self):
		return self.value is not None

	def is_top_level(self):
		return self.left_child is None

	def is_leaf(self):
		return self.is_top_level() or not (self.left_child.has_value() or self.right_child.has_value())

	def num_children_recursive(self):
		if self.is_empty():
			return 0
		if self.is_top_level():
			return 1
		children = [p for p in [self.left_child, self.right_child] if p.has_value() and (not p.visited)]
		for child in children:
			child.visited = True
		return (1 if self.has_value() else 0) + sum((p.num_children_recursive() for p in children))

	def drip(self):
		original_value = self.value
		if self.is_empty() or self.is_top_level():
			self.value = None
		else:
			num_children_left = self.left_child.num_children_recursive()
			self.reset_visited_recursive()
			num_children_right = self.right_child.num_children_recursive()
			self.reset_visited_recursive()
			if num_children_left >= num_children_right:
				self.value = self.left_child.drip()
			else:
				self.value = self.right_child.drip()
		return original_value

	def reset_visited_recursive(self):
		self.visited = False
		if not self.is_top_level():
			self.left_child.reset_visited_recursive()
			self.right_child.reset_visited_recursive()

	def __str__(self):
		return str(self.value) if self.has_value() else ' '

class Funnel(object):

	def __init__(self):
		self.count = 0
		prev_level = [Node() for _ in range(5)]
		for i in range(4, 0, -1):
			level = [Node() for _ in range(i)]
			for (j, parent) in enumerate(level):
				parent.left_child = prev_level[j]
				parent.right_child = prev_level[j + 1]
			prev_level = level
		self.root = prev_level[0]

	def fill(self, *args):
		for value in args:
			self.fill_one(value)

	def fill_one(self, value):
		if self.count < 15:
			if self.root.is_empty():
				self.root.value = value
			else:
				pool = [self.root]
				space_found = False
				while not space_found:
					for (i, node) in enumerate(pool):
						if node.left_child.is_empty():
							node.left_child.value = value
							space_found = True
							break
						elif node.right_child.is_empty():
							node.right_child.value = value
							space_found = True
							break
					children = [n.left_child for n in pool] + [pool[-1].right_child]
					pool = children
			self.count += 1

	def drip(self):
		if self.count == 0:
			return None
		self.count -= 1
		return self.root.drip()

	def get_levels(self):
		pool = [self.root]
		levels = []
		levels.insert(0, pool)
		for i in range(4):
			pool = [n.left_child for n in pool] + [pool[-1].right_child]
			levels.insert(0, pool)
		return levels

	def __str__(self):
		s = ''
		for (i, level) in enumerate(self.get_levels()):
			s += ' ' * i + '\\' + ' '.join([str(n) for n in level]) + '/\n'
		return s[:-1]


class Funnel(object):

	def __init__(self):
		self.data = [[None for _ in range(row + 1)] for row in range(5)]

	def fill(self, *args):
		if args:
			for row in self.data:
				for (i, val) in enumerate(row):
					if val == None:
						(row[i], args) = (args[0], args[1:])
						if not args:
							return

	def __weight(self, pos, hist):
		if pos in hist:
			return 0
		(y, x) = pos
		if not (0 <= y < len(self.data) and 0 <= x < len(self.data[y])):
			return 0
		hist.append(pos)
		return 0 if self.data[y][x] == None else 1 + sum((self.__weight(p, hist) for p in ((y + 1, x), (y + 1, x + 1))))

	def drip(self):
		ret = self.data[0][0]
		pos = (0, 0)
		top = [(1, 0), (1, 1)]
		while True:
			top = [(pos[0] + 1, pos[1] + i) for i in range(2)]
			top = [(x, self.__weight(x, [])) for x in top]
			top = list([x for x in top if x[1] != 0])
			if not top:
				if pos == (0, 0):
					self.data[pos[0]][pos[1]] = None
				return ret
			top.sort(key=lambda x: x[1], reverse=True)
			t_pos = top[0][0]
			self.data[pos[0]][pos[1]] = self.data[t_pos[0]][t_pos[1]]
			self.data[t_pos[0]][t_pos[1]] = None
			pos = t_pos

	def __str__(self):
		str_row = lambda r: str(r).replace('[', '\\').replace(']', '/').replace(',', '').replace('None', ' ').replace("'", '').center(11, ' ').rstrip()
		return '\n'.join((str_row(row) for row in self.data[::-1]))