max len of dict creative solution for Long Repeat by veky - python coding challenges

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

max len of dict solution in Creative category for Long Repeat by veky

long_repeat=lambda l:len(l)and max(map(len,dict(__import__('re').findall(r'((.)\2*)',l))))

Aug. 14, 2017

Comments:

veky on Aug. 14, 2017, 1:35 a.m.
Now I have `\2` problems. ;-D

artyko94 on Aug. 18, 2017, 9:52 a.m.
Very strong

veky on Aug. 20, 2017, 10:14 p.m.
Very ambiguous. :-P

kumaus on Oct. 13, 2017, 12:27 p.m.
Neat!!!

bsquare on Aug. 22, 2019, 10:43 a.m.
Really great!!!

delapi on Dec. 15, 2019, 11:44 p.m.
As a newbie for Python, I think it is magical while also beyond my comprehension. Could you please explain this sentence a bit: like, what does r'((.)\2*)' mean in regular expression? And why map(len, dict) is different from len(dict)?

veky on Dec. 16, 2019, 1:33 p.m.
Not surprising. "Magic" is just another name for "something we don't understand". :-) How much do you know about regular expressions? And about Python dictionaries? I can answer your questions, but it really seems you should play with those expressions for yourself a bit. For example, set `l='aaabbcaaaa'` and then `from re import findall`. Then try those: <pre class='brush: python'>rx = r'((.)\2*)' findall(rx, l) dict(_) *map(len, _), max(_) </pre> You see how the result is constructed? <hr /> And now answers to your questions: `r'...'` just means a "raw" string, where backslash is not interpreted by Python (e.g. `'\n'` is a newline, `r'\n'` is a two-character string composed of a backlash and a letter n). `.` in the context of a regex just means any character. `*` means zero or more of the previous. Parentheses remember what's matched inside them, and inside the same expression, those remembered values can be referenced with `\1`, `\2`, and so on, in the order of appearance of their left parentheses. <pre class='brush: python'> ((.)\2*) aaabbcaaaa \1 ------ --- \2 - - </pre> So, `((.)\2*)` means: match any character `.`, and remember it as `\2` (since it's in the second pair of parentheses). Then match zero or more of the same character, and remember it all (the first `.` match, and zero or more repetitions of it) as `\1`. `map` is not the same as `apply`, it means "iterate and apply". So, `len(['This', 'is', 'an', 'example'])` is simply 4 (the len of the list), while `map(len, ['This', 'is', 'an', 'example'])` yields 4, 2, 2, and 7 (lens of the elements encountered while iterating through the list). If there are more questions, feel free to ask -- but you'll learn better if you play with it yourself.

delapi on Dec. 16, 2019, 5:11 p.m.
Thank you for your elaboration! It's very helpful and I have got it regarding the second question. As for the first question, I can understand the logic itself. However, I tried this : <pre class='brush: python'>findall(r'((.)*)', 'aaabbcaaad') </pre> And the result is: <pre class='brush: python'>[('aaabbcaaad', 'd'), ('', '')] </pre> This made me more confused. In my intuition it should be like that: <pre class='brush: python'> ((.)*) aaabbcaaad \1 ---- ---------- \2 - - </pre> So my questions are: 1. Why it has an empty result ('', '') which not exist in your answer? 2. Why ('aaabbcaaad', 'd')[1] is the last character of this string rather than the first character?

veky on Dec. 17, 2019, 6:34 a.m.
Ah, so there are more details in the picture. Yes, re is an ancient technology, full of interesting warts and corner cases. But we can explain everything. First let's explain 2. The intuition behind "remembering" should be the same as for normal assignment. When you match `((.)*)`, you're saying "match any character and remember it as `\2`", in a loop that executes zero or more times (and remember the whole thing as `\1`). Of course, then if you ask for `\2` after the loop, it will have the last remembered value. [In my example, it was not so, since the star wasn't applied to parentheses, so "remembering" was only once before the loop. "recalling" `\2` was inside the star loop.] Which raises a question: What will `\2` be if the loop is executed zero times (that is, if `\1` is empty)? If no assignment to `\2` is ever made, it will have some default value it had before the loop. Long time ago, it was `None`, but people were complaining (read <a href="https://bugs.python.org/issue1519638">https://bugs.python.org/issue1519638</a> if you want to know painful details), so it was changed to `''`. That explains the second empty string in 1. And now the only thing that remains to be explained is the whole last pair in 1. Why is it even there? Well, empty strings are weird. :-) When Python tries to match a regex to 'abc', it tries at position 0. `search` instead of `match` tries at all positions 0,1,2,3 in order, and reports the first successful one. `findall` tries all of them in a way, but since it must return non-overlapping matches, it remembers where the first match ended, and the next search begins from that position. However, that naive algorithm would obviously give you an infinite loop if you had an empty match, since it would end at the same spot it began. So a hybrid algorithm is used: the position is advanced in any case, but it is advanced by more than 1 if the match is longer. Or in other words, each position 0,1,2,3 is tried in order, but some are skipped if the previous match reached over them. The effect is that empty pattern can still match at any point of the string, but at most once. You can easily see that with <pre class='brush: python'>>>> findall(r'', 'abc') ['', '', '', ''] </pre> So, I guess you can now understand what happened in 1. Previous match was greedy and collected all of the string, leaving the cursor at the end. But "at the end" is also a valid position, and the pattern you gave can match an empty string there. So it did. HTH. If you have more questions, you know what to do. ;-)

delapi on Dec. 17, 2019, 3:31 p.m.
Yes, it really helps! Thank you for your patience and inspiring explanation.

StefanPochmann on Dec. 20, 2019, 6:26 p.m.
Just a variation... <pre class='brush: python'>long_repeat=lambda l:max(map(len,__import__('re').split(r'((.)\2*)',l))) </pre>

veky on Dec. 20, 2019, 6:29 p.m.
Ah yes, collect both of them, but \2 will always be shorter. Nice. :-)

StefanPochmann on Dec. 20, 2019, 6:35 p.m.
Plus it gives empty strings so you don't need that special case handling.

veky on Dec. 20, 2019, 6:37 p.m.
Yes. And of course, the "real" strings into which `l` is split, but those are also of length 1. :-)

Strings Theory

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.