Thanks to PL uncategorized solution for The Most Wanted Letter by bryukh - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Thanks to PL solution in Uncategorized category for The Most Wanted Letter by bryukh

import string

def checkio(text):
    return max(string.ascii_lowercase, key=lambda ch: text.lower().count(ch))
    
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    assert checkio("Hello World!") == "l", "Hello test"
    assert checkio("How do you do?") == "o", "O is most wanted"
    assert checkio("One") == "e", "All letter only once."

Sept. 11, 2013

Comments:

david.navrkal on Sept. 20, 2013, 11:54 a.m.
<pre class='brush: python'> return max(string.ascii_lowercase, key=lambda ch: text.lower().count(ch)) </pre> Cool.

bryukh on Sept. 20, 2013, 8:31 p.m.
Thanks

veky on Sept. 26, 2013, 6:24 a.m.
Yes, that's that. However, you don't need lambda: bounded methods are functions. (See mine.)

bryukh on Sept. 26, 2013, 6:39 a.m.
Nice!

tanglong on Sept. 24, 2013, 8:25 a.m.
WOW!

orhalimi on Sept. 29, 2013, 11:06 a.m.
i dont understand how its work /=

bryukh on Sept. 30, 2013, 7:53 a.m.
It's iterate through all letters and count each letter in the text.

orhalimi on Sept. 30, 2013, 9:53 a.m.
Thanks for the replay, but i don't understand the syntax. i hope i will in the future.

veky on Sept. 30, 2013, 10:27 a.m.
Syntax is almost certainly not your problem. See my solution, it has almost no syntax, and it's the same algorithm. :-)

orhalimi on Oct. 1, 2013, 4:31 a.m.
i mean all the "key=lambda ch: text.lower().count(ch)" look like japanse to me, even after i look what the does /=

veky on Oct. 1, 2013, 6:21 a.m.
That's why I told you to see my solution. It has not that lambda. Lambda usually makes people unconfortable, sometimes with a reason, but here is unnecessary. "key=" really is an element of syntax that is unavoidable here (because BDFL made a slightly bad design decision allowing max to take either an iterable or a bunch of arguments). It just means an additional setting for max, saying how to compare elements to determine which one is maximal. Here, we take all the lowercase ASCII letters, and find a maximal one according to count in lowercased version of text. HTH,

orhalimi on Oct. 2, 2013, 1:27 p.m.
but max take all the elements no? one elements is ascii lower and other is the count of each of them?

veky on Oct. 2, 2013, 4:04 p.m.
Actually no. That's what I'm telling you. max(a,f) is the greater of a and f. max(a,key=f) is not that. It is the maximal element of a according to transformation f -- that is, (first) such a0 that a0 in a and f(a1)<=f(a0) for all a1 in a.

orhalimi on Oct. 5, 2013, 4:16 p.m.
So let me try again. The key count the letters and the 'max' return the letter with the max number from asciilower that key pass to him. And if the number are the same it just return the letter that as closer position to the start of the asciilower list. Am I right?

veky on Oct. 5, 2013, 5:48 p.m.
Close enough. :-)

orhalimi on Oct. 6, 2013, 6:40 p.m.
<hr />

_Chico__5d82cee4f5234e78a5c65e on June 12, 2021, 6:12 a.m.
Why

veky on June 12, 2021, 6:13 a.m.
You really should learn to ask questions in a sensible way.

leafonsword on Oct. 10, 2013, 8 a.m.
<pre class='brush: python'> return max(string.ascii_lowercase, key=lambda ch: text.lower().count(ch)) </pre> awesome！

alexche_8 on Oct. 10, 2013, 12:19 p.m.
<pre class='brush: python'> return max(string.ascii_lowercase, key=lambda ch: text.lower().count(ch)) </pre> awesome

bryukh on Oct. 10, 2013, 8:50 p.m.
Thx. But i think, you should look at Veky and PositronicLama solutions too.

veky on Oct. 11, 2013, 6:24 a.m.
Understand that you're a cult. Whatever you write here, someone will say it's awesome. :-) (And whatever I write, somebody will say it's short, even if it's five bloody lines.:)))

bryukh on Oct. 11, 2013, 6:35 a.m.
I think, this is "snowball" effect :-) I like your solutions for new tricks and like PositronicLama solutions for nice comments and readability.

veky on Oct. 11, 2013, 7:41 a.m.
Though, both of us need to cope with "nonunderstanding" comments. Only, in your case, people would honestly say "i dont understand how its work /=". And in my case, they'd just shout "unreadable!". :-]

bryukh on Oct. 11, 2013, 7:45 a.m.
:-)

nickie on Oct. 12, 2013, 2:47 p.m.
Short code but very inefficient. This is O(n^2) instead of O(n).

bryukh on Oct. 13, 2013, 12:02 a.m.
No, this is not O(n^2). Please, look more careful to what i am counting.

nickie on Oct. 13, 2013, 9:17 a.m.
You're scanning over the text once in max, this is O(n). Then, you're using the key function for comparing: the key function calls count over text and again takes O(n). How is this not O(n^2)? Plus you're converting the text to lower case n times...

bryukh on Oct. 13, 2013, 9:20 a.m.
Nope. I scan the text 26 times, not N times. This is 26 * N + N for max. So we have 27 * N. This is O(CN) = O(N)

nickie on Oct. 13, 2013, 9:42 a.m.
Yes, you're right, my mistake. I thought max was iterating over the text; it's iterating over the 26 letters. So "very inefficient" is not fair, it's just inefficient (traversing the text 26 times instead of one). Too bad I cannot edit my original comment, sorry about that.

bryukh on Oct. 13, 2013, 9:48 a.m.
No problem. I think, this discussion can be useful for other users. I agree with you -- for first glance this is looked as O(N^2). About "inefficient" -- Ask Veky about it ;-) If i need performance, then i use pypy or Java.

bryukh on Oct. 13, 2013, 9:29 a.m.
You can easily check my words with the next code <pre class='brush: python'>from random import choice import string def checkio(text): return max(string.ascii_lowercase, key=lambda ch: text.lower().count(ch)) text = "".join(choice(string.ascii_letters) for _ in range(10000)) text_long = "".join(choice(string.ascii_letters) for _ in range(100000)) import timeit if __name__ == "__main__": print("N= {0:6}".format(len(text)), timeit.timeit("checkio(text)", setup="from __main__ import checkio, text", number=1)) print("N= {0:6}".format(len(text_long)), timeit.timeit("checkio(text_long)", setup="from __main__ import checkio, text_long", number=1)) </pre> My results for this <pre class='brush: python'>N= 10000 0.00043067500519100577 N= 100000 0.004053762007970363 </pre> As we can see -- this is O(N). One more example. <pre class='brush: python'>N= 10000 0.0004422469937708229 N= 1000000 0.04485608400136698 </pre>

nickie on Oct. 13, 2013, 11:03 a.m.
As you and @Veky are fond of one-liners, here's a one-liner for this in Haskell (plus two extra lines for importing the two libraries; there's no way to do that in the same line, unfortunately): <pre class='brush: python'>import Data.Char (ord, toLower) import qualified Data.Map as M checkio = snd . maximum . map (\(c, n) -> ((n, -ord(c)), c)) . M.toList . foldl (\m c -> M.insertWith (+) (toLower c) 1 m) M.empty </pre> It scans the text just once, not once for each letter. Unfortunately, you cannot write this in Python, as it has no decent foldl function (reduce is not good enough, it's the equivalent of Haskell's foldl1).

veky on Oct. 13, 2013, 11:49 a.m.
Correct me if I'm wrong, but isn't Haskell much more inefficient here? Every insertWith makes a new copy of Data.Map, no?

nickie on Oct. 13, 2013, 12:04 p.m.
Each insertWith makes a new map, but it's not an entire copy. Maps are balanced trees: the path from the root to the updated element is copied and everything else is reused. This incurs a O(log(m)) overhead (where m is the number of elements in your map, m=26 here). This logarithmic overhead is in general the price you pay for having purely functional data structures. In Python, you pay for hashing in dicts.

veky on Oct. 13, 2013, 12:14 p.m.
Ok, so the "in spirit" Python equivalent is using collections.Counter, right? :-)

nickie on Oct. 13, 2013, 12:38 p.m.
You're right. Here's a one-liner in Python that works, more or less, in the same way as my Haskell one-liner. I'll add a new solution with this. <pre class='brush: python'>checkio = lambda text: max([(n, -ord(c), c) for (c, n) in Counter(c.lower() for c in text if c != ' ').items()])[2] </pre>

veky on Oct. 13, 2013, 1:54 p.m.
Morale: never say "you can't do something in Python". Especially when I'm around. :-D

bryukh on Oct. 13, 2013, 9:27 p.m.
Thanks -- it was interesting discussion.

bryukh on Oct. 13, 2013, 9:35 p.m.
I don not want offend you, but this is solution is slower than mine. <pre class='brush: python'>bryukh N= 1000000 0.04498169900034554 nickie N= 1000000 0.6059437070070999 </pre>

veky on Oct. 13, 2013, 10:01 p.m.
I'm not surprised - Counter is not really meant to be used that way. :-/ But try removing [] in max.

bryukh on Oct. 13, 2013, 10:03 p.m.
<blockquote> But try removing [] in max. </blockquote> the same result.

bryukh on Oct. 13, 2013, 10:04 p.m.
But if change c.lower at text.lower the -20% but it still slower.

veky on Oct. 13, 2013, 10:10 p.m.
Yes, removing instructions from inner loops makes sense. Another idea in this regard: move removal of spaces to outer comprehension (... for (c, n) in Counter(text.lower()) if c != " "...)

bryukh on Oct. 13, 2013, 10:30 p.m.
<pre class='brush: python'>checkio = lambda text: max(((n, -ord(c), c) for (c, n) in Counter(text.lower()).items() if c != ' '))[2] </pre> little faster, but <pre class='brush: python'>bryukh N= 1000000 0.04553114999725949 nickie N= 1000000 0.4019883529981598 </pre>

veky on Oct. 14, 2013, 5:43 a.m.
So, this is just one more of those "optimization anecdotes", when something "should be" faster but in fact isn't. Python is full of them, because really, implementation is quite intricate, and many things are factors that we are not really used to think about as factors. My opinion still holds: lowering algorithmic class is relevant, and that only if input is potentially unbounded. Lowering multiplicative constants is not, especially if it means rewriting code.

bryukh on Oct. 13, 2013, 10:32 p.m.
You are the best <pre class='brush: python'>bryukh N= 1000000 0.044759907003026456 nickie N= 1000000 0.4040005110000493 veky N= 1000000 0.024152671001502313 </pre>

veky on Oct. 14, 2013, 4:50 a.m.
Not surprising. :-)

nickie on Oct. 14, 2013, 8:31 a.m.
I'd be surprised if the one-liner using Counter did any better than this. I'd bet my <a href="http://www.checkio.org/mission/implementation/python-3/29197/">first</a> solution does much better than any of the one-liner.

bryukh on Oct. 14, 2013, 8:38 a.m.
I am sorry, but :-) <pre class='brush: python'>bryukh thanksPL N= 1000000 0.04882402801013086 nickie 1line N= 1000000 0.41053052300412674 veky shortest N= 1000000 0.024339889001566917 nickie first N= 1000000 0.16278485300426837 </pre>

nickie on Oct. 14, 2013, 9:54 a.m.
OK, this means that hashing when using dicts in Python (more precisely, all the defaultdict machinery that I used) incurs an overhead that is (way) larger than 26... This would not happen with a real array. It seems that I have a lot to learn about how to write efficient Python code. Or, rather, I have to admit that it doesn't make much sense trying to optimize things in Python in the way one does in lower level, statically typed languages. I think I'll stick with asymptotic optimization from now on, this can hardly fail you... :-)

veky on Oct. 14, 2013, 6:37 p.m.
If you haven't already, read "An optimization anecdote", by Guido (I referred to it in the comment above). If BDFL himself considers it counterintuitive, surely it's pointless for us mortals. :-D

bryukh on Oct. 13, 2013, 9:29 p.m.
<blockquote> @Veky </blockquote> Hm, this is interesting idea about "mention", thx.

mzero on Nov. 4, 2013, 12:07 a.m.
My Haskell solution would have been: <pre class='brush: python'>import Data.List (group, sort, sortBy) import Data.Char (isAlpha, toLower) import Data.Function (on) checkio = head . last . sortBy (compare \`on\` length) . group . sort . map toLower . filter isAlpha </pre>

Stanley_V on Oct. 17, 2013, 7:40 a.m.
<pre class='brush: python'> return max(string.ascii_lowercase, key=lambda ch: text.lower().count(ch)) </pre> Amazing

neilengineer on Oct. 17, 2013, 5:26 p.m.
<pre class='brush: python'>def checkio(text): </pre> cool!

mathieu.raby on Oct. 18, 2013, 1:52 p.m.
Nicely done !

lavalamp on Oct. 23, 2013, 7:53 p.m.
<pre class='brush: python'> return max(string.ascii_lowercase, key=lambda ch: text.lower().count(ch)) </pre> very clean

assertnotnull on Oct. 29, 2013, 7:51 p.m.
Very nice. I will remember that use of a lambda. I just don't understand how the max() returns the lowest alpha value from all the letters in the string.ascii_lowercare when 2 maximums are equals

bryukh on Oct. 30, 2013, 3:29 a.m.
"max" iterates through "ascii_lowercase" and if it meet two "equal" elements, then it take the first (if a

poik on Nov. 12, 2013, 3:23 a.m.
ive been trying to read up on asciilowercase vs asciiuppercase, (<a href="http://docs.python.org/2/library/string.html),">http://docs.python.org/2/library/string.html),</a> my understanding is that ascii_lowercase would only count lowercase letters.. is that correct?

veky on Nov. 12, 2013, 4:21 a.m.
Yes, but it will count them in text.lower(). So it accomplishes what's written: <blockquote> The letter returned must be in lower case. While checking for the most wanted letter, casing does not matter, so for the purpose of your search, "A" == "a". </blockquote>

veky on Oct. 30, 2013, 6 a.m.
The only thing you don't need to remember here is that use of a lambda. :-P See my solution (or the comment below).

oduvan on Oct. 30, 2013, 8:55 a.m.
using <pre class='brush: python'>key=text.lower().count </pre> looks better for me too then <pre class='brush: python'>key=lambda ch: text.lower().count(ch) </pre>

veky on Oct. 30, 2013, 12:04 p.m.
Of course. Eta-reduction is an old thing. All these things were developed 50 years before Python. ;-) <a href="http://www.lambda-bound.com/book/lambdacalc/node21.html">http://www.lambda-bound.com/book/lambdacalc/node21.html</a>

CyroAvernus on Nov. 3, 2013, 1:28 p.m.
Really nice solution in one line...had to do a bit of research on the use of max with a key....

chros on Nov. 7, 2013, 3:16 p.m.
great, short, and functional solution. me likey ;-)

aotus on Nov. 7, 2013, 5:08 p.m.
Great use of the built-in string functions! Nothing will ever convince me to like lambdas, though. :^)

veky on Nov. 14, 2013, 8:22 a.m.
You don't have to. See mine, same thing without lambda. :-P

maksibonus on Nov. 7, 2013, 8:22 p.m.
<pre class='brush: python'>import string </pre> how it works?

veky on Sept. 15, 2017, 6:52 p.m.
You mean how importing works in general, or what specifically does `string` module enable you to do? <ol> <li><a href="https://docs.python.org/3.5/library/importlib.html">https://docs.python.org/3.5/library/importlib.html</a> In short, importing means locating a module (usually a Python file on disk) using a Finder, compiling it (if not already done) and executing using a Loader, and making available its namespace to the code doing the import, either as a separate namespace or by grafting (specified or all) names from it onto the importing namespace.</li> <li><a href="https://docs.python.org/3.5/library/string.html">https://docs.python.org/3.5/library/string.html</a> In short, it enables you to use various utility functions (such as capwords), classes (such as Template) and constants (such as hexdigits) pertaining to working with strings.</li> </ol>

fangtao on Nov. 11, 2013, 8:55 a.m.
牛逼

Antonf26 on Nov. 12, 2013, 11:44 a.m.
<pre class='brush: python'> return max(string.ascii_lowercase, key=lambda ch: text.lower().count(ch)) </pre> Nice

Reloader on Nov. 13, 2013, 11:19 a.m.
Great use of 'key'! Way to advanced for my current level of experience :) I suppose that 'lambda' function also iterates through lowercase version of 'text', counting every single element (or character), and then compare elements with 'string.ascii_lowercase' to determine which one is maximal. Am I right?

bryukh on Nov. 13, 2013, 8:14 p.m.
It iterates through "lowercase" and count each letter in the text.

rhcoder on Nov. 13, 2013, 12:10 p.m.
can u explain your code, please?

bryukh on Nov. 13, 2013, 8:13 p.m.
You can read about it lower in the comments.

bylijinnan on Nov. 26, 2013, 9:30 a.m.
very impressed!

highland_mark on Nov. 28, 2013, 2:43 p.m.
It looks to me as if text.lower() will be called multiple times. Perhaps ake that out of the loop?

bryukh on Nov. 28, 2013, 9:07 p.m.
Yeah, you can read about it (and results) below in the comments.

Khaled_SAB on Nov. 28, 2013, 6:55 p.m.
<pre class='brush: python'> return max(string.ascii_lowercase, key=lambda ch: text.lower().count(ch)) </pre> nice

AdamHoward on Nov. 29, 2013, 5:50 a.m.
... I can see that I have a lot to learn about Python still. Good thing I have you all to learn from!

marshall.zheng on Dec. 5, 2013, 1:29 p.m.
really awesome solution!

berserk9779 on Dec. 7, 2013, 10:37 p.m.
wow

berserk9779 on Dec. 7, 2013, 10:39 p.m.
wow

forrest1988 on Dec. 10, 2013, 2:22 p.m.
Interesting approach.

cwahbong on Dec. 10, 2013, 2:23 p.m.
Too much iterations. It can be done in one iteration.

datruth29 on Dec. 10, 2013, 5:04 p.m.
Niceeeeee Great approach! Similar to mine, but I didn't import string, I assumed it wouldn't let you!

Sergey.Levandovskiy on Dec. 18, 2013, 12:41 p.m.
OMG )! It so redundant and counterproductive Count will be executed and text.lower 26 times

bryukh on Dec. 28, 2013, 3:44 p.m.
Please read the disscusion about "productivity" lower. <a href="http://www.checkio.org/mission/most-wanted-letter/publications/bryukh/python-3/thanks-to-pl/#comment-outer-5902">First</a> <a href="http://www.checkio.org/mission/most-wanted-letter/publications/bryukh/python-3/thanks-to-pl/#comment-outer-5909">Second</a>

bryukh on Dec. 29, 2013, 12:18 a.m.
But of course, if move "lower" out from "max" -- it give the good performance improvement. But for performance i use another algorithms and no cPython :)

Ping-Lin on Dec. 21, 2013, 7:21 p.m.
Shock!

Kartoshka548 on Dec. 28, 2013, 2:32 p.m.
this is interesting solution - but it's far form being optimal in terms of efficiency. you count characters which do not exist, and apply lower() each time. I would vote + for elegance, but big minus for productivity - this will badly lag while scaling your solution.

p4r4d0x42 on Jan. 14, 2014, 12:32 a.m.
Not bad but has efficiency issues.

bryukh on Jan. 14, 2014, 12:35 a.m.
Hm, i've looked your solution :) Could you explain "efficiency issues" (i know couple, but would hear more)

grutte_pier on Jan. 27, 2014, 3:40 p.m.
Nice and short, but this executes a full count for every single character in the string (i.e. a string with 100 characters will be looped over 100 times) even if the count for that character was already done before. Just imagine what would happen if you asked your text editor to do the count of your next shiny book....... :-(

bryukh on Jan. 27, 2014, 7:56 p.m.
Sirry, but you are wrong. Please read the solution more careful and discussion below. "count" runs 26 times. Please read the disscusion about "productivity" lower. <a href="http://www.checkio.org/mission/most-wanted-letter/publications/bryukh/python-3/thanks-to-pl/#comment-outer-5902">First</a> <a href="http://www.checkio.org/mission/most-wanted-letter/publications/bryukh/python-3/thanks-to-pl/#comment-outer-5909">Second</a>

Vladimir_Salitrinskij on May 25, 2014, 1:38 p.m.
Short and simple! Excellent! :-)

bcristian on July 20, 2014, 6:10 a.m.
I've just started learning Python, so I might be wrong, but I do not see in the specs of max the guarantee that in the case of a tie will return the first (lower index) one. Obviously in the current implementation it does that, but shouldn't reliance on undocumented implementation details be avoided?

bryukh on July 20, 2014, 6:15 a.m.
"max" will return the first occurrence with the maximum value.

bcristian on July 20, 2014, 6:22 a.m.
The specs at <a href="https://docs.python.org/2/library/functions.html">https://docs.python.org/2/library/functions.html</a>#max do not mention anything about ties - is there other canonical reference?

bryukh on July 20, 2014, 6:25 a.m.
From <a href="https://docs.python.org/3.3/library/functions.html">https://docs.python.org/3.3/library/functions.html</a>#max <blockquote> If multiple items are maximal, the function returns the first one encountered. This is consistent with other sort-stability preserving tools such as sorted(iterable, key=keyfunc, reverse=True)[0] and heapq.nlargest(1, iterable, key=keyfunc). </blockquote>

bcristian on July 20, 2014, 6:35 a.m.
Oh, the other python :D Thanks for the tip.

Pavetta on June 28, 2018, 3:30 p.m.
1 string decision!

Strings and Integers

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.