Packing Problem

[Rob Cliffe]

On 02/03/2023 19:40, Weatherby,Gerard wrote:
> 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
Why?
Rob Cliffe
>
> 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$>