Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regular Expression That Checks If A Number Is Prime

iluxonchik.github.io

Post reply on HN
Print view View original

71–80 of 117 posts

Re: Regular Expression That Checks If A Number Is Prime

#71

Post by posterboy »

delsarto wrote: post #6

tl;dr if you know a little regex - convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111) - handle 0 / 1 separately - ^(..+?)\1+$ - trick; the WHOLE thing has to match to return (^$) - first \1 match is "11", ergo string must be "11", "1111", "111111" to match - second \1 match "111", ergo string must be "111", "111111", "111111111" to match - and so on. if you find before length of string, it was no…

Is the applicant asked to explain the regex or to come up with the regex and the conversion to unary?

Re: Regular Expression That Checks If A Number Is Prime

#72

Post by YeGoblynQueenne »

Can't quite get this to work in vim [1]:

  \(^1\{-,1}$\)\|\(^\(11\+\)\1\+$\)
The two parts match what you'd expect on their own but the OR-ing screws it up: it means the whole regex matches everything.

Is this something vim gets right and every other engine wrong, the other way around, or...?

_____________

[1] I'm matching 1's rather than dots to avoid highlighting every bit of text ever anywhere all the time.

Also, that way it's so much more pleasing to the eye and easy to read, don't you think?

Re: Regular Expression That Checks If A Number Is Prime

#73

Post by [deleted] »

mmagin wrote: post #7
delsarto wrote: post #6

tl;dr if you know a little regex - convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111) - handle 0 / 1 separately - ^(..+?)\1+$ - trick; the WHOLE thing has to match to return (^$) - first \1 match is "11", ergo string must be "11", "1111", "111111" to match - second \1 match "111", ergo string must be "111", "111111", "111111111" to match - and so on. if you find before length of string, it was no…

Doesn't this have some relation to https://en.wikipedia.org/wiki/Church_encoding

[deleted]

Re: Regular Expression That Checks If A Number Is Prime

#74

Post by DasIch »

Chinjut wrote: post #45
btilly wrote: post #33

Earlier quoted context omitted.

No, it is not. You can invent a variety of notations to describe a DFA. But you can't change the formal definition of a DFA, or what kinds of things a DFA can match without making it not a DFA.

I'll say to you what I said above, but even moreso: Er... I'm not sure what you're saying here, so I'll clarify what I was saying. What I mean is, we all agree on what DFAs are, and so we all agree on what regular languages in the original, Kleene sense are. But once we start admitting non-regular languages into our notion of "regular expression" because they're "straightforwardly tacked on", it's unclear what the li…

You can actually quite easily add features to regular expressions, that are typically excluded while still being actually regular. Examples would be an `and` or a `not` operator.

Re: Regular Expression That Checks If A Number Is Prime

#75

Post by thaumasiotes »

YeGoblynQueenne wrote: post #72

Can't quite get this to work in vim [1]: \(^1\{-,1}$\)\|\(^\(11\+\)\1\+$\) The two parts match what you'd expect on their own but the OR-ing screws it up: it means the whole regex matches everything . Is this something vim gets right and every other engine wrong, the other way around, or...? _____________ [1] I'm matching 1's rather than dots to avoid highlighting every bit of text ever anywhere all the time. Also, t…

> Also, that way it's so much more pleasing to the eye and easy to read, don't you think?

No, it's harder to read. For ease of reading, you need to match something that isn't already part of the expression, like 2s or Ks.

Re: Regular Expression That Checks If A Number Is Prime

#76

Post by Chinjut »

School-Cotton wrote: post #67
jdnier wrote: post #56

Earlier quoted context omitted.

For some great exposition on what "regular" actually means, check out http://nikic.github.io/2012/06/15/The-true-power-of-regular-... "Thus the question arises: Can regular expressions match only regular grammars, or can they also match more? The answer to this is both yes and no"...

"regular" has a fairly simple mathematical definition: the set of languages that can be matched with a finite state automaton. You can think of this as the languages that can be matched with an algorithm that is bounded (i.e., O(1) ) in memory, no matter what is the string to be matched. The following pseudocode is not bounded in memory -- can you guess why? bool is_prime(Number n) { for (Number i = 2; i

The value i can take an a priori unbounded amount of memory.

It should be noted, so can the value n, but in defining regular languages in this way, we allow our O(1) memory algorithms to be fed the characters of an a priori unbounded input string one by one sequentially.

Re: Regular Expression That Checks If A Number Is Prime

#77

Post by snicky »

Is it just me or the author of this blog post has a very annoying way of writing? He keeps explaining things and then a couple of lines below he writes something like "remember the discussion above?" or "if you remember correctly ...". Hell, sure I remember, because I just read about this 10 seconds ago. Do people really have such a short attention span and can't remember what was in a previous paragraph? Repeating stuff over and over seems almost like content farming to me.

Re: Regular Expression That Checks If A Number Is Prime

#78

Post by thaumasiotes »

db48x wrote: post #39
Chinjut wrote: post #25

Earlier quoted context omitted.

Is there a standard for which additional features one can add on top of regular expressions in the original limited sense and still be considered a regex?

"regular language" is a mathematical term. You can add any features you want to your matcher, but some features allow you to match languages that are not "regular". However, most programmers are not mathematicians or computer scientists, and so are effectively using lay terminology which is similar to but not precisely the same as the mathematical terminology. Most programmers only care that their regex library allow…

> there are two standards you could follow: the precise mathematical definition of "regular", or the lay definition

Considering this writeup leads with a giant headline saying "Regular Expressions - The Theory"... I think the complaints about how it's not actually a regular expression are even more valid than usual.

Re: Regular Expression That Checks If A Number Is Prime

#79

Post by DasIch »

duaneb wrote: post #35
jnordwick wrote: post #15

Earlier quoted context omitted.

One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.

Sure, but on the pragmatic hand, "regular" isn't super useful unless you're designing a language yourself. If you're parsing something, not understanding "regular" is going to hurt a lot less than attempting to use PCRE to do something it can't.

Regular is actually incredibly useful because it allows you to confidently parse or validate (large amounts of) untrusted data without having to worry about DoS attacks.

I'd argue that this is useful, even if you use it as part of a parser that doesn't just parse regular languages, as you'll have a slightly easier time reasoning about the time and space complexity of the construction.

Re: Regular Expression That Checks If A Number Is Prime

#80

Post by thaumasiotes »

iluxonchik wrote: post #21
Chinjut wrote: post #19

Earlier quoted context omitted.

Presumably, they thought of A as in front of B in the expression "AB" rather than in the expression "BA". (Which is also how I would normally think of "in front", for what it's worth!)

Oh, that was probably it. That would be true if we were talking about FIFO queues :)

I'm another one who thinks the letter "in front" is the one that comes first. May I ask how you were thinking about the "front" and "back" of text?
Post reply on HN