this post was submitted on 31 Oct 2024
328 points (97.7% liked)

Programmer Humor

32533 readers
473 users here now

Post funny things about programming here! (Or just rant about your favourite programming language.)

Rules:

founded 5 years ago
MODERATORS
 

^.?$|^(..+?)\1+$

Matches strings of any character repeated a non-prime number of times

https://www.youtube.com/watch?v=5vbk0TwkokM

top 50 comments
sorted by: hot top controversial new old
[–] fubo@lemmy.world 134 points 3 weeks ago* (last edited 3 weeks ago) (5 children)

The answer given in the spoiler tag is not quite correct!

Test caseAccording to the spoiler, this shouldn't match "abab", but it does.

Corrected regexThis will match what the spoiler says: ^.?$|^((.)\2+?)\1+$

Full workupAny Perl-compatible regex can be parsed into a syntax tree using the Common Lisp package CL-PPCRE. So if you already know Common Lisp, you don't need to learn regex syntax too!

So let's put the original regex into CL-PPCRE's parser. (Note, we have to add a backslash to escape the backslash in the string.) The parser will turn the regex notation into a nice pretty S-expression.

> (cl-ppcre:parse-string "^.?$|^(..+?)\\1+$")
(:ALTERNATION
 (:SEQUENCE :START-ANCHOR (:GREEDY-REPETITION 0 1 :EVERYTHING) :END-ANCHOR)
 (:SEQUENCE :START-ANCHOR
  (:REGISTER
   (:SEQUENCE :EVERYTHING (:NON-GREEDY-REPETITION 1 NIL :EVERYTHING)))
  (:GREEDY-REPETITION 1 NIL (:BACK-REFERENCE 1)) :END-ANCHOR))

At which point we can tell it's tricky because there's a capturing register using a non-greedy repetition. (That's the \1 and the +? in the original.)

The top level is an alternation (the | in the original) and the first branch is pretty simple: it's just zero or one of any character.

The second branch is the fun one. It's looking for two or more repetitions of the captured group, which is itself two or more characters. So, for instance, "aaaa", or "abcabc", or "abbaabba", but not "aaaaa" or "abba".

So strings that this matches will be of non-prime length: zero, one, or a multiple of two numbers 2 or greater.

But it is not true that it matches only "any character repeated a non-prime number of times" because it also matches composite-length sequences formed by repeating a string of different characters, like "abcabc".

If we actually want what the spoiler says — only non-prime repetitions of a single character — then we need to use a second capturing register inside the first. This gives us:

^.?$|^((.)\2+?)\1+$.

Specifically, this replaces (..+?) with ((.)\2+?). The \2 matches the character captured by (.), so the whole regex now needs to see the same character throughout.

[–] ikidd@lemmy.world 56 points 3 weeks ago (2 children)

I upvoted this because I hate it.

[–] fubo@lemmy.world 18 points 3 weeks ago* (last edited 3 weeks ago) (2 children)

Whatever you do, don't get in a time machine back to 1998 and become a Unix sysadmin.

(Though we didn't have CL-PPCRE then. It's really the best thing that ever happened to regex.)

[–] Treczoks@lemmy.world 4 points 3 weeks ago

I have to admit that using CL-PPCRE does not really help me understanding the regexp any better. But this may be because I deal with complex regexps for decades now, and I just read them.

load more comments (1 replies)
[–] MalReynolds 7 points 3 weeks ago (1 children)

I upvoted you because I consider Perl write only (used to know it, now it inspires readable code as a high priority)

[–] Treczoks@lemmy.world 11 points 3 weeks ago* (last edited 3 weeks ago) (1 children)

Let's put it this way: You can produce unreadable code in basically any language. With Perl, it is just a bit easier.

And of course if you have the discipline of a good programmer, even your casual Perl programs should be readable. That's what differenciates a good programmer from a hacker.

[–] MalReynolds 7 points 3 weeks ago

Yeah, I was younger then, perhaps less disciplined, and as always, given enough work you can decompile or regenerate anything. Still, I contend, the nature of Perl, powerful as it was, lent itself to unmaintainable messes, and I'm not talking regex's, which is why it has faded, no amount of get gud withstanding.

[–] taiyang@lemmy.world 10 points 3 weeks ago (1 children)

Thanks, I now have insight into my own personal hell for when I die.

[–] fubo@lemmy.world 12 points 3 weeks ago (1 children)

Regex is good for a few very specific things, and sysadmins used to use it for goddamn everything. If all your server logs are in lightly-structured text files on a small number of servers, being able to improvise regex is damn useful for tracking down server problems. Just write a shell loop that spawns an ssh logging into each server and running grep over the log files, to look for that weird error.

These days, if you need to crunch production server logs you probably need to improvise in SQL and jq and protobufs or systemd assmonkery or something.

But if you actually need a parser, for goodness sake use a parser combinator toolkit, don't roll your own, especially not with regex. Describing your input language in plain Haskell is much nicer than kludging it.

(This is the "totally serious software engineering advice" forum, right?)

load more comments (1 replies)
[–] NateNate60@lemmy.world 5 points 3 weeks ago (3 children)
load more comments (3 replies)
[–] Morphit@feddit.uk 4 points 3 weeks ago (1 children)

“abbabba”

“abbabba” doesn't match the original regex but “abbaabba” does

load more comments (1 replies)
load more comments (1 replies)
[–] sundray@lemmus.org 53 points 3 weeks ago
[–] sbv@sh.itjust.works 43 points 3 weeks ago (2 children)
load more comments (2 replies)
[–] captain_aggravated@sh.itjust.works 41 points 3 weeks ago (1 children)

knowing Matt Parker it only matches prime numbers or multiples of e or something.

looks at <ansewer>

Yeah see?

load more comments (1 replies)
[–] balsoft@lemmy.ml 35 points 3 weeks ago* (last edited 3 weeks ago) (1 children)

So, here's my attempt

The first portion (^.?$) matches all lines of 0 or 1 characters.

The second portion (^(..+?)\1+$) is more complicated:

  1. (..+?) is a capture group that matches the first character in any line, followed by a smallest possible non-zero number of characters such that (2) still matches (note that the minimum length of this match is 2)
  2. \1+ matches as many as possible (and more than 0) repeats of the (1) group

I think what this does is match any line consisting of a single character with the length

  • divisible by some number (due to the more than 0 condition in (2), so that there have to be repeats in the string), that's not
    • 1 (due to the note in (1), so that the repeating portion has to be at least 2 characters long), or
    • the length itself (due to the more than 0 condition in the (2), so that there is at least one repetition)

Therefore, combined with the first portion, it matches all lines of the same character whose lengths are composite (non-prime) numbers? (it will also match any line of length 1, and all lines consisting of the same string repeated more than one time)

[–] CanadaPlus@lemmy.sdf.org 24 points 3 weeks ago (6 children)

So this is a definite example of "regex" that's not regular, then. I really don't think there's any finite state machine that can track every possible number of string repeats separately.

[–] NateNate60@lemmy.world 20 points 3 weeks ago (1 children)

You got downvoted here but you're absolutely right. It's easy to prove that the set of strings with prime length is not a regular language using the pumping lemma for regular languages. And in typical StackExchange fashion, someone's already done it.

Here's their proof.

Claim 1: The language consisting of the character 1 repeated a prime number of times is not regular.

A further argument to justify your claim—

Claim 2: If the language described in Claim 1 is not regular, then the language consisting of the character 1 repeated a composite number of times is not regular.

Proof: Suppose the language described in Claim 2 is regular if the language described in Claim 1 is not. Then there must exist a finite-state automaton A that recognises it. If we create a new finite-state automaton B which (1) checks whether the string has length 1 and rejects it, and (2) then passes the string to automaton A and rejects when automaton A accepts and accepts when automaton A rejects, then we can see that automaton B accepts the set of all strings of non-composite length that are not of length 1, i.e. the set of all strings of prime length. But since the language consisting of all strings of prime length is non-regular, there cannot exist such an automaton. Therefore, the assumption that the language described in Claim 2 being regular is false.

load more comments (1 replies)
[–] ProfessorScience@lemmy.world 12 points 3 weeks ago

Yeah backreferences in general are not "regular" in the mathematical sense.

load more comments (4 replies)
[–] RegalPotoo@lemmy.world 24 points 3 weeks ago (1 children)
[–] RegalPotoo@lemmy.world 10 points 3 weeks ago* (last edited 3 weeks ago) (2 children)

Something like

!"A line with exactly 0 or 1 characters, or a line with a sequence of 1 or 3 or more characters, repeated at least twice"!<

[–] naonintendois@programming.dev 8 points 3 weeks ago

You're misreading the ..+? part. That means 2 or more characters, non greedy.

[–] NateNate60@lemmy.world 3 points 3 weeks ago (1 children)

It's a line with a sequence of two or more characters repeated at least twice.

[–] MummifiedClient5000@feddit.dk 4 points 3 weeks ago (1 children)

Only the part after the pipe character. The pipe character works as an "or" operator. RegalPotoo is right.

[–] NateNate60@lemmy.world 3 points 3 weeks ago (1 children)

They said—

A line with exactly 0 or 1 characters, or a line with a sequence of 1 or 3 or more characters, repeated at least twice

Note—

...or a line with a sequence of 1 or 3 or more characters, repeated at least twice

It should be—

...or a line with a sequence of 2 or more characters, repeated at least twice

The regex in the post will match "abab". Their original description (line 2 of this comment) will not match "abab".

[–] MummifiedClient5000@feddit.dk 4 points 3 weeks ago

I agree, you're right about the part after the pipe and RegalPotoo's explanation was not entirely correct.

[–] muntedcrocodile@lemm.ee 17 points 3 weeks ago

Just waiting for the oppertunity to hide this in prod.

[–] ShinkanTrain@lemmy.ml 15 points 3 weeks ago

I'm going to assume the answer is a magic square attempt that just isn't very good

[–] nroth@lemmy.world 12 points 3 weeks ago (1 children)

A non prime number of times... It looks like the string of characters could repeat number of times because the whole capture group repeats. I don't see a prime constraint.

[–] Feathercrown@lemmy.world 4 points 3 weeks ago

The capture group must be the same each time it repeats, so the number of characters stays the same. So X groups of Y characters = string of length X*Y. X and Y can be anything so any string length that can be made by multiplying two numbers-- which is every non-prime string length-- is matched. 0 and 1 are handled specially at the start.

[–] fysihcyst@lemmy.ml 8 points 3 weeks ago (1 children)

This is brilliantly disgusting.

Literal interpretation of the regexThe regex matches either a line with a single character or a line with a sequence of two or more characters that's repeated two or more times. For some examples: the regex matches "a", "b", "abab", "ababab", "aaaa", and "bbbbbb", but does not match "aa", "bb", "aaa", "ab", "aba", or "ababa".
Hint for the special thing it matchesFor a line with a single character repeated n times, what does matching (or not matching) this regex say about the number n?

[–] thevoidzero@lemmy.world 4 points 3 weeks ago

You forgot empty line. Since first part is ^.?$ it's one or zero of any character.

[–] S_H_K@lemmy.dbzer0.com 4 points 3 weeks ago (2 children)

No cookie for me I just tried it in Notepad++ and VS code and it matches lines of one characer (first group I think) or the starting of a line that is an at least 2 characters string repeated twice (second group it seems)
so the second group matches abab
abcabc abcdeabce abcdefabcdef

Nothing about prime numbers really only first repetition gets a match. Very interesting Honestly I used regex from years and never had to retort to something like this ever. I can only imagine it useful to check for a password complexity to not be repeated strings like I do for sites that I just want in and use a yopmail.com mail to register a fake user.

load more comments (2 replies)
[–] AVincentInSpace@pawb.social 4 points 2 weeks ago

...either an empty string, a single character, or the same sequence of characters repeated more than once?

[–] PeriodicallyPedantic@lemmy.ca 3 points 3 weeks ago (2 children)

Empty input Or input of exactly 1 character Or input of at least 2 characters, followed by at least 1 something (idk what \1 matches)

Did I get it (almost)?

load more comments (2 replies)
[–] RiQuY@lemm.ee 3 points 3 weeks ago

Looks like APL to me.

[–] NigelFrobisher@aussie.zone 3 points 3 weeks ago

It matches “yo momma”.

[–] Feathercrown@lemmy.world 3 points 3 weeks ago (1 children)

Is there a reason to use (..+?) instead of (.+) ?

[–] explore_broaden@midwest.social 5 points 3 weeks ago (1 children)

Yes, the first one matches only 2 more characters while the second matches 1 or more. Also the +? is a lazy quantifier so it will consume as little as possible.

[–] Feathercrown@lemmy.world 3 points 3 weeks ago (2 children)

Ah, didn't know +? was lazy, thanks

load more comments (2 replies)
[–] bitjunkie@lemmy.world 3 points 3 weeks ago

For a second I thought I was still in the thread about monkeys face-rolling typewriters until the heat death of the universe not eventually producing Hamlet

load more comments
view more: next ›