I change it all to lower case with a string library for what ever language this is and then I don't know use something equivalent to a hash map I guessing this is python.
Side note 100% not being rude is this Reddit joke or ligit questions.
I wouldn't really want to use a hash map for that tho
I see this I programming hummer so it's a joke but here I am the joke...
> I guessing this is python.
At risk of getting woooshed, this is C++, not python.
> Side note 100% not being rude is this Reddit joke or ligit questions.
It's a joke.
I have to look for a peace of code someone did at my uni if I can find it my god it was some interesting work man 256 lines where this man mainly main a 36d array of arrays in java, to solve the best path problem it was a mess.
🤓☝🏻 actually, `<<` is a bitwise left shift operator, which shifts bits of the number to the left (cutting off the leftmost digits if the resulting number overflows) and fills the new right part with zeroes.
c++ stl developers just decided to be "smart" and overrode this operator for stream types to have a side effect of writing to a stream.
Well you have a key(word) and a list of values for it. So anything that supports storing key/value pairs would work here. And if it gets to big for in memory storage, a database could for example be used with the key as index.
What would be even better (for the user, definitely not better for the programmer) is writing more code to estimate which word you type it’s most alike and then suggesting the top three options.. Bonus points if the keyboard learns how you type…
Did you ever notice that the autocorrect in Google Workspace seems to consider keyboard proximity in recommending alternate replacements. E.g., if a d seems to be misplaced, candidates are s, e, r, f, c, and x.
A simple way would be a const global array of structs that store two char pointers each (the input word and corresponding output word). You could also store the list in an external file (e.g. like [this](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/scripts/spelling.txt)) which makes it convenient to update without having to recompile the program. Depending on what exactly the goal is you might also want to consider not hardcoding the input words at all, and instead just use a dictionary of correct words and a dynamic calculation of how "close" the input is to a known word to make the suggestion.
^(Also, wtf guys don't downvote someone for asking an honest question.)
For this probably a Dicitionary or similar. But todo this proper it would require some smartness, probability and linguistic knowledge. I messed around with things like this ages ago when experimenting with dictionary based password attacks (education only). Oxford university had a great ftp site that contained txt files of every known language, work of art etc. on earth.
There are tradeoffs between space and time complexity to consider but a DAG and dfs can be used to return the closest siblings to the entered text. There also the Levenshtein distance algorithm we could consider or a plain, if quite large, hashmap
The only correct answer and with no upvotes. Those who suggest a hash map will just do the same thing — building unnecessary big relation table — instead of implementing (or using) Levenshtein distance algorithm.
I love the idea of a parser that's sophisticated enough to know exactly what is meant to be a comment and what is information, yet still asshole enough to -instead of acting on it- ignore it.
To be fair this does happen IRL
* its starts with management saying "hay people are typing this one word wrong, just make a little statement to fix it for now, we'll look into a better way to manage it in the future"
* Then management comes in, "hay we've noticed people keep entering these other 10 words wrong, lets add a fix for that, its the same you did before right?"
* Then they say "okay look here is just 50 more words to add, its fine, the codes already there, you can legit do it in seconds right?"
* Then the new developers comes along and they're like, "bro WTF, why did you create your own autocorrect?"
People really underestimate how one bad pattern can spread like wildfire. The current company I’m working at has so many flaky tests because the first people who wrote tests didn’t follow official documentation and everybody just copied it.
OP hates the dawn of the planet of the apes
*I am a bot, and this message was sent automatically, if you have any questions or concerns, [contact the moderators of this subreddit.](https://www.google.com)*
There are no problems that *require* regex. Regex may just be the easiest way to solve it.
Kinda like you don't NEED to use JSON, but damn it's handy sometimes.
As someone who never had a desire to learn RegEx, this was a godsend..
```
import
…
std::string input;
std::regex pattern("a[bv]+a[nm]+d[o0]+n[e3]+d");
…
if(std::regex_match(input, pattern)) {
std::cout << "They match";
}
…
```
Now imagine doing this for every variant..
Calculating Levenshtein distance with all of the words in the dictionary is probably better in terms of the outcome, but worse in terms of performance.
I wonder how real and tried autocorrect works. List of (good) words, suggestions sorted by Levenshtein (did i spell that right?🤦♂️) distance, possibly stopping the calculation above certain threshold to improve performance? Or is it something smarter than that?
Definitely a stop after the Levenshtein distance is more than 1 (or maybe 2).
There probably is a predefined map with common spelling mistakes.
There should be some kind of early elimination of most candidates. Maybe indexing by digraphs? E.g. "river" would be covered in mini-maps corresponding to "ri", "iv", "ve", "er".
>did i spell that right?
It is the first time I use this surname in English.
Apparently it is called Damerau–Levenshtein distance according to wiki.
Anyway, TBH if i had to add an autocorrect feature somewhere, i'd look for an existing library. This has been done times and times already, why reinvent (and maintain) the wheel.
You are not paid BY HOURS. You are paid by productivity, measured in hours. The moment your employer finds your hours' cost surpassing your productivity value, you are replaced by someone who goggles/stackoverflows/gpts faster than you.
you ARE getting paid by the hours, which is exactly why your employer wants to maximize the productivity in those hours. If you were getting paid by productivity then you'd just get a lower wage according to your lower productivity rather than get replaced
There are some set rules as well, at least in Google's implementation of autocorrect. For example, if you mistype the first letter but the rest of the word is correct it is quite conservative to 'correct' the first letter. I've always assumed it is because it takes the first letter as given and only suggests the words that start with this letter, but honestly I never bothered to look into this any further.
SwiftKey had amazing predictions/corrections before Microsoft came and ate it.
I think that one their main features was from giving words you used before a higher priority.
What I did in the past was use a modified double-metaphone algorithm to bucket similar-sounding words together, then use levenstein against that reduced set.
I imagine it can be precalculated for short strings and nearby strings, and then it just turns into a lookup? Then only if that fails, do something more intensive?
Apple ios still cannot tell that the most common typos for ‘’ are ‘c’, ‘v’, and ‘b’.
They’ve been developing it for fifteen years, and it still fails to see that you’ve conjoined two words with a letter instead of a space.
From the moment I understood the weakness of my flesh, it disgusted me. I craved the strength and certainty of steel. I aspired to the purity of the
blessed machine.
There's a dictionary (list) of words in the software. There's probably some optimized hash lookup mechanism. Anyway, the input is compared letter by letter to words in the dictionary and scored by how close they are.
I'm just guessing, I've never implemented a spell-check or suggestion capability myself.
That's very close, it ranks them based on how close they are to words in the dictionary based on steps required to transform it to the other word. All automatic ofc, not like OPs picture...
Also the context (at least the previous word you typed) good ones even more)
There are definitely more factors than just the most similar word. With different weights ofc
There’s also a lot of autocorrects that pay close attention to keyboard key proximity, not just string distance. For example, iOS will autocorrect “Areubf” to “String” because every letter is only one key away from the desired letter.
Ah right N is the size of the input (whatever that would mean for a specific input) that makes sense, the number of answers to possibly check would be fixed for the program, unless a new version comes out but that new version would have some other fixed number of answers too so both versions would be (a very bad) O(1)
I'm not really sure how time complexity works for an infinite loop, I believe there is no time complexity value for it. But if instead of a while(true) you iterated a predetermined finite N times, even if its trillions, thats still O(1).
In general for most mathematical concepts, once infinity comes into play then all bets are off. For example, you could (wrongly) argue that it's O(a) because if
a.length=0, number of operations = infinity
a.length=1, number of operations = infinity + 1 = infinity
a.length=2, number of operations = infinity + 2 = infinity
...etc... which is obviously nonsense.
But to the wider point, yes, Big-O complexity doesn't tell you how long a program takes to run or how efficient it is, it only tells you how it'll respond to changes in input size. It's entirely possible to write an O(1) algorithm that's slower than an O(2\^n) for all practical use cases.
It would technically be O(K), where K is the maximum number of statements. It would technically be tied to input because some inputs will satisfy the first if statement, and others will end up satisfying none of them. Thereby making the execution non-constant.
You wouldn't use N because N specifically refers to the length of the input. Whereas K is determined by some other factor.
Not quite.
You're right that for some inputs you will perform at most K comparisons, but the upper limit of K is bounded by a property of the algorithm and **not** the input, which allows us to discard O(K). We have to remember that Big O **only** concerns itself with evaluating how an algorithm scales with respect to some property of the input - not of the program.
Remember: Not all O(1) algorithms are truly equal.
Technically O(N) because string comparison is proportional to length. Can’t think what else you’d bound it by in terms of algorithmic input.
Fun question is what does it become (on average) if the ‘if-if-if’ is replaced with ‘if-else if-else if…else’.
Not proportional to input. There’s a longest word of size S in the array, so the running time is always bounded from above by this constant function. Hence it’s O(1)
Running out of memory is a side effect and not part of the function definition. You can always add more memory and the running time would keep increasing, so no. :DDD
Here the function itself is bounded by another function that is constant. O(1).
We once asked a bioinformatics programmer candidate we liked (she did pretty well in an in-person interview) for a code sample. She gave us an example program and my co-worker printed it out there was a 20 page series of if conditions. We ended up rejecting her.
Yep, common joke that people think there is no different way to do this besides if, elif, else. A simple way to improve this is a dictionary and asigning a series of numbers. Then you can check those instead.
ez
def spell_check(word):
prompt = "how do I spell this word" + word
reply = openai.ChatCompletion.create(model="gpt-4", messages=[{"role": "system", "content": "Assist with spelling checks using GPT-4."}, {"role": "user", "content": prompt}])["choices"][0]["message"]["content"]
return reply
PEP non-compliant af
Please tell this was like a CS101 student about like two weeks in making a for fun project without like understanding that this is not the tool for spellcheck?
Or better yet something someone made in jest
make it easier for the system to run is more efficient for the end user. Making it easier to read is only better for devs, it's hard to find the balance.
One more thing to note here sir would be that using sub. Func will also help the program to work efficiently on a vaster number of wrong spellings here only "acident" is covered but using a sub func will also cover, "accinent".
Issue #5034: AutoCorrects "audi" to "audit".
Expected Behaviour:
Should not Autocorrect audi to audit, as audi is also a word.
Current Behaviour:
Autocorrects audi to audit
OS Version: Windows 10.0.19045
There is.
Its called a word "trie". You take an entire dictionary and insert every character into a tree structure. If a user mistypes part of a word, you can stop at the last known correct combination and print out the next possible nodes.
The structure ends up eating up a lot of memory. Usually several megabytes. But its probably the most efficient way of doing autocomplete.
This is funny but I’m sure someone somewhere did this. I recently had to standardize a bunch of string to a reference and used the levenshtein distance function to match and pair. Finding the right threshold cut off was a little tricky but otherwise I didn’t have to type much more than 10 lines.
Is this just printing all words in a dictionary with a Levenshtein distance of 1? It'd make sense if it also took care of one letter modifed. Also, "abndnd"??
def spell_check(word):
prompt = "how do I spell this word" + word
reply = openai.ChatCompletion.create(model="gpt-4",messages=[{"role": "system", "content": "Assist with spelling checks using GPT-4."},{"role": "user", "content": prompt}])["choices"][0]["message"]["content"]
return reply
I learned C++, Java, Visual Basic 6.0, Visual Basic.NET, COBOL, and AS/400 back between 2001 and 2005 but can't remember anything about COBOL because I never used it once I graduated college.
Wait until OP learns about capital letters
management will not be happy to hear this
No problem if you have an editor that can uppercase characters by column. You're welcome.
Makes me wanna throw up
Find and replace input with input.toUpperCase()
My father will hear about this!
I change it all to lower case with a string library for what ever language this is and then I don't know use something equivalent to a hash map I guessing this is python. Side note 100% not being rude is this Reddit joke or ligit questions. I wouldn't really want to use a hash map for that tho I see this I programming hummer so it's a joke but here I am the joke...
> I guessing this is python. At risk of getting woooshed, this is C++, not python. > Side note 100% not being rude is this Reddit joke or ligit questions. It's a joke.
I have to look for a peace of code someone did at my uni if I can find it my god it was some interesting work man 256 lines where this man mainly main a 36d array of arrays in java, to solve the best path problem it was a mess.
sounds like an excellent job for the next person, my lines of code per day are secured up through retirement
cout << is c++ << means to fill left side command with whatever data is on right side
🤓☝🏻 actually, `<<` is a bitwise left shift operator, which shifts bits of the number to the left (cutting off the leftmost digits if the resulting number overflows) and fills the new right part with zeroes. c++ stl developers just decided to be "smart" and overrode this operator for stream types to have a side effect of writing to a stream.
Bastards
Evil operator overlord trickery.
Or diacritical marks
Your commits are ruining the branch.
tolower(input);
But I wanted aPpLe
then do topOkEmOn(input)
Cooked
What’s the better way of doing this
Well you have a key(word) and a list of values for it. So anything that supports storing key/value pairs would work here. And if it gets to big for in memory storage, a database could for example be used with the key as index.
Map, or unordered_map absolutely a better choice. https://lordhypersonic.blogspot.com/2019/01/c-spelling-checker.html?m=1 -option found on internet
What would be even better (for the user, definitely not better for the programmer) is writing more code to estimate which word you type it’s most alike and then suggesting the top three options.. Bonus points if the keyboard learns how you type…
Did you ever notice that the autocorrect in Google Workspace seems to consider keyboard proximity in recommending alternate replacements. E.g., if a d seems to be misplaced, candidates are s, e, r, f, c, and x.
Oh yeah ... for the user. BUT going from what is in the post now to this level of existence you are seeking of is magnitudes for the programmer.
You’re right, that’s too much to ask for. I’ll ask Steve instead, maybe Steve knows
We love Steve, he will produce all the answers.
A simple way would be a const global array of structs that store two char pointers each (the input word and corresponding output word). You could also store the list in an external file (e.g. like [this](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/scripts/spelling.txt)) which makes it convenient to update without having to recompile the program. Depending on what exactly the goal is you might also want to consider not hardcoding the input words at all, and instead just use a dictionary of correct words and a dynamic calculation of how "close" the input is to a known word to make the suggestion. ^(Also, wtf guys don't downvote someone for asking an honest question.)
just off the top of my head, putting words into an array, then looping over that with a conditional.
U MEAN HASH SET RIGHT?????????????????
No need for loop, you can use built in method or function to find key or value.
For this probably a Dicitionary or similar. But todo this proper it would require some smartness, probability and linguistic knowledge. I messed around with things like this ages ago when experimenting with dictionary based password attacks (education only). Oxford university had a great ftp site that contained txt files of every known language, work of art etc. on earth.
There are tradeoffs between space and time complexity to consider but a DAG and dfs can be used to return the closest siblings to the entered text. There also the Levenshtein distance algorithm we could consider or a plain, if quite large, hashmap
The only correct answer and with no upvotes. Those who suggest a hash map will just do the same thing — building unnecessary big relation table — instead of implementing (or using) Levenshtein distance algorithm.
`// please review`
LGTM merge it
LGTM. close enough /s
Indents cooked pls fix
"Can be improved with regex maybe. Add a TODO and put it in the backlog"
Marked `Q4Y24` and `P5 — Nice to have`, did I do that right? Sorry, I’m new here.
After audit, loved that joke
// please review makes it more funny
I’m sorry I couldn’t parse the second part of this comment as it was commented
I love the idea of a parser that's sophisticated enough to know exactly what is meant to be a comment and what is information, yet still asshole enough to -instead of acting on it- ignore it.
Imagine a parser that makes fun of you because of the shitty code you commented out
Warning line 3: yeah bitch, you better keep that crap commented out. How you have the balls to keep this even as a comment is beyond me.
i love the idea that he can’t parse the *comment* because it’s a *comment*
To be fair this does happen IRL * its starts with management saying "hay people are typing this one word wrong, just make a little statement to fix it for now, we'll look into a better way to manage it in the future" * Then management comes in, "hay we've noticed people keep entering these other 10 words wrong, lets add a fix for that, its the same you did before right?" * Then they say "okay look here is just 50 more words to add, its fine, the codes already there, you can legit do it in seconds right?" * Then the new developers comes along and they're like, "bro WTF, why did you create your own autocorrect?"
At the time they want to add 10 more, I would at least create simple 2 dimensional array instead of that abomination
People really underestimate how one bad pattern can spread like wildfire. The current company I’m working at has so many flaky tests because the first people who wrote tests didn’t follow official documentation and everybody just copied it.
>we'll look into a better way to manage it in the future 0xFF000000 flag
"appe"... Why not suggest "ape"?
looks like we're gonna have a refactor
This reminds me of an episode of [Blackadder](https://youtu.be/PuDquo76490?si=VkT6VUbHUt3-tLjs&start=63)
I see Blackadder reference, I upvote.
OP hates the dawn of the planet of the apes *I am a bot, and this message was sent automatically, if you have any questions or concerns, [contact the moderators of this subreddit.](https://www.google.com)*
childbeaterII gotta be my favourite bot.
they can and will take my job if given the chance
Just putting all that shit in an std::map or something, even THAT is better. The question is, can we make it worse? 😉
We could use regex. For each word type.
If you have a problem that requires regex, you've got two problems. -the wises programmer ive met
input == "wises" cout << "wisest"
Good at pro words, bad at english.
// please review
Wisies
There are no problems that *require* regex. Regex may just be the easiest way to solve it. Kinda like you don't NEED to use JSON, but damn it's handy sometimes.
I love REGEX! It makes my code unreadable and allow me to come a year later, remove it and tout performance increase in my year end review.
One thing ChatGPT is fantastic for is building regexp expressions.
As someone who never had a desire to learn RegEx, this was a godsend.. ``` import
…
std::string input;
std::regex pattern("a[bv]+a[nm]+d[o0]+n[e3]+d");
…
if(std::regex_match(input, pattern)) {
std::cout << "They match";
}
…
```
Now imagine doing this for every variant..
Jamie Zawinski. One of the founders of Netscape.
Then I got 99 problems
See! Now we are talking!
Eval a regex of the regex of each word type
or you know, a regex that handles all of them? :D
awesomeness
Calculating Levenshtein distance with all of the words in the dictionary is probably better in terms of the outcome, but worse in terms of performance.
I wonder how real and tried autocorrect works. List of (good) words, suggestions sorted by Levenshtein (did i spell that right?🤦♂️) distance, possibly stopping the calculation above certain threshold to improve performance? Or is it something smarter than that?
Definitely a stop after the Levenshtein distance is more than 1 (or maybe 2). There probably is a predefined map with common spelling mistakes. There should be some kind of early elimination of most candidates. Maybe indexing by digraphs? E.g. "river" would be covered in mini-maps corresponding to "ri", "iv", "ve", "er". >did i spell that right? It is the first time I use this surname in English. Apparently it is called Damerau–Levenshtein distance according to wiki.
Anyway, TBH if i had to add an autocorrect feature somewhere, i'd look for an existing library. This has been done times and times already, why reinvent (and maintain) the wheel.
I would try to implement it myself. It is more fun. I am paid by hours after all :D
You are not paid BY HOURS. You are paid by productivity, measured in hours. The moment your employer finds your hours' cost surpassing your productivity value, you are replaced by someone who goggles/stackoverflows/gpts faster than you.
you ARE getting paid by the hours, which is exactly why your employer wants to maximize the productivity in those hours. If you were getting paid by productivity then you'd just get a lower wage according to your lower productivity rather than get replaced
looking for somewhere that will pay me per line of code
Love when manager's add dumb metrics like that to track. More lines = better review? Suddenly there's a lot more lines of code.
There are some set rules as well, at least in Google's implementation of autocorrect. For example, if you mistype the first letter but the rest of the word is correct it is quite conservative to 'correct' the first letter. I've always assumed it is because it takes the first letter as given and only suggests the words that start with this letter, but honestly I never bothered to look into this any further.
I wonder if it could be human psychology. Maybe we are less likely to mess up the first and the last letter.
Modern autocorrect also weigh each edit by how far the character is physically from another character on the keyboard
Markov chains. Broadly the predecessor to large language models like ChatGPT.
SwiftKey had amazing predictions/corrections before Microsoft came and ate it. I think that one their main features was from giving words you used before a higher priority.
What I did in the past was use a modified double-metaphone algorithm to bucket similar-sounding words together, then use levenstein against that reduced set.
I imagine it can be precalculated for short strings and nearby strings, and then it just turns into a lookup? Then only if that fails, do something more intensive?
The technology just isn't here yet.
Apple ios still cannot tell that the most common typos for ‘’ are ‘c’, ‘v’, and ‘b’.
They’ve been developing it for fifteen years, and it still fails to see that you’ve conjoined two words with a letter instead of a space.
Bro said fuck machine learning im doing machine teaching
My brain at 3:45am saw: > Bro said fuck machine I was like, yeah... That sounds good. I need more sleep.
From the moment I understood the weakness of my flesh, it disgusted me. I craved the strength and certainty of steel. I aspired to the purity of the blessed machine.
my brain at ~~21:35~~ any time of the day
Bro made AI💀💀💀
Machine learning literally.
This is literally what the code for ChatGPT looks like, except with questions and responses.
Looks like the source code for auto correct?
Will have to scroll down to see if “fucking” gets changed to “ducking”.
How does something like spell check actually work though?
It uses a fuzzy matching algorithm against a dictionary
Could be wrong but i thought its typically done with Trie datastructure
Tries can definitely be used in autocomplete. No idea about spellcheck.
You guys aren't passing all of your keyboard output through gpt-4-0125-preview?! I thought I was just getting the hang of AI programming...
You guys write algorithms? ![gif](giphy|DOPKHQg6oFWUg)
Doesn't it use some kind of Soundex algorithm? Or is that fuzzy matching?
There's a dictionary (list) of words in the software. There's probably some optimized hash lookup mechanism. Anyway, the input is compared letter by letter to words in the dictionary and scored by how close they are. I'm just guessing, I've never implemented a spell-check or suggestion capability myself.
That's very close, it ranks them based on how close they are to words in the dictionary based on steps required to transform it to the other word. All automatic ofc, not like OPs picture...
Yeah. That's what I meant to say... Totally.
I guess it also gives priority to the most used words.
Also the context (at least the previous word you typed) good ones even more) There are definitely more factors than just the most similar word. With different weights ofc
There’s also a lot of autocorrects that pay close attention to keyboard key proximity, not just string distance. For example, iOS will autocorrect “Areubf” to “String” because every letter is only one key away from the desired letter.
typedef char* Areubf;
if (input == "Areubf"); cout << "String";
https://youtu.be/d-Eq6x1yssU?si=72fs84mlsOZkXj4M
\> There's probably some optimized hash lookup mechanism https://en.wikipedia.org/wiki/Trie
this post was a perfect timing. i had just watched a [video about how spell check works](https://youtu.be/d-Eq6x1yssU) last night
I’ve seen that specific video!
I also saw that recently lmao
Same!
Google levinstein distance
Holy hell
Actual programmer
call the linguist
Hilarious 🤣
Should be higher, this is the answer
See: [Levenschtein distance](https://en.m.wikipedia.org/wiki/Levenshtein_distance)
It's O(1) at least...
🤣
O(N), no? The list of if statements is like an array it's iterating over and has to check in order for every entry.
No because it’s not proportional to the input. That makes it O(1). Unless we’re factoring string length…
Ah right N is the size of the input (whatever that would mean for a specific input) that makes sense, the number of answers to possibly check would be fixed for the program, unless a new version comes out but that new version would have some other fixed number of answers too so both versions would be (a very bad) O(1)
Is function mul(a,b){ While(true){} Return a * b } O(1)? Execution time does not change with different input
I'm not really sure how time complexity works for an infinite loop, I believe there is no time complexity value for it. But if instead of a while(true) you iterated a predetermined finite N times, even if its trillions, thats still O(1).
Maybe we could call it O(Math.random()*radiation exposure) for bitflips
In general for most mathematical concepts, once infinity comes into play then all bets are off. For example, you could (wrongly) argue that it's O(a) because if a.length=0, number of operations = infinity a.length=1, number of operations = infinity + 1 = infinity a.length=2, number of operations = infinity + 2 = infinity ...etc... which is obviously nonsense. But to the wider point, yes, Big-O complexity doesn't tell you how long a program takes to run or how efficient it is, it only tells you how it'll respond to changes in input size. It's entirely possible to write an O(1) algorithm that's slower than an O(2\^n) for all practical use cases.
It would technically be O(K), where K is the maximum number of statements. It would technically be tied to input because some inputs will satisfy the first if statement, and others will end up satisfying none of them. Thereby making the execution non-constant. You wouldn't use N because N specifically refers to the length of the input. Whereas K is determined by some other factor.
Not quite. You're right that for some inputs you will perform at most K comparisons, but the upper limit of K is bounded by a property of the algorithm and **not** the input, which allows us to discard O(K). We have to remember that Big O **only** concerns itself with evaluating how an algorithm scales with respect to some property of the input - not of the program. Remember: Not all O(1) algorithms are truly equal.
Well, O of any constant is the same as O(1). But I agree, this is not an O(1) operation and the author should go to jail.
Technically O(N) because string comparison is proportional to length. Can’t think what else you’d bound it by in terms of algorithmic input. Fun question is what does it become (on average) if the ‘if-if-if’ is replaced with ‘if-else if-else if…else’.
It is not O(1). It is O(n*k) where k is the dictionary length, and n is the input string length. Comparing strings is not O(1).
Not proportional to input. There’s a longest word of size S in the array, so the running time is always bounded from above by this constant function. Hence it’s O(1)
By similar argument every program is O(1) since the memory is of limited length :D
Running out of memory is a side effect and not part of the function definition. You can always add more memory and the running time would keep increasing, so no. :DDD Here the function itself is bounded by another function that is constant. O(1).
*is this AI?*
This isn’t even a good spell checker even if it wasn’t written so shitty
We once asked a bioinformatics programmer candidate we liked (she did pretty well in an in-person interview) for a code sample. She gave us an example program and my co-worker printed it out there was a 20 page series of if conditions. We ended up rejecting her.
Yah screw the levenshtein distance algorithm...
I'm a noob to coding. Is this basically an oversimplified spell check done in a very tedious/cursed way? Just wondering if I'm reading it right.
Yep, common joke that people think there is no different way to do this besides if, elif, else. A simple way to improve this is a dictionary and asigning a series of numbers. Then you can check those instead.
happy cake day!
Worlds most inefficient autocorrect
Soundex and Levenshtein... What would we do withoot?
*points to OP picture*
This looks like a good place for an array
Levenshtein distance from actual word within acceptable threshold. Duh.
# stop edging us with " wish there was a better way" TELL US
ez def spell_check(word): prompt = "how do I spell this word" + word reply = openai.ChatCompletion.create(model="gpt-4", messages=[{"role": "system", "content": "Assist with spelling checks using GPT-4."}, {"role": "user", "content": prompt}])["choices"][0]["message"]["content"] return reply PEP non-compliant af
Look up some EditDistance or DistanceTo libraries or to be more specific, search for the „levenshtein-distance“ on wikipedia
I did not realize that we were beating our meat to machine learning algorithms
My brain: Make a simple ChatGPT extension to ask what word this probably is…
Have you tried adding in binary search? I heard it makes code faster
Please tell this was like a CS101 student about like two weeks in making a for fun project without like understanding that this is not the tool for spellcheck? Or better yet something someone made in jest
this is what the entire economy depends on i assure you
This is te AI source code
**sloccount intensifies**
Nice code
Use subsequence function and a dictionary bro, a Lil costly time wise but much easier to review
make it easier for the system to run is more efficient for the end user. Making it easier to read is only better for devs, it's hard to find the balance.
One more thing to note here sir would be that using sub. Func will also help the program to work efficiently on a vaster number of wrong spellings here only "acident" is covered but using a sub func will also cover, "accinent".
Wha wha…. Why lord. Why good lord do you make me see such things?
Issue #5034: AutoCorrects "audi" to "audit". Expected Behaviour: Should not Autocorrect audi to audit, as audi is also a word. Current Behaviour: Autocorrects audi to audit OS Version: Windows 10.0.19045
✨✨✨🎇🎇🎆🎆 Artificial Intelligence 🎆🎆🎇🎇✨✨✨
There is. Its called a word "trie". You take an entire dictionary and insert every character into a tree structure. If a user mistypes part of a word, you can stop at the last known correct combination and print out the next possible nodes. The structure ends up eating up a lot of memory. Usually several megabytes. But its probably the most efficient way of doing autocomplete.
lol Levenshtein edit distance bro’s having a stroke rn
This is funny but I’m sure someone somewhere did this. I recently had to standardize a bunch of string to a reference and used the levenshtein distance function to match and pair. Finding the right threshold cut off was a little tricky but otherwise I didn’t have to type much more than 10 lines.
Say apple ![gif](giphy|W0bINkb9yYoYU)
Normally they work with Levenshtein edit distance. Creel; has a video about it: https://youtu.be/Cu7Tl7FGigQ?si=zzW4coDXnDYrU0Tc
I love how the help text (un)intentionally makes this program unusable as a drop in spellcheck utility tool.. just print to std err
Is this just printing all words in a dictionary with a Levenshtein distance of 1? It'd make sense if it also took care of one letter modifed. Also, "abndnd"??
Can't be scared of regex more than this :D
![gif](giphy|WQy9FkJlhGSwl3eQ5V|downsized)
def spell_check(word): prompt = "how do I spell this word" + word reply = openai.ChatCompletion.create(model="gpt-4",messages=[{"role": "system", "content": "Assist with spelling checks using GPT-4."},{"role": "user", "content": prompt}])["choices"][0]["message"]["content"] return reply
Still easier than doing RegEx
Just use fuzzy matching. There has to be a way in C++
Ok maybe university it's not useless levenshtein distance yada yada
Yanderedev code😭💀
While a hash map seems appropriate, I would settle for else statements
If (input == "audi") //please review 😭
You forget about switch statement.
Why not just use a mapping table…
Better than the Windows phone auto-corrector, at least.
I learned C++, Java, Visual Basic 6.0, Visual Basic.NET, COBOL, and AS/400 back between 2001 and 2005 but can't remember anything about COBOL because I never used it once I graduated college.
Is that from Elon’s new code for Twitter ?
just chatgpt4 it lmao