Packing Problem

[Rob Cliffe]

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

[Rob Cliffe]

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

[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

--
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$>

[Hen Hanna]

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


bappricnanadloety =17 chars

[Hen Hanna]

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.

[Hen Hanna]

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.

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