Задача: Города. Покритикуйте.

[m1st]

Широко известна игра "Города". Называется какой-нибудь город, допустим, "Саратов". Кончается на "в", значит требуется назвать другой город, у которого в названии первая буква "в". Это может быть "Воронеж". Следующий город должен начинаться на "ж" и т.д. Запрещено повторять название городов. Надо написать программу, которая из набора названий городов (все названия разные) строит цепочку максимальной длины.

Привет, решение данной задачи на Java. (файл-список городов в аттаче)

[m1st]

Код: Выделить всё

package olympicexercises;

import java.util.*;
import java.io.*;


public class CitiesSolver
{
  /**
   * Получение первой буквы для сравнения
   *
   * @param city - город для выбора первой буквы
   * @return первая буква
   */
  public static Character getFirstChar(String city)
  {
    return city.charAt(0);
  }


  /**
   * Получение последней буквы для сравнения, с пропуском "неправильных" букв
   *
   * @param city - город для выбора последней буквы
   * @return последняя буква
   */
  public static Character getLastChar(String city)
  {
    int pos = city.length() - 1;
    char lastChar = city.toUpperCase().charAt(pos);
    if (city.toUpperCase().charAt(pos) == 'Й') {
      return 'И';
    }
    else if (lastChar == 'Ь' || lastChar == 'Ы' || lastChar == 'Ъ') {
      pos--;
    }
    return city.toUpperCase().charAt(pos);
  }


  /**
   * Рекурсия обхода дерева
   *
   * @param cities - набор городов для инициализации коллекции
   * @return наиболее длинная цепочка из всех цепочек городов
   */
  public static List<String> findLongestChain(Set<String> cities)
  {
    Map<Character, Set<String>> citiesIndex = createIndex(cities);
    return findLongestChain(citiesIndex);
  }


  /**
   * Рекурсия обхода дерева
   *
   * @param citiesIndex - коллекция городов для поиска
   * @return наиболее длинная цепочка из всех цепочек городов
   */
  private static List<String> findLongestChain(Map<Character, Set<String>> citiesIndex)
  {
    List<String> chain = new ArrayList<String>(0);
    for (Character firstChar : citiesIndex.keySet()) {
      List<String> newChain = findLongestChain(citiesIndex, firstChar);
      System.out.println("Цепочка максимальной длины (" + newChain.size() + "): " + newChain + "\n==");
      if (chain.size() < newChain.size()) {
        chain = newChain;
      }
    }
    System.out.println("Самая длинная из цепочек (" + chain.size() + "): " + chain);
    return chain;
  }


  /**
   * Рекурсия обхода дерева
   *
   * @param citiesIndex - коллекция городов для поиска
   * @param firstChar - первая буква для поиска города
   * @return цепочки городов
   */
  private static List<String> findLongestChain(Map<Character, Set<String>> citiesIndex, Character firstChar)
  {
    List<String> chain = new ArrayList<String>(0);
    try {
      for (String city : citiesIndex.get(firstChar)) {
        Map<Character, Set<String>> index = cloneIndex(citiesIndex); // работаем с копией коллекции городов
        index.get(firstChar).remove(city); // удаляем использованный город
        List<String> newChain = new ArrayList<String>(); // инициализация массива цепочки городов
        newChain.add(city); // добавление города в цепочку
        newChain
            .addAll(findLongestChain(index, getLastChar(city))); // добавление наиболее перспективных городов в цепочку
        System.out.println("Прорабатывается цепочка (" + newChain.size() + "): " + newChain);
        if (chain.size() < newChain.size()) {  // выход из рекурсии
          chain = newChain;
        }
      }
    }
    catch (NullPointerException e) {
    }
    return chain;
  }


  /**
   * Создание копии коллекции городов
   *
   * @param citiesIndex - коллекция городов для копии
   * @return копия коллекции городов
   */
  private static Map<Character, Set<String>> cloneIndex(Map<Character, Set<String>> citiesIndex)
  {
    Map<Character, Set<String>> newIndex = new HashMap<Character, Set<String>>();
    for (Character key : citiesIndex.keySet()) {
      newIndex.put(key, new HashSet<String>(citiesIndex.get(key)));
    }
    return newIndex;
  }


  /**
   * Инициализация коллекции городов для поиска
   *
   * @param cities - города для инициализации
   * @return коллекция городов
   *
   * key - первая буква города, value - имена городов начинающихся на эту букву
   */
  private static Map<Character, Set<String>> createIndex(Set<String> cities)
  {
    Map<Character, Set<String>> index = new HashMap<Character, Set<String>>();
    for (String city : cities) {
      Set<String> cs = index.get(getFirstChar(city));
      if (cs == null) index.put(getFirstChar(city), cs = new HashSet<String>());
      cs.add(city);
    }
    return index;
  }


  public static void main(String[] args) throws IOException
  {
    final Set<String> cities = new HashSet<String>();

    // Загрузим города из файла
    final BufferedReader in = new BufferedReader(new FileReader("src/olympicexercises/cities2.txt"));
    for (String city; (city = in.readLine()) != null ;) {
      cities.add(city); // и сложим все имена в этот массив
    }
    in.close();
    Set<String> sortedCities = new TreeSet<String>(cities);
    System.out.println("Список городов (" + sortedCities.size() + "): " + sortedCities);
    System.out.println("----------------------------");

    findLongestChain(cities);
  }
}
 

[m1st]

Допустим, существует набор городов "Абв", "Акв", "Вба": для данного набора городов возможны два варианта решения и в моем алгоритме будут вычеслены обе цепочки (хотя это не нужно), как оптимизировать алгоритм так чтобы при таком раскладе вычислялась только одна цепочка (не важно какая)?

Как оптимизировать решения для городов с одинаковыми первой и последней буквой ("Анапа")?