I created a few functions to accomplish the goal:
least_check that give a True/False as to whether or not the sequence is a "least" (e.g. '2 4' would return False, while '3 4' would return True)find_leasts which is the recursive function that breaks a sequence down to the the next level in the tree shown in the question (e.g. '2 2 4 4' would break down to '2 4 4', '2 3 4', and '2 2 4') until it reaches all "leasts" main which creates a list of all the "leasts" yielded from the find_leasts function, and removes any duplicates (e.g. example sequence has '3' twice) and returns the list of unique "leasts"
Answer:
def least_check(n):
check_list = [int(x) for x in n.split(' ')]
for a, b in zip(check_list[:-1], check_list[1:]):
if (a + b) % 2 == 0:
return False
return True
def find_leasts(n):
if len(n.split(' ')) == 1:
yield n
for i in range(len(n.split(' '))-1):
s = [int(x) for x in n.split(' ')]
if (s[i] + s[i+1]) % 2 == 0:
s[i] = int((s[i] + s[i+1]) / 2)
s.pop(i+1)
sub_n = ' '.join(str(j) for j in s)
if least_check(sub_n):
yield sub_n
else:
yield from find_leasts(sub_n)
def main(s):
all_leasts = [x for x in find_leasts(s)]
unique_leasts = list(set(all_leasts))
return unique_leasts
seq = '2 2 4 4'
print(sorted(main(seq), key=len))
Result:
['3', '2 3', '3 4', '2 3 4']
Update:
The above solution has many split()s and ' '.join()s in order to avoid the recursive function modifying a list reference (a list name is a pointer to its memory address - if needed, see this site for further explanation) from a depth other than the current scope.
When looking at the error received on a '30 20 10 30 6 6' sequence and considering that playing with the max recursion via sys.setrecursionlimit is not recommended, I re-evaluated whether or not recursion was even necessary - and determined it is not.
Here are the functions used in the iterative solution:
least_check - same as original answerbreak_down - takes a list and breaks it down to all lists down one level in the tree (e.g. '2 2 4 4' would break down to '2 4 4', '2 3 4', and '2 2 4')least_lister - iterates through the queue of lists that are potential leasts, until all lists in least_lists are leastsmain - does all split() and ' '.join() operations and removes duplicates before returning results
Iterative Solution:
def least_check(check_list):
for a, b in zip(check_list[:-1], check_list[1:]):
if (a + b) % 2 == 0:
return False
return True
def break_down(s, ret):
for i in range(len(s)-1):
if (s[i] + s[i+1]) % 2 == 0:
bd_list = s.copy()
bd_list[i] = int((bd_list[i] + bd_list[i+1]) / 2)
bd_list.pop(i+1)
ret.append(bd_list)
def least_lister(n):
least_lists = []
if least_check(n):
least_lists.append(n)
else:
i = 0
break_down(n, least_lists)
while i < len(least_lists):
if least_check(least_lists[i]):
i+=1
else:
break_down(least_lists[i], least_lists)
least_lists.pop(i)
return least_lists
def main(s):
s_list = [int(x) for x in s.split(' ')]
all_leasts = least_lister(s_list)
unique_leasts = list(set([' '.join(str(j) for j in i) for i in all_leasts]))
return unique_leasts
seq = '30 20 10 30 6 6'
print(sorted(main(seq), key=len))
Iterative Result:
['18', '19', '19 6', '25 6', '25 10', '25 14', '30 13', '30 15', '30 17', '30 13 6', '30 17 6', '30 15 12', '30 15 18']
List Reference Example
def add_to_list(n):
n.append(len(n))
print(n)
a = [0, 1]
add_to_list(a)
print(a)
List Reference Example Output:
[0, 1, 2]
[0, 1, 2]
