Instantly share code, notes, and snippets.

# albinotonnina/groupCitiesByRotatedName.js

Created June 12, 2018 13:23
Show Gist options
• Save albinotonnina/e5eb9589f3a2322678b75461ac230181 to your computer and use it in GitHub Desktop.
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
 /* Problem: ['Tokyo', 'London', 'Rome', 'Donlon', 'Kyoto', 'Paris'] // YOUR ALGORITHM [ [ 'Tokyo', 'Kyoto' ], [ 'London', 'Donlon' ], [ 'Rome' ], [ 'Paris' ] ] */ const getWordRotations = word => [...word].reduce( acc => [acc[0].substring(1) + acc[0].substring(0, 1), ...acc], [word] ); const groupCitiesByRotatedNames = cities => cities.reduce((acc, city) => { const cityGroup = acc.find(item => getWordRotations(city.toLowerCase()).includes(item[0].toLowerCase()) ); cityGroup ? acc.splice(acc.indexOf(cityGroup), 1, [...cityGroup, city]) : acc.push([city]); return acc; }, []); const test = groupCitiesByRotatedNames([ "Tokyo", "London", "Rome", "Donlon", "Kyoto", "Paris" ]); console.log("test", test);

### meisterluk commented Jul 11, 2018

Assuming `n` is the number of accesses to the cities array, you can achieve linear time `O(n)` using the following approach:

``````// returns word such that letter 0 will be found at position idx in the return value
// permuteWord('foobar', 1) === "rfooba"
const permuteWord = (word, idx) =>
[...Array(word.length).keys()]
.map(i => word.substr((i - idx + word.length) % word.length, 1))
.join("");

// a high rank means that high UTF-16 code points will be found at the beginning of the string;
// a low rank means that low UTF-16 code points will be found at the beginning of the string;
// assuming strings of equal length. Thus it provides a partial order for string permutations.
const rank = (word, idx) =>
permuteWord(word, idx).split('').map((l, i) => l.charCodeAt(0) * 65535 * (i + 1)).reduce((a, b) => a + b);

// returns a permutation-independent representation of lowercased name
// canonicalName('london') === canonicalName('donlon')
// canonicalName('some') !== canonicalName('different')
const canonicalName = name => {
name = name.toLowerCase();
let start = [...Array(name.length).keys()].map(i => [i, rank(name, i)]).reduce((a, b) => (a[1] > b[1]) ? a : b)[0];
return permuteWord(name, start);
};

// the desired grouping function
const groupCitiesByRotatedNames = cities => {
let categories = {};
for (city of cities) {
let canonical = canonicalName(city);
if (categories[canonical] === undefined)
categories[canonical] = [city];
else
categories[canonical].push(city);
}
var result = [];
for (category in categories)
result.push(categories[category]);
return result
}

groupCitiesByRotatedNames([
"Tokyo",
"London",
"Rome",
"Donlon",
"Kyoto",
"Paris"
]);
// returns [["Tokyo","Kyoto"],["London","Donlon"],["Rome"],["Paris"]]"
``````