The aim of this puzzle is to find the shortest string containing a set of substrings. As the size of this set is small, I brute forced my way out of this one. I developped a function nesting all the strings contained in a list, in order, and an other generating all the permutations of a list (of string). In the end I just had to apply the nesting function on all the permutations and print the length of the smallest string obtained.
def nest(strings):
''' tries to nest strings, in order, and return the result'''
res = strings.pop()
while len(strings) > 0:
new = strings.pop()
for i in range(len(new)+1):
subLast = min(i+len(res), len(new))
if (new[i:subLast] == res[:subLast-i]):
res = new[:subLast] + res[subLast-i:] + new[i+len(res):]
break
return res
def permutations(l):
'''returns a list of all the permutations of the list l'''
if len(l) == 0:
return [[]]
else:
res = []
for head in l:
l2 = l[:]
l2.remove(head)
for tail in permutations(l2):
res.append([head] + tail)
return res
# reads sub sequences
N, strings = int(input()), []
for i in range(N):
strings.append(input())
# bruteforce : computes the length of the nested string for each permutation
# and prints the minimal length found
print(min(len(nest(p)) for p in permutations(strings)))