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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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@python.org> on behalf of Rob Cliffe via Python-list <python-list@python.org>
Date: Thursday, March 2, 2023 at 2:12 PM
To: python-list@python.org <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
# 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$>

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Thursday, March 2, 2023 at 11:10:37 AM UTC-8, Rob Cliffe wrote:

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

thanks.... i'd be surprised to find a shorter answer.


bappricnanadloety =17 chars

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Friday, March 3, 2023 at 12:00:00 PM UTC-8, Hen Hanna wrote:

On Thursday, March 2, 2023 at 11:10:37 AM UTC-8, Rob Cliffe wrote:

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.

is ths (above) the same as this?


It is safe to add an initial letter of (subset of) the words if
All words start with it.
OR ELSE
The remaining words don't contain that letter.

thanks.... i'd be surprised to find a shorter answer.

bappricnanadloety =17 chars

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Friday, March 3, 2023 at 5:34:14 PM UTC-8, Hen Hanna wrote:

On Friday, March 3, 2023 at 12:00:00 PM UTC-8, Hen Hanna wrote:

On Thursday, March 2, 2023 at 11:10:37 AM UTC-8, Rob Cliffe wrote:

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.

is ths (above) the same as this?

It is safe to add an initial letter of (subset of) the words if
All words start with it.
OR ELSE
The remaining words don't contain that letter.

thanks.... i'd be surprised to find a shorter answer.

bappricnanadloety =17 chars

when i Copy-Pasted the code (into a file) and tried run it, i got:

py packBad.py

SyntaxError: Non-UTF-8 code starting with '\xa0' in file C:\pypy3.9...........\packBad.py on line 3, but no encoding declared.........


and so i needed to put this ( # -*- coding: UTF-8 -*- ) to fix the problem.


_________________________

'\xa0' is ....

\xa0 is actually non-breaking space in Latin1 (ISO 8859-1), also chr(160). You should replace it with a space

Where is it in line-3 ? ----- where line 3 is
# Slightly improved version (deals with multiple characters together instead of one at a time):

To remove xa0 from string in Python, we can use the value NFKD in the normalize() function, which is an abbreviation for Normal Form KD . The use of NFKD in the normalize() function results in the substitution of all the characters into their

equivalent values. The equivalent value of xa0, for example, is a space.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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@python.org> on behalf of Rob Cliffe via Python-list <python-list@python.org>
Date: Thursday, March 2, 2023 at 2:12 PM
To: python-list@python.org <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
# 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$>

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)