In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.


Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10, 10, 10]
Output: 11

Input: answers = []
Output: 0


Note:


       answers will have length at most 1000.
       Each answers[i] will be an integer in the range [0, 999].

Difficulty: interview

Starter code:

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        

Solutions:

 import re
 
 
 class Solution:
     def calc(self, a, b, op):
         if op == '+':
             for k, v in b.items():
                 a[k] = a.get(k, 0) + v
             return a
         elif op == '-':
             for k, v in b.items():
                 a[k] = a.get(k, 0) - v
             return a
         elif op == '*':
             t = {}
             for k1, v1 in a.items():
                 for k2, v2 in b.items():
                     t[tuple(sorted(k1+k2))] = t.get(tuple(sorted(k1+k2)), 0) + v1 * v2
             return t
 
     def basicCalculatorIV(self, expression, evalvars, evalints):
         vars = {n:v for n,v in zip(evalvars, evalints)}
         d = []  # operands
         op = []
         priority = {'(': 0, '+': 1, '-': 1, '*': 2}
         for t in re.findall(r'\(|\)|[a-z]+|[0-9]+|[\+\-\*]', expression):
             if t[0].isdigit():
                 d.append({tuple():int(t)})
             elif t[0].isalpha():
                 if t in vars:
                     d.append({tuple():vars[t]})
                 else:
                     d.append({(t,): 1})
             elif t == '(':
                 op.append(t)
             elif t == ')':
                 while op and op[-1] != '(':
                     d.append(self.calc(d.pop(-2), d.pop(-1), op.pop()))
                 op.pop()
             elif t in '+-*':
                 if not op or priority[t] > priority[op[-1]]:
                     op.append(t)
                 else:
                     while op and priority[t] <= priority[op[-1]]:
                         d.append(self.calc(d.pop(-2), d.pop(-1), op.pop()))
                     op.append(t)
         while op:
             d.append(self.calc(d.pop(-2), d.pop(-1), op.pop()))
 
         res = []
         for k in sorted(d[0].keys(), key=lambda x: (-len(x), x)):
             v = d[0][k]
             if v != 0:
                 if not k:
                     res.append(str(v))
                 else:
                     res.append('%s*%s' % (v, '*'.join(k)))
         return res


from collections import Counter
 
 class Poly():
     def __init__(self,v):
         self.c = Counter()
         self.c[''] = 0
         
         if isinstance(v,int):
             self.c[''] = v
         elif isinstance(v,str):
             self.c[v] = 1
         elif isinstance(v,Counter):
             self.c = v
     
     def __add__(self,other):
         cn = Counter()
         for el,c in self.c.items():
             cn[el] += c
         for el, c in other.c.items():
             cn[el] += c
         return Poly(cn)
     
     def __sub__(self,other):
         cn = Counter()
         for el,c in self.c.items():
             cn[el] += c
         for el, c in other.c.items():
             cn[el] -= c
         return Poly(cn)
     
     def __mul__(self,other):
         cn = Counter()
         for el1, v1 in self.c.items():
             for el2, v2 in other.c.items():
                 #print(el1.split('*'))
                 sn = '*'.join(sorted(it for it in el1.split('*')+el2.split('*') if it != ''))
                 cn[sn] += v1*v2
         return Poly(cn)
     
     def toList(self):
         vet = []
         def comp(key):
             el = key[0]
             v = [it for it in el.split('*') if it != '']
             return (-len(v),v)
         
         for el,v in sorted(self.c.items(), key = comp):
             #print(len(el),el,v)
             if v == 0:
                 continue
             
             vap = [str(v)]
             vap += [it for it in el.split('*') if it != '']
             #print(vap)
             vet.append('*'.join(vap))
         
         return vet
     
     def __str__(self):
         return str(self.c)
 
 def rfind(vet,v):
     for i in range(len(vet)-1,-1,-1):
         if vet[i] == v:
             return i
     return -1
 
 class Solution:
     def basicCalculatorIV(self, expression, evalvars, evalints):
         """
         :type expression: str
         :type evalvars: List[str]
         :type evalints: List[int]
         :rtype: List[str]
         """
         
         valToInt = dict(zip(evalvars,evalints))
         self.i = 0
         def parse():
             parsed = []
             while self.i < len(expression):
                 ch = expression[self.i]
                 if ch.isalpha():
                     s = ''
                     while self.i < len(expression) and expression[self.i].isalpha():
                         s += expression[self.i]
                         self.i += 1
                     parsed.append(s if s not in valToInt else valToInt[s])
                 elif ch.isdigit():
                     s = ''
                     while self.i < len(expression) and expression[self.i].isdigit():
                         s += expression[self.i]
                         self.i += 1
                     parsed.append(int(s))
                 elif ch in '+-*':
                     self.i += 1
                     parsed.append(ch)
                 elif ch == '(':
                     self.i += 1
                     parsed.append(parse())
                 elif ch == ')':
                     self.i += 1
                     return parsed
                 else:
                     self.i += 1
             return parsed
         
         parsed = parse()
         
         def polyPlus(vet):
             if '+' in vet:
                 i = vet.index('+')
                 #print(polyPlus(vet[:i])+polyPlus(vet[i+1:]))
                 return polyPlus(vet[:i])+polyPlus(vet[i+1:])
             return polyMinus(vet)
         
         def polyMinus(vet):
             if '-' in vet:
                 i = rfind(vet,'-')
                 #print(polyMinus(vet[:1])-polyMinus(vet[2:]))
                 return polyMinus(vet[:i])-polyMinus(vet[i+1:])
             return polyTimes(vet)
         
         def polyTimes(vet):
             if '*' in vet:
                 i = vet.index('*')
                 return polyTimes(vet[:i])*polyTimes(vet[i+1:])
             return polyElement(vet)
         
         def polyElement(vet):
             if len(vet) == 0:
                 return Poly(None)
             assert len(vet) == 1
             el = vet[0]
             if isinstance(el,list):
                 return polyPlus(el)
             return Poly(el)
             
         polyAns = polyPlus(parsed)
         ans = polyAns.toList()
         return ans


class Identifier:
     def __init__(self, name):
         self.name = name
 
     def __str__(self):
         return "{}".format(self.name)
 
 class Number:
     def __init__(self, value):
         self.value = value
 
     def __str__(self):
         return "{}".format(self.value)
 
 class Binary:
     def __init__(self, op, left, right):
         self.op = op
         self.left = left
         self.right = right
 
     def __str__(self):
         return "({} {} {})".format(self.left, self.op, self.right)
 
 class Solution:
     def basicCalculatorIV(self, expression, evalvars, evalints):
         """
         :type expression: str
         :type evalvars: List[str]
         :type evalints: List[int]
         :rtype: List[str]
         """
         variables = dict(zip(evalvars, evalints))
 
         def lex(string):
             output = []
             i = 0
             while i < len(string):
                 if string[i] == " ":
                     i += 1
                 elif string[i] in "()*+-":
                     output.append(string[i])
                     i += 1
                 elif string[i].islower():
                     j = i
                     while j < len(string) and string[j].islower():
                         j += 1
                     name = string[i:j]
                     output.append(Identifier(name))
                     i = j
                 elif string[i].isdigit():
                     j = i
                     while j < len(string) and string[j].isdigit():
                         j += 1
                     value = int(string[i:j])
                     output.append(Number(value))
                     i = j
                 else:
                     i += 1
             return output
 
         precedence = { "*" : 2, "+" : 1, "-" : 1 }
 
         def parse(tokens, p = 0):
             if not tokens:
                 return tokens, None
             elif tokens[0] == "(":
                 tokens = tokens[1:]
                 tokens, node = parse(tokens)
                 if tokens[0] != ")":
                     return tokens, None
                 tokens = tokens[1:]
             elif isinstance(tokens[0], Identifier):
                 name = tokens[0].name
                 if name in variables:
                     node = Number(variables[name])
                 else:
                     node = Identifier(name)
                 tokens = tokens[1:]
             elif isinstance(tokens[0], Number):
                 node = Number(tokens[0].value)
                 tokens = tokens[1:]
             while tokens and tokens[0] in precedence and precedence[tokens[0]] > p:
                 binary = tokens[0]
                 tokens, right = parse(tokens[1:], precedence[binary])
                 node = Binary(binary, node, right)
             return tokens, node
 
         def compare(a, b):
             if a is None or b is None:
                 return (b is None) - (a is None)
             cmp = len(a) - len(b)
             if cmp != 0:
                 return cmp
             a = " ".join(a)
             b = " ".join(b)
             return (a < b) - (a > b)
 
         def evaluate(ast):
             if isinstance(ast, Identifier):
                 return [(1, [ast.name])]
             elif isinstance(ast, Number):
                 return [(ast.value, [])] if ast.value != 0 else []
             elif isinstance(ast, Binary):
                 left = evaluate(ast.left)
                 right = evaluate(ast.right)
                 if ast.op == "*":
                     output = {}
                     for a in left:
                         for b in right:
                             value = sorted(a[1] + b[1])
                             key = " ".join(value)
                             if key not in output:
                                 output[key] = 0
                             output[key] += a[0] * b[0]
                             if output[key] == 0:
                                 del output[key]
 
                     class K:
                         def __init__(self, inner):
                             self.inner = inner[1]
                         
                         def __lt__(self, other):
                             return compare(self.inner, other.inner) > 0
 
                     return sorted(map(lambda x: (x[1], x[0].split()), output.items()), key=K)
                 elif ast.op in "+-":
                     output = []
                     left = iter(left)
                     right = iter(right)
                     a = next(left, None)
                     b = next(right, None)
                     while a or b:
                         result = compare(a and a[1], b and b[1])
                         if result > 0:
                             output.append(a)
                             a = next(left, None)
                         elif result < 0:
                             output.append(b if ast.op == "+" else (-b[0], b[1]))
                             b = next(right, None)
                         else:
                             coeff = a[0] + b[0] if ast.op == "+" else a[0] - b[0]
                             if coeff != 0:
                                 output.append((coeff, a[1]))
                             a = next(left, None)
                             b = next(right, None)
                     return output
                 else:
                     return None
             else:
                 return None
 
         def format(expression):
             return ["*".join([str(e[0])] + e[1]) for e in expression]
 
         tokens = lex(expression)
         _, ast = parse(tokens)
         expression = evaluate(ast)
         output = format(expression)
 
         return output

class Solution:
     def basicCalculatorIV(self, expression, evalvars, evalints):
         """
         :type expression: str
         :type evalvars: List[str]
         :type evalints: List[int]
         :rtype: List[str]
         """
         class C(collections.Counter):
             def __add__(self, other):
                 self.update(other)
                 return self
             def __sub__(self, other):
                 self.subtract(other)
                 return self
             def __mul__(self, other):
                 product = C()
                 for x in self:
                     for y in other:
                         xy = tuple(sorted(x + y))
                         product[xy] += self[x] * other[y]
                 return product
         vals = dict(zip(evalvars, evalints))
         def f(s):
             s = str(vals.get(s, s))
             return C({(s,): 1}) if s.isalpha() else C({(): int(s)})
         c = eval(re.sub('(\w+)', r'f("\1")', expression))
         return ['*'.join((str(c[x]),) + x)
                 for x in sorted(c, key=lambda x: (-len(x), x))
                 if c[x]]        

class Solution:
     def basicCalculatorIV(self, expression, evalvars, evalints):
         """
         :type expression: str
         :type evalvars: List[str]
         :type evalints: List[int]
         :rtype: List[str]
         """
         class C(collections.Counter):
             def __add__(self, other):
                 self.update(other)
                 return self
             def __sub__(self, other):
                 self.subtract(other)
                 return self
             def __mul__(self, other):
                 product = C()
                 for x in self:
                     for y in other:
                         xy = tuple(sorted(x + y))
                         product[xy] += self[x] * other[y]
                 return product
         vals = dict(zip(evalvars, evalints))
         def f(s):
             s = str(vals.get(s, s))
             return C({(s,): 1}) if s.isalpha() else C({(): int(s)})
         c = eval(re.sub('(\w+)', r'f("\1")', expression))
         return ['*'.join((str(c[x]),) + x)
                 for x in sorted(c, key=lambda x: (-len(x), x))
                 if c[x]]

class Poly(collections.Counter):
     def __add__(self, other):
         self.update(other)
         return self
 
     def __sub__(self, other):
         self.update({k: -v for k, v in other.items()})
         return self
 
     def __mul__(self, other):
         ans = Poly()
         for k1, v1 in self.items():
             for k2, v2 in other.items():
                 ans.update({tuple(sorted(k1 + k2)): v1 * v2})
         return ans
 
     def evaluate(self, evalmap):
         ans = Poly()
         for k, c in self.items():
             free = []
             for token in k:
                 if token in evalmap:
                     c *= evalmap[token]
                 else:
                     free.append(token)
             ans[tuple(free)] += c
         return ans
 
     def to_list(self):
         return ["*".join((str(v),) + k)
                 for k, v in sorted(self.items(),
                     key = lambda x: (-len(x[0]), x[0], x[1]))
                 if v]
 
 # https://leetcode.com/problems/basic-calculator-iv/solution/
 class Solution(object):
     def basicCalculatorIV(self, expression, evalvars, evalints):
         evalmap = dict(zip(evalvars, evalints))
 
         def combine(left, right, symbol):
             if symbol == '+': return left + right
             if symbol == '-': return left - right
             if symbol == '*': return left * right
             raise
 
         def make(expr):
             ans = Poly()
             if expr.isdigit():
                 ans.update({(): int(expr)})
             else:
                 ans[(expr,)] += 1
             return ans
 
         def parse(expr):
             bucket = []
             symbols = []
             i = 0
             while i < len(expr):
                 if expr[i] == '(':
                     bal = 0
                     for j in range(i, len(expr)):
                         if expr[j] == '(': bal += 1
                         if expr[j] == ')': bal -= 1
                         if bal == 0: break
                     bucket.append(parse(expr[i+1:j]))
                     i = j
                 elif expr[i].isalnum():
                     for j in range(i, len(expr)):
                         if expr[j] == ' ':
                             bucket.append(make(expr[i:j]))
                             break
                     else:
                         bucket.append(make(expr[i:]))
                     i = j
                 elif expr[i] in '+-*':
                     symbols.append(expr[i])
                 i += 1
 
             for i in range(len(symbols) - 1, -1, -1):
                 if symbols[i] == '*':
                     bucket[i] = combine(bucket[i], bucket.pop(i+1),
                                         symbols.pop(i))
 
             if not bucket: return Poly()
             ans = bucket[0]
             for i, symbol in enumerate(symbols, 1):
                 ans = combine(ans, bucket[i], symbol)
 
             return ans
 
         P = parse(expression).evaluate(evalmap)
         return P.to_list()