Skip to content

Instantly share code, notes, and snippets.

@albinotonnina
Created June 12, 2018 13:23
Show Gist options
  • Save albinotonnina/e5eb9589f3a2322678b75461ac230181 to your computer and use it in GitHub Desktop.
Save albinotonnina/e5eb9589f3a2322678b75461ac230181 to your computer and use it in GitHub Desktop.
/*
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
Copy link

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"]]"

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment