Find word by given characters

dn PythonList at DancesWithMice.info
Mon Nov 2 22:10:39 EST 2020


On 03/11/2020 13:13, duncan smith wrote:
> On 02/11/2020 19:09, dn wrote:
>> On 02/11/2020 23:29, Bischoop wrote:
>>> On 2020-11-01, duncan smith <duncan at invalid.invalid> wrote:
>>>> But this generates the letters counts for each word. They only need to
>>>> be generated once (outside the for loop). And using count requires
>>>> iterating over the letters / words for each x in letters (rather than
>>>> once). For a large enough collection of words you'd notice the
>>>> difference.

>> Multiple loops written in Python are likely to be slower than same in
>> compiled code - which was probably part of the motivation for @Terry's
>> response. Plus, "re-use" - why write something ourselves if someone else
>> has already done the work?
...

>> - str.find() or .index() will locate a character within the string...

> But he appears to need the count in order to compare against the counts
> in letters. I assume letters could be something like 'att', in which
> case knowing a word contains more than one 't' doesn't cut it. He could
> try iterating over the characters in each word once, checking that no
> count from letters is exceeded, and that the number of remaining
> characters gives some chance that the relevant counts from letters could
> be achieved. In the worst case (e.g. a conforming word) this requires
> iterating over all the characters in a word once. That's not to say it
> would actually run quicker 'on average' than a solution using Counter.


The str.index() idea solves both (ie "all") examples given, but beyond 
that, no guarantees!


The (full) specs are not clear. There's certainly room for 
misunderstanding. I'd be happier if I could 'see' a full spec or 
recognise a practical application, because then we'd be better able to 
discuss facts. Meantime, we try to help with what we have been given...


The OP's sample code only realises "conforming word[s]" (good term 
BTW!). The snippet does not report any "count". Similarly, there's no 
facts to avoid ("I assume") an assumption about whether "Letters" may 
include duplication - indeed: whether duplication has meaning or should 
be regarded as user-error.


The point has been made that finding multiple instances of "Letters" 
disqualifies that word.  Does that (also) disqualify having repetition 
of a letter within Letters? (or not?)

What does "att" imply? That there must be one and only one "a" in the 
word, plus a "t", and only one *other* "t"? Can't see it in 'the specs' 
to be able to say "right" or "wrong"! (Nor is it my spec!)

Whereas the OP indicates (first example) that the two characters "a" and 
"t" must appear, there was no apparent, required, linkage (or 
separation) between them, eg "auto" doesn't include the two letters 
consecutively (one of my first (mistaken) thoughts when looking at the OP).

Accordingly, I (again, rightly or wrongly), assumed that the lack of 
linkage between characters in "Letters" reasonably suggested (if not, 
implied) that if "auto" matches "at", it would also match "ta". 
Similarly, and without further detail, I couldn't see good reason why 
Letters itself would contain repetition, eg "att". (or not!)


Aside: that idea might make for a good second-level challenge!
(complicating both the nested-loops and the str.index() ideas - but 
possibly not when using counter()...)


When counter() was suggested, it was necessary to 'count' the characters 
in both the candidate-word and "Letters". Isn't that 'requirement' 
necessary only to be able to perform the final comparison/validation 
step? (there is no equivalent in the .index() algorithm)

Whereas counter() was mentioned as a potential solution, it didn't seem 
to fit. So, I sought another...


Moving to the suggested speed-comparison (and lesson in drawing from 
Python's rich collection of resources) was originally aimed at putting a 
native-Python nested list string manipulation solution, alongside an 
embedded function alternative. (cf anything involving Counter)
- but hey, "the more the merrier..."!

Performing this sort of experiment, and making such an observation (for 
oneself) is a great motivator (should one be needed) to learn Python's 
built-in functions, what is available in the PSL, and locating other 
similar 'riches' offered within the Python 'eco-system'!
-- 
Regards =dn


More information about the Python-list mailing list