Mathematical Regexes

12:56 AM

That’s very true

3:21 PM

I made an ECMA regex to match ^[,x]+$ where no number appears exactly once

Completely ungolfed right now, and also bugs on zero, but it still means this problem isn’t enough to prove ECMA+(?*) is more powerful than plain ECMA

Deadcode

6:50 PM

@Grimy Oh yes, I see what you mean about zero: ^(?!(?=.*?(\bx*\b)(?!.*\b\1\b))(?!.*\b\1\b.*\b\1\b))

The version for matching strings with no unique characters: ^(?!(?=.*?(.)(?!.*\1))(?!.*\1.*\1))

And for returning the unique character as a match with ECMA+\K: ^(?=.*?(.)(?!.*\1))(?!.*\1.*\1).*\K\1

So, do you think A well linked challenge is possible in plain ECMA?

(Ignoring the restricted-source)

Deadcode

7:10 PM

@Grimy Handling zero: ^(?!(?=.*?(^|,)(x*)(,|$)(?!.*(^|,)\2(,|$)))(?!.*(^|,)\2(,|$).*(^|,)\2(,|$)))

Deadcode

7:27 PM

Oh, never mind, none of those solutions are valid

@Grimy Please share your solution.

It's not possible in PCRE either, BTW.

But even more impossible in ECMA, because NEO+ prevents using that quantification trick.

Grimy

7:42 PM

What’s not possible in PCRE?

^(?!(x+)(?=(x.*?,\1\b))(?!\2.*,\1\b))(?=(x+)\b.*,\3\b)((?=((x+),.*?(?=\6x)|.*))\5(?!(\6x+)(?=(x.*?,\7\b))(?!\8.*,\7\b))(?=(x+)\b.*,\9\b|$))*$

I tested it on several thousand randomly generated lists of integers, didn’t get any false positives or negatives

Grimy

7:56 PM

(And matching strings with no unique characters can be done with pure regular expressions, don’t even need lookahead or capture groups)

Deadcode

8:36 PM

@Grimy I mean without having the regex grow in size with the number of characters it has to handle.

Just at a glance I would suspect your regex only reduces the probability of failing to the point that random sequences wouldn't trigger a false result

@Grimy Do you have a commented version of this?

Grimy

^

# no number < first number occurs exactly once
(?! (x+) (?= (x .*? ,\1\b) ) (?! \2 .* ,\1\b ) )

# first number doesn’t occur exactly once
(?= (x+) \b .* ,\3\b)

# start main loop
(
# Move to the first number > the current one
(?= ((x+), .*? (?=\6x) | .* ) ) \5

# no number between \6 and current number occurs exactly once
(?! (\6 x+) (?= (x .*? ,\7\b) ) (?! \8 .* ,\7\b ) )

# current number doesn’t occur exactly once
(?= (x+) \b .* ,\9\b | $)
)* $

i’m pretty sure the algorithm is sound

Deadcode

Can it be ported to characters instead of delimited unary numbers?

Grimy

@Deadcode

No, it can’t

I relies on iterating over integers

But characters (or any other finite set) can be handled exhaustively

(though, yes, the regex grows proportionally with the size of the set, or exponentially when not using lookahead)

Deadcode

Okay, so it's still impossible to match strings consisting of delimited strings of arbitrary characters (excluding the delimiter character) in which no string occurs only once.

Grimy

Yep, I guess that’s true

Deadcode

8:50 PM

Your algorithm isn't just for sorted lists, is it?

Grimy

That’s an infinite set, and ECMA doesn’t have the tools to iterate over it, I think

No, it works for arbitrary lists

The problem is trivial on sorted lists x)

Arbitrary strings is still possible with PCRE, though

Deadcode

How?

Grimy

Well with recursion and forward-references you can match “arbitrary string of length ≤ the length of a capture group”

And then the rest of my algorithm works the same as with integers

Deadcode

@Grimy Okay, how about a version just for single characters that doesn't exhaustively enumerate the character set?

Grimy

Seems obviously impossible, but I’d love to be proven wrong

Deadcode

9:01 PM

So your version for strings would have to enumerate the character set?

Grimy

Nah

Deadcode

What?

How can you have something that works for strings but not single characters?

Strings can be just single characters

Grimy

I meant impossible in ECMA

Deadcode

I mean in PCRE

How would you match strings with no unique characters in PCRE without enumerating the character set?

Grimy

Gimme a moment to code it

Grimy

9:18 PM

^((.)(?=.*\2)((?1)|\2)*)$

Deadcode

Very nicely done with the unary delimited numbers... I see how it works. It relies on the fact that you can compare the numbers, less than, greater than... which can't be done for characters.

Grimy

wait no that doesn’t work

hmm i might’ve been wrong about matching strings with no repeated characters in PCRE

Deadcode

Ahh.

Grimy

which would also mean that matching lists of strings with no repeated strings would require enumerating the character set

Deadcode

Yes, I can see how that would work.

Grimy

9:23 PM

Too bad [\1] doesn’t work, that would make the thing trivial =p

Deadcode

What's [\1]?

Oh

Treat \1 as a character class

Grimy

yep

Deadcode

Well it wouldn't work with that alone, right? You'd need [\1-\2] or [-\1] or [\1-], wouldn't you?

Grimy

I was thinking [^\1] to match any character not in \1

Deadcode

You already have something similar

(?!\1). - works only for single-character backrefs though

Grimy

9:30 PM

yeah it already exists for single character

but having it for multiple-characters would give an easy solution

^(?!(.*)([^\1])[^\2]*$) or similar

[^\2] can be eliminated from that, but [^\1] can’t

Deadcode

Ahh, nice.

I think that might be doable with forward references.

Eliminating the [^\1], I mean.

Grimy

I thought so too, but couldn’t figure it out

Admittedly I only spent ~10mn on it

Deadcode

10:02 PM

Okay, so can you think of anything that has no apparent ECMA solution for domain ^[x,]*$ but does have an ECMA+(?*) solution?

Grimy

No 0-terminated sub-list of integers occurs exactly once

Well, a 0-terminated sublist of integers is equivalent to a ,,-delimited arbitrary string, so that problem is equivalent to the string version (if you’re allowed to enumerate the character set)

Deadcode

But this is one that's possible in PCRE but not ECMA even with enumerating the character set, right?

Can you think of a problem in domain ^(x*(,|$)){N}$ (where N is a constant) that has no apparently ECMA solution but does have an ECMA+(?*) solution?

Oops, messed up that domain. Meant ^(x*(,\b|$)){N}$ or ^(x*,){N-1}x*$

Grimy

10:31 PM

Sure, 1-terminated sublists instead of 0-terminated

Deadcode

But you can just enumerate all sublist lengths and positions

Grimy

Oh wait right

That’s a pretty small domain, ℕ^N is very similar to ℕ

I can’t think of such a problem, no

Deadcode

10:46 PM

Got any ideas on whether it's possible to make an ECMA regex that divides the input unary number by a transcendental constant number >1 (or multiplies by one <1) and returns the rounded result? (Or matches correct statements of such, with the input being two delimited unary numbers.)

Grimy

11:05 PM

Might be possible for some transcendental numbers with special properties, but definitely impossible in the general case

Did you ever finish the “divide by √2” regex? that sounds considerably easier than any transcendental number.

Deadcode

By "finish" do you mean port to plain ECMA? Nope, it still uses one (?*).

I'm pretty sure it's possible for all algebraic numbers.

Grimy

11:58 PM

Yep, that’s what I meant. And yeah, given √2 is possible, I’d expect all algebraic numbers to be possible.

Transcript for

Mathematical Regexes