Mailing List Archive

I found Hen Hanna's "packing" problem to be an intriguing one: Given a
list of words:
    ['APPLE', 'PIE', 'APRICOT', 'BANANA', 'CANDY']
find a string (in general non-unique) as short as possible which
contains the letters of each of these words, in order, as a subsequence.
It struck me as being rather hard for a homework problem, unless I'm
missing something blindingly obvious.
Here is what I came up with (I could have done with
removeprefix/removesuffix but I'm stuck on Python 3.8 for now ????):

# Pack.py
def Pack(Words):
    if not Words:
        return ''
    # The method is to build up the result by adding letters at the
beginning
    # and working forward, and by adding letters at the end, working
backwards,
    # meanwhile shrinking the words in the list.
    Words = list(Words) # Don't mutate the original
    Initial = ''
    Final = ''
    while True:
        AnyProgress = False
        # It is safe to add an initial letter (of one or more of the
words) if
        # EITHER    There is no word that contains it as
        #             a non-initial letter but not as an initial letter.
        #  OR       All words start with it.
        while True:
            FirstLetters = ''.join(w[0] for w in Words)
            FirstLetters = [ ch for ch in FirstLetters if
                all(w[0]==ch for w in Words)
                or not any(ch in w[1:] and w[0]!=ch for w in Words) ]
            if not FirstLetters:
                break
            AnyProgress = True
            ch = FirstLetters[0]    # Pick one
            Initial += ch           # Build up the answer from the
beginning
            Words = [ (w[1:] if w[0]==ch else w) for w in Words ]
            Words = [ w for w in Words if w != '']
            if not Words:
                return Initial + Final
        # It is safe to add a final letter (of one or more of the words) of
        # EITHER    There is no word that contains it as
        #             a non-final letter but not as a final letter.
        #  OR       All words end with it.
        while True:
            LastLetters = ''.join(w[-1] for w in Words)
            LastLetters = [ ch for ch in LastLetters if
                all(w[-1]==ch for w in Words)
                or not any(ch in w[:-1] and w[-1]!=ch for w in Words) ]
            if not LastLetters:
                break
            AnyProgress = True
            ch = LastLetters[0]     # Pick one
            Final = ch + Final      # Build up the answer from the end
            Words = [ (w[:-1] if w[-1]==ch else w) for w in Words ]
            Words = [ w for w in Words if w != '']
            if not Words:
                return Initial + Final
        if not AnyProgress:
            break
    # Try all the possibilities for the next letter to add at the
beginning,
    # with recursive calls, and pick one that gives a shortest answer:
    BestResult = None
    for ch in set(w[0] for w in Words):
            Words2 = list( (w[1:] if w[0] == ch else w) for w in Words )
            Words2 = [ w for w in Words2 if w != '' ]
            res = ch + Pack(Words2)
            if BestResult is None or len(res) < len(BestResult):
                BestResult = res
    return Initial + BestResult + Final

print(Pack(['APPLE', 'PIE', 'APRICOT', 'BANANA', 'CANDY']))

The output:
BAPPRICNANADYOTLE
which has the same length as the answer I came up with trying to solve
it with my unaided brain, which may or may not be reassuring ????,
and also contains a much-needed BRANDY.
I expect there are simpler and more efficient solutions.
Best wishes
Rob Cliffe
--
https://mail.python.org/mailman/listinfo/python-list