1. Forum
  2. Usenet
  3. COMP.LANG.PYTHON

  • Find 6-letter words that are hidden (embedded) within

    From Hen Hanna@21:1/5 to All on Fri Feb 24 10:34:21 2023
    i just wrote a program, which...
    within [FunFunPython]
    finds: (funny, futon, python)

    ( 5- and 6- letter words )


    (my program uses a Trie, but is pretty simple)



    Maybe someone would show me
    how it's done using itertools, Permutations, etc.

    Wouldn't it get too slow for Letter-Seeds longer than 11 letters or so?


    ______________________

    Find 6-letter words that are hidden (embedded) within each row of letters.
    The letters are in the correct order.

    1. JSOYOMFUBELR
    2. SCDUARWDRLYE
    3. DASNAGEFERTY
    4. CLULOOTSCEHN
    5. USENEARSEYNE

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Pancho@21:1/5 to Hen Hanna on Fri Feb 24 18:59:18 2023
    On 24/02/2023 18:34, Hen Hanna wrote:

    i just wrote a program, which...
    within [FunFunPython]
    finds: (funny, futon, python)

    ( 5- and 6- letter words )


    (my program uses a Trie, but is pretty simple)



    Maybe someone would show me
    how it's done using itertools, Permutations, etc.

    Wouldn't it get too slow for Letter-Seeds longer than 11 letters or so?


    For performance, generally you sort the characters in a word to create a
    new word (character list) and compare the sorted character lists (which
    you can use a string for). Two anagrams will produce the same sorted
    character list.

    The problem with going through all permutations is that the number of permutations tends to grow exponentially, so that is why you sort first.

    So first take an English dictionary and build a python dictionary with
    the key being the character sorted list and the value being a list of
    the English words that produce the sorted list, aka anagrams.

    You then sort your specific word and test each subset of this sorted
    word (each combination of characters) against your python anagram
    dictionary.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Hen Hanna@21:1/5 to Hen Hanna on Fri Feb 24 12:15:22 2023
    On Friday, February 24, 2023 at 10:34:31 AM UTC-8, Hen Hanna wrote:
    i just wrote a program, which...
    within [FunFunPython]
    finds: (funny, futon, python)

    ( 5- and 6- letter words )


    (my program uses a Trie, but is pretty simple)



    Maybe someone would show me
    how it's done using itertools, Permutations, etc.

    Wouldn't it get too slow for Letter-Seeds longer than 11 letters or so?


    ______________________

    Find 6-letter words that are hidden (embedded) within each row of letters.
    The letters are in the correct order.

    1. JSOYOMFUBELR
    2. SCDUARWDRLYE
    3. DASNAGEFERTY
    4. CLULOOTSCEHN
    5. USENEARSEYNE



    The letters are in the correct order. -------- So this problem is not about Anagraming.



    it seems that
    https://docs.python.org/3/library/itertools.html
    doesn't offer waht i want, so i wrote this (below) and it works.

    Is there a better or faster way to do the same thing?


    def subs( x ):
    if x=='': return ['']
    x1= subs( x[1:] )
    return x1 + mapAdd(x[0] , x1)

    def mapAdd( x, Ylis ): return [ x+y for y in Ylis ]

    print( subs('ab' ))
    print( subs('abc' ))

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From David Raymond@21:1/5 to All on Fri Feb 24 21:16:17 2023
    PiBGaW5kIDYtbGV0dGVyIHdvcmRzIHRoYXQgYXJlIGhpZGRlbiAoZW1iZWRkZWQpIHdpdGhpbiBl YWNoIHJvdyBvZiBsZXR0ZXJzLiANCj4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBU aGUgbGV0dGVycyBhcmUgaW4gdGhlIGNvcnJlY3Qgb3JkZXIuIA0KPiANCj4gMS4gSlNPWU9NRlVC RUxSIA0KPiAyLiBTQ0RVQVJXRFJMWUUgDQo+IDMuIERBU05BR0VGRVJUWSANCj4gNC4gQ0xVTE9P VFNDRUhOIA0KPiA1LiBVU0VORUFSU0VZTkUNCg0KPiBUaGUgbGV0dGVycyBhcmUgaW4gdGhlIGNv cnJlY3Qgb3JkZXIuIC0tLS0tLS0tIFNvIHRoaXMgcHJvYmxlbSBpcyBub3QgYWJvdXQgQW5hZ3Jh bWluZy4NCg0KDQpZb3UgY2FuIGdldCBldmVyeSBjb21iaW5hdGlvbiBvZiA2IGxldHRlcnMgb3V0 IG9mIGl0IHdpdGggaXRlcnRvb2xzLmNvbWJpbmF0aW9ucyBsaWtlIGJlbG93Lg0KSnVzdCBpbXBs ZW1lbnQgdGhlIGlzV29yZCBmdW5jdGlvbiB0byByZXR1cm4gd2hldGhlciBhIHN0cmluZyBhY3R1 YWxseSBjb3VudHMgYXMgYSBsZWdpdCB3b3JkIG9yIG5vdC4NCjEyIGNob29zZSA2IGlzIG9ubHkg OTI0IGNvbWJpbmF0aW9ucyB0byBjaGVjaywgc28gc2hvdWxkbid0IGJlIHRvbyBiYWQgdG8gY2hl Y2sgdGhlbSBhbGwuDQoNCg0KZGVmIGlzV29yZCh3b3JkKToNCiAgICByZXR1cm4gVHJ1ZSAjQmVz dCBsZWZ0IGFzIGFuIGV4ZXJjaXNlIHRvIHRoZSByZWFkZXINCg0Kc3RhcnRXb3JkID0gIkpTT1lP TUZVQkVMUiINCnN1YkxldHRlckNvdW50ID0gNg0KDQpmb3VuZFdvcmRzID0gc2V0KCkNCg0KZm9y IGxldHRlcnMgaW4gaXRlcnRvb2xzLmNvbWJpbmF0aW9ucyhzdGFydFdvcmQsIHN1YkxldHRlckNv dW50KToNCiAgICB3b3JkID0gIiIuam9pbihsZXR0ZXJzKQ0KICAgIGlmIHdvcmQgbm90IGluIGZv dW5kV29yZHMgYW5kIGlzV29yZCh3b3JkKToNCiAgICAgICAgcHJpbnQod29yZCkNCiAgICAgICAg Zm91bmRXb3Jkcy5hZGQod29yZCkNCg==

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Hen Hanna@21:1/5 to David Raymond on Fri Feb 24 15:49:56 2023
    On Friday, February 24, 2023 at 1:18:28 PM UTC-8, David Raymond wrote:
    Find 6-letter words that are hidden (embedded) within each row of letters. The letters are in the correct order.

    1. JSOYOMFUBELR
    2. SCDUARWDRLYE
    3. DASNAGEFERTY
    4. CLULOOTSCEHN
    5. USENEARSEYNE

    The letters are in the correct order. -------- So this problem is not about Anagraming.
    You can get every combination of 6 letters out of it with itertools.combinations like below.
    Just implement the isWord function to return whether a string actually counts as a legit word or not.
    12 choose 6 is only 924 combinations to check, so shouldn't be too bad to check them all.


    def isWord(word):
    return True #Best left as an exercise to the reader

    startWord = "JSOYOMFUBELR"
    subLetterCount = 6

    foundWords = set()

    for letters in itertools.combinations(startWord, subLetterCount):
    word = "".join(letters)
    if word not in foundWords and isWord(word):
    print(word)
    foundWords.add(word)



    thank you... i could use the Pset below, too.


    # Factorial Python One-Liner
    def fac(n): return reduce(lambda x, y: x * y, range(1, n+1))

    for i in range(1,11): print ( '\t', fac(i) )


    # Power set Python One-Liner
    def Pset(L): return reduce(lambda z, x: z + [y + [x] for y in z], L, [[]])

    print( '\n', Pset( [1,] ))
    print( '\n', Pset( [1,2,] ))
    print( '\n', Pset( [1,2,3] ))

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Paul Rubin@21:1/5 to David Raymond on Fri Feb 24 16:16:11 2023
    David Raymond <[email protected]> writes:
    You can get every combination of 6 letters out of it with itertools.combinations like below.

    That is a cute approach, though the help string for combinations doesn't specify that the results will come out in order. I haven't checked the
    manual but would not depend on this unless the manual says it is ok.
    for letters in itertools.combinations(startWord, subLetterCount):
    word = "".join(letters)
    if word not in foundWords and isWord(word) ...

    I think you can speed this up by building two sets and intersecting them: ================================================================

    from itertools import combinations

    ww = "JSOYOMFUBELR SCDUARWDRLYE DASNAGEFERTY CLULOOTSCEHN USENEARSEYNE".split() ss = set(''.join(s) for w in ww for s in combinations(w.lower(),6))
    d6 = set(d.strip().lower() for d in open('/usr/share/dict/words') if len(d)==7) print(ss & d6)

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