groupcities.js

// 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' ] ]