Skip to content

Instantly share code, notes, and snippets.

@kottenator
Created April 15, 2018 19:54
Show Gist options
  • Save kottenator/514d55ee80abbf846128de0e6b932e4b to your computer and use it in GitHub Desktop.
Save kottenator/514d55ee80abbf846128de0e6b932e4b to your computer and use it in GitHub Desktop.
Own custom diff
/*
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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment