Last active
April 29, 2020 02:29
-
-
Save johan/4beaa326203aca8d6176be3a4b058d88 to your computer and use it in GitHub Desktop.
list edit distances between all inputs of the same length, ascending order
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #! /usr/bin/env node | |
| // for a JSON array of strings, or an array of lines on stdin, | |
| // shows edit distances between all the inputs, ascending | |
| const fs = require('fs'); | |
| const ed = require('edit-distance'); | |
| // read all strings from stdin: | |
| let names = fs.readFileSync(0, 'utf-8'); | |
| try { | |
| names = JSON.parse(names); | |
| } catch (e) { | |
| names = names.trim().split('\n'); | |
| } | |
| names = uniq(names); | |
| function uniq(arr) { | |
| const seen = {}; | |
| for (const n of arr) { | |
| seen[n] = 1; | |
| } | |
| return Object.keys(seen); | |
| } | |
| function bySize(arr) { | |
| const sized = {}; | |
| for (const n of arr) { | |
| sized[n.length] = (sized[n.length] || []).concat(n); | |
| } | |
| return sized; | |
| } | |
| const bysize = bySize(names); | |
| const moreThanOne = Object.keys(bysize).filter(k => bysize[k].length > 1); | |
| const wanted = Object.fromEntries(moreThanOne.map(k => [k, bysize[k]])); | |
| function insert(node) { return 1; } | |
| function remove(node) { return 1; } | |
| function update(a, b) { return a !== b ? 1 : 0; } | |
| const ascending = (a, b) => a[0] - b[0]; | |
| const dist = (a, b) => ed.levenshtein(a, b, insert, remove, update).distance; | |
| const maxDist = (w, i, a) => { const d = a.slice(i + 1).map(W => dist(w, W)); return d.map((n, j) => [n, w, a[i+j+1]]); } | |
| const byDist = (w, i, a) => { | |
| const d = a.slice(i + 1).map(W => dist(w, W)); | |
| return d.map((n, j) => [n, w, a[i+j+1]]).sort(ascending); | |
| }; | |
| const concat = (arr) => arr.reduce((a, b) => a.concat(b), []); | |
| const allDist = (arr) => concat(arr.map(byDist)).sort(ascending); | |
| const distances = Object.fromEntries(Object.keys(wanted).map( | |
| n => [n, allDist(wanted[n])] | |
| )); | |
| const all = concat(Object.keys(distances).map(n => distances[n])).sort(ascending); | |
| console.log(all); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "name": "editdistance-cli", | |
| "version": "1.0.0", | |
| "description": "list edit distances between all inputs, ascending order", | |
| "main": "editdistance", | |
| "license": "MIT", | |
| "dependencies": { | |
| "edit-distance": "^1.0.2" | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment