Skip to content

Instantly share code, notes, and snippets.

@dmoney dmoney/groupcities.js
Last active Jun 28, 2018

Embed
What would you like to do?
// groupcities.js
// An alternative solution to:
// https://dev.to/albinotonnina/how-to-lose-a-it-job-in-10-minutes-35pi
//
// Given an array of city names, group the ones that are rotations of
// each other together. e.g.:
//
// input: ['Tokyo', 'London', 'Rome', 'Donlon', 'Kyoto', 'Paris']
// output:
// [
// [ 'Tokyo', 'Kyoto' ],
// [ 'London', 'Donlon' ],
// [ 'Rome' ],
// [ 'Paris' ]
// ]
// generator to yield the rotations of a string
function* getRots(s){
let tempstr = s
for (let i = 0; i < s.length; i++){
tempstr = tempstr.substring(1) + tempstr.substring(0, 1)
yield tempstr
}
}
// return the rotation of the string
// that is the lowest alphabetically
function canonicalize(s){
let lowestRotation = s.toLowerCase()
for (let rotation of getRots(lowestRotation)){
if (rotation < lowestRotation){
lowestRotation = rotation
}
}
return lowestRotation
}
// given array of cities as strings,
// return ojbect mapping canonical string
// to a Set of strings that match it
function groupCities(cities){
let groups = {}
for (let city of cities){
let canonicalName = canonicalize(city)
if (!groups[canonicalName]) {
groups[canonicalName] = new Set([city])
}
else {
groups[canonicalName].add(city)
}
}
return groups
}
// given a map of sets, return an array of arrays
function arrayify(groupedCities){
let groups = []
for (let key in groupedCities){
let cityGroup = []
for (let city of groupedCities[key]){
cityGroup.push(city)
}
groups.push(cityGroup)
}
return groups
}
// > arrayify(groupCities(['Dallas', 'Llasda', 'Lasagna',
// 'Rome', 'Mburg', 'Gmbur', 'Mubrg']))
// ==> [ [ 'Dallas', 'Llasda' ],
// [ 'Lasagna' ],
// [ 'Rome' ],
// [ 'Mburg', 'Gmbur' ],
// [ 'Mubrg' ] ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.