# 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: interview

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):
    # Coding and coding...
    
    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(
            fr"{' ' * i}\{' '.join(' ' if x is None else str(x) for x in row)}/"
            for i, row in enumerate(self.levels)
        )

from typing import Tuple


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

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

    def fill(self, *args):
        args = [*args]
        for row in reversed(self.arr):
            for i, x in enumerate(row):
                if args and x is None:
                    row[i] = args.pop(0)

    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.arr[row][col], val = self.drip(row - 1, col + (right > left)), self.arr[row][col]
            return val

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



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
        # create and link up nodes for each funnel value space
        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'

        # exclude final newline
        return s[:-1]


class Funnel(object):
    # Coding and coding...
    
    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])