14
\$\begingroup\$

From my CMC.

Given a regex and a non-empty printable ASCII text, return one bit per character in the text, indicating the positions of beginnings of non-overlapping matches, and also the positions of beginnings of sequences that are not part of any non-overlapping matches.

You can:

  • take the regex as a regex object, string or any other way that is reasonable or allowed by default rules
  • take the text as a string object, character list, or any other way that is reasonable or allowed by default rules
  • return the bits as an array, integer, or any other way that is reasonable or allowed by default rules

You may use any flavour, library, or implementation for regexes, as long as you support:

  • any-character wildcards, e.g. .
  • positive and negative character classes, e.g. [ab] and [^ab]
  • repetitions, e.g. a? and a+ and a* and/or the general a{m,n} form
  • capturing groups, e.g. (ab)
  • alternatives, e.g. a|b

Examples

[0123456789]+ or [0123456789]{1,}
Hello4the42
10000110010

(aa)+ or (aa){1,}
aaaaaaa
1000001

aaa
baaaab
110010

aaa|b
baaaab
110011

aab? or aab{0,1}
baaaab
110100

x.*z or x.{0,}z
abcdef
100000

 (you can take this as (?:) if necessary)
Hello
11111

[^aeiou]+ or [^aeiou]{1,}
Hello, world!
1110110011000

aaa
aaaaaaa
1001001

10101
101010101
100001000

\$\endgroup\$
13
  • \$\begingroup\$ I think the last testcase is supposed to be [^aeiou]+, otherwise the output would be all 1's. And for the aab? case I get b<aa><aab> -> 1 1 0 1 0 0. \$\endgroup\$
    – ovs
    Nov 22 at 11:19
  • \$\begingroup\$ @ovs Thanks. So much for doing them by hand. \$\endgroup\$
    – Adám
    Nov 22 at 11:21
  • \$\begingroup\$ What happens in situations where there is more-than-one way to assign non-overlapping matches? Such as aaa inside aaaaaaa (possible outputs: 1001001 (back-to-back aaa matches, followed by a single a), 1001100 (aaa,a,aaa) or 1100100 (a,aaa,aaa)... \$\endgroup\$ Nov 22 at 11:36
  • \$\begingroup\$ @DominicvanEssen Regexes begin as early as possible and are greedy by default. I've added a test case to the effect. \$\endgroup\$
    – Adám
    Nov 22 at 11:38
  • 1
    \$\begingroup\$ @pxeger Right, you really do have to support. (Left over from when moving the list of required regex features into its own list.) \$\endgroup\$
    – Adám
    Nov 22 at 12:14
4
\$\begingroup\$

APL (Dyalog Unicode), 23 bytes

Assumes an index origin of 0.

{(⍳≢⍵)∊0,∊+\¨⍺⎕S 0 1⊢⍵}

Try it online!

⍺⎕S 0 1⊢⍵: Search for matches of the regex in the string . For each each match return the number of characters before the match (0) and the length of the match (1).
+\¨: For each match, get the cumulative sums. This gives the 0-based starting index of the match and the first index after the match. : Flatten into a single list of indices.
0,: Prepend a zero in case there was no match at the beginning.
(⍳≢⍵)∊: For each index of the string , is it an element of this list?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice! Btw, Dyalog APL uses PCRE which handles the empty regex just fine. \$\endgroup\$
    – Adám
    Nov 22 at 11:29
4
\$\begingroup\$

Retina, 42 bytes

0G`
\(
(?:
~)`^.*
0A`¶S`($&)
.
0
m`^.
1
¶

Try it online! Link includes test suite which doesn't support empty regex, so () is used instead. Explanation:

0G`

Delete the ASCII text.

\(
(?:

Convert capturing groups into non-capturing groups.

^.*
0A`¶S`($&)

Wrap the regex in a capturing group and prefix it with commands that delete the regex from the input and split the ASCII text on the regex.

~)`

Evaluate those commands on the original input.

.
0

Change all characters to 0s.

m`^.
1

Change all characters at the beginning of lines to 1s.

Join everything back together.

\$\endgroup\$
1
  • \$\begingroup\$ All regex to deal with regex. Gotta love it! \$\endgroup\$
    – Adám
    Nov 22 at 12:10
4
\$\begingroup\$

Python 3.8 (pre-release), 86, 79 bytes

lambda r,s:(c:=1<<len(s)-1)|sum({c>>j for i in r.finditer(s)for j in i.span()})

Try it online!

Old version

Takes a re object and a string and returns a string of 1s and 0s an integer that encodes the mask in binary.

Output is created by bitwise arithmetic. As we know the leftmost bit is set there are no worries about leading zeros. Ideally, we would like to or-reduce the set bits. As there is no short way to do this (is there?) we instead take the sum after eliminating any duplicates.

\$\endgroup\$
3
\$\begingroup\$

R, 77 bytes

function(p,t,m=el(gregexpr(p,t))){T[c(m,m+attr(m,"m"))[m>0]]=1;T[1:nchar(t)]}

Try it online!

Outputs 1 for starts of matches/non-matches, NA otherwise.


R, 84 86 84 bytes

Edit: thanks to pajonk for spotting a bug when there is no match

function(p,t,l=0:nchar(t),m=el(gregexpr(p,t)))`[<-`(!l,c(m,m+attr(m,"m"))[m>0],1)[l]

Try it online!

Outputs 1/0.

function(p,t,           # p = pattern, t = text,
 m=el(gregexpr(p,t)))   # m = positions of matches,
                        # with attribute "match.length" = lengths of matches
                        # (can be abbreviated as "m");
 head(...,-1)           # Return all except the last element of...                       
 `[<-`(                 # assigning the elements of...
 !0:nchar(t)            # ...a vector of 1 followed by nchar(t) zeros...
 c(m,                   # at the positions of the matches, 
     m+attr(m,"m")      # and the positions immediately after the matches,
  )[m>0]                # (but ignoring the value of -1 assigned to 'no match')...
 ,1)                    # ...to 1
\$\endgroup\$
1
  • 1
    \$\begingroup\$ @pajonk - Thanks for catching that. I think it's fixed now... \$\endgroup\$ Nov 22 at 15:17
3
\$\begingroup\$

Ruby, 81 bytes

f=->r,s,a=0{s>''?[(a=((s=~r)!=0?a-1:[a-1,s[r].size].max))>0,*f[r,s[1..-1],a]]:[]}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python, 87 bytes

def f(s,p):
 r=[i:=0]
 for m in p.finditer(s):r+=m.span()
 for x in s:yield i in r;i+=1

Attempt This Online!

Takes a string and an re.Pattern object, and returns a generator of booleans.

I'm really not happy with the last line; it seems like there must be a better way of doing it.


Explanation:

  • i:=0: using the observation that the first bit is always set, we can abuse the initial definition of r to initialise i to 0 at the same time
  • for m in p.finditer(s):: for every (non-overlapping) match of p inside s:
    • r+=m.span(): append the range of the match object - inclusive start, exclusive end. This is convenient, because we need to include a 1 for the start of every match, and after the end of every match.
      If two matches are consecutive, this is not a problem, because it doesn't matter if the same value is added to the list twice (once for the end of the first, and once for the start of the second).
  • Finally, output a generator of booleans for each index in the string's range according to whether that index is in the list r.

If a match occurs at the end of the string, an out-of-bounds index will be appended to r, but this also doesn't matter, because we only check indeces in s's range.

\$\endgroup\$
2
\$\begingroup\$

Burlesque, 43 bytes

s1{g1~&l_j}{g1~=}w!ClFL`Fz?{L['0j.*'10sa}\m

Try it online!

s1       # Set 1 to be the RegEx
{g1      # Get the RegEx
 ~&      # Partition based on the RegEx (PreMatch, Match, PostMatch)
 l_j     # Get PostMatch out of block and on top of the stack
}
{
 g1~=    # PostMatch still contains match to RegEx
}w!      # While
ClFL     # Collect results and flatten
`Fz?     # Remove empty string(s)
{
 L[      # Length
 '0j.*   # "0"*Len
 '1 0 sa # Set first char to 1
}\m      # Map and concatenate
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 84 bytes

s=>r=>[...s].map((_,i)=>s.replace(r,(...p)=>i=(v=p.at(-2)-i)&&v+p[0].length&&i)&&!i)

Try it online!

  • Array#at is ES2022.

Could be 73 bytes if regex passed to this function use (?:aa) instead of (aa).


JavaScript (Node.js) + core-js, 78 bytes

s=>r=>[...s].map((_,i)=>s.matchAll(`(${r})|((?!${r}).)+`).some(v=>v.index==i))

\$\endgroup\$
1
\$\begingroup\$

Julia 1.3, 73 bytes

a\b=(r=[0;b...].==0;findall(a,b).|>m->r[m.start]=r[m.stop+1]=1;pop!(r);r)

Try it online!

  • findall(::Regex,::String) was added in Julia 1.3 and returns a vector of ranges for each match.
  • pop!(r);r is one byte shorter than r[1:end-1]
  • expects a as a Regex object and b a String
  • output is a vector of Bools
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.