Live programming @ University of Washington
{
// Now with fuzzyfind
// Example usage
let largerString = "This is the \n\n larger string, which\n contains our nearly identical substring.";
let substring = `lerger strng, which cotain our nearly`;
const {start, end, score} = await fuzzyFindStartAndEndWithNormalizedWhitespace(largerString, substring)
return largerString.slice(start, end)
}
md`Some code for string normalization mapping based on https://chat.openai.com/share/cf7741b4-374f-426b-955c-e8c3499bf076`
function normalizeStringAndMapPositions(str) {
let normalized = '';
let positionMap = [];
let originalPosition = 0;
for (let i = 0; i < str.length; i++) {
if (str[i].match(/\s/) && (i == 0 || str[i-1].match(/\s/))) {
// Skip multiple whitespaces
continue;
}
// Add character to normalized string and map its position
normalized += str[i].match(/\s/) ? ' ' : str[i];
positionMap.push(originalPosition);
originalPosition = i + 1;
}
return { normalized, positionMap };
}
function findOriginalPositions(originalStr, matchStart, matchEnd, positionMap) {
// Adjust the positions based on the position map
const originalStart = positionMap[matchStart + 1] - 1;
const originalEnd = positionMap[matchEnd] + (originalStr[positionMap[matchEnd]] === ' ' ? 0 : 1);
return { originalStart, originalEnd };
}
{
// Example usage
let largerString = "This is the \n\n larger string, which\n contains the nearly identical substring.";
let substring = `lerger strng, which cotain the nearly`;
// Normalize and map positions
const {normalized: normalizedLargerString, positionMap} = normalizeStringAndMapPositions(largerString);
const {normalized: normalizedSubstring} = normalizeStringAndMapPositions(substring);
// Assume we found the match in the normalized strings (example positions)
let {start: matchStart, end: matchEnd} = fuzzyFindSubstringIndices(normalizedLargerString, normalizedSubstring)
// let matchEnd = matchStart + normalizedSubstring.length - 1;
// Find original positions
const {originalStart, originalEnd} = findOriginalPositions(largerString, matchStart, matchEnd, positionMap);
return largerString.slice(originalStart, originalEnd)
// console.log(`Match found from ${originalStart} to ${originalEnd} in the original string.`);
}
function indexOfNthOccurrence(str, searchStr, n) {
let index = -1;
// Loop until we find the nth occurrence
for(let i = 0; i < n; i++) {
index = str.indexOf(searchStr, index + 1);
if (index === -1) break;
}
return index;
}
{
// Example usage:
const str = "This is a test. This test is only a test.";
const searchStr = "test";
const n = 2; // Looking for the 2nd occurrence
return indexOfNthOccurrence(str, searchStr, n); // Output will be the index of the 2nd occurrence of "test"
}
function findStartAndEndNormalized(largerString, substring, nthOccurence=0) {
// Normalize and map positions
const {normalized: normalizedLargerString, positionMap} = normalizeStringAndMapPositions(largerString);
const {normalized: normalizedSubstring} = normalizeStringAndMapPositions(substring);
// Assume we found the match in the normalized strings (example positions)
let matchStart = normalizedLargerString.indexOf(normalizedSubstring);
let matchEnd = matchStart + normalizedSubstring.length - 1;
// Find original positions
const {originalStart, originalEnd} = findOriginalPositions(largerString, matchStart, matchEnd, positionMap);
return {
start: originalStart,
end: originalEnd
}
}
{
// Example usage
let largerString = "This is the \n\n larger string, which\n contains the nearly identical substring.";
let substring = "larger string, which contains the nearly";
// Normalize and map positions
const {normalized: normalizedLargerString, positionMap} = normalizeStringAndMapPositions(largerString);
const {normalized: normalizedSubstring} = normalizeStringAndMapPositions(substring);
// Assume we found the match in the normalized strings (example positions)
let matchStart = normalizedLargerString.indexOf(normalizedSubstring);
let matchEnd = matchStart + normalizedSubstring.length - 1;
// Find original positions
const {originalStart, originalEnd} = findOriginalPositions(largerString, matchStart, matchEnd, positionMap);
return largerString.slice(originalStart, originalEnd)
// console.log(`Match found from ${originalStart} to ${originalEnd} in the original string.`);
}
{
// Example usage
let largerString = `const cart = [];
function addItem(item) {
cart.push(item);
}
function removeItem(itemName) {
const index = cart.findIndex(item => item.name === itemName);
if (index !== -1) {
cart.splice(index, 1);
}
}
function calculateTotalPrice() {
let totalPrice = 0;
for (let item of cart) {
totalPrice += item.price * item.quantity; // Updated to multiply by the quantity
}
return totalPrice;
}
function viewCart() {
for (let item of cart) {
console.log(\`Item: \${item.name}, Price: \${item.price}, Quantity: \${item.quantity}\`); // Updated to display the quantity
}
}
// Test the functionality
const item1 = { name: 'Apple', price: 0.5, quantity: 2 }; // Added quantity property
const item2 = { name: 'Banana', price: 0.25, quantity: 3 }; // Added quantity property
addItem(item1);
addItem(item2);
viewCart(); // Output: Item: Apple, Price: 0.5, Quantity: 2
// Item: Banana, Price: 0.25, Quantity: 3
removeItem('Apple');
viewCart(); // Output: Item: Banana, Price: 0.25, Quantity: 3
console.log(\`Total Price: \${calculateTotalPrice()}\`); // Output: Total Price: 0.75`
let substring = `function calculateTotalPrice() {
let totalPrice = 0;
for (let item of cart) {
totalPrice += item.price * item.quantity;
}
return totalPrice;
}`;
// largerString = "abc"
// substring = "bc"
const {start, end} = fuzzyFindSubstringIndices(largerString, substring)
return largerString.slice(start, end)
}
uFuzzy = require('@leeoniya/ufuzzy@1.0.14/dist/uFuzzy.cjs.js').catch(() => window["uFuzzy"])
fuzzyFindSubstringIndices('abcdefghij', 'bqfi')
result = {
const options = {
includeScore: true, // Include the score of how well each result matches the search term
includeMatches: true, // Include the matches and their indices
findAllMatches: true, // Find all matches, not just the first
threshold: 0.1, // Set a threshold for matching. The lower, the stricter. Adjust based on testing.
//location: 0, // Approximate location where the pattern is expected to be found (0 by default)
distance: 100, // Determines how close the match must be to the fuzzy location (0 is strict, 1000 is very loose)
ignoreLocation: true, // Search entire string, ignore location and distance. Good for variable-length strings.
minMatchCharLength: 1, // Minimum number of characters that must be matched before a result is considered a match
keys: ["text"], // Specify the keys in objects to search. This is necessary if searching in an array of objects.
};
const list = [
{ text: "This is the larger string, which contains the nearly identical substring." },
// ... other items
];
// Initialize Fuse with your list and options
const fuse = new Fuse(list, options);
// The search term
const searchTerm = "larger strng, which contans the nearly";
// Perform the search
const result = fuse.search(searchTerm);
return result
}
copy(JSON.stringify(result))
import {copy, asyncCopy} from '@ryanseddon/copy'
fuse.search(query)
function fuzzyFindSubstringIndices(largerString, substring, params={}) {
const uf = new uFuzzy(params)
const search = uf.search([largerString], substring)[1]
console.log(largerString, substring, search)
const ranges = search.ranges
if (!ranges || !(ranges[0])) {return {start: undefined, end: undefined}}
return {start: ranges[0][0], end: ranges[0][ranges[0].length -1]}
// // Step 2 & 3: Initialize Fuse.js with the larger string and configure fuzziness
// const options = {
// includeScore: true,
// includeMatches: true,
// findAllMatches: true,
// threshold: .5, // Adjust based on required fuzziness
// // other options as needed
// };
// const fuse = new Fuse([largerString], options);
// // Step 4: Search for the substring
// console.log('inputs', largerString, substring)
// const result = fuse.search(substring);
// // return result
// console.log('indices', result)
// // Step 5: Extract the best match's start and end indices
// if (result.length > 0) {
// const bestMatch = result[0];
// if (bestMatch.matches && bestMatch.matches.length > 0) {
// const match = bestMatch.matches[0];
// // Assuming the match indices are accurate for the purpose
// const startIndex = match.indices[0][0];
// const endIndex = match.indices[match.indices.length - 1][1];
// return { startIndex, endIndex };
// }
// }
// return { startIndex: -1, endIndex: -1 }; // Indicate no match found
}
uf = new uFuzzy({intraMode: 1, interIns: 2}) // see options at https://github.com/leeoniya/uFuzzy
[...Array(string.length)].map((_, i) => [...new Array(4)].map((_, j) => string.slice(i + j, substring.length - 2 + j))).flat()
fuzzyFindIndex = async (string, substring, params= {}) => {
// fuse.js options documented at https://www.fusejs.io/api/options.html#basic-options
const search = (await (await new Fuse([...Array(string.length)].map((_, i) => [...new Array(4)].map((_, j) => string.slice(i + j, substring.length - 2 + j))).flat(), {
isCaseSensitive: true,
includeScore: true,
shouldSort: true,
// includeMatches: true,
// findAllMatches: true,
// minMatchCharLength: 1,
location: 0,
threshold: 0.2,
distance: 20,
useExtendedSearch: false,
ignoreLocation: true,
ignoreFieldNorm: true,
...params
})).search(substring))
console.log(string, substring, search)
return search[0].refIndex
}
fuzzyFindIndexWithScore = async (string, substring, params= {}) => {
// fuse.js options documented at https://www.fusejs.io/api/options.html#basic-options
const search = (await (await new Fuse([...Array(string.length)].map((_, i) => [...new Array(4)].map((_, j) => string.slice(i + j, substring.length - 2 + j))).flat(), {
isCaseSensitive: true,
includeScore: true,
shouldSort: true,
includeMatches: true,
findAllMatches: true,
minMatchCharLength: 1,
// location: 0,
threshold: 0.2,
distance: 20,
// useExtendedSearch: false,
ignoreLocation: true,
ignoreFieldNorm: true,
...params
})).search(substring))
console.log(string, substring, search)
return {index: search[0].refIndex, score: search[0].score}
}
async function fuzzyFindStartAndEndWithNormalizedWhitespace(string, substring, params={}) {//, fuseParams={}) {
const {normalized: normalizedLargerString, positionMap} = normalizeStringAndMapPositions(string);
const {normalized: normalizedSubstring} = normalizeStringAndMapPositions(substring);
// Assume we found the match in the normalized strings (example positions)
let {start: matchStart, end: matchEnd, score} = fuzzyFindSubstringIndices(normalizedLargerString, normalizedSubstring, params)//await fuzzyFindIndexWithScore(normalizedLargerString, normalizedSubstring, fuseParams);
console.log(matchStart, matchEnd)
// let matchEnd = matchStart + normalizedSubstring.length - 1;
// Find original positions
const {originalStart, originalEnd} = findOriginalPositions(string, matchStart, matchEnd, positionMap);
return {start: originalStart, end: originalEnd, score}
}
fzf = require('fzf')
test1 = '(((display "Enter item name: ")\n(define name (read))\n(display "Enter quantity: ")\n(define quantity (read))\n(display "Enter price: ")\n(define price (read))\n(display "Enter category: ")\n(define category (read))\n(add-item name quantity price category)))'
string.indexOf(substring)
// fuzzyFindIndex(string, substring)
string = "```racket\n;; data-structures.rkt\n#lang racket\n\n(provide add-item\n grocery-list\n substitute-item)\n\n(define grocery-list '())\n\n(define (add-item name quantity price category)\n (set! grocery-list (cons (list 'name name 'quantity quantity 'price price 'category category) grocery-list)))\n\n(define (substitute-item item)\n (let ((category (list-ref item 4)))\n (filter (lambda (x) (eq? (list-ref x 4) category))\n grocery-list)))\n```\n\n```racket\n;; functions.rkt\n#lang racket\n\n(require \"data-structures.rkt\")\n(provide calculate-total-cost\n display-grocery-list)\n\n(define (calculate-total-cost grocery-list)\n (foldl (lambda (item total)\n (+ total (* (list-ref item 1) (list-ref item 3))))\n 0\n grocery-list))\n\n(define (display-grocery-list grocery-list)\n (for-each (lambda (item)\n (display \"Name: \")\n (display (list-ref item 1))\n (display \", Quantity: \")\n (display (list-ref item 3))\n (display \", Price: \")\n (display (list-ref item 5))\n (display \", Category: \")\n (display (list-ref item 7))\n (newline))\n (reverse grocery-list)))\n```\n\n```racket\n;; main.rkt\n#lang racket\n\n(require \"data-structures.rkt\"\n \"functions.rkt\")\n\n(define (grocery-shopping-assistant)\n (let loop ()\n (display \"1. Add item\\n\")\n (display \"2. Calculate total cost\\n\")\n (display \"3. Get substitution suggestions\\n\")\n (display \"4. Display grocery list\\n\")\n (let ((choice (read)))\n (case choice\n ((1) (begin\n (display \"Enter item name: \")\n (define name (read))\n (display \"Enter quantity: \")\n (define quantity (read))\n (display \"Enter price: \")\n (define price (read))\n (display \"Enter category: \")\n (define category (read))\n (add-item name quantity price category)))\n ((2) (display \"Total cost: \") \n (display (calculate-total-cost grocery-list)))\n ((3) (begin\n (display \"Enter item index: \")\n (define index (read))\n (display \"Substitution suggestions: \")\n (for-each (lambda (item)\n (display (list-ref item 1))\n (newline))\n (substitute-item (list-ref grocery-list (- index 1))))))\n ((4) (display-grocery-list grocery-list))\n (else (display \"Invalid choice, please try again.\"))))))\n\n;; Test cases\n(add-item \"Apple\" 5 1 \"Fruits\")\n(add-item \"Banana\" 7 0.5 \"Fruits\")\n(add-item \"Milk\" 2 2 \"Dairy\")\n\n(grocery-shopping-assistant)\n``★display (calculate-total-cost grocery-list)★ket\n\n(provide add-item\n grocery-list\n substitute-item)\n\n(define grocery-list '())\n\n(define (add-item name quantity price category)\n (set! grocery-list (cons (list 'name name 'quantity quantity 'price price 'category category) grocery-list)))\n\n(define (substitute-item item)\n (let ((category (list-ref item 4)))\n (filter (lambda (x) (eq? (list-ref x 4) category))\n grocery-list)))\n```\n\n```racket\n;; functions.rkt\n#lang racket\n\n(require \"data-structures.rkt\")\n(provide calculate-total-cost\n display-grocery-list)\n\n(define (calculate-total-cost grocery-list)\n (foldl (lambda (item total)\n (+ total (* (list-ref item 1) (list-ref item 3))))\n 0\n grocery-list))\n\n(define (display-grocery-list grocery-list)\n (for-each (lambda (item)\n (display \"Name: \")\n (display (list-ref item 1))\n (display \", Quantity: \")\n (display (list-ref item 3))\n (display \", Price: \")\n (display (list-ref item 5))\n (display \", Category: \")\n (display (list-ref item 7))\n (newline))\n (reverse grocery-list)))\n```\n\n```racket\n;; main.rkt\n#lang racket\n\n(require \"data-structures.rkt\"\n \"functions.rkt\")\n\n(define (grocery-shopping-assistant)\n (let loop ()\n (display \"1. Add item\\n\")\n (display \"2. Calculate total cost\\n\")\n (display \"3. Get substitution suggestions\\n\")\n (display \"4. Display grocery list\\n\")\n (let ((choice (read)))\n (case choice\n ((1) (begin\n (display \"Enter item name: \")\n (define name (read))\n (display \"Enter quantity: \")\n (define quantity (read))\n (display \"Enter price: \")\n (define price (read))\n (display \"Enter category: \")\n (define category (read))\n (add-item name quantity price category)))\n ((2) (display \"Total cost: \") \n (display (calculate-total-cost grocery-list)))\n ((3) (begin\n (display \"Enter item index: \")\n (define index (read))\n (display \"Substitution suggestions: \")\n (for-each (lambda (item)\n (display (list-ref item 1))\n (newline))\n (substitute-item (list-ref grocery-list (- index 1))))))\n ((4) (display-grocery-list grocery-list))\n (else (display \"Invalid choice, please try again.\"))))))\n\n;; Test cases\n(add-item \"Apple\" 5 1 \"Fruits\")\n(add-item \"Banana\" 7 0.5 \"Fruits\")\n(add-item \"Milk\" 2 2 \"Dairy\")\n\n(grocery-shopping-assistant)\n```"
substring = '(define (display-grocery-list grocery-list)\r\n (for-each (lambda (item)\r\n (display "Name: ")\r\n (display (list-ref item 1))\r\n (display ", Quantity: ")\r\n (display (list-ref item 3))\r\n (display ", Price: ")\r\n (display (list-ref item 5))\r\n (display ", Category: ")\r\n (display (list-ref item 7))\r\n (newline))\r\n (reverse grocery-list)))'.replaceAll('\r', '')
fuse.search(substring)
list = [...Array(string.length)].map((_, i) => string.slice(i, i + substring.length))
fuse = new Fuse(list, {
// isCaseSensitive: false,
includeScore: true,
// shouldSort: true,
// includeMatches: false,
// findAllMatches: false,
// minMatchCharLength: 1,
location: 0,
threshold: 0.6,
distance: 60,
// useExtendedSearch: false,
// ignoreLocation: true,
ignoreFieldNorm: true
})
Fuse = require('fuse.js')
import { text } from '@observablehq/legacy-inputs'
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.