Packing Problem

[Weatherby,Gerard]

Haven’t look at it all in detail, but I’d replace the list comprehensions with a loop:
CopyOfWords = list(Words)
            Words = [(w[1:] if w[0] == ch else w) for w in Words]
            Words = [w for w in Words if w != '']
            nextWords = []
            for w in CopyOfWords:
                if w[0] != ch:
                    nextWords.append(w)
                elif len(w) > 1:
                    nextWords.append(w[1:])
            assert Words == nextWords

From: Python-list <python-list-bounces+gweatherby=uchc.edu at python.org> on behalf of Rob Cliffe via Python-list <python-list at python.org>
Date: Thursday, March 2, 2023 at 2:12 PM
To: python-list at python.org <python-list at python.org>
Subject: Re: Packing Problem
*** Attention: This is an external email. Use caution responding, opening attachments or clicking on links. ***

Slightly improved version (deals with multiple characters together
instead of one at a time):

# 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:
         # 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 = set(w[0] for w in Words)
             FirstLettersSafe = sorted(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))
                 # sorted() to make the answer deterministic
                 # (not dependent on set ordering)
             if not FirstLettersSafe:
                 break
             AnyProgress = True
             Initial += ''.join(FirstLettersSafe)   # Build up the
answer from the beginning
             Words = [ (w[1:] if w[0] in FirstLettersSafe 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 = set(w[-1] for w in Words)
             LastLettersSafe = sorted(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))
                 # sorted() to make the answer deterministic
                 # (not dependent on set ordering)
             if not LastLettersSafe:
                 break
             Final = ''.join(LastLettersSafe) + Final   # Build up the
answer from the end
             Words = [ (w[:-1] if w[-1] in LastLettersSafe else w) for w
in Words ]
             Words = [ w for w in Words if w != '']
             if not Words:
                 return Initial + Final
         if not (FirstLettersSafe or LastLettersSafe):
             break # stuck
     # 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 FirstLetters:
             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']))

Rob Cliffe
--
https://urldefense.com/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!l3ysx0BUPZBdKdwb9F8mw4BAE2UIflvNqWeZLfALY2kjEo9e4KTy6fEYoGCTileOUtYe0yp6nL18ymdOguC3TGagEA$<https://urldefense.com/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!l3ysx0BUPZBdKdwb9F8mw4BAE2UIflvNqWeZLfALY2kjEo9e4KTy6fEYoGCTileOUtYe0yp6nL18ymdOguC3TGagEA$>