Take your personal data back with Incogni! Use code standupmaths at the link below and get 60% off an annual plan: incogni.com/standupmaths Don’t use code ^.?$|^(..+?)\1+$.
@Kosmokraton I did think Matt was going to add this to his code. But on reflection, it's probably a good thing he didn't. Code like that is truely terrifying. Perl has a reputation of being a "write only language." Then regexes must be the "write only, and get it right only occasionally by fluke or trial and error API of coding."
15+ years of programming experience including using regular expressions and I still watched and enjoyed this video. It's a testament to Matt's enthusiasm and his skill as a speaker/teacher.
Same, I figure out how it worked by just reading it, but he’s a joy to watch. Although, granted tapping on the video I was confused how it would be able to parse “17” as a prime and took a re-read of the regex to understand that it’s a length of the same character
Same here. That's a really neat way to use regex. Not as efficient as the sieve of Eratosthenes, for the reasons mentioned at 14:30, but still really cool :)
To simplify, this takes the number and expresses it as a unary numeral system, where the number of marks is the value of the number you put in (e.g. 1 is 1, 2 is 11, 3 is 111, ...). The regex then looks to divide the unary representation into exactly N groups of size M, where both N and M are natural numbers with value 2 or larger. For example, you can divide 4 (represented as 1111) into 2 groups of "11". You can divide 6 (represented 111111) into 2 groups of "111" or 3 groups of "11". However, you can't divide 3 (represented as 111) into groups of the same size (technically you can do 3 groups of "1", but then M isn't 2 or larger). Basically, you are checking if the number has any factors bigger than 1, which obviously is only false for prime numbers.
Still, I get why M should be 2 or bigger ( because the first dot in [..+?] is obligatory and the + means at least 1 extra. I don't get why N should be at least 2. The + after the group means 1 group or more doesn't it? 1 group of three dots shouldn't render True however.
@@dudicrous oops, yes I do, fixed it now. N must be 2 or larger because the part in the parenthesis needs to match something (the first group), and the \1+ means that the same thing must appear at least one more time. The parenthesis part also "consumes" whatever it matches. So basically 4 (aka 1111) would match 11 with the (..+?) and the remaining 11 would match the \1+. If you have 2 (aka 11) you can match the parenthesis, but then you have nothing left to match the \1+ part.
I'm trying to figure out if the algorithm is quadratic or exponential I'd guess it's at least pseudo-exponential because the length of the number is n=LogN.. But this algorithm is N*N. Since LogN^b = N. Then the algorithm is O(n^b*N) = O(n^2b). Which is very big. Also for huge primes the O(N) memory requirement could be prohibitive.
A minor bit of pedantry: ^.?$|^(..+?)\1+$ is a "regex" (i.e. a pattern specification understood by most common implementations of regular-expression-based pattern-matching engines), but it is not a regular expression in the strict sense of the term. The minimal definition of a strict regular expression includes only literal characters, a symbol standing for an empty string (typically ε), parentheses to clarify the order of operations, the alternation operator (vertical bar), and the Kleene star (asterisk). Most of the other symbols in our prime-matching regex can be derived from those in the minimal definition: The wildcard . is shorthand for (a|b|c|d|...), and a+ is shorthand for aa*. The symbols ^, $, and ? are irrelevant in a strict regular expression, since it either matches the entire string or it doesn't match at all. The real problem is the \1: There's no way to construct an equivalent out of the minimal definition.
Yup. Most modern "regex" engines are actually context-free grammar engines but they use syntax similar to true regex engines from decades past so people keep calling them that.
Thank you for this comment! As someone who spends a good bit of time in theoretical computer science land it always bugs me when "regex" arent actually regular at all. Saved me the trouble of writing this comment myself
thank you @TheRyulord for mentioning that the relation to CFG. i think it's something even more sinister... 'cz whereas a CFG/PDA uses stack, i.e. single time contiguous use, the backref uses arbitrary memory. & i dont remember which Grammar represents automaton with arbitrary append-only (say immutable read/write) memory.
It's like actual wizardry, and no less arcane. Reading someone else's regex really is like deciphering a spell comprising ancient runes you individually understand...
As a Regex connoisseur, I was really confused as to how the expression could possibly do that. But it makes perfect sense now. So simple, and yet so clever!
Someone has to say it. Regular expressions,in their truest sense, ie ones that are equivalent to regular languages are not capable of primality test. Only extended ones that have “memory” can do it. I.e \1 part of the example above is what’s not possible in regular languages
I'm not sure what you mean by "truest sense." The sense you gave is wrong - regular expressions aren't /equivalent to/ regular languages, they /describe/ regular languages. Backreferences add the ability to also describe non-regular languages, but that doesn't make such a regular expression implementation somehow be not a regular expression implementation.
@@glowingfatedienot sure thats right. regular expressions / regular languages etc can't do prime testing because they by definitin be matched with/reduced to a finite state machine which can't do counting. ie unbounded memory ie not finite i think we are just being too pedantic about the word regular tbh.
My 8 year old loves your videos…I predict he will giggle uncontrollably anytime a new number is summoned but also give me a genuine look of confusion when trying to understand regex. And I wouldn’t be completely mad if he picks up on “what the factor” because that’s freaking hilarious but I still wouldn’t want to have to explain it to his teachers. 😂
The reason we use strings rather than sentences, is because it can be any combination of characters. A string could be a book, or might just be random letters. Sentences infer grammar, punctuation and scope.
A bit pedantic, but 127.0.0.1 is a loopback address. It's like stepping outside to ring the doorbell to make sure it is working. The only time it sends you home is if you are already home.
After spending 52 years of my life coding, this is the first time any bit of code made me laugh. Good thing I had put my coffee down first. Great video!
just to be that more annoying guy. Um actually, it's technically the default loopback. You can add more manually and some operating systems support more out of the box. Any ip address in the subnet 127/8 is available for use as loopback.
@@HenryLoenwind Have you ever tried doing that? It is _not_ easy. Our brains did not evolve to process third-person feedback like that, so unless you have quite a bit of practice, you will need to do a lot of adjusting after your initial guess.
Thank you, Matt, for reminding me how I truly feel about regular expressions. On an unrelated note, beware of “clever” code. I read that in a Fortran book once [citation needed].
You want "clever" code? Check out the International Obfuscated C Code contest (hosted for many years by a fellow that worked for me, who (non-ironically) is a famous prime-hunter.)
Its not quite the Sieve of Eratosthenes as it checks if a the target number is a factor of all numbers smaller than it. The Sieve, as written by Eratosthenes, will only use prime numbers up the to the square root of the number as it will discard all composites before they are used.
I believe that's still trial division, not the actual sieve. See Melissa E. O’Neill's The Genuine Sieve of Eratosthenes, which goes into detail on this and derives asymptotics for both: The sieve does a lot less work to find all primes up to n than trial division, even trial division only checking prime numbers up to sqrt(n).
Original algorithm, as writen by Eratostenes, doesn't stop at sqrt n. It doesn't change the complexity, so it doesn't really matter, in fact. For him would have been a strange "optimization", as very few integers have rational square roots, an calculating the rest would be almost as tedious as the siege itself.
@@framegrace1I don't think he would've been that confused by the idea of taking the ceiling of the square root. You can easily describe what that means in the language of geometry, which he definitely understood
13:45 Hey! Regex capture groups *are* zero-indexed; the brackets start at one but capture group zero is the entire match. Don't you slander regular expressions by calling them one-indexed
No. The whole match is not a capture group. You can observe it by doing ‘re.search('bar', 'foobarbaz').groups()` which returns an empty tuple because there are no capture groups. \0 is the syntax to refer to the whole match. where `n` is non-zero digit is a syntax to refer to 1-indexed capture group.
@@mina86 No is syntax for the nth backreference. It just so happen that the 0th backreference is the whole match and the (n+1)th backreference is the nth group. Groups by themselves are not 1-indexes, that only seem to happen when referring to them using backreferences because backreferences are not just groups.
@@giacomostevanato2203 So you're saying groups are not indexed at all because you reference the backreference and backreference \1 is the "first" (in a normal language sense) or "0th" (in a fictitious 0-indexed sense) group.
@@androlsaibot I mean, in the 0-indexed list of backreferences, the one at index 1 is the first that is also a group (and is followed by the other groups).
Pass the string “1112" to the regex and it will think that 4 is a prime number. This is because the substring (..+?) becomes “11” upon matching and \1 is the ACTUAL string matched, so \1 is “11” which does not match “12”. The regex only works if you pass in strings with all the same character - “aaaa” tests correctly, but “abcd” doesn’t.
This was your silliest video yet and I loved it, haha. Was cracking up at the thought of someone chasing you round a wood throwing numbers at you while filming it.
I was baffled until you pointed out that what we're really regex-ing against is a sequence of 1's. Regex is just trying to see if it can break that string of 1's into a number of equal-sized chunks (that are of length 2 or greater); for example, it could break "1111" into two chunks of length two, but it could not do anything similar with "11111".
Same here. I was baffled before, aghast after. It's as if someone was trying to come up with the least efficient, most memory-intensive prime-seeking method possible.
@@manlyadvice1789 tbh it only takes pcre2 860 microseconds on my computer to test 1001 in 1468 steps. 3089 is tested to be prime in 3.52ms and 25310 steps. I've had regexes used in production take more steps.
Yeah, I was immediately proving it false by counter-example until he explained that 1) it's checking the length of the string, not the contents and 2) it's the opposite, it's checking for composite numbers. If you want prime lengths, use this instead: ^(?!.?$|(..+?)\1+$)
I liked that it checked the primality of a series of ‘1’ characters. It shows that prime numbers are not dependent on the base of the numbers, just the number of ‘things’ being tested
For anyone else who like me was confused at 14:20, when Matt says "we can have multiples of them" he's referring just to the \1+ portion of the expression. This is in addition to the preceding capture group that it references, which in effect means that we *must* have multiples of them when taken across the whole string -- thus ensuring that prime numbers don't themselves get "factored" as p*1 and matched by the regex. This is more obvious when he says "you can have two twos, or three twos, or four twos, all the way up" even though the graphic makes it look like one two is an option.
Thanks. I've worked with regex, but never \1 inside the regex. This actually makes sense to me now, whereas I was confused by Matt's phrasing. It's literally like 'insert whatever group 1 matched here'
That was confusing to me as well! Not sure I now fully understood how it does that but at least I got that it's somehow only referring to two or more groups.
Or, to say it in other words: The second part of regex grabs any number that's 2 or higher that is repeated 2 or more times. So if it can be expressed as "[2,3,4,...] x [2,3,4,...]", it matches.
Yeah, despite the first column of "or"s, the regex is "find something that matches what's in the brackets, and then find that exact string again one or more times" so if the bit in the brackets found "11", then the regex would be looking for "11" followed by at least one "11", taking up the entire string.
In essence, this regex is a creative way to test the indivisibility property of prime numbers using string patterns. It’s a fascinating example of how regular expressions can be applied beyond their usual text-processing tasks!
As someone who understands regex I still didn't understand how it could produce primes. Was super interesting to learn how, and what an amazing bit at the end! Thanks for all the great content you provide 🙏❤
it it orders of magnitude more efficient, this regex can check all numbers up to ~10_000 in ~3 seconds on my machine (using the fancy_regex crate in rust)
I'm proud I was able to learn regular expressions well enough to update a popular stack exchange answer that had sat for a decade with a tiny error in the explanation. Subtle and important.
"for completeness, I will show you that this definitely does work in practice" Can confirm. I said the incantation aloud and a wild 163 appeared, what about you guys?
The demonic power might be accessing your memories while the incantation progresses because I got 41,024,320 random numbers that I don't know what to do with now.
I stumbled upon your rgb Christmas tree and thought that was cool. So I looked into your Channel more. As someone who’s been learning r and wrangling data I was instantly intrigued. I was like, “is that a regular expression? Generate primes? It can’t be”. Subscribed.
This isn't actually the Sieve of Eratosthenes, it's just trial division. The thing that makes the SoE powerful is you don't ecer check crossed-out numbers, meaning you're only checking if *primes* are a factor of n, but this does no such thing, and so is much slower.
It's a fundamental law of computer science that any sufficiently complex regular expression is, by definition, immutable code: It can only be written or re-written, never edited (or understood).
calculate it for me and i will ;) tl;dw: after two infinities, my computer spits out its answer, confirming that which we definitonally knew to be true. we look at each other, and say "nice".
The important part in cracking this is the text you’re running it on and what on earth ‘1’*n means in python. Once I figured out it means “repeat the character n times” and so you’re matching against a string of repeating characters, what the regex is doing became clear.
13:48 This is not technically a "regular" expression because backreferences are not regular; as what the backreference matches changes based on previous input, and regular expressions are context-free (you can concatenate two regular expressions and it has the expected effect, but this does not hold true if the expression contains a backreference). "Regular" is an important property because it guarantees performance within a fixed amount of memory regardless of the input size, and compute time proportional to the input size, but the backreference obliterates that characteristic.
@@asandax6 that's okay, I've been doing them for 20 and I feel the same. At least we can now ask ChatGPT... One time ages ago someone asked in a local forum about a regex and I thought he was parodying them because on top of the whole cat-walked-on-keyboard mess it had smileys in it! (this is before emojis, but the image equivalent of a 😊 😢 etc) Until I realised the colons and brackets were part of the original regex, transformed by the forums software And while that doesn't demonstrate how annoying regex is, it sure shows it
Yes. The '^' is the caret, and the '|' is the stick. You know, "Do this, or else ..." That's a stick. And that's what '|' is used for, though usually doubled to accomplish that. `Do() || die("Hey, I've died twice.")` works in C, though it's a Perl idiom.
A string is a "string of characters". It makes sense to say because it applies to all strings, not just those that also happen to be grammatically correct sentences. For example "^.?$|^(..+?)\1+$" is a string, but certainly not a sentence.
IMHO @15:21 explanation of (..+)\1 in the picture is incorrect! For instance, (11)\1 shall NOT match 11 but shall match 1111 or 111111 because at least ONE REPETITION of the given group given in parentheses MUST be present! If there is no repetition of the given group, then there is no match!
@@fatemonkey 11 will not match. + matches indeed 1 or more times, but \1+ means that you have to match 1 or more times whatever was matched by the capture group *following* the match of the capture group.
I remember reading Humble Pi and near the end thinking 'Matt is really more of a Computer Scientist at this point rather than just a mathematician' I think this is the nail in the coffin.
This regular expression has been around for decades. Attributed to Abigail, a Dutch JAPH (just another Perl hacker). I hope YT will not eat my comment.
I don't think I've ever heard somebody pronounce the 'g' in 'regex' like the 'g' in 'regular', even though it obviously makes sense when you think about it.
I have only ever heard it pronounced rejex. The sound from the reg in register. I think it's pronounced this way because it is more phonetically satisfying.
@@JavedAlam-ce4mu That is the normal pronunciation, and makes sense in English (usually G before I or E is a soft G, like in other languages), but a hard G also makes sense because it comes from "reGular."
If we took the formal language theory definition of regular expressions (from the Chomsky hierarchy), evaluating primes should not be possible. Regex implementations (like in Python) uses backtracking and recursive matching.
Well then you shouldn't be afraid of ^(?!.?$|(..+?)\1+$) since it's looking for the beginning of something that _isn't_ matching the regular expression.
I love all your posts ever since I discovered "Festival of the Spoken Nerd" ( Iave all the DVDs 🥰) but this wone was special. It put a massive smile on my face, thank you.
The most useful thing to master in coding is how to make the most readable code possible. In that light, regex is the least useful things you could master. Never be clever!
@@_Agent_86 Yes and no. Yes on, readability is key to good code; code that is easy to maintain tends towards fewest bugs. No on your disdain for regular expressions: even simple regular expressions are useful as hell. For example, if you want to test the format of a positive integer with no leading zeros, it's /^[1-9]\d*$/ . That involves fewer gyrations than trying to evaluate the expression numerically and stripping off leading zeroes / a decimal / etc. Or trying to extract fields of data from a string, regular expressions can make difficult tasks very simple. You're right that regular expressions can be abused, to which I say: don't abuse them. Problem solved.
@@mjkmetso2935 Even that isn't the fault of regex. The incident report identifies this as the problem: "The content validator evaluated the new template instances under the assumption that the IPC template type would provide all 21 inputs. Due to the mismatch, the validator failed, leading to the incident." It wasn't a regex blunder or a bug in regex or an ambiguity in regex; from what they're describing, the coder operated under incorrect assumptions about the data. The same error would have occurred with a non-regex validator.
@@kingbeauregardI do agree, and I do use them, but they are inherently low readability. And when I review code with one, I assume it was copy pasted from somewhere. Then I have to divert and research carefully. My comment was mostly to quell the enthusiasm of the op a bit! Appreciate your POV though.
i think youve got that backwards. for non-programmers theyre spooky. for a programmer theyre the least spooky thing in the world. theyre so wonderfully logical and structured (hence 'regular') that theyre a joy to work with. for non-programmers (and this includes 'coders/developers' in my mind) i can see how they might be a little daunting.
@@radiobabylon You are clearly either not a programmer in regular life or a novice if you think regexes (especially ones using non-regular extensions such as backreferences) are "wonderfully logical and structured". If you are, your teammates probably dislike your over-use of regexes in production code and try to replace it with something more maintainable every chance they get. Regexes are a write-only language, they can't meaningfully be read like actual code. A mere 16 characters or so took an entire 18 minute video to explain. This is not a good thing. They're useful for use-once search/replace like grep/sed, not in code that runs without direct supervision.
@@timh.6872 I think your reply is a very good confirmation for @radiobabylon 's statement. Regex are easy to read, but as it is with every language, you become better at reading and writing with experience.
Sorry to point this out - this isn't a regex. Regular expressions themselves are not powerful enough to calculate primes. This is an extension to regular expressions that makes it turing complete.
Totally fascinating! I love regex and this is such a cool example! Thanks so much for documenting and explaining your expedition to the prime realm Matt!
I have been using regular expressions in my work very regularly for years and yet I am amazed by this one and especially by its simplicity compared to the task accomplished ! Kudos to Illya for coming up with that piece of cryptic string !
I don't understand what the "\1+?" is doing. If "\1" is the first index of all the possible matches from the expression in the parentheses, then wouldn't it just be the match "11"? So wouldn't this regex only match on multiples of 2?
@vibaj16 when this regexp matches, (...+?) captures the smallest prime divisor. For example 5 consecutives "1" if you test 385=5*7*11=77 groups of 5 consecutives "1". \1 will then also represent 5 consecutives "1" and \1+ will match the 76 remaining groups of 5 consecutives "1".
@@vibaj16 It is "\1+" without "?" "\1" is a reference to whatever the "first set of parentheses" matches. In this case, there is only one set of parenthesis, so there is no \2 and so on. When "(..+?)" matches "11", then "\1" is matching "11". The "+" repeats "\1" and therefore matches "11" as often as possible. ^(..+?)\1+$ The regex takes the smallest [i.e. "?"] sequence of repeating characters [i.e. "..+"] at the beginning [i.e. "^"] of the string [together "^(..+?)"] and looks if the found beginning [in this case "11"] is repeated [i.e. "\1"] over and over again [i.e. "+"] until exactly the end of the string (i.e. "$"). If it is not, then, "11" is not the smallest sequence that can be matched by "the parenthesis" and also fulfilling the entire regex, but maybe "111" is the smallest sequence. If not, then maybe "1111" is and so on.
@@snygg1993 thanks. I think I understand now. The exact meaning of "\1" wasn't explained very well in the video, nor by the first reply to my question.
A good way to define a regular expression is that it defines a set of strings. We normally use them to check if a string belongs to the set, but we could also use them to generate strings that belong in the set. In other words, we could use the regex pattern to generate primes instead of just checking if a number is prime.
It isn't anything to do with the Sieve of Eratosthenes. It's just brute force factorisation. A sieve is an algorithm to produce all primes. This is an algorithm to check if a number is a prime. Totally different things.
@@wyattsheffield6130this is true in this instance (not always with modern "regex"), but this grammar actually describes strings with non-prime lengths, so its about as useful at finding primes as the multiplication button on your calculator :)
@wyattsheffield6130 But it wouldn't be the Sieve of Eratosthenes, since it would be checking each number separately. The Sieve of Eratosthenes uses the previous steps to make it more efficient. You don't check for divisibility by 4 because you already removed 4 when checking divisibility by 2. And by checking every number for divisibility by each number at once, you don't have to do any division and can just do a single addition for each number. It's a specific algorithm that is intelligently designed to be efficient. It's very different to just brute force checking each number.
Saying it's "nothing to do with" the sieve is going too far though. If you used this (non-regular) expression in the generative direction, to generate all the composite numbers, it would generate all the multiples of 2, then all the multiples of 3, then yes admittedly all the multiples of 4, then 5, then 6, etc. It's not the sieve proper but anyone can see the resemblance.
13:57 no, the capture groups ARE zero-indexed. The \0 capture group is the whole regex pattern itself. You can't use the \0 capture group within the regex itself, but you can use it in re.sub(...) and re.findall(...).group(0).
No. The whole match is not a capture group. You can observe it by doing ‘re.search('bar', 'foobarbaz').groups()` which returns an empty tuple because there are no capture groups. \0 is the syntax to refer to the whole match. where `n` is non-zero digit is a syntax to refer to 1-indexed capture group.
we have a saying in programming. Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.
Take your personal data back with Incogni! Use code standupmaths at the link below and get 60% off an annual plan: incogni.com/standupmaths
Don’t use code ^.?$|^(..+?)\1+$.
2
3
5
3:24 that poor second + sign doesnt get highlighted :(
7
wow, what a neat trick! i'm adding this to my production code immediately, good luck new hires!
You monster
@@omnijack ‘Tis the season
YOURE why my neck hurts!! ='(
make sure to comment
"// not sure what this does but the system breaks if you remove it"
Halloween post
The plural of regex is regrets.
strangely enough, also the singular
"I have a problem. Oh, I know, I'll use regex to solve that problem." [...] "Now I have two problems."
To many IT/Prog guys here. 😁
That said, pretty solid explanation by Matt, but yeah, pretty easy to get lost in RE
@@JPBelanger is that really a surprise?
@lox7182 not really😁
Guessing not many strangers to twenty sided die, board games, and LotR either 😁
Regular expressions are already scary by nature. Making one that produces primes is truly terrifying.
Checks for*
It does not produce them
Also, this isn't a true regex. The type of self referentialism in action here is imopssible in simple regex's.
@GustvandeWal True, but just hook it up to an incrementing int and a while loop and you've got yourself a generator.
(Or abuse a for loop, lol.)
@Kosmokraton I did think Matt was going to add this to his code.
But on reflection, it's probably a good thing he didn't.
Code like that is truely terrifying.
Perl has a reputation of being a "write only language."
Then regexes must be the "write only, and get it right only occasionally by fluke or trial and error API of coding."
@@minamagdy4126So only "simple" regexes are "true" regexes?
How does that work?
It really works! I put it on the extra notes section of my Amazon delivery, and it became Prime!
I forgot the not and my parcel came chopped up into different parts.
@@colmx8441 Should've used ^(?!.?$|(..+?)\1+$) instead.
😂
Haha lemme try it-
Tried it on my AliExpress delivery and it became Prime the drink. It tastes awful.
My doctor also said my body have lead in them.
I loved the home joke at the end; you're such a good localhost.
I tried the second incantation myself, but I just got sent to the party just down the road. Maybe I should have just used "~"...
@@MrSonny6155 it's cool that your neighborhood has a designated local host
15+ years of programming experience including using regular expressions and I still watched and enjoyed this video. It's a testament to Matt's enthusiasm and his skill as a speaker/teacher.
Retired life long professional Unix user - Perl and Vi(m) mean regex is my native tongue!
Same, I figure out how it worked by just reading it, but he’s a joy to watch. Although, granted tapping on the video I was confused how it would be able to parse “17” as a prime and took a re-read of the regex to understand that it’s a length of the same character
Same here. That's a really neat way to use regex. Not as efficient as the sieve of Eratosthenes, for the reasons mentioned at 14:30, but still really cool :)
Which Python editor/IDE is this
@@amits4744 Matt is using VSCode
love that the halloween horror episode on a math channel is . . . code
Great idea for the next horror video. Simply presenting samples of hacked together python code from past videos
No, the real horror would be ultra-optimized C++ code. The badly-written python code is a staple
Nothing scarier than regular expressions.
But it's code that software engineers hate :)
And a prime-al forest and a computer joke
To simplify, this takes the number and expresses it as a unary numeral system, where the number of marks is the value of the number you put in (e.g. 1 is 1, 2 is 11, 3 is 111, ...). The regex then looks to divide the unary representation into exactly N groups of size M, where both N and M are natural numbers with value 2 or larger. For example, you can divide 4 (represented as 1111) into 2 groups of "11". You can divide 6 (represented 111111) into 2 groups of "111" or 3 groups of "11". However, you can't divide 3 (represented as 111) into groups of the same size (technically you can do 3 groups of "1", but then M isn't 2 or larger). Basically, you are checking if the number has any factors bigger than 1, which obviously is only false for prime numbers.
I think you mean N and M are 2 or bigger (not "bigger than 2").
Still, I get why M should be 2 or bigger ( because the first dot in [..+?] is obligatory and the + means at least 1 extra. I don't get why N should be at least 2. The + after the group means 1 group or more doesn't it? 1 group of three dots shouldn't render True however.
@@dudicrous oops, yes I do, fixed it now.
N must be 2 or larger because the part in the parenthesis needs to match something (the first group), and the \1+ means that the same thing must appear at least one more time. The parenthesis part also "consumes" whatever it matches. So basically 4 (aka 1111) would match 11 with the (..+?) and the remaining 11 would match the \1+. If you have 2 (aka 11) you can match the parenthesis, but then you have nothing left to match the \1+ part.
@@RMDragon3 Ah yes, so ".+" is different from "(.)\1+". Looking back, Matt mentions it correctly, the video shows an erroneous first "or" though.
I'm trying to figure out if the algorithm is quadratic or exponential
I'd guess it's at least pseudo-exponential because the length of the number is n=LogN.. But this algorithm is N*N.
Since LogN^b = N. Then the algorithm is O(n^b*N) = O(n^2b). Which is very big.
Also for huge primes the O(N) memory requirement could be prohibitive.
A minor bit of pedantry: ^.?$|^(..+?)\1+$ is a "regex" (i.e. a pattern specification understood by most common implementations of regular-expression-based pattern-matching engines), but it is not a regular expression in the strict sense of the term. The minimal definition of a strict regular expression includes only literal characters, a symbol standing for an empty string (typically ε), parentheses to clarify the order of operations, the alternation operator (vertical bar), and the Kleene star (asterisk). Most of the other symbols in our prime-matching regex can be derived from those in the minimal definition: The wildcard . is shorthand for (a|b|c|d|...), and a+ is shorthand for aa*. The symbols ^, $, and ? are irrelevant in a strict regular expression, since it either matches the entire string or it doesn't match at all. The real problem is the \1: There's no way to construct an equivalent out of the minimal definition.
Yup. Most modern "regex" engines are actually context-free grammar engines but they use syntax similar to true regex engines from decades past so people keep calling them that.
Thank you for this comment! As someone who spends a good bit of time in theoretical computer science land it always bugs me when "regex" arent actually regular at all. Saved me the trouble of writing this comment myself
thank you @TheRyulord for mentioning that the relation to CFG. i think it's something even more sinister... 'cz whereas a CFG/PDA uses stack, i.e. single time contiguous use, the backref uses arbitrary memory. & i dont remember which Grammar represents automaton with arbitrary append-only (say immutable read/write) memory.
Google’s regex library, called RE2, does *not* allow backreferences like this since they can cause a regex search to take exponential time.
I love regular expressions. The xkcd is true, you really do feel like you've developed a super power when you master them
It's like actual wizardry, and no less arcane. Reading someone else's regex really is like deciphering a spell comprising ancient runes you individually understand...
To clarify: a '?' on it's own matches 0 or 1 of the preceding character. A '?' following '+' modifies the greedy behavior of '+' to be less greedy
Knows the different flavors of ? but doesn't know the difference between its and it's
@@DCSWCCkingpin1we’re programmers. Not languagers.
@@DCSWCCkingpin1 it'?s
@@DeronMeranda I see what you did there.
Just a note, what you call "less greedy" is known as lazy.
As a Regex connoisseur, I was really confused as to how the expression could possibly do that. But it makes perfect sense now. So simple, and yet so clever!
nobody is a regex connoisseur. nobody. it is where happiness goes to die...
@@WoolyCow Did you know that there exists a Regex Crossword puzzle game? It's surprisingly fun!
@@WoolyCow Maybe for you, but I married RegEx and had two kids with it.
@@HugoBDesigner WHERE?? IT DOES SOUND FUN I WANNA TRY IT /silly
@@WoolyCow Incorrect. I find RegEx quite fun and interesting. Figuring out the RegEx you need for a specific task is like solving a puzzle.
Someone has to say it. Regular expressions,in their truest sense, ie ones that are equivalent to regular languages are not capable of primality test. Only extended ones that have “memory” can do it. I.e \1 part of the example above is what’s not possible in regular languages
This brought me flashbacks having to prove that on an exam with the pumping lemma
@@ModusTrollens91 *shudders*
@@ModusTrollens91 "prove that on an exam". username checks out
I'm not sure what you mean by "truest sense." The sense you gave is wrong - regular expressions aren't /equivalent to/ regular languages, they /describe/ regular languages. Backreferences add the ability to also describe non-regular languages, but that doesn't make such a regular expression implementation somehow be not a regular expression implementation.
@@glowingfatedienot sure thats right. regular expressions / regular languages etc can't do prime testing because they by definitin be matched with/reduced to a finite state machine which can't do counting. ie unbounded memory ie not finite i think we are just being too pedantic about the word regular tbh.
*Matt:* "What the factor?"
*Primes:* "Your factors can't help you here."
I've been writing code professionally for 20 years and this is the best explanation of regex I've seen. Great job!
At first I thought the ? meant unknown quantity before watching the video lol.
The cinematography of some of the more recent videos has been astounding. Nice work!
Indeed! The only minor point is that the editor should use a higher brightness or a screen with wider contrast.
Regex is already halloween worthy.
use regex all the time now to validate llm output formats, they arent scary they are lovely
It's the blackest of black magic
@@aikumaDKOh yeah? Have you tried PERL?
@@Swordfish42 RegEx inside Perl. The darkest of black magic.
@@Talderas RegEx inside Malbolge: try that, if you are brave enough! =)
"What the factor" got me hahaha
My 8 year old loves your videos…I predict he will giggle uncontrollably anytime a new number is summoned but also give me a genuine look of confusion when trying to understand regex.
And I wouldn’t be completely mad if he picks up on “what the factor” because that’s freaking hilarious but I still wouldn’t want to have to explain it to his teachers. 😂
The reason we use strings rather than sentences, is because it can be any combination of characters. A string could be a book, or might just be random letters. Sentences infer grammar, punctuation and scope.
A bit pedantic, but 127.0.0.1 is a loopback address. It's like stepping outside to ring the doorbell to make sure it is working. The only time it sends you home is if you are already home.
The correct incantations would indeed be either "Set-Location -LiteralPath $env:USERPROFILE" or "cd" . (-:
The doorbell thing is how I'm gonna explain loopback from now on
"stepping outside", its more like trying to reach doorbell while standing inside :D
Or like if you would have portal gun then it makes the blue and orange portals the same.
"The only time it sends you home is if you are already home"
Well that was oddly poetic
This looks like an alternate version of Abigail's prime regex that was posted on a Perl newsgroup in the '90s. Legendary Perl hacker.
Right. There should be an entire episode on Abigail's tricks
@@MishaTheElder Sounds like an episode of the "The Scary Door".
i love matts videos
maths videos are the best
import re
comment = input()
print(re.match(r'm...s',comment))
>>> True
import re
comment = input()
print(re.match(r'm...s',comment))
>>>True
Oh, it's nice to see a totally normal person saying a totally normal sentence in the wild!
17:25 Imagine just walking in the forest and watching some dude running out from the cameraman, who throwns at him 3D-printed digits...😅
After spending 52 years of my life coding, this is the first time any bit of code made me laugh. Good thing I had put my coffee down first. Great video!
just to be that guy: 127.0.0.1 isn't "home", it's loopback, so it should just send you back to where you're at right now.
If you really want home, use ~
thanks for being that guy
@@thepython10110 That just translates (or expands as shell nerds like to say) to home. If you actually want to go home you should use cd.
just to be that more annoying guy. Um actually, it's technically the default loopback. You can add more manually and some operating systems support more out of the box. Any ip address in the subnet 127/8 is available for use as loopback.
I love all the other "that guy"s replying to this
There's no place like 127.0.0.1 ... except the rest of the /8 block of 16,777,216 addresses also reserved for loopback
And ::1
@@martijnvdsthat's just 127.0.0.1 in ipv6
3:31 The ability of Matt to accurately point to symbols that he'll put in later...
it was seriously impressive. i wonder if it was first try
Not so impressive when you realise he's looking at a monitor showing a life feed from the camera. Easy to mark the right positions on that...
@@HenryLoenwind Still tough to nail the pointing.
@@HenryLoenwind Have you ever tried doing that? It is _not_ easy. Our brains did not evolve to process third-person feedback like that, so unless you have quite a bit of practice, you will need to do a lot of adjusting after your initial guess.
@@WJS774 Unless the camera feed is mirrored. Then it's pretty easy.
you know its going to be a good day when Matt releases a video that intersects with my most used number sets and my most used programming feature.
Thank you, Matt, for reminding me how I truly feel about regular expressions. On an unrelated note, beware of “clever” code. I read that in a Fortran book once [citation needed].
You want "clever" code? Check out the International Obfuscated C Code contest (hosted for many years by a fellow that worked for me, who (non-ironically) is a famous prime-hunter.)
Its not quite the Sieve of Eratosthenes as it checks if a the target number is a factor of all numbers smaller than it. The Sieve, as written by Eratosthenes, will only use prime numbers up the to the square root of the number as it will discard all composites before they are used.
I believe that's still trial division, not the actual sieve. See Melissa E. O’Neill's The Genuine Sieve of Eratosthenes, which goes into detail on this and derives asymptotics for both: The sieve does a lot less work to find all primes up to n than trial division, even trial division only checking prime numbers up to sqrt(n).
I still haven't figured out how to do that one in Human Resource Machine optimally
Original algorithm, as writen by Eratostenes, doesn't stop at sqrt n. It doesn't change the complexity, so it doesn't really matter, in fact.
For him would have been a strange "optimization", as very few integers have rational square roots, an calculating the rest would be almost as tedious as the siege itself.
@@framegrace1I don't think he would've been that confused by the idea of taking the ceiling of the square root. You can easily describe what that means in the language of geometry, which he definitely understood
@@framegrace1 You don't need to know roots, just stop when the square of the current number exceeds your chosen max.
What in the ^.?$|^(..+?)\1+$ did I just watch?
Edit: Added
Now it won't work! without +, ..? captures one or two ones, so magic stops after 1111. You gotta be lazy!
Oh, it was 179, AKA p[41].
It's pronounced "factor".
@@lockaltubeactually it will now only say true for multiples of 1 and 2, which is all the numbers
This just tests for odd numbers greater than 1.
13:45 Hey! Regex capture groups *are* zero-indexed; the brackets start at one but capture group zero is the entire match. Don't you slander regular expressions by calling them one-indexed
They're Parker-one-indexed
No. The whole match is not a capture group. You can observe it by doing ‘re.search('bar', 'foobarbaz').groups()` which returns an empty tuple because there are no capture groups. \0 is the syntax to refer to the whole match.
where `n` is non-zero digit is a syntax to refer to 1-indexed capture group.
@@mina86 No
is syntax for the nth backreference. It just so happen that the 0th backreference is the whole match and the (n+1)th backreference is the nth group. Groups by themselves are not 1-indexes, that only seem to happen when referring to them using backreferences because backreferences are not just groups.
@@giacomostevanato2203 So you're saying groups are not indexed at all because you reference the backreference and backreference \1 is the "first" (in a normal language sense) or "0th" (in a fictitious 0-indexed sense) group.
@@androlsaibot I mean, in the 0-indexed list of backreferences, the one at index 1 is the first that is also a group (and is followed by the other groups).
Pass the string “1112" to the regex and it will think that 4 is a prime number.
This is because the substring (..+?) becomes “11” upon matching and \1 is the ACTUAL string matched, so \1 is “11” which does not match “12”.
The regex only works if you pass in strings with all the same character - “aaaa” tests correctly, but “abcd” doesn’t.
This was your silliest video yet and I loved it, haha. Was cracking up at the thought of someone chasing you round a wood throwing numbers at you while filming it.
I was baffled until you pointed out that what we're really regex-ing against is a sequence of 1's. Regex is just trying to see if it can break that string of 1's into a number of equal-sized chunks (that are of length 2 or greater); for example, it could break "1111" into two chunks of length two, but it could not do anything similar with "11111".
Thank you! He left out that kind of nice example and left me confused.
Same here. I was baffled before, aghast after. It's as if someone was trying to come up with the least efficient, most memory-intensive prime-seeking method possible.
Yeah, it's not JS hyere, so '1' != 1 ^^
(Killing my own joke, but JS typing system is really bloated. Not to that point, though)
@@manlyadvice1789 tbh it only takes pcre2 860 microseconds on my computer to test 1001 in 1468 steps. 3089 is tested to be prime in 3.52ms and 25310 steps. I've had regexes used in production take more steps.
Yeah, I was immediately proving it false by counter-example until he explained that 1) it's checking the length of the string, not the contents and 2) it's the opposite, it's checking for composite numbers.
If you want prime lengths, use this instead:
^(?!.?$|(..+?)\1+$)
I liked that it checked the primality of a series of ‘1’ characters. It shows that prime numbers are not dependent on the base of the numbers, just the number of ‘things’ being tested
For anyone else who like me was confused at 14:20, when Matt says "we can have multiples of them" he's referring just to the \1+ portion of the expression. This is in addition to the preceding capture group that it references, which in effect means that we *must* have multiples of them when taken across the whole string -- thus ensuring that prime numbers don't themselves get "factored" as p*1 and matched by the regex. This is more obvious when he says "you can have two twos, or three twos, or four twos, all the way up" even though the graphic makes it look like one two is an option.
Thanks, I was so confused by how prime were not flagged as well!
Thanks. I've worked with regex, but never \1 inside the regex. This actually makes sense to me now, whereas I was confused by Matt's phrasing.
It's literally like 'insert whatever group 1 matched here'
That was confusing to me as well! Not sure I now fully understood how it does that but at least I got that it's somehow only referring to two or more groups.
Or, to say it in other words: The second part of regex grabs any number that's 2 or higher that is repeated 2 or more times. So if it can be expressed as "[2,3,4,...] x [2,3,4,...]", it matches.
Yeah, despite the first column of "or"s, the regex is "find something that matches what's in the brackets, and then find that exact string again one or more times" so if the bit in the brackets found "11", then the regex would be looking for "11" followed by at least one "11", taking up the entire string.
In essence, this regex is a creative way to test the indivisibility property of prime numbers using string patterns. It’s a fascinating example of how regular expressions can be applied beyond their usual text-processing tasks!
As someone who understands regex I still didn't understand how it could produce primes. Was super interesting to learn how, and what an amazing bit at the end! Thanks for all the great content you provide 🙏❤
If have a problem, and you try to use regex to solve it, you now have two problems.
(problems)+
@@zeikjt (problems)*
I was sure somebody would have commented this, so I scrolled through a lot until I found this
@@roxas8999 Me too... first thing I did was search for "problems" and found this comment. Oldie... but goodie...
Pff... coward.
This is approaching the level of LLM powered IsEven
it it orders of magnitude more efficient, this regex can check all numbers up to ~10_000 in ~3 seconds on my machine (using the fancy_regex crate in rust)
I'm proud I was able to learn regular expressions well enough to update a popular stack exchange answer that had sat for a decade with a tiny error in the explanation. Subtle and important.
I would be proud if I could post a question to Stack Overflow without it immediately being closed for one reason or another...
I applaud your commitment to making regular expressions make sense.
Having regex as an arcane script in a halloween video is so accurate
"for completeness, I will show you that this definitely does work in practice"
Can confirm. I said the incantation aloud and a wild 163 appeared, what about you guys?
The demonic power might be accessing your memories while the incantation progresses because I got 41,024,320 random numbers that I don't know what to do with now.
i must have said it wrong... i got an 8
An Amazon Prime delivery appeared.
@@colinmcconnell827 can confirm, i was the package
I tried it and I discovered a new programming language called C** what should i do!?
I am always so happy to see a stand-up maths video. The ending spoky bit was quite a fun touch 😁
Dang, prime numbers *AND* regex? It must be my birthday!
Happy birthday!c
hap birf
Surely your birthday, as in anyone's birthday, is a regex?
I stumbled upon your rgb Christmas tree and thought that was cool. So I looked into your Channel more. As someone who’s been learning r and wrangling data I was instantly intrigued. I was like, “is that a regular expression? Generate primes? It can’t be”.
Subscribed.
My favorite type of thing in the entire world is anything which is all three of:
1) funny
2) extremely clever
3) extremely stupid
The camera man never dies! I am so sharing this with my work group tomorrow.
They loved it btw!
"What the factor!" , nice one Matt
Screaming in regular expressions 😂
Careful, with good luck and bad luck it'll match, not necessarily the same or right things.
@Milamberinx hahahaha absolutely true! 🤣
"A+"
One of my favourite quotes "If you have a problem that can be solved by regular expressions, you now have two problems" 😁
This isn't actually the Sieve of Eratosthenes, it's just trial division. The thing that makes the SoE powerful is you don't ecer check crossed-out numbers, meaning you're only checking if *primes* are a factor of n, but this does no such thing, and so is much slower.
It's a fundamental law of computer science that any sufficiently complex regular expression is, by definition, immutable code: It can only be written or re-written, never edited (or understood).
But if you put a regex in your code without a comment explaining what it does, I WILL fail your pull request.
Haven't watched the full video yet but I immediately said, "Now plug the largest Mersenne Prime into that regex"
I'm not quite sure python can handle a number of that size, but if it could, it would take an eternity to run anyway!
calculate it for me and i will ;)
tl;dw: after two infinities, my computer spits out its answer, confirming that which we definitonally knew to be true. we look at each other, and say "nice".
Ka -- blooie!
@@MrKahrum "Top long ; didn't ..... Write?"
@@marcoottina654 Too Long; Didn't Watch
The important part in cracking this is the text you’re running it on and what on earth ‘1’*n means in python. Once I figured out it means “repeat the character n times” and so you’re matching against a string of repeating characters, what the regex is doing became clear.
The b/w part at the end is a very precise depiction of how programmers feel when using regex.
13:48 This is not technically a "regular" expression because backreferences are not regular; as what the backreference matches changes based on previous input, and regular expressions are context-free (you can concatenate two regular expressions and it has the expected effect, but this does not hold true if the expression contains a backreference). "Regular" is an important property because it guarantees performance within a fixed amount of memory regardless of the input size, and compute time proportional to the input size, but the backreference obliterates that characteristic.
Aaahh yes, RegEx's
Fun to concoct
Absolute nightmare to debug
As someone who's written Regex for 2 years I still have no idea what I'm doing and I have a feeling I never will.
@@asandax6 that's okay, I've been doing them for 20 and I feel the same.
At least we can now ask ChatGPT...
One time ages ago someone asked in a local forum about a regex and I thought he was parodying them because on top of the whole cat-walked-on-keyboard mess it had smileys in it! (this is before emojis, but the image equivalent of a 😊 😢 etc)
Until I realised the colons and brackets were part of the original regex, transformed by the forums software
And while that doesn't demonstrate how annoying regex is, it sure shows it
regex in RUclips titles. coming back to this later 📌
no place like 127.0.0.1
_Tom Scott has unentered retirement…_
@@benharri actually, there's no place like ~
'^' is called a caret. An up-arrow would be ↑...
In the 7-bit world of the 1960s, they were the same thing. Have a look at the early days of ASCII. Terrible Python has yet to fully escape that world.
It's called a circumflex
Yes. The '^' is the caret, and the '|' is the stick.
You know, "Do this, or else ..." That's a stick. And that's what '|' is used for, though usually doubled to accomplish that. `Do() || die("Hey, I've died twice.")` works in C, though it's a Perl idiom.
I prefer to think of it as a naked circumflex.
@@menachemsalomon 丨 and 人 and 个 is used where?
I’ve never been happier to be even slightly fluent in regex. It was torture to learn but this made it worth it.
A string is a "string of characters". It makes sense to say because it applies to all strings, not just those that also happen to be grammatically correct sentences. For example "^.?$|^(..+?)\1+$" is a string, but certainly not a sentence.
"20 to life" is a string, a sentence, and a noun phrase.
IMHO @15:21 explanation of (..+)\1 in the picture is incorrect! For instance, (11)\1 shall NOT match 11 but shall match 1111 or 111111 because at least ONE REPETITION of the given group given in parentheses MUST be present! If there is no repetition of the given group, then there is no match!
There doesn't need to be a repitition. + matches 1 or more times, so it's checking if 11 appears 1 or more times, thus 11 would match...
@@fatemonkey 11 will not match. + matches indeed 1 or more times, but \1+ means that you have to match 1 or more times whatever was matched by the capture group *following* the match of the capture group.
'i love matts videos'
I remember reading Humble Pi and near the end thinking 'Matt is really more of a Computer Scientist at this point rather than just a mathematician'
I think this is the nail in the coffin.
No computer scientist would consider "sentence" to be the proper meaning of "string"
@@TheGreatAtario was going to post the same, but thanks for doing it first.
Matt the Warlock facing the Prime Evils!
This video's production value is like finding a new prime - astronomically impressive!
This regular expression has been around for decades. Attributed to Abigail, a Dutch JAPH (just another Perl hacker). I hope YT will not eat my comment.
I don't think I've ever heard somebody pronounce the 'g' in 'regex' like the 'g' in 'regular', even though it obviously makes sense when you think about it.
I've always pronounced it that way in my head, and was surprised when I heard it the other way. It really is exactly the same as the GIF thing.
I have only ever heard it pronounced rejex. The sound from the reg in register. I think it's pronounced this way because it is more phonetically satisfying.
@@JavedAlam-ce4mu That is the normal pronunciation, and makes sense in English (usually G before I or E is a soft G, like in other languages), but a hard G also makes sense because it comes from "reGular."
@@thepython10110the folks who get mad when people say gif with a soft g would like a word with you 😂
i’ve heard it so many times both ways, at this point i’m not even sure which way i usually say it
If we took the formal language theory definition of regular expressions (from the Chomsky hierarchy), evaluating primes should not be possible.
Regex implementations (like in Python) uses backtracking and recursive matching.
Quality is never an accident; it is always the result of intelligent effort.
127.0.0.1 is a loopback so if you actually did it it would just send you to wherever you already were not home.
There's no place like ::1...
There's no place like ~
Hey ! I'm your new postman. You can trustfully bring me all your mail, including valuables.
(yes, this is an ipv6 joke too :p )
I can think of nothing scarier than regular expressions
Well then you shouldn't be afraid of ^(?!.?$|(..+?)\1+$) since it's looking for the beginning of something that _isn't_ matching the regular expression.
regex is definitely one of the scariest things you can show to any programmer
But not THE scariest.
Timezones.
I love all your posts ever since I discovered "Festival of the Spoken Nerd" ( Iave all the DVDs 🥰) but this wone was special. It put a massive smile on my face, thank you.
16:40 I appreciate the factor joke in a video about primes.
Regular expressions are otherworldly. Do learn them if you do any programming, though; they are one of the most useful things you can master.
They are also the easiest way to introduce massive bugs into production *Looking at crowdstrike*
The most useful thing to master in coding is how to make the most readable code possible. In that light, regex is the least useful things you could master. Never be clever!
@@_Agent_86 Yes and no. Yes on, readability is key to good code; code that is easy to maintain tends towards fewest bugs. No on your disdain for regular expressions: even simple regular expressions are useful as hell. For example, if you want to test the format of a positive integer with no leading zeros, it's /^[1-9]\d*$/ . That involves fewer gyrations than trying to evaluate the expression numerically and stripping off leading zeroes / a decimal / etc. Or trying to extract fields of data from a string, regular expressions can make difficult tasks very simple.
You're right that regular expressions can be abused, to which I say: don't abuse them. Problem solved.
@@mjkmetso2935 Even that isn't the fault of regex. The incident report identifies this as the problem: "The content validator evaluated the new template instances under the assumption that the IPC template type would provide all 21 inputs. Due to the mismatch, the validator failed, leading to the incident." It wasn't a regex blunder or a bug in regex or an ambiguity in regex; from what they're describing, the coder operated under incorrect assumptions about the data. The same error would have occurred with a non-regex validator.
@@kingbeauregardI do agree, and I do use them, but they are inherently low readability. And when I review code with one, I assume it was copy pasted from somewhere. Then I have to divert and research carefully. My comment was mostly to quell the enthusiasm of the op a bit! Appreciate your POV though.
Spooky that the QR code at 9:19 has a ghost in the middle.
If you ask a programmer, its not the primes that are spooky but the regex. 😂
i think youve got that backwards. for non-programmers theyre spooky. for a programmer theyre the least spooky thing in the world. theyre so wonderfully logical and structured (hence 'regular') that theyre a joy to work with. for non-programmers (and this includes 'coders/developers' in my mind) i can see how they might be a little daunting.
@@radiobabylon Ask Crowdstrike if Regex are spooky. It is too easy to get them wrong or miss edge-cases
@@radiobabylon You are clearly either not a programmer in regular life or a novice if you think regexes (especially ones using non-regular extensions such as backreferences) are "wonderfully logical and structured". If you are, your teammates probably dislike your over-use of regexes in production code and try to replace it with something more maintainable every chance they get.
Regexes are a write-only language, they can't meaningfully be read like actual code. A mere 16 characters or so took an entire 18 minute video to explain. This is not a good thing. They're useful for use-once search/replace like grep/sed, not in code that runs without direct supervision.
@@timh.6872 yeah, thats probably it.
@@timh.6872 I think your reply is a very good confirmation for @radiobabylon 's statement.
Regex are easy to read, but as it is with every language, you become better at reading and writing with experience.
As a student who at the time give a lecture to the class on regex, I love this video, thank you Matt!
Thank you Matt for this prodigious incantation unveiling the deep mystery of regular expressions!
wow just 1 line of code! that must be really fast, right ... right?
😂
It will be fast, as it is only applicable to relatively small numbers.
00:30 I like how you can see Matt's Matte.
17:15 Who wants to play the Matt Parker platformer video game now?
Prime runner
Sorry to point this out - this isn't a regex. Regular expressions themselves are not powerful enough to calculate primes. This is an extension to regular expressions that makes it turing complete.
While modern "regex" are more powerful than context free languages, I think they can be described with context sensitive grammar.
🤓
@@antonf.9278nah, backreferences make it Turing complete. You can't produce primes in CSG.
Totally fascinating! I love regex and this is such a cool example! Thanks so much for documenting and explaining your expedition to the prime realm Matt!
I have been using regular expressions in my work very regularly for years and yet I am amazed by this one and especially by its simplicity compared to the task accomplished ! Kudos to Illya for coming up with that piece of cryptic string !
I don't understand what the "\1+?" is doing. If "\1" is the first index of all the possible matches from the expression in the parentheses, then wouldn't it just be the match "11"? So wouldn't this regex only match on multiples of 2?
@vibaj16 when this regexp matches, (...+?) captures the smallest prime divisor. For example 5 consecutives "1" if you test 385=5*7*11=77 groups of 5 consecutives "1". \1 will then also represent 5 consecutives "1" and \1+ will match the 76 remaining groups of 5 consecutives "1".
@@vibaj16 It is "\1+" without "?"
"\1" is a reference to whatever the "first set of parentheses" matches. In this case, there is only one set of parenthesis, so there is no \2 and so on.
When "(..+?)" matches "11", then "\1" is matching "11".
The "+" repeats "\1" and therefore matches "11" as often as possible.
^(..+?)\1+$
The regex takes the smallest [i.e. "?"] sequence of repeating characters [i.e. "..+"] at the beginning [i.e. "^"] of the string [together "^(..+?)"] and looks if the found beginning [in this case "11"] is repeated [i.e. "\1"] over and over again [i.e. "+"] until exactly the end of the string (i.e. "$").
If it is not, then, "11" is not the smallest sequence that can be matched by "the parenthesis" and also fulfilling the entire regex, but maybe "111" is the smallest sequence. If not, then maybe "1111" is and so on.
@@snygg1993 thanks. I think I understand now. The exact meaning of "\1" wasn't explained very well in the video, nor by the first reply to my question.
Wildcards are OutOfMemoryExceptions waiting to happen
True story! I'm a pentester, and one of the things we always look for is dangerous regex or "redos" vulnerabilities in code we're testing.
That scene in another dimension was right out of "Planet of the Prime Matts."
Uh, 314159, as in asteroid 314159 Mattparker, is prime.
What a twist at the end 🤣 I think many of us are expecting more horror episodes now!
A good way to define a regular expression is that it defines a set of strings. We normally use them to check if a string belongs to the set, but we could also use them to generate strings that belong in the set. In other words, we could use the regex pattern to generate primes instead of just checking if a number is prime.
It isn't anything to do with the Sieve of Eratosthenes. It's just brute force factorisation. A sieve is an algorithm to produce all primes. This is an algorithm to check if a number is a prime. Totally different things.
You can also use a regex to generate any/all valid strings in the language defined by that regex! I'd say this counts (pun intended) 😉
@@wyattsheffield6130this is true in this instance (not always with modern "regex"), but this grammar actually describes strings with non-prime lengths, so its about as useful at finding primes as the multiplication button on your calculator :)
@wyattsheffield6130 But it wouldn't be the Sieve of Eratosthenes, since it would be checking each number separately. The Sieve of Eratosthenes uses the previous steps to make it more efficient. You don't check for divisibility by 4 because you already removed 4 when checking divisibility by 2. And by checking every number for divisibility by each number at once, you don't have to do any division and can just do a single addition for each number. It's a specific algorithm that is intelligently designed to be efficient. It's very different to just brute force checking each number.
"it's just brute force factorisation" uhm, yeah, that's what the sieve does...
Saying it's "nothing to do with" the sieve is going too far though. If you used this (non-regular) expression in the generative direction, to generate all the composite numbers, it would generate all the multiples of 2, then all the multiples of 3, then yes admittedly all the multiples of 4, then 5, then 6, etc. It's not the sieve proper but anyone can see the resemblance.
REGEX for Halloween video. Yeah that tracks
13:57 no, the capture groups ARE zero-indexed. The \0 capture group is the whole regex pattern itself. You can't use the \0 capture group within the regex itself, but you can use it in re.sub(...) and re.findall(...).group(0).
No. The whole match is not a capture group. You can observe it by doing ‘re.search('bar', 'foobarbaz').groups()` which returns an empty tuple because there are no capture groups. \0 is the syntax to refer to the whole match.
where `n` is non-zero digit is a syntax to refer to 1-indexed capture group.
we have a saying in programming.
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.