Re: Packing Problem
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 on behalf of Rob Cliffe via Python-list Date: Thursday, March 2, 2023 at 2:12 PM To: python-list@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 # EITHERThere 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 # EITHERThere 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$> -- https://mail.python.org/mailman/listinfo/python-list
Re: Packing Problem
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 on behalf of Rob Cliffe via Python-list Date: Thursday, March 2, 2023 at 2:12 PM To: python-list@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 # EITHERThere 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 # EITHERThere 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$> -- https://mail.python.org/mailman/listinfo/python-list
Re: Packing Problem
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://mail.python.org/mailman/listinfo/python-list
Packing Problem
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
