5
\$\begingroup\$

Challenge

Given two lists of strings where each string is of length 50 and each list is also of length 50 generate the shortest regex you can that fully matches all the strings in the first list and does not match any of the strings in the second list.

Scoring

Your score will be the average length of the regexes your program outputs when applied to this file: https://pastebin.com/MvwPbH1G

In this file the lists are separated by a single newline and the pairs of lists by two newlines. Apply your program to each pair twice with once with the first list as the strings to match and once with the second list as the strings to match.

Rules

  • We will use Javascript flavor regexes for simplicity.
\$\endgroup\$
4
  • \$\begingroup\$ When you say fully match, does that mean that the regex has to match the full string (assuming leading ^ and trailing $ for engines that require it)? \$\endgroup\$
    – Neil
    Jul 1 at 23:12
  • \$\begingroup\$ @Neil yes that is what I meant \$\endgroup\$
    – user197974
    Jul 2 at 0:19
  • \$\begingroup\$ Python has a number of APIs for pattern matching, re.fullmatch, re.match and re.search. Which API's behaviour do you want us to support? \$\endgroup\$
    – Neil
    Jul 2 at 9:38
  • 3
    \$\begingroup\$ It would be nice if the users that voted to close this question could explain what is unclear in their minds. So the OP can address it. \$\endgroup\$
    – Grain Ghost
    Jul 2 at 20:20
3
\$\begingroup\$

Score: 212.84

import re

def ngraphs(ss):
	n = [set() for _ in ss[0]]
	for s in ss:
		for i in range(1, len(s) + 1):
			for j in range(len(s) - i + 1):
				n[i - 1].add(s[j:j + i])
	return n

while True:
	y = [input() for _ in " " * 50]
	input()
	n = [input() for _ in " " * 50]
	input()
	input()
	yngraphs = sum([sorted(a - b) for a, b in zip(ngraphs(y), ngraphs(n))], [])
	regex = yngraphs.pop(0)
	while not all(re.search(regex, a) for a in y):
		regex += "|" + yngraphs.pop(0)
	print("^.*(" + regex + ").*$")
	print()

Try it online!

A pretty uninteresting brute-force solution. Only uses alphanumeric characters and |, so a) flavor doesn't really matter b) I expect this to be easily beaten by a smarter brute-force solution at least.

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

Python 3, score 122.39

count = 0
total = 0
while True:
    y = [input() for _ in range(50)]
    input()
    n = [input() for _ in range(50)]
    input()
    input()
    s = set()
    for x in y:
        i = 1
        while any(a[:i] == x[:i] for a in n):
            i += 1
        s.add(x[:i])
    regex = "^(" + "|".join(s) + ").*"
    count += 1
    total += len(regex)
    print(regex)
    print(total / count)

Try it online! Explanation: Simply takes the set of minimal prefixes of the strings in the first list that aren't prefixes of any strings of the second list and uses that to build a regex.

\$\endgroup\$
5
  • \$\begingroup\$ This is a pretty nice answer, but I think it misses a ^ at the start of the regexes generated: from the question "does not match any of the strings in the second list" see in regex101. With just a ^ it works: see in regex101 and it's just 1 byte more \$\endgroup\$
    – Kaddath
    Jul 2 at 7:38
  • \$\begingroup\$ @Kaddath My regex was designed to work with Python's re.fullmatch. If I can use re.match then I can save two bytes. If I'm forced to use re.search then that will as you say cost me a byte. I'll ask the OP for clarification. \$\endgroup\$
    – Neil
    Jul 2 at 9:37
  • \$\begingroup\$ yes maybe that's one of the reason the post is closed, it could be clearer.. however I don't understand why the other answer got upvoted and not this one, as the other doesn't match the full string but just part of it.. \$\endgroup\$
    – Kaddath
    Jul 2 at 9:47
  • \$\begingroup\$ @Kaddath Perhaps people didn't read the spec clearly enough - I only noticed my mistake too after reading your comment. Anyway, I've fixed my answer for a slight score increase by just surrounding my partial match with ^.*(...).*$ - thanks for pointing that out. \$\endgroup\$
    – hyper-neutrino
    Jul 2 at 20:32
  • 1
    \$\begingroup\$ @hyper-neutrino You don't need the trailing $ though, since the .* is greedy. \$\endgroup\$
    – Neil
    Jul 2 at 20:50

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