/*
Specific conditions:

- input: `oldString` and `newString` (e.g. `'old same'` and `'same new'`)
- output format: `'(old )same[ new]'`
- return diff of min length, not counting `()[]`
- return diff which is min among all diff variants by lexicographical order, with one remark: consider `\w` < `()` < `[]`

Taken from CodeFights: Dropbox bot challange.
*/

function displayDiff(oldVersion, newVersion) {
  let lcsMatrix = buildLcsMatrix(oldVersion, newVersion);
  log(lcsMatrix);
  let diffs = buildDiffs(lcsMatrix, oldVersion, newVersion);
  let minDiff = null;

  for (let diff of diffs) {
    if (minDiff === null || compare(diff, minDiff) === -1) {
      minDiff = diff;
    }
  }

  return minDiff;
}

function buildLcsMatrix(oldVersion, newVersion) {
  let lcsMatrix = new Array(newVersion.length + 1).fill().map(
    () => new Array(oldVersion.length + 1).fill(0)
  );
  
  for (let row = 1; row <= newVersion.length; row++) {
    for (let col = 1; col <= oldVersion.length; col++) {
      if (oldVersion[col - 1] === newVersion[row - 1]) {
        lcsMatrix[row][col] = lcsMatrix[row - 1][col - 1] + 1;
      } else {
        lcsMatrix[row][col] = Math.max(
          lcsMatrix[row - 1][col], lcsMatrix[row][col - 1]
        );
      }
    }
  }
  
  return lcsMatrix;
}

function buildDiffs(lcsMatrix, oldVersion, newVersion, row = newVersion.length, col = oldVersion.length) {
  let res = new Set();

  if (!row) {
    if (col) {
      res.add(`(${oldVersion.substring(0, col)})`);  
    } else {
      res.add('');
    }
    
    return res;
  }

  if (!col) {
    if (row) {
      res.add(`[${newVersion.substring(0, row)}]`);  
    } else {
      res.add('');
    }

    return res;
  }

  if (oldVersion[col - 1] === newVersion[row - 1]) {
    let char = oldVersion[col - 1];
    
    for (let diff of buildDiffs(lcsMatrix, oldVersion, newVersion, row - 1, col - 1)) {
      res.add(`${diff}${char}`);
    }
  }

  if (lcsMatrix[row][col] === lcsMatrix[row - 1][col]) {
    let char = newVersion[row - 1];

    for (let diff of buildDiffs(lcsMatrix, oldVersion, newVersion, row - 1, col)) {
      res.add(
        diff[diff.length - 1] === ']' ? 
        `${diff.substring(0, diff.length - 1)}${char}]` : 
        `${diff}[${char}]`
      );
    }
  }

  if (lcsMatrix[row][col] === lcsMatrix[row][col - 1]) {
    let char = oldVersion[col - 1];

    for (let diff of buildDiffs(lcsMatrix, oldVersion, newVersion, row, col - 1)) {
      res.add(
        diff[diff.length - 1] === ')' ? 
        `${diff.substring(0, diff.length - 1)}${char})` : 
        `${diff}(${char})`
      );
    }
  }

  return res;
}

function isAlnum(c) {
  return /\w/.test(c);
}

function isPths(c) {
  return /[()[\]]/.test(c);
}

function compare(s1, s2) {
  for (let i = 0; i < Math.min(s1.length, s2.length); i++) {
    let c1 = s1[i];
    let c2 = s2[i];

    if (c1 === c2) {
      continue;
    }

    if (isAlnum(c1) && isPths(c2)) {
      return -1;
    } else if (isPths(c1) && isAlnum(c2)) {
      return 1;
    } else {
      return c1 > c2 ? 1 : -1;
    }
  }

  return s1.length - s2.length;
}

function log(...args) {
  if (log.enabled) {
    console.log(...args);
  }
}

log.enabled = false;