Public
Edited
Sep 23, 2023
lcsFunctions = {
function longestCommonSubsequence(s1, s2) {
const m = s1.length;
const n = s2.length;
const C = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i - 1] === s2[j - 1]) {
C[i][j] = C[i - 1][j - 1] + 1;
}
else {
C[i][j] = Math.max(C[i][j - 1], C[i - 1][j]);
}
}
}
return C;
}
function backtrack(C, s1, s2, i, j) {
if (i === 0 || j === 0) {
return "";
}
else if (s1[i - 1] === s2[j - 1]) {
return backtrack(C, s1, s2, i - 1, j - 1) + s1[i - 1];
}
else {
return C[i][j - 1] > C[i - 1][j]
? backtrack(C, s1, s2, i, j - 1)
: backtrack(C, s1, s2, i - 1, j);
}
}
function generateOperations2(
text,
updateText
){
const m = text.length;
const n = updateText.length;
const C = longestCommonSubsequence(text, updateText);
const lcs = backtrack(C, text, updateText, m, n);
const ops= [];
const removeOps = [];
let i = 0,
j = 0;
for (const char of lcs) {
while (text[i] !== char) {
removeOps.push({
type: "remove_text",
offset: i,
text: text[i],
path: [],
});
i++;
}
while (updateText[j] !== char) {
ops.push({
type: "insert_text",
offset: i,
text: updateText[j],
path: [],
});
j++;
}
i++;
j++;
}
while (i < m) {
removeOps.push({ type: "remove_text", offset: i, text: text[i], path: [] });
i++;
}
while (j < n) {
ops.push({ type: "insert_text", offset: i, text: updateText[j], path: [] });
i++;
j++;
}
// Reverse the remove operations and merge with other ops.
return ops.concat(removeOps.reverse());
}
return { longestCommonSubsequence, backtrack, generateOperations2 };
}
// function that takes two strings and generates text ops that can transform s1 to s2
function generateOperations4(text, updateText) {
const ops = [];
let i = 0, j = 0;
let offsetAdjustment = 0;
while (i < text.length || j < updateText.length) {
const currentOffset = i + offsetAdjustment;
if (i < text.length && j < updateText.length && text[i] === updateText[j]) {
// Characters match, move to the next character in both strings
i++;
j++;
} else if (i < text.length && (j >= updateText.length || text[i] !== updateText[j])) {
// Character in text doesn't match character in updateText or updateText is shorter, remove character from text
ops.push({
type: "remove_text",
offset: currentOffset,
text: text[i],
path: []
});
i++;
} else if (j < updateText.length && (i >= text.length || text[i] !== updateText[j])) {
// Character in updateText doesn't match character in text or text is shorter, insert character into text
ops.push({
type: "insert_text",
offset: currentOffset,
text: updateText[j],
path: []
});
j++;
offsetAdjustment++; // Increase offset adjustment as we've inserted a character
}
}
return ops;
}
// takes a string `a` and applies ops to `a` and returns the result string
function applyOperations2(a, ops) {
let resultArray = a.split('');
let offsetAdjustment = 0;
// Sort ops by offset in ascending order for insert operations and descending for remove operations.
ops.sort((op1, op2) => {
if (op1.type === 'insert_text' && op2.type === 'insert_text') {
return op1.offset - op2.offset;
}
if (op1.type === 'remove_text' && op2.type === 'remove_text') {
return op2.offset - op1.offset; // reverse order for remove operations
}
return op1.type === 'insert_text' ? -1 : 1; // insertions first, then removals
});
for (const op of ops) {
const adjustedOffset = op.offset + offsetAdjustment;
if (op.type === 'insert_text') {
resultArray.splice(adjustedOffset, 0, ...op.text.split(''));
offsetAdjustment += op.text.length;
} else if (op.type === 'remove_text') {
resultArray.splice(adjustedOffset, op.text.length);
offsetAdjustment -= op.text.length;
}
}
return resultArray.join('');
}
function findLCS(s1, s2) {
const C = lcsFunctions.longestCommonSubsequence(s1, s2);
return lcsFunctions.backtrack(C, s1, s2, s1.length, s2.length);
}
findLCS("AGGTAB", "GXTXAYB")
tests.map(testCase => {
let ops = generateOperations4(testCase.s1, testCase.s2)
let result = applyOperations2(testCase.s1, ops)
const isCorrect = result === testCase.s1;
// return isCorrect
return `${isCorrect} | >> | ${testCase.s1}, ${testCase.s2}: |${result}#${testCase.s2}| (${ops.length}) `;
})
tests.map(testCase => {
const result = findLCS(testCase.s1, testCase.s2);
const isCorrect = result === testCase.lcs;
return `${isCorrect} | >> | ${testCase.s1}, ${testCase.s2}: |${result} -> ${testCase.lcs}| `;
// return isCorrect
})
data = lcsFunctions.generateOperations2('xabcdef', 'aabc')
function applyOperations (a, ops) {
let resultArray = a.split('');
// Sort the operations: first all the remove operations in decreasing order of offset,
// then all the insert operations in increasing order of offset.
ops.sort((a, b) => {
if (a.type === 'remove_text' && b.type === 'insert_text') return -1;
if (a.type === 'insert_text' && b.type === 'remove_text') return 1;
return a.type === 'remove_text'
? b.offset - a.offset
: a.offset - b.offset;
});
for (let i = 0; i < ops.length; i++) {
const op = ops[i];
if (op.type === 'insert_text') {
// For insert operations, splice in the new text at the specified offset
resultArray.splice(op.offset, 0, ...op.text.split(''));
} else if (op.type === 'remove_text') {
// For remove operations, splice out the text at the specified offset
resultArray.splice(op.offset, op.text.length);
}
}
return resultArray.join('');
}
data2 = lcsFunctions.generateOperations2('1xab3cdef', '2a3abc')
applyOperations('xabcdef', data2)
function generateOperations3(a, b){
const ops = [];
let offsetA = 0;
let offsetB = 0;
while (offsetA < a.length && offsetB < b.length) {
if (a[offsetA] !== b[offsetB]) {
// Check if the character in b is inserted
if (!a.includes(b[offsetB]) || a.indexOf(b[offsetB], offsetA) === -1) {
ops.push({
type: "insert_text",
offset: offsetB,
text: b[offsetB],
path: [],
});
offsetB++; // Move forward in b as a character is inserted
} else {
// Else the character in a is removed
ops.push({
type: "remove_text",
offset: offsetA,
text: a[offsetA],
path: [],
});
offsetA++; // Move forward in a as a character is removed
}
} else {
// Characters are the same, move forward in both strings
offsetA++;
offsetB++;
}
}
// Handle any remaining characters in a or b
while (offsetA < a.length) {
ops.push({
type: "remove_text",
offset: offsetA,
text: a[offsetA],
path: [],
});
offsetA++;
}
while (offsetB < b.length) {
ops.push({
type: "insert_text",
offset: offsetB,
text: b[offsetB],
path: [],
});
offsetB++;
}
return ops;
}
d = generateOperations3('1xab3cdef', '2a3abc')
applyOperations2('1xab3cdef', d)
d1 = generateOperations4('1xab3cdef', '2a3abc')
applyOperations2('1xab3cdef', d1)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
