Y2024 - A Regex starter challenge.

[davidktw]

PROBLEM
Given a string of alphanumeric characters [A-Z0-9] of length range [10-1000], produce a regular expression that will find the first sequence of distinct characters(substring) of length 5.
That means given the found substring ABCDE, the distinct characters are 5 while the substring ABABA, the distinct characters are 2 only since the unique characters are only A and B.
Only output if there is such a substring found.

INPUT

WZ8JL74NK2UU4A3NGW7T3PBXZCRQDI1U
V11FTVO5KBJ3XVAJQN4FY9GWX0V4DH4X
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAABCDDABCDEAAAAAA

OUTPUT

WZ8JL
1FTVO

ABCDE

Happy New Year.

 

[davidktw]

Seems to me like regex is a very difficult topic?

Spoiler: Hint

lookahead

 

[davidktw]

Well well I was thinking AOC problems are even harder.
Anyway if you are keen to try your own, don't read what is in the spoiler.

Spoiler

# VARIANT 1
(.)((?!\1).)((?!\1|\2).)((?!\1|\2|\3).)(?!\1|\2|\3|\4).

# VARIANT 2
(.)(?!\1)(.)(?!\1|\2)(.)(?!\1|\2|\3)(.)(?!\1|\2|\3|\4).

#VIM EQUIV:
# \(.\)\1\@!\(.\)\%(\1\|\2\)\@!\(.\)\%(\%(\1\|\2\)\|\3\)\@!\(.\)\%(\%(\1\|\2\)\|\%(\3\|\4\)\)\@!.

# VARIANT 1 LOOKAHEAD
#LC_ALL=C tr -dc A-Za-z0-9 </dev/urandom | head -c 100 | perl -e 'undef $/; $_=<>; print "$_\n"; print "$&($-[0],$+[0])\n" if /(.)((?!\1).)((?!\1|\2).)((?!\1|\2|\3).)((?!\1|\2|\3|\4).)/;'
# VARIANT 2 LOOKAHEAD
#LC_ALL=C tr -dc A-Za-z0-9 </dev/urandom | head -c 100 | perl -e 'undef $/; $_=<>; print "$_\n"; print "$&($-[0],$+[0])\n" if /(.)(?!\1)(.)(?!\1|\2)(.)(?!\1|\2|\3)(.)(?!\1|\2|\3|\4)(.)/;'

$c = shift(@ARGV) - 1;
while (<>) {
  chomp;
  $re = '(.)'.join('',map { '((?!'.join('|', map { "\\$_" } (1..$_)).').)' } (1..$c));
  print $_, "\n";
  print STDOUT /$re/ && $&, "\n";
}

OUTPUT:

$ ./distinct_seq.pl 5 input.txt
WZ8JL74NK2UU4A3NGW7T3PBXZCRQDI1U
WZ8JL
V11FTVO5KBJ3XVAJQN4FY9GWX0V4DH4X
1FTVO
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAAAAABCDDABCDEAAAAAA
ABCDE

VIM SOLUTION:

$ cat vimscript.txt
1G/\(.\)\1\@!\(.\)\%(\1\|\2\)\@!\(.\)\%(\%(\1\|\2\)\|\3\)\@!\(.\)\%(\%(\1\|\2\)\|\%(\3\|\4\)\)\@!./
:let a = getcurpos()
1G
:exec "%s/.*/".a[2]."/"
:wq

Why would I have this question ? The inspiration comes from


First challenge myself using Perl regex, then later come up with a VIM equivalent regex (I might be wrong, but in VIM, as I figured I cannot express (?!A|B|C), it will need to be (?!(?!A|B)|C)) that can do exactly what the VIM challenge requires.