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: MEDIUM_HARD
Tags: Fundamentals

Data structures

Mathematics
Skill types: Data structures

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 ** 0.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]]


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

def primeFactors(n):
	prime_factors = []
	while n % 2 == 0:
		(prime_factors.append(2),)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		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, 100000000000.0]
		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):
	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]