We are given a certain number ```n``` and we do the product partitions of it.
```[59, 3, 2, 2, 2]``` is a product partition of ```1416``` because:
```
59 * 3 * 2 * 2 * 2 = 1416
```
We form a score, ```sc``` for each partition in the following way:
- if ```d1, d2, ...., dk``` are the prime factors of ```n```, and ```f1, f2, ...., fk```, the corresponding frequencies for each factor, we calculate:



Suposse that we have that ```n = 1416``` 
The product partitions of this number with a corresponding special score are as follows:
```
Product Partition           Score(sc)
[59, 3, 2, 2, 2]             350    # equals to: (59^1 + 3^1 + 2^3) * 5
[177, 2, 2, 2]               740    # equals to: (177^1 + 2^3) * 4
[118, 3, 2, 2]               500
[59, 6, 2, 2]                276
[354, 2, 2]                 1074
[59, 4, 3, 2]                272
[236, 3, 2]                  723
[177, 4, 2]                  549
[118, 6, 2]                  378
[59, 12, 2]                  219
[708, 2]                    1420  <---- maximum value
[118, 4, 3]                  375
[59, 8, 3]                   210
[472, 3]                     950
[59, 6, 4]                   207
[354, 4]                     716
[236, 6]                     484
[177, 8]                     370
[118, 12]                    260
[59, 24]                     166  <---- minimum value
```
So we need a function that may give us the product partition with maximum or minimum score.

The function ```find_spec_prod_part()``` will receive two arguments:

- an integer ```n, n > 0```
- a command as a string, one of the following ones: ```'max' or 'min'```

The function should output a list with two elements: the found product partition (as a list sorted in descendin order) with its corresponding score.
```
find_spec_prod_part(n, com) ---> [prod_partition, score]
```
Let'see some cases:
```python
find_spec_prod_part(1416, 'max') == [[708, 2], 1420]

find_spec_prod_part(1416, 'min') == [[59, 24], 166]
```

The function should reject prime numbers:
```python
find_spec_prod_part(10007 , 'max') == "It is a prime number"
```
Enjoy it!

Hint: In this kata, optimization is one of the purposes or tags. The algorithm to produce the product partition is a key factor in terms of speed. Your code will be tested for an ```n``` value up to ```500000```.

Difficulty: interview

Starter code:

def find_spec_prod_part(n, com):
	

Solutions:
def primeFactors(n):
    
    factors = []
    
    while n % 2 == 0: 
        n /= 2
        factors.append(2)
        
    for i in range(3, int(n**.5) + 1,2): 
        while n % i == 0: 
            n /= i
            factors.insert(0, i)
            
    if n > 2: factors.insert(0, int(n))
        
    return factors
        
def score(p):
    
    last, xp, s = p[0], p[0], 0
    
    for j in p[1:]:
        if j == last:
            xp *= j
        else:
            s += xp
            xp, last = j, j
    return (s + xp) * len(p)
    

def prod(lst):
    
    res = 1
    
    for v in lst: res *= v
    return res

def multiply_partitions(partition): return [prod(sub) for sub in partition]

def partition(collection):
    
    if len(collection) == 1:
        yield [collection]
        return

    first = collection[0]
    
    for smaller in partition(collection[1:]):      
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        yield [ [ first ] ] + smaller


def find_spec_prod_part(n, com):  
    
    factors = primeFactors(n)
    
    if len(factors) == 1: return 'It is a prime number'
    
    fn = min if com == 'min' else max
    mplist = []
    best = [factors, score(factors)]
    
    for p in partition(factors):
        mp = multiply_partitions(p)
        
        if mp in mplist or mp[0]==n:
            continue            
        mplist.append(mp)
        best = fn(best, [mp, score(mp)], key=lambda x: x[1])
    
    return [sorted(best[0], reverse=True), best[1]]

def primeFactors(n):
    factors = []
    while n % 2 == 0: 
        n /= 2
        factors.append(2)
    for i in range(3,int(n**.5)+1,2): 
        while n % i == 0: 
            n /=i
            factors.insert(0, i)
    if n > 2: 
        factors.insert(0, int(n))
    return factors
        
def score(p):
    last, xp, s = p[0], p[0], 0
    for e in p[1:]:
        if e == last:
            xp *= e
        else:
            s += xp
            xp, last = e, e
    return (s + xp) * len(p)
    

def prod(lst):
    res = 1
    for v in lst: res *= v
    return res

def multiply_partitions(partition):
    return [prod(sub) for sub in partition]

def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller


def find_spec_prod_part(n, com):    
    factors = primeFactors(n)
    if len(factors) == 1: return 'It is a prime number'
    fn = min if com == 'min' else max
    mplist = []
    best = [factors, score(factors)]
    for p in partition(factors):
        mp = multiply_partitions(p)
        if mp in mplist or mp[0]==n:
            continue
        mplist.append(mp)
        best = fn(best, [mp, score(mp)], key=lambda x: x[1])
    
    return [sorted(best[0], reverse=True), best[1]]

from collections import Counter
from itertools import permutations
from itertools import chain
import numpy as np


def prime_factors(n):
    factors = []
    while n % 2 == 0:
        n = n // 2
        factors.append(2)
        
    for k in range(3, n+1, 2):
        while n % k == 0:
            n = n // k
            factors.append(k)
        if n == 1:
            break
    return factors

   
def get_score(factors):
    factor_counts = Counter(factors)
    return sum(f**factor_counts[f] for f in factor_counts)*sum(c for c in factor_counts.values())


def int_partitions(m, memo = {}):
    if m in memo:
        return memo[m]
    all_partitions = [[m]]
    
    for i in range(1, m):
        for p in int_partitions(m-i, memo):
            all_partitions.append([i] + p)
    
    memo[m] = all_partitions
    return all_partitions


def make_partitions(factors):
    partitions = int_partitions(len(factors))
    part_perm = []
    
    for p in partitions:
        part_perm.append(set(list(permutations(p, len(p)))))

    part_perm = set(list(chain.from_iterable(part_perm)))
    all_new_factors = []

    for inds in part_perm:        
        new_factors = []
        j_start = 0

        for i in inds:
            j_end = j_start + i
            new_factors.append(np.product(factors[j_start:j_end]))
            j_start = j_end
        
        if len(new_factors) > 1:
            all_new_factors.append(new_factors) 
    
    return all_new_factors


def find_spec_prod_part(n, com):
    factors = prime_factors(n)   
    
    if len(factors) == 1:
        return "It is a prime number"
    
    all_factors = make_partitions(factors)
    scores = [get_score(x) for x in all_factors]
    
    if com == "max":
        opt_id = np.argmax(scores)
    else:
        opt_id = np.argmin(scores)
    
    return [sorted(all_factors[opt_id], reverse=True), scores[opt_id]] 

from itertools import cycle, groupby, islice
from operator import lt, gt

def find_spec_prod_part(n, com):
    prime_factors = list(factor(n))
    if len(prime_factors) < 2:
        return 'It is a prime number'
    cmp = lt if com == 'min' else gt
    best_part = None
    best_score = None
    for part in set(islice(partitions(prime_factors), 1, None)):
        sc = score(part)
        if not best_score or cmp(sc, best_score):
            best_part = part
            best_score = sc
    return [list(best_part), best_score]

def factor(n):
    if n < 1: raise ValueError('factor: n must be > 0')
    for d in [2, 3, 5]:
        while n % d == 0:
            yield d
            n = n // d
    d = 7
    wheel = cycle([4, 2, 4, 2, 4, 6, 2, 6])
    while n > 1 and d * d <= n:
        if n % d == 0:
            yield d
            n = n // d
        else:
            d += next(wheel)
    if n > 1:
        yield n

def partitions(factors):
    if len(factors) == 1:
        yield factors[0],
        return
    first = factors[0]
    for subpart in partitions(factors[1:]):
        for n, fact in enumerate(subpart):
            yield tuple(sorted(subpart[:n] + (first * fact,) + subpart[n+1:], reverse=True))
        yield tuple(sorted((first,) + subpart, reverse=True))

def score(part):
    factors = [(f, len(list(g))) for f, g in groupby(part)]
    return sum(f**e for f, e in factors) * sum(e for _, e in factors)


import math
from collections import Counter
from itertools import permutations

def find_spec_prod_part(n, com):
    # your code here
    temp_partition = []    
    factors = primeFactors(n)
    counter = Counter(factors)
    max_score = calculateScore(counter)
    min_score = max_score
    partition_min = factors
    partition_max = factors
    
    x = len(factors)
    
    if len(factors) == 1:
        return "It is a prime number"
    
    perms = list(set(list(permutations(factors))))
    
    
    divs = list(accel_asc(len(factors)))     
    

    for div in divs:
        if len(div) == 1 or len(div) == len(factors):
            continue
        for perm in perms:
            temp_partition = []
            start = 0
            product = 1
            seq = []

            for i in div:
                seq = perm[start:(start+i)]
                for j in seq:
                    product *= j
                temp_partition.append(product)
                start = start+i
                product = 1

            counter = Counter(temp_partition)
            score = calculateScore(counter)
            
            if score > max_score:
                max_score = score
                partition_max = temp_partition
                
            if score < min_score:
                min_score = score
                partition_min = temp_partition
                
            
    if com == 'max':
        partition_max.sort(reverse = True)
        return [partition_max, max_score]
    if com == 'min':
        partition_min.sort(reverse = True)
        return [partition_min, min_score]


def calculateScore(count):
    score = 0
    coef = 0
    for key in count:
        score += key**count[key]
        coef += count[key]
    score = score * coef
    return score

# A function to print all prime factors of  
# a given number n 
def primeFactors(n): 
    prime_factors = []  
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        prime_factors.append(2), 
        n = n / 2
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3, int(math.sqrt(n))+1, 2): 
          
        # while i divides n, print i ad divide n 
        while n % i == 0: 
            prime_factors.append(i), 
            n = n / i 
    if n != 1:
        prime_factors.append(int(n))

    return prime_factors

def accel_asc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield a[:k + 2]
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield a[:k + 1]

from functools import reduce
from operator import mul,gt,lt
from itertools import combinations
from collections import Counter
def is_prime(n):
    if n<2:
        return False
    elif n==2:
        return True
    elif n%2==0:
        return False
    for i in range(3,int(n**0.5)+1,2):
        if n%i==0:
            return False
    return True

memo={}
    
def _prot_part(arr):
    if len(arr)<2:
        return set({(arr[0],)})
    elif len(arr)==2:
        return set([tuple(sorted(arr)),(arr[0]*arr[1],)])
    elif tuple(arr) in memo:
        return memo[tuple(arr)]
    r=set()
    for j in range(1,len(arr)//2+1):
        for t in combinations(arr,j):
            arr2=arr[:]
            for e in t:
                arr2.remove(e)
            s2=_prot_part(arr2)
            for e1 in _prot_part(list(t)):
                for e2 in s2:
                    r.add(tuple(sorted(list(e1+e2))))
    r.add((reduce(mul,arr),))
    memo[tuple(arr)]=r
    return r

def find_spec_prod_part(n, com):
    if is_prime(n):
        return 'It is a prime number'
    r=[]
    while(n%2==0):
        r.append(2)
        n//=2
    x=3
    while(n>1 and not is_prime(n)):
        while(n%x==0):
            r.append(x)
            n//=x
        x+=2
    if n>1:
        r.append(n)
    p=_prot_part(r)
    if com=='max':
        m=[None,-1]
        f=gt
    else:
        m=[None,10e10]
        f=lt
    for t in p:
        if len(t)==1:
            continue
        a,b=0,0
        for k,v in Counter(t).items():
            a+=k**v
            b+=v
        score=a*b
        if f(score,m[1]):
            m=[sorted(t,reverse=True),score]
    return m    

from numpy import prod
def find_spec_prod_part(n, com):
    partitions = []
    current_partition = 2
    while n > 1:
        if n % current_partition == 0:
            partitions.append(current_partition)
            n /= current_partition
            current_partition  = 2
        else:
            current_partition += 1

    if len(partitions) == 1:
        return "It is a prime number"
    
    result = [([0], -1)] if com == "max" else [([0], float('Inf'),)]
    sc_opt(partitions, result, com)
        
    result[0][0].sort(reverse=True)
    return [result[0][0], result[0][1]]

def sc_opt(partitions, result, com):
    if (com == "min" and result[0][1] > sc(partitions)) or (com == "max" and result[0][1] < sc(partitions)):
        result[0] = (partitions, sc(partitions))
    if len(partitions) == 2 or (com == "min" and max(partitions) > result[0][1]) or (com == "min" and max(partitions) > result[0][1]) :
        return
    for p in set(partitions):
        current = partitions.copy()
        current.remove(p)
        for i in filter(lambda x: x >= p, set(current)):
            curr = current.copy()
            curr[curr.index(i)] *= p
            sc_opt(curr, result, com)

def sc(partitions):
    return sum([p ** partitions.count(p) for p in set(partitions)]) * len(partitions)

def partition(n):
    return [[int(n/x)] for x in range(1, 1+int(n/2)) if n % x == 0]
    
def prod(a):
    prod = 1
    for n in a:
        prod *= n
    return prod

def score(a):
    return sum(n ** a.count(n) for n in reversed(sorted(set(a)))) * len(a)
    
def find_spec_prod_part(n, com):
    #non-recursive way to find partitions
    there_are_new = True
    
    partitions = partition(n)
    
    while there_are_new:
        there_are_new = False
        new_partitions = []
        for p in partitions:
            product = prod(p)
            if product < n:
                for new in partition(n/product):
                    if new[0] <= p[-1] and prod(p+new) <= n:
                        there_are_new = True
                        new_partitions.append(p + new)
            else: 
                new_partitions.append(p)
    
        partitions = new_partitions
        
    if len(partitions) <= 1:
        return ("It is a prime number")
        
    func = max if com == "max" else min
    return func( ([p, s] for (p, s) in ((p, score(p)) for p in partitions if len(p) > 1)), key=lambda x: x[1])

def partition(n):
    return [[int(n/x)] for x in range(1, 1+int(n/2)) if n % x == 0]
    
def prod(a):
    prod = 1
    for n in a:
        prod *= n
    return prod

def score(a):
    return sum(n**a.count(n) for n in reversed(sorted(set(a))))*len(a)  
    
def find_spec_prod_part(n, com):
    there_are_new = True
    
    partitions = partition(n)
    
    while there_are_new:
        there_are_new = False
        new_partitions = []
        for p in partitions:
            product = prod(p)
            if product < n:
                for new in partition(n/product):
                    if new[0] <= p[-1] and prod(p+new) <= n:
                        there_are_new = True
                        new_partitions.append(p + new)
            else: 
                new_partitions.append(p)
    
        partitions = new_partitions
        
    if len(partitions) <= 1:
        return ("It is a prime number")
        
    result = None
    result_score = None
      
    for p in partitions:
        if len(p) > 1:
            s = score(p)
            if (com == "max" and (not result_score or result_score < s)) or (com == "min" and (not result_score or result_score > s)):
                result = p
                result_score = s
            
    return [result, result_score]