Generate Matching Regexes

Question

Write a program that takes two lists of strings and generates a javascript regex that fully matches all the strings in the first list and matches none of the strings in the second list.

To be specific when for all stings in the first list str.match(/[your-output]/) must produce a match for the full string and for all strings in the second list str.match(/[your-output]/) must produce no matches.

Scoring

Your score is the average length of the regexes you produce not the length of your program. Your regexes should be tested against this file: https://pastebin.com/9iNZvGJC. Take the file in blocks of 20 lines and run your program with the first ten lines to match and the second ten to not match. Average the lengths of your program's output for all of the blocks in the file. This is your score.

Rules

Do not output the / for the regex

Answer 1

JavaScript (ES7), Score: 767 / 50 = 15.34

This code is rather ugly and implements only one strategy. (I did try negative lookaheads, but it was not worth the effort and is disabled here.)

It could probably shave off a few more bytes with a higher maximum branching factor and/or a more clever pattern scoring function. For instance, /.*[LObcln]o.*/ and /.*(Y|o[otvy]).*/ are better solutions for the first 2 test cases which are currently not found.

The TIO link only includes the first 40 lines.

const MAX_PAT_LEN = 2;
const MAX_BF = 8;
const ESC = ".^$*+?()[{\\|";

let list = require("fs").readFileSync(0).toString().split("\n");
let block = [];

for(let n = 0; list[n]; n += 20) {
  block.push([list.slice(n, n + 10), list.slice(n + 10, n + 20)]);
}

let score = 0;

block.forEach(([A, B]) => {
  let res = process(A, B, false);

  console.log(res.length.toString().padStart(2) + " /" + res + "/");

  if(
    A.some(s => (s.match(RegExp(res)) || [])[0] != s) ||
    B.some(s => s.match(RegExp(res)))
  ) {
    throw "Failed";
  }

  score += res.length;
});

console.log(score);

function process(A, B, neg) {
  let chr = [...new Set([...A, ...B].join(''))]
            .map(c => ~ESC.indexOf(c) ? "\\" + c : c);
  let set = new Set;

  A.forEach(s => {
    for(let n = 1; n <= MAX_PAT_LEN; n++) {
      choose(chr, n).forEach(a => {
        let pat = a.join(''),
            regex = RegExp(pat);

        if(regex.test(s) && !B.some(s => regex.test(s))) {
          set.add(pat.toString());
        }
      });
    }
  });

  function score(A, pat) {
    return A.reduce((p, s) => p + RegExp(pat).test(s), 0);
  }

  let solution = [];

  function search(A, expr) {
    if(!A.length) {
      let c = compress(expr);

      solution.push(neg ? "^(?!.*" + c + ").*" : ".*" + c + ".*");
      return;
    }

    let patList = [...set].filter(a => score(A, a))
                  .sort((a, b) => score(A, b) - score(A, a));

    patList.slice(0, MAX_BF).forEach(pat => {
      search(A.filter(s => !RegExp(pat).test(s)), [...expr, pat]);
    });
  }

  search(A, []);

  return solution.sort((a, b) => a.length - b.length)[0];
}

function choose(list, n) {
  let sz = list.length;
  let max = sz ** n;
  let res = [];

  for(let k = 0; k < max; k++) {
    let sel = [];

    for(let i = 0; i < n; i++) {
      sel.push(list[Math.floor(k / sz ** i) % sz]);
    }
    res.push(sel);
  }
  return res;
}

function compress(list) {
  let maxW = Math.max(...list.map(s => s.length)),
      res = [];

  list.sort();

  for(let w = 1; w <= maxW; w++) {
    let subList = list.filter(s => s.length == w);

    for(let i = 0; i < w; i++) {
      let trunc = {};

      subList.forEach(s => {
        let key = s.slice(0, i) + s.slice(i + 1);
        trunc[key] = (trunc[key] || '') + s[i];
      });

      Object.keys(trunc).forEach(k => {
        let s0 = trunc[k].length + 2 + w,
            s1 = trunc[k].length * (w + 1);

        if(s0 <= s1) {
          res.push(k.slice(0, i) + '[' + trunc[k] + ']' + k.slice(i));
          list = list.filter(s =>
            s.length != w || s.slice(0, i) + s.slice(i + 1) != k
          );
        }
      });
    }
  }

  list = [...list, ...res];

  return list.length > 1 ? "(" + list.join('|') + ")" : list.join('|');
}

Try it online!

Full output

14 /.*(an|la|ts).*/
17 /.*( n|Y|o[otv]).*/
19 /.*(J|ca|go|e[dy]).*/
16 /.*(j|ns|s,|t').*/
19 /.*(ke|wh|i[,dgl]).*/
12 /.*( c|W|p).*/
16 /.*(e'|j|nn|ve).*/
18 /.*(B|T|op|r,|un).*/
12 /.*a[ btuy].*/
16 /.*('s|3|r[ i]).*/
13 /.*(H|ar|po).*/
14 /.*(I |ie|nd).*/
16 /.*(sa|[nrs]\.).*/
17 /.*(Ye|ay|it|wh).*/
13 /.*("|nt|we).*/
16 /.*( f|A|He|am).*/
17 /.*(ce|id|ma|r ).*/
16 /.*(nk|o[bfpw]).*/
13 /.*( r|T|fl).*/
14 /.*(y |[1SW]).*/
18 /.*('l|un|[btw]e).*/
14 /.*(L| [Obe]).*/
15 /.*( p|-|eb|j).*/
13 /.*(H|ma|se).*/
10 /.*[clt]e.*/
15 /.*(G|ne|ry|x).*/
16 /.*(J|S|o[dos]).*/
16 /.*(Al|W|oo|w ).*/
16 /.*(T|j|['cn]t).*/
16 /.*(s\.|r[osy]).*/
18 /.*(E|il|[Inrs]s).*/
16 /.*(S|n'|su|uc).*/
16 /.*( w|s[!emo]).*/
15 /.*(!|K|ea|rr).*/
16 /.*(D|Yo|h,|si).*/
11 /.*[dhlr]i.*/
17 /.*(ll|st| [rv]).*/
15 /.*(!|H|a[ds]).*/
16 /.*( f|F|ic|wa).*/
16 /.*(ev|[abgu]r).*/
17 /.*(ti|ul|[AFS]).*/
16 /.*(ed| [RYly]).*/
14 /.*(ea|a[ b]).*/
18 /.*(Oa|k |['be]l).*/
15 /.*(\? |ni|ot).*/
13 /.*("|al|ta).*/
11 /.*(f |pa).*/
15 /.*(L|Re|W|nk).*/
18 /.*(fl|ly|[enr]t).*/
17 /.*('t|om|[dt]e).*/