Packing Problem
Rob Cliffe
rob.cliffe at btinternet.com
Sat Mar 18 20:54:48 EDT 2023
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$>
More information about the Python-list
mailing list