91 lines
2.6 KiB
JavaScript
91 lines
2.6 KiB
JavaScript
/**
|
|
* Find the letter the word ends on
|
|
* @param {string} word
|
|
* @returns {string}
|
|
*/
|
|
const endsWith = word => word[word.length - 1];
|
|
|
|
/**
|
|
* Remove the used elements from the candidate elements
|
|
* @param {Array<string>} words Candidate words
|
|
* @param {Array<string>} used Used words
|
|
* @returns {*}
|
|
*/
|
|
const getCandidates = (words, used) => words.filter(e => !used.includes(e));
|
|
|
|
/**
|
|
* Build a map of letters to words that start with that letter
|
|
* @param {Array<string>} words
|
|
* @returns {Map<string, Array<string>>}
|
|
*/
|
|
const buildLookup = words => {
|
|
const lookup = new Map();
|
|
words.forEach(e => {
|
|
const start = e[0];
|
|
lookup.set(start, [...(lookup.get(start) || []), e]);
|
|
});
|
|
return lookup;
|
|
};
|
|
|
|
|
|
/**
|
|
* Main function
|
|
* @param {Array<string>} names
|
|
*/
|
|
const findPaths = names => {
|
|
const t0 = process.hrtime();
|
|
console.log('Checking:', names.length, 'names');
|
|
const lookup = buildLookup(names);
|
|
|
|
let maxNum = 0;
|
|
let maxPaths = [];
|
|
|
|
const parseResult = arr => {
|
|
if (typeof arr[0] === 'object') {
|
|
arr.forEach(el => parseResult(el))
|
|
} else {
|
|
if (arr.length > maxNum) {
|
|
maxNum = arr.length;
|
|
maxPaths = [arr];
|
|
}
|
|
if (arr.length === maxNum) {
|
|
maxPaths.push(arr)
|
|
}
|
|
}
|
|
};
|
|
|
|
const searchWords = (word, res) => {
|
|
const cs = getCandidates(lookup.get(endsWith(word)) || [], res);
|
|
return cs.length ? cs.map(e => searchWords(e, [...res, e])) : res;
|
|
};
|
|
|
|
names.forEach(word => {
|
|
const res = searchWords(word, [word]);
|
|
parseResult(res);
|
|
});
|
|
|
|
const t1 = process.hrtime(t0);
|
|
console.info('Execution time (hr): %ds %dms', t1[0], t1[1] / 1000000);
|
|
console.log('Max Path:', maxNum);
|
|
console.log('Matching Paths:', maxPaths.length);
|
|
console.log('Example Path:', maxPaths[0]);
|
|
|
|
};
|
|
|
|
const pokimon = ["audino", "bagon", "baltoy", "banette",
|
|
"bidoof", "braviary", "bronzor", "carracosta", "charmeleon",
|
|
"cresselia", "croagunk", "darmanitan", "deino", "emboar",
|
|
"emolga", "exeggcute", "gabite", "girafarig", "gulpin",
|
|
"haxorus", "heatmor", "heatran", "ivysaur", "jellicent",
|
|
"jumpluff", "kangaskhan", "kricketune", "landorus", "ledyba",
|
|
"loudred", "lumineon", "lunatone", "machamp", "magnezone",
|
|
"mamoswine", "nosepass", "petilil", "pidgeotto", "pikachu",
|
|
"pinsir", "poliwrath", "poochyena", "porygon2", "porygonz",
|
|
"registeel", "relicanth", "remoraid", "rufflet", "sableye",
|
|
"scolipede", "scrafty", "seaking", "sealeo", "silcoon",
|
|
"simisear", "snivy", "snorlax", "spoink", "starly", "tirtouga",
|
|
"trapinch", "treecko", "tyrogue", "vigoroth", "vulpix",
|
|
"wailord", "wartortle", "whismur", "wingull", "yamask"];
|
|
|
|
findPaths(pokimon);
|