how to regex

DLosc

Jun 21, 2021 18:20

CMC: Given a simple regex (only alphanumeric characters and *, +, and ? repetition operators), output all strings that it fully matches.

2

StackMeter

@DLosc what about [ab]*a

how does one eval that

DLosc

You don't have to handle character classes for this CMC.

Though you can if you want to. :)

hyper-neutrino

@cairdcoinheringaahing is 1 composite or neither, or can we decide

@DLosc do we have to handle *? and +? non-greedy, or will the input match /([^*+?][*+?]?)*/

Adám

@DLosc There are infinitely many if there are any * or +.

DLosc

@hyper-neutrino Input will match ^([A-Za-z0-9][*+?]?)*$

caird coinheringaahing

Jun 21, 2021 18:34

@hyper-neutrino 1 is neither, and so will never be an input or output

Adám

E.g. a+ will match a and aa and aaa etc.

StackMeter

@hyper-neutrino wait what do *, + and ? do

ok, that explains + - one or more

DLosc

@Adám Correct, which means the challenge is to make sure that any matching string will be output eventually (assuming infinite time/memory/etc).

Adám

Oh.

DLosc

@StackMeter * means 0 or more repetitions, + means 1 or more repetitions, ? means 0 or 1 repetitions

StackMeter

Jun 21, 2021 18:37

so a*b+c? matches any string with 0 or more a's, then 1 or more b's then 0 or 1 c's

so things like aaaaaaabbbbbbc, bbbbbbbbbbbbbbc, aaaaaaaaaaabc are included

DLosc

Correct, and also aabb (0 c's).

StackMeter

that is true

I have no idea how you would do this if more than one +/* is involved

that's double infinite recursive

DLosc

^__^

StackMeter

one does not simply infinitely recurse more than once

you'd need to know in advance the number of pluses

DLosc

Hint

Adám

Jun 21, 2021 18:44

I think I have an algorithm for it.

hyper-neutrino

@cairdcoinheringaahing yuno, 12 bytes: ιPΞ┥i+1ɨ┝ιP‖ (Try it online!)

ngn

@DLosc why? a++ is the same as a+

hyper-neutrino

i will add built-ins to shorten these down but basically it creates an infinite list of primes, finds the index, adds one, and indexes into the infinite list of non-primes (which includes 1, hence the increment)

Adám

Basically, start with the shortest string (i.e. set all ? to 0) add a "binary counter" for all repetitions +0/1. Then do the same with +0/1/2, then +0/1/2/3 etc.

StackMeter

@DLosc That somewhat makes sense.

@Adám That works for 2, but what about 3 or higher

hyper-neutrino

Jun 21, 2021 18:47

> etc.

StackMeter

@hyper-neutrino oh that's the etc.

Adám

@StackMeter If you don't want duplicates then remember all you've outputted so far. (inf. memory)

ngn

generate all possible strings and filter the ones that match - done :)

Adám

Right, that's another one. D'oh.

StackMeter

@ngn how do you know that that will hit every single possible string

Adám

Jun 21, 2021 18:49

@StackMeter C'mon, that's trivial.

hyper-neutrino

i'll be impressed if you manage to generate all strings and not generate all strings

StackMeter

ok I'll give you that one @ngn

Adám

Heh, ngn's method doesn't work if the challenge has an arbitrary regex.

ngn

@StackMeter well, start with the empty string, then generate all strings of length 1, then 2, etc. - that will go through all of them

@Adám why?

Adám

@ngn Because some regexes never terminate.

DLosc

Jun 21, 2021 18:51

@ngn Yeah, that's the boring way :)

StackMeter

we're looking for the slick way

ngn

@Adám all regular automata terminate on finite inputs

Adám

Sure, but today's regexes are not regular.

ngn

@Adám the ones from the cmc are

StackMeter

and honestly, I think a Cantor Pairing function would be shorter (it's 6 bytes in Jelly)

Adám

Jun 21, 2021 18:53

> arbitrary

ngn

@Adám you said "arbitrary regex". regexes are actually regexes and have always been. pcre-s ("modern regexes") are not regexes.

hyper-neutrino

this should theoretically work but it requires infinite steps to start generating items with an f in it (for the test data I have)

ngn

@StackMeter the slick way would be to build an automaton and breadth-first search it

hyper-neutrino

to make the output more interesting I could cartesian product a bunch of infinite sequences together but idk if itertools handles that

Adám

> This is the Apocalypse on Pattern Matching, generally having to do with what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood). (source)

ngn

Jun 21, 2021 18:58

@Adám well, exactly

DLosc

@hyper-neutrino That doesn't theoretically work, precisely because it requires infinite steps before generating some items.

Adám

@ngn I deliberately used the term "regex" and not "regular expression" ;-)

DLosc

@hyper-neutrino I'd be (pleasantly!) surprised if itertools handled cartesian products of infinite sequences

If so, that's the right tool for the job.

ngn

@Adám i'm taking that as a joke

StackMeter

@hyper-neutrino if it takes infinite steps to output abcdefgh, I don't think it counts

hyper-neutrino

Jun 21, 2021 19:01

well idk how that whole infinite automata / turing machine / whatever / the thing WW was talking about a few weeks back theoretically works

is outputting duplicates permitted

actually a simple set() makes it easy to avoid that

StackMeter

yes, if it outputs every possible string in guaranteed finite time

DLosc

@hyper-neutrino Sure, duplicates are fine.

hyper-neutrino

ungolfed but working, at least i think

pxeger

@ngn indeed, it's only a fraction of the knapsack problem! :þ

ngn

the handbag problem :)

DLosc

Jun 21, 2021 19:12

@hyper-neutrino I think that's working, yes!

StackMeter

@pxeger ok what's the knapsack problem

pxeger

@StackMeter lmgtfy.app/?q=knapsack+problem

rak1507

@ngn on the other hand, it's always extremely entertaining :)

StackMeter

@pxeger thanks

hyper-neutrino

golfed to 309

just some trivial python golfs

StackMeter

Jun 21, 2021 19:18

not bad

@DLosc I'd recommend sandboxing that and seeing if it's good for the main site

rak1507

most would just do ngn's method of iterating through every string, which is boring

StackMeter

@rak1507 subject to the constraints every string possible is generated in finite time

ngn

@rak1507 what if we iterate through every string and filter the ones that describe apl flaws? would it be entertaining or boring? :P

rak1507

@ngn lol

can you make a regex to match apl flaws?

ngn

@rak1507 theoretically, maybe

hyper-neutrino

Jun 21, 2021 19:23

198 with infinite generation

183

StackMeter

@hyper-neutrino what are the asterisks on the ranges

hyper-neutrino

list splat syntax

[*a] = [a[0], a[1], ..., a[-1]]

StackMeter

oh ok

DLosc

@StackMeter Yeah, what @rak1507 said. :( Plus, if you do it "properly," it's essentially the same challenge as this.

StackMeter

sorry just spent a minute looking through the first 8 pages of the "ok" log and seeing myself on every page multiple times sent my sides into orbit - they'll be coming down in around 2 minutes

EliteDaMyth

Jun 21, 2021 19:29

@DLosc x nickdrane.com/build-your-own-regex somewhat related

Peilonrayz

@hyper-neutrino Do the upper have to come first? You can get 174 if not

hyper-neutrino

@Peilonrayz ah, good idea to import string :p forgot about that thanks

order shouldn't matter as long as all get outputted, so this is perfectly fine

DLosc

[goes to post TIO link to ungolfed reference solution]
"This message is too long."
>:^/

hyper-neutrino

you can multiline to make it work

but then users will need to click (see full text) for the link to work

Yorch

is there a reason why the try it online text is always the same?

is there like something that generates it automatically?

Adám

Jun 21, 2021 19:37

@Yorch What text?

Yorch

gyazo.com/9272c2b98d25a397473d97818a6bff4e

Try it online!

hyper-neutrino

yeah, Try It Online has formatting options (the link button at the top) and one of those options is SE-submission-style

Adám

@Yorch See imgur.com/a/FjIpUzN

hyper-neutrino

you can also use <esc>, <s>, <g> (not a combination)

Yorch

Oh I hadn't even tried to create the hyperlink yet

no wonder I din't find it

thanks everyone !

DLosc

Jun 21, 2021 19:41

@hyper-neutrino Or Github. :P Ungolfed reference solution

hyper-neutrino

works as well :P

ngn

my eyes hurt from ungolfed code

DLosc

@ngn I made sure to use long_explanatory_variable_names just for you ;)

StackMeter

@DLosc this is what Code Review looks like

rak1507

@ngn please post ngn/k on code review

it would be hilarious

pxeger

Jun 21, 2021 19:43

pls no

ngn

@rak1507 they gonna eat me alive :)

StackMeter

let's not

that would be sus

DLosc

@StackMeter Nah, they'd tell me I need better names for my functions, docstrings, put the test code in its own module, etc. :P

Yorch

oh, it doesn't highlight syntax on math stack exchange :/

Peilonrayz

@hyper-neutrino I'm so not used to golfing ofc print(*()) wouldn't work with count... We can -1, to 173, by using count. I'm going to go do some 'proper programming' before I join the dark side ;)

The Nineteenth Byte

Participants