this post was submitted on 31 Oct 2024
330 points (97.1% liked)

Programmer Humor

32472 readers
1043 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

you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 35 points 2 weeks ago* (last edited 2 weeks ago) (8 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)

[–] [email protected] 24 points 2 weeks ago (7 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.

[–] [email protected] 12 points 2 weeks ago

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

load more comments (6 replies)
load more comments (6 replies)