Hi :) Probably could've thought of a cooler name for this room with more time, but this should do, right? :)

So I noticed you posted a PCRE solution to the divisibility-by-7 problem a couple years ago. I had actually viewed that before.

What got you interested in (ab)using regex this way? :)

And how much of it did you do before discovering my work?

BTW, it took me several hours to understand your binary-heavy regex!

I did quite a bit of regex abuse a while ago, but only with Perl regex

I haven't spent the time for your log2 regex yet, and that's just the 66 char version

Mostly because I really like Perl as a golfing language

I tried for a while, but realized it'd take a lot more time

Ahhh.

I didn’t think you could do much with the ECMA restrictions, but seeing your abundant regex was inspiring

:D

Yeah, I think before teukon and I got working on it, nobody in the world had done any more than just Primes and Powers of 2

There are some things I still think are impossible, but perhaps some of them aren't...

Do you think there's any possibility of proving at least one unary function impossible?

Outside of the trivially impossible ones like f(x) = x+1, you mean?

Of course.

Well probably

I mean, input is a nonnegative integer n, and output is 0..n or no-match.

But proving things impossible is always hard

One I’ve been considering is, given ^[x,]+$ (comma-separated list of unary numbers), return a match iff the first number is a perfect power of any other number

That’s easy enough with (?*) but maybe impossible without it

Hmmm

Shouldn't it be possible? Just try every possible base, and then check if any of the other numbers = that base.

Right, yeah, I see it

But there is a typographical problem that ECMA can't do but ECMA + (?*) can do

Oh?

Provably so?

Match a string iff no character appears more than once.

So for comma-delimited unary numbers... match if no number appears more than once.

I haven't formally proved it, but it seems pretty cut-and-dry.

^((.)(?!.*\2))+$, or am I missing something?

I think I got it backwards. Match iff no character appears only once.

Ooh, yeah, that would be harder

Yeah that would require either variable-length look behind or something else

Exactly.

But proving anything impossible with single-unary-number input would be much, much harder.

It may be that ECMA+(?*) has the same power as plain ECMA, for that domain.

Hmm actually it’s still solvable if your character set is finite

Though of course the resulting regex will be monstrous

Yes.

But not possible for delimited unary numbers.

Yep, that’s effectively an infinite set

And even more monstrous for strings if you have Unicode ;)

I plan on adding delimiter support to my engine's numerical mode.

Does it currently do any numerical optimization on things like matching valid addition / multiplication statements?

Oh, another problem I dabbled with: Find the unary "busy beaver" for each regex length in characters. But this is rather different than the Turning Machine version. In this case, the busy beaver is the string that matches exactly one unary number, and the goal is to match the largest number with that length of regex.

x xx xxx x{9} x{99}…

pastebin.com/VPGKVWZg

and then it gets hard

Oh, I explicitly prohibit {number}

because that makes it insane

Oh ok

Do you also prohibit (?=) and other structures?

No!

Because some of the latter scores look very beatable with this

It was a surprisingly long time before chinese-remainder-theorem multiplication started getting used

Yeah, I expect you can beat these...

I'd like to see that.

If I write a regex that matches the smallest counterexample to Goldbach’s conjecture, do I win?

LOL

Nothing that relies on unproven statements!

Oh I just noticed (xxxxx){xxxxx}. That’s an interesting notation.

Right, I allowed {unary number}, and only found that one place where it wins.

That's nonstandard of course, but I thought it made a decent substitute for {decimal number}.

The best I could get without {xxxx} for that length was 24.

^((x+)(?=\2$)){xxxxxxxxxxxxxxxxxxxx}x$ matches 1048576 only

which handily beats your last 10 or so scores

Ohhhh of course!

Well done. Now that of course changes everything!

yeah it’s not even close to optimal

Powers of 3 are stronger, for a start

I knew this would happen though!

It seemed suspiciously slow.

This wins at 256

length 26

The ^ and $ are implied in all patterns right?

No, because the return-match is what is important

Not the input they're matching

So the ^ can be dropped

^((x+)(?=\2$)x){xxxxxxxx}$ is bigger

just by moving that x inside the parens

matches 510 instead of 256

Oh yeah, and in theory, you only need to give it one input, an infinite string of x's, to get its return match value.

And then ^((x+)\2(?=\2$)x){xxxxxx}$ is even bigger, using powers of 3 instead of 2 (matches 1092)

I'd like to add that mode to my engine, too.

How would $ work with infinite input?

Is it actually left-infinite?

Either ^ or $ has to never match, or we run into contradictions

Yes, left-infinite. It starts checking for matches at the right end, and moves left until it finds one.

But, I'd have to make it check if it's a unique return match... probably can't make it prove that, just have to make it scan for a while to see if it gets any different answers.

So not quite the normal regex behavior, but at least it’s useful

Well, ^((x+)\2(?=\2$)x){6} would work with a right-infinite input

Oops no it starts matching non-1092 numbers at some point

How so? That matches a bunch of different numbers.

etc.

Yeah yeah my bad

Looks like a while before \2{xxxxx} becomes worth it

135 (((xxxxx)\3\3)\2\2)\1\1 still wins

Ugh right lines 14 and 15 are the same length

This breaks the linenum = length equality from that point on

Yeah, I guess I should've just deleted the 24 version

Yep, just delete that line.

How soon can we start doing tetration or something? ;)

Well, double-exponentiation would come first

Tetration would be done by repeated-log then x$, similar to how exponentiation is done by repeated division

Right.

So it would need at least 57 chars to fit a log pattern

More like 70 if we account for (){xxxxxx} and stuff

So how would double-exponentiation work?

My idea was to match a large number with an exp regex, then assert the tail is that number to a certain power

But of course it’s not that easy, because both parts need the $

Yeah, it seems you'd need log-base-N for that.

Generalized powers would be enough

You think that can be done in shorter than log-N?

Hmm powers of 2 is length 17, generalized powers is length 43, and it needs two {xxx...} constructs instead of one

Doesn’t look good

You've done a generalized-powers without using log?

I don't see how? It's basically the same thing as log...

I’m talking about yours, ^(x+)((\1(x+))(?=(\3*)\1*$)\3*(?=\4$\5))+x$

Oh right

(?=.* (big number) $)\1((\1(x+))(?=(\3*)\1*$)\3*(?=\4$\5)){xxx...}x$ should work

But seems like this doesn’t get optimized, so big number > 2 takes ages to test

Yeah, without implementing the right kind of optimization for that, we just need to calculate what it is manually and then test it by -t <specific number>

It'd be great if some kind of general optimization for Chinese Remainder Theorem could be implemented into my engine

Currently, I think at least one form of it is optimized

but there are so many possible ways it can be expressed

By the time generalized-powers comes into play, the numbers will be far bigger than 64 bits. Have to implement bignum support ;)

But that'd be useless without much better optimizations in place first.

There's a non-unary problem I found very interesting to golf. Just pushed the test mode.

Binary addition statements.

Should I say what length I got it down to?

Sure

You did binary Xor too, right?

@Grimy Yes, but that one is much easier

Okay, for 16 digit binary addition (where the 17th bit carry is discarded), 80 chars.

Standard ECMAScript.

Is it not possible in the general case?

Anyway, gotta go. See ya!

Okay! It's been fun, seeya!

Right, not possible in the general case in ECMA.

You could handle leftmost-digit carry of course

but not variable length

unless the length was confined to a range