#!/usr/bin/env python3
import random
import sys

sys.setrecursionlimit(10000)

# Tries to create a test case with the given word lengths by repeatedly
# choosing the lexicographically minimal next string. This is impossible for
# some inputs (such as [1,2] * 27). In these cases, an exception is raised.
def minimal_from_lengths(ks):
    return case_from_lengths(ks, False)

# Tries to create a test case with the given lengths by randomly splitting the
# sequence into 26 segments starting with the letters 'a' to 'z' respectively,
# and then recursing to find the remaining letters of the words. Falls back to
# lexicographically minimal generation if this fails.
def random_from_lengths(ks):
    return case_from_lengths(ks, True)

# Main function used for the actual test case generation as described above:
def case_from_lengths(ks, is_random):
    words = [[0] * k for k in ks]

    def rec(a, b, dep, random_attempts):
        nonlocal ks, words
        if a == b:
            return
        if ks[a] == dep:
            return rec(a+1, b, dep, random_attempts)
        if min(ks[a:b]) <= dep:
            raise RuntimeError('Could not create a test case')
        if a+1 == b:
            words[a][dep:] = random.choices(range(26), k=ks[a]-dep)
            return
        
        for _ in range(random_attempts):
            try:
                borders = [a,b] + [i for i in range(a+1,b) if ks[i] == dep+1]
                if len(borders) > 27:
                    raise RuntimeError('Could not create a test case')
                extra = random.randint(0, 27-len(borders))
                borders += random.choices(range(a,b+1), k=extra)
                borders = sorted(borders)
                alphabet = sorted(random.sample(range(26), k=len(borders)-1))
                for c, u, v in zip(alphabet, borders, borders[1:]):
                    for i in range(u,v):
                        words[i][dep] = c
                    rec(u, v, dep+1, random_attempts)
                return
            except:
                pass
         
        words[a][dep:] = [0] * (ks[a]-dep)
        for i in range(a+1,b):
            if ks[i] <= ks[i-1]:
                words[i][dep:ks[i]] = words[i-1][dep:ks[i]]
                for j in range(dep,ks[i])[::-1]:
                    if words[i][j] < 25:
                        words[i][j] += 1
                        break
                    else:
                        words[i][j] = 0
                        if j == dep:
                            raise ValueError('Impossible to create a test case with these lengths')
            else:
                words[i][dep:ks[i-1]] = words[i-1][dep:ks[i-1]]
                words[i][ks[i-1]:ks[i]] = [0] * (ks[i]-ks[i-1])

    rec(0, len(ks), 0, 2 if is_random else 0)
    return [''.join(chr(ord('a')+int(k)) for k in w) for w in words]