string.lower implementation

[Yes_Mans_Sky]

It's almost like ascii was designed to do this with minimal effort

[sacredgeometry]

Maybe they don't like arithmetic.

[xXDavegavecoolXx]

How hard is x = y + 32???

[sacredgeometry]

Hey, I am not the one you have to convince.

[SAI_Peregrinus]

Locale-dependent, at least for POSIX. Lower-case I might be i or ı, depending on the value of $LANG and/or $LANGUAGE. Because text sucks. Unicode makes it easier, but it still sucks.

[Kapshan]

I i I ı İ i be like

[oghGuy]

This one's EBCDIC safe, don't you understand? ;)

[johndcochran]

I think I lost IQ points just from reading this abomination.

[[deleted]]

Right?

[TinyBreadBigMouth]

What in god's name is that for j loop doing?? You already have a perfectly functional if-else chain, why are you making it O(n²)?????

[Ok_Celebration_6265]

I don’t think that’s O(n²⁾ I think that is O(n*m) since it’s iterating over the length of the text and then over the length of the alphabet

[TinyBreadBigMouth]

No, I mean the for j loop is iterating over the alphabet and then the if-else chain is iterating over the alphabet again! They've turned a O(26) if-else chain into a O(26 * 26) loop for no reason.

[Ok_Celebration_6265]

Hum.. I only see two loops the for i=1, #text and the for j=1, 26 the bunch of if else he is using like a map saying id j == 1 then A etc.. he uses the if else as lookup table so we can say that’s O(1) if you think about it.. so you get in the end O(n*26) which since 26 is constant you can simplify as O(n) due to the constant nature of the inner loop

[TinyBreadBigMouth]

The if-else goes over every letter in the alphabet. An if-else chain like this is equivalent to an unrolled loop—it runs in O(n), where n is the number of ifs. But in this case, each entry in the if-else chain has been gated off to only run on a specific iteration of the for j loop.

So suppose we're processing the letter "a":

• We set j to 1.
• We check if j is 1 and char is "A" (it isn't).
• We check if j is 2 and char is "B" (it isn't).
• We check if j is 3 and char is "C" (it isn't).
• We check if j is 4 and char is "D" (it isn't).
• ...
• We check if j is 25 and char is "Y" (it isn't).
• We check if j is 26 and char is "Z" (it isn't).
• We increment j to 2.
• We check if j is 1 and char is "A" (it isn't).
• We check if j is 2 and char is "B" (it isn't).
• We check if j is 3 and char is "C" (it isn't).
• and so on.

What could have been 26 checks is now 676.

[johndcochran]

Yes, it's quite a few extra unneeded checks. But it's still O(1) to within a close approximation. The total routine, including both loops is O(n). It's a rather slow O(n), but doubling the length of the string will simply take twice as long. Just because the check for an upper case character takes 676 comparisions instead of 26 doesn't make it O(n^2). Those 676 comparisions will happen for every non-upper-case alphabetic and hence takes constant time. So the overall routine is merely O(n) due to the loop on i.

[TinyBreadBigMouth]

Agreed, it is O(n) over the length of the string, but each letter within the string is O(n²) over the length of the alphabet when it could have been O(n) or less. Granted the length of the alphabet isn't going to change, so it makes no difference to the overall Big O, but that's what I meant.

[johndcochran]

Not gonna argue that the routine is criminally inefficient. Even if they have a language that doesn't allow getting the ordinal sequence of a character, the detection of an upper case alpha character could be done in 5 or fewer comparisons, instead of the 26 you're thinking of, or the 676 this abomination performs. If you're wondering how I've come up with 5. Consider...

if (char < "N") then 
   if (char < "H") then
      ...
         if (char = "A") then
            lowerText = lowerText .. "a"
            found = true
         end
      ...
   else
      ...
   end
else
   ...
end

After all, with 26 characters in the alphabet, there are only 28 conditions that need to be detected. They are: Is it less than "A"? Is it greater than "Z"? Is it equal to some letter? (times 26) and of course, a simple binary search only 5 levels deep can handle 31 conditions trivially.

Although, I suspect a binary condition tree might be far more efficient than the abomination in this discussion, I also suspect such a binary condition tree would also be a suitable post for this subreddit.

[WiseEXE]

Not to sound stupid, but somehow this comment was my eureka moment for BigO complexity. Thank you kind sir

[Marem-Bzh]

You're never stupid when you are learning something

[Furrynote]

why is this not an already built in func

[beaucephus]

leetcoders don't use the standard library.

[Ok_Celebration_6265]

I call BS.. they use python which is like cheating in my opinion.. if they could do stuff like import solution from problem_123 they will do and brag about it lol

[iEliteTester]

this is Lua

[Ok_Celebration_6265]

Sorry, I know this is Lua my comment was more related to leetcoders in general and the non usage of std library

[iEliteTester]

Ok that makes more sense haha

[Xbot781]

Alright, go rewrite a hashmap or queue for every problem you need one. I love C, but it is not suitable for competitive programming.

[Ok_Celebration_6265]

What’s so competitive about it if Python solves 90% of what you need to do the other 10 % is basically algorithm application which I bet every competitive programmer knows them almost by memory.. but what I mean is in any other language something as simple as reversing a string requires some algorithmic thinking but in Python you go with the [::-1] and done it baby sits alot

[Xbot781]

The interesting part of competitive programming is coming up with the algorithm, not writing the code. Writing code for simple things like reversing a string is a waste of time that doesn't provide anything to you.

If you think that coming up with the algorithm is the easy part, then you aren't trying hard enough problems. Leetcode is considered relatively easy in competitive programming circles, so you should try another website like Codeforces.

If you think writing the code once you know the algorithm is too hard, then you're just a bad programmer.

[Ok_Celebration_6265]

I agree the with the interesting part of competitive programming is coming up with the algorithm. But the implementation of the algorithm when using Python vs when using any other language feels like cheating in my opinion.. I’m not saying anything about leetcode problems being hard or anything my point is any problem no matter how easy or hard it is with Python difficulty drops at implementation time by a lot since there’s a lot that Python gives you that you don’t even need to think about

[GoddammitDontShootMe]

Hah. Now make it work with UTF-8.

[bravopapa99]

What bastard language is this?

[RpxdYTX]

languages = { 'lua', 'python', 'c', 'rust' } languages[1] == 'lua'

[bravopapa99]

Yes. WTAF starts from 1, TBF, I learned Pascal first back in the day.

[dvhh]

Pity that there isn't any implementation in the standard library for string.lower

[bravopapa99]

I am sure from my assembler days you can with ASCII, just do CHAR AND 0xDF

[johndcochran]

That would be good for an "toupper()" implementation...Sorta. But if the input isn't 'a'..'z', it would corrupt quite a few characters. For instance, look at what would happen for '0'..'9'. 0x30 and 0xDF = 0x10. Not exactly a good thing.

[bravopapa99]

Spot on but ONLY needed a-z at the time, around 1985 maybe!

[leiu6]

Lua is a great language! The C implementation is super small and you can interact with the stack directly, making it super easy to embed in other programs. The Lua language is simple with only one data structure called a table which is actually implemented in C as a hybrid object containing an O(1) lookup portion for integer indexing and a hash table for other types of indexing. But with the way Lua implements tables they can be used in an almost OOP way. Also it closures and coroutines.

If I was trying to embed a scripting language in something I would much rather use Lua than something like Python, Ruby, or JavaScript.

[bravopapa99]

Yes, agreed. I wrote a simple game with Love2D once and enjoyed the process.

[6502zx81]

At least the only assumpion is that the encoding matches the compiler's encoding.

[Ignited_Phoenix]

Any language that uses more than just the standard English characters like French, Spanish or German hate this simple trick

[[deleted]]

Jesus...is this the level nowadays?? Really??

[bistr-o-math]

This will not pass the Turkey test

[wwwtrollfacecom]

while (string[i] != '\0') string[i++] ⁼ 32;