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

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

Привет, решение данной задачи на Java. Покритикуйте:
package OlympicExercises;

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

public class g6_1011 {
    public static void main(String[] args) throws IOException {
        BufferedReader in2 = new BufferedReader(new FileReader("src/OlympicExercises/cities.txt"));
        String city2;
        ArrayList cities = new ArrayList();
        while((city2 = in2.readLine()) != null)
        cities.add(city2);
        in2.close();

        String city3, firstChar;
        boolean[] used = new boolean[cities.size()];
        ArrayList citiesSequenceTMP = new ArrayList(),
                     citiesSequence = new ArrayList();
        for(int i4 = 0; i4 < cities.size(); i4++) {
        for(int i3 = 0; i3 < cities.size(); i3++) {
            used[i3] = false; }
        String city = cities.get(i4).toString();
        String lastChar = city.substring(city.length()-1);
        for(int i2 = 0; i2 < cities.size(); i2++) {
            for(int i = 0; i < cities.size(); i++) {
//                if(cities.get(i).toString().equals(city)) continue;
                if(used[i]) continue;
                city3 = cities.get(i).toString();
                firstChar = city3.substring(0, 1).toLowerCase();
                if(firstChar.equals(lastChar)) {
                    citiesSequenceTMP.add(cities.get(i));
                    lastChar = city3.substring(city3.length()-1);
                    used[i] = true;
                    }
                }
            if(citiesSequenceTMP.size() > citiesSequence.size()) {
                citiesSequence.clear();
                citiesSequence.addAll(citiesSequenceTMP);
                citiesSequenceTMP.clear();
        }
            if(citiesSequenceTMP.size() < citiesSequence.size())
                citiesSequenceTMP.clear();
                }
        }
        System.out.println(citiesSequence + " = " + citiesSequence.size() + " cities");
    }
}
 
 
Сообщения:35
Мне кажется, что данная реализация не является лучшей и главное правильной.
Если я правильно понял ваш код, то тут есть несколько неточностей:
1) цикл i в котором ищется следующий элемент не подразумевает остановки после нахождения, следовательно за один проход он может добавить несколько новых значений, что никуда не заносится и приведет к лишней работе цикла i2, а следовательно потере работоспособности.

2) выборка следующего элемента не подразумевает, что может быть несколько элементов, которые могут стать первым для текущего, а наибольшая длина цепочки может достигаться, к примеру, только в случае выбора второго из подходящих элементов, что у вас не реализованно.

Вроде как-то так, если нужна будет помощь с алгоритмом, пишите, можно придумать несколько вариантов.
 
 
Сообщения:1263
к критике предыдущего оратора добавлю следующее:
1. нет коментариев
2. форматирование. все уже давно форматируется автоматом, пренебрегать тем что не требует ни какого труда и выкладывать на обозренее не очень хорошая идея.
3. Используйте типизированные коллекции, например ArrayList<String>

А вообще, в задачке нужно построить дерево, узлы которого принадлежат множеству имен городов кроме корня, причем каждая ветка не содержит любой элемент этого множества дважды. Корень дерева - некий стартовый элемент не из множества имен городов, все элементы множества имен городов являются дочерними по отношению к корню. Самая длинная ветка этого дерева будет решением. Нужно использовать рекурсию.

 
 
Сообщения:128
unki:
Если я правильно понял ваш код, то тут есть несколько неточностей:
1) цикл i в котором ищется следующий элемент не подразумевает остановки после нахождения, следовательно за один проход он может добавить несколько новых значений, что никуда не заносится и приведет к лишней работе цикла i2, а следовательно потере работоспособности.
Ваша правда!

Quote:
2) выборка следующего элемента не подразумевает, что может быть несколько элементов, которые могут стать первым для текущего, а наибольшая длина цепочки может достигаться, к примеру, только в случае выбора второго из подходящих элементов, что у вас не реализованно.
Реализовывался "алгоритм" brute-force. :)
Первое, что сейчас пришло на ум - шахматы. Когда ход просчитывается на несколько итераций. Как результат можно просчитывать N-кол-во цепочек до N-глубины и выбирать наибольшую...

Quote:
Вроде как-то так, если нужна будет помощь с алгоритмом, пишите, можно придумать несколько вариантов.
Спасибо!
 
 
Сообщения:128
Evgenic:

2. форматирование. все уже давно форматируется автоматом, пренебрегать тем что не требует ни какого труда и выкладывать на обозренее не очень хорошая идея.
О каком форматировании вы говорите? Используется дефолтное форматирование (IDEA v8).

Evgenic:

3. Используйте типизированные коллекции, например ArrayList<String>
Действительно, решает сразу 2 задачи:
1. получаем добавление элемента только заданного типа
2. при извлечении элемента его тип будет таким, который нам нужен

Спасибо!
 
 
Сообщения:1263
m1st:
О каком форматировании вы говорите? Используется дефолтное форматирование (IDEA v8).

О нем и говорил. :shock: О ужас!!!
С вашей подачи принял жесткую сторону противников IDEA в IDE-холеваре. :D

PS. в таком случае прошу пардона и снимаю все ошибочные претензии к вам по форматированию. теперь все они к IDEA :lol:

 
 
Сообщения:1263
типо, тоже решил поучаствовать. вот что у меня получилось. но вряд ли получится применить эту программу для игры, если у вас нету процессора с гиганской частотой и столько же времени :D
эт задачка клево параллелется, можно разложить по потокам и посмотреть реальный прирост ... если делать будет нечего
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;

/**
 *
 * @author Evgenic
 */
public class Main {

    final static LinkedList<String> cities = new LinkedList<String>();
    static LinkedList<String> resultBranch = new LinkedList<String>();
    static int varCount = 0;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // Загрузим города из файла
        final BufferedReader in2 = new BufferedReader(new FileReader("cities.txt"));
        String city;
        // и сложим все имена в этот массив
        city = in2.readLine().substring(1);
        while (city != null) {
            cities.add(city);
            city = in2.readLine();
        }
        in2.close();
        System.out.println("кол-во городов " + cities.size() + "\n" + cities);
        // Начинаем обход дерева начиная с первого уровня, если учесть
        // что корень это нулевой уровень
        for (String cty : cities) {
            System.out.println("Старт ветки " + cty);
            tree(cty, new LinkedList<String>());
        }
        System.out.println("РЕЗУЛЬТАТ\nкол-во городов " + resultBranch.size() + "\n" + resultBranch);
    }

    /**
     * Рекурсия обхода дерева
     * @param rootCity имя текущего узла
     * @param branch выстраиваемая ветка
     */
    private static void tree(String rootCity, LinkedList<String> branch) {
        branch.addLast(rootCity);
        // обход всего множества имен городов для обнаружения подходящих в следующие
        boolean flag = true;
        for (String city : cities) {
            // Учеть возможность мягкого знака.
            // проверка на неповроряемость и соответствию правилам игры
            if (!branch.contains(city) && city.toLowerCase().startsWith(getLastLetter(rootCity))) {
                flag = false;
                tree(city, new LinkedList<String>(branch));
            }
        }
        // выходим из рекурсии и оцениваем собранный результат
        if (resultBranch.size() < branch.size()) {
            resultBranch = new LinkedList<String>(branch);
        }
        // посмотрим на потенциальные варианты
        if (flag) {
            if (!checkBranch(branch)) {
                System.err.println("НАРУШЕНИЕ ПРАВИЛ в варианте " + (varCount + 1));
            }
            System.out.println("вариант " + (++varCount) + "\nкол-во городов " + branch.size() + "\n" + branch);
        }
    }

    /**
     * Чтобы не дублировать. Получение последней буквы для сравнения
     * @param word  слово для выбора последней буквы
     */
    private static String getLastLetter(String word) {
        int pos = word.length();
        if ("ь".equals(word.substring(pos - 1))) {
            pos--;
        }
        return word.substring(pos - 1, pos).toLowerCase();
    }

    /**
     * Проверим ветку на условия задачи, т.е. следование городов согдастно их буквам
     * @param branch испытуемая ветка
     * @return верно ли построена
     */
    private static boolean checkBranch(LinkedList<String> branch) {
        for (int i = 0; i < branch.size() - 2; i++) {
            final String first = branch.get(i);
            final String second = branch.get(i + 1);
            final String s_first = second.substring(0, 1).toLowerCase();
            final String f_last = getLastLetter(first);
            // проверка на соответствию правилам игры
            if (!f_last.equals(s_first)) {
                System.err.println("в варианте " + (varCount + 1) + " " + first + " != " + second + " " + f_last + "<>" + s_first);
                return false;
            }
        }
        return true;
    }
}

 
 
Сообщения:7990
Какая жесть... %)

"Решением" в задачах на алгоритмизацию обычно не принято называть реализации, достигающие результата за экспоненциальное или факториальное время... Например задачу коммивояжёра мы вроде как считаем нерешённой, несмотря на наличие эвристических алгоритмов дающих хорошее в общем-то время... ;-)

А как на самом деле-то задача решается?

Хм... Вообще интересная задачка (хотя наверное в наше время продвинутые какие-нибудь 10-классники знают правильное решение)... Структура данных у нас всё же не дерево, а граф... Ориентированный... И в этом графе нам надо найти путь максимальной длины... Хм... Но в этом случае нам не повезло и задача действительно не решается способами лучшими, чем перебор (другое дело что по школьной памяти подходов к перебору в этом конкретном случае может быть несколько):
http://en.wikipedia.org/wiki/Longest_path_problem

Надо подумать, есть ли для "городов" какие-то нюансы которые отличают эту задачу от поиска максимального пути... Я их что-то не вижу...

www.codeabbey.com - programming problems for novice coders (+ certificates)
 
 
Сообщения:35
Если рассматривать приближенные алгоритмы для решения этой задачи, то наиболее удобным будем алгоритм Флойда( http://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уоршелла), только из нахождения минимального пути сделать максимальное, а расстаяния использывать как 1 и 0 в зависимости от возможности перехода между словами.
Сложность кубического порядка, не хорошо, но терпимо.Решение с большим шансом будет наилучшим.
 
 
Сообщения:7990
Из нахождения минимального пути не сделать максимального если в графе есть циклы. Распространённое заблуждение... %)

Для ациклических графов решение существует и так...

www.codeabbey.com - programming problems for novice coders (+ certificates)
 
 
Сообщения:128
Вот что получилось:

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);
  }
}
 
 
Сообщения:128
Допустим, существует набор городов "Абв", "Акв", "Вба": для данного набора городов возможны два варианта решения и в моем алгоритме будут вычеслены обе цепочки (хотя это не нужно), как оптимизировать алгоритм так чтобы при таком раскладе вычислялась только одна цепочка (не важно какая)?

Как оптимизировать решения для городов с одинаковыми первой и последней буквой ("Анапа")?
 
 
Сообщения:1263
1. никак
2. использовать правило игры: города не повтотряются

 
 
Сообщения:3
Quote:
if (city.toUpperCase().charAt(pos) == 'Й') {
      return 'И';
    }


Эта проверка не правильная, есть слова которые начинаются на Й.
 
 
Сообщения:128
space:
Quote:
if (city.toUpperCase().charAt(pos) == 'Й') {
      return 'И';
    }


Эта проверка не правильная, есть слова которые начинаются на Й.
Это исключение из правил. Согласен, что без документации - выглядит странно.
 
Модераторы:Нет
Сейчас эту тему просматривают:Нет