В компании A* задали такую тестовую задачку.

Задание: необходимо разбить слово на составные части (приставка, корень, суффикс, окончание).
Вводим: прекрасный
Выводим: пре-крас-н-ый

Укажите, сколько времени у вас заняло выполнение этого задания.

Мое решение по каким-то причинам не подошло.
Комментарии от компании я пока не получил.
Поэтому хочу услышать критику к моему решению от Вас.

#include <set>
#include <vector>
#include <string>
#include <fstream>
#include <iostream>
#include <algorithm>

#include <cassert>

typedef std::set< std::string > strings_t;

/**
 * Loads set of lines from file. Reverse strings if required
*/
void load_strings(const char *file, strings_t *strings, int *max_length, bool reverse) {
    std::ifstream is(file);
    std::string buffer;
    *max_length = 0;
    while (is.good()) {
        std::getline(is, buffer);
        if (!buffer.empty()) { 
            if (reverse) { std::reverse(buffer.begin(), buffer.end()); }
            *max_length = std::max((int)buffer.length(), *max_length);
            strings->insert(buffer);
        }
    }
}

/**
 * Returns max match length from set for given iterator
*/
template < typename TIter >
int match_strings(TIter it, TIter end, const strings_t &strings, int max_length) {
    std::string match;
    match.reserve(max_length);
    int max_match = 0;
    while (it != end && match.length() < max_length) {
        match += *it++;
        if (strings.find(match) != strings.end()) {
            max_match = match.length();
        }
    }
    return max_match;
}

int main(int argc, char* argv[]) {

    strings_t prefixes, suffixes, endings;
    int prefix_length, suffix_length, ending_length;

    if (argc < 3) {
        std::cerr << "Usage: " << argv[0] 
            << " prefixes.txt suffixes.txt endings.txt" << std::endl;
        return 1;
    }

    load_strings(argv[1], &prefixes, &prefix_length, false);
    load_strings(argv[2], &suffixes, &suffix_length, true);
    load_strings(argv[3], &endings, &ending_length, true);

    std::string input;
    std::getline(std::cin, input);

    std::cerr << input << std::endl;

    std::string::iterator dit = input.begin(), dend = input.end();
    std::string::reverse_iterator rit = input.rbegin(), rend = input.rend();

    int prefix = match_strings(dit, dend, prefixes, prefix_length);
    int ending = input.length() - match_strings(rit, rend, endings, ending_length);
    int suffix = ending;

    // NOTE: assume that there are no suffixes without endings
    if (!ending < input.length()) {
        rit += input.length() - ending;
        suffix -= match_strings(rit, rend, suffixes, suffix_length);
    }

    assert(prefix <= suffix);

    std::cout << input.substr(0, prefix) << "-";
    std::cout << input.substr(prefix, suffix - prefix) << "-";
    std::cout << input.substr(suffix, ending - suffix) << "-";
    std::cout << input.substr(ending) << std::endl; 

    return 0;
}

Здравствуйте, insearch, Вы писали:

I>В компании A* задали такую тестовую задачку.

I>

I>Задание: необходимо разбить слово на составные части (приставка, корень, суффикс, окончание).
I>Вводим: прекрасный
I>Выводим: пре-крас-н-ый

I>Укажите, сколько времени у вас заняло выполнение этого задания.

I>Мое решение по каким-то причинам не подошло.
I>Комментарии от компании я пока не получил.
I>Поэтому хочу услышать критику к моему решению от Вас.

Очень интересная задача. По-моему слабое место в понимании языка. Прежде всего нужно искать корень. И думаю что не по списку корней.

Здравствуйте, insearch, Вы писали:

I>В компании A* задали такую тестовую задачку.

I>

I>Задание: необходимо разбить слово на составные части (приставка, корень, суффикс, окончание).
I>Вводим: прекрасный
I>Выводим: пре-крас-н-ый

I>Укажите, сколько времени у вас заняло выполнение этого задания.

I>Мое решение по каким-то причинам не подошло.
I>Комментарии от компании я пока не получил.
I>Поэтому хочу услышать критику к моему решению от Вас.

Ты филолог? Я например нет, потому даже не буду думать как это сделать. Если да, то не у программистов спрашивай, а у тех кто естественными языками занимается, таких знать ты должен А уж алгоритм запрограммировать в такой задаче дело десятое.

Здравствуйте, Ytz, Вы писали:

Ytz>Ты филолог? Я например нет, потому даже не буду думать как это сделать. Если да, то не у программистов спрашивай, а у тех кто естественными языками занимается, таких знать ты должен А уж алгоритм запрограммировать в такой задаче дело десятое.

Речь идет о ТЕСТОВОМ задании, которое высылают на дом пред собеседованием.
На сколько я знаю, проекты компании к лингвистике никакого отношения не имеют.

Здравствуйте, insearch, Вы писали:

I>Здравствуйте, Ytz, Вы писали:

Ytz>>Ты филолог? Я например нет, потому даже не буду думать как это сделать. Если да, то не у программистов спрашивай, а у тех кто естественными языками занимается, таких знать ты должен А уж алгоритм запрограммировать в такой задаче дело десятое.

I>Речь идет о ТЕСТОВОМ задании, которое высылают на дом пред собеседованием.

Это понятно.

I>На сколько я знаю, проекты компании к лингвистике никакого отношения не имеют.

Ну и зачем тогда тебе эта компания? Выполнить это задание без глубокого понимания предметной области нельзя. Сразу написал бы им об этом.

Здравствуйте, insearch, Вы писали:

I>В компании A* задали такую тестовую задачку.
I>Укажите, сколько времени у вас заняло выполнение этого задания.

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

Здравствуйте, Кодёнок, Вы писали:

Кё>Первое что приходит в голову — должно быть есть в открытом доступе библиотека для этого, и именно способность ее найти и применить и тестируется. Потому что в лоб это не решается, а изучать предметную область ради тестового задания это бред.

Спасибо, интересная точка зрения.

P.S. Забыл добавить. Перед определением частей слова желательно разбить слово на слоги.
Может это вообще через Word делается

Здравствуйте, insearch, Вы писали:


I>Укажите, сколько времени у вас заняло выполнение этого задания.

Вот в этом месте и сконцентрирован юмор. Тот факт, что вы на полном серьёзе взялись решать эту "тестовую задачу" и привёл к тому, что ...решение по каким-то причинам не подошло...

Здравствуйте, insearch, Вы писали:

I>В компании A* задали такую тестовую задачку.

I>

I>Задание: необходимо разбить слово на составные части (приставка, корень, суффикс, окончание).
I>Вводим: прекрасный
I>Выводим: пре-крас-н-ый

I>Укажите, сколько времени у вас заняло выполнение этого задания.

Задание некорректно.
Во-первых, "слово" — понятие растяжимое. "Ой", "ёж", "какая" — тоже слова.
Во-вторых, даже если мы заранее оговариваем, что слова у нас — исключительно прилагательные, нет никаких гарантий, что там обязательно встретится ровно одна приставка, суффикс, и будет ненулевое окончание. "Распрекраснейший", "непредвиденный", "ясен" (пень).
В-третьих, поиск границ между морфемами с использованием списков — не всегда хорош. "Предзакатный", "предательский", "предельный" — как отличить "пред-" от "пре-"?

I>Мое решение по каким-то причинам не подошло.

Ввиду того, что задание некорректное, оценивали, скорее всего, по независящим от здравого смысла параметрам — например, по количеству использованных в коде указателей, или по наличию (вариант: отсутствию) комментариев, или по использованию (вариант: неиспользованию) STL.

I>Комментарии от компании я пока не получил.

И не надейся.
Конторы к выполненным тестовым заданиям практически никогда не дают комментариев — в частности потому, что критерии оценки могут зависеть от положения левой пятки проверяющего.

I>Поэтому хочу услышать критику к моему решению от Вас.

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

Причина — опять же, не в тебе, а в них: задание изначально составлено некорректно.

Но если бы его выполнял я — я бы сделал все гораздо проще:
1. Берем слово.
2. Открываем большо-о-ой файл базы данных, где для каждого известного в русском языке слова дается его разбивка на морфемы (возможно, с несколькими вариантами).
3. Ищем там наше слово и выводим найденные варианты. Если слово не найдено — выводим его как есть.

Отсылаем саму программу (10 строчек), а за базу данных требуем денег.

Здравствуйте, insearch, Вы писали:

Может они хотели проверить умеете ли вы пользоваться гуглом и использовать чужие библиотеки?
зы: Это не сарказм и не стеб, такое действительно вполне возможно, потому что задача то явно не тестовая

Эта задача очень старая и называется stemming http://en.wikipedia.org/wiki/Stemming
Вероятно от вас ожидалось что
а) вы хотя бы умеете пользоваться гуглом и найдете стандартные подходы к ее решению
б) возьмете какой-нибудь готовый словарь\подход и реализуете его
в) у вас в коде будут хотя бы зачатки понимания алгоритмов, а не тупой брутфорс
г) вы проявите минимальную культуру и будете хотя бы использовать Unicode и сравнивать строки case-insensitive

Здравствуйте, rm822, Вы писали:

R>Эта задача очень старая и называется stemming http://en.wikipedia.org/wiki/Stemming
R>Вероятно от вас ожидалось что
R>а) вы хотя бы умеете пользоваться гуглом и найдете стандартные подходы к ее решению
R>б) возьмете какой-нибудь готовый словарь\подход и реализуете его
R>в) у вас в коде будут хотя бы зачатки понимания алгоритмов, а не тупой брутфорс
R>г) вы проявите минимальную культуру и будете хотя бы использовать Unicode и сравнивать строки case-insensitive

А кто за это заплатит?

Здравствуйте, insearch, Вы писали:

I>В компании A* задали такую тестовую задачку.

I>[q]
I>Задание: необходимо разбить слово на составные части (приставка, корень, суффикс, окончание).
I>Вводим: прекрасный
I>Выводим: пре-крас-н-ый

Я так понимаю, здесь неверно выбраны входные данные.
Простым поиском частей слова здесь явно не обойтись.

Все слова в словаре следует представить в виде примерно таких правил:

пре-крас-н-ый

// приставки
приставка=["пре", прилагательное]
...

// корни
корень=["крас", существительное, прилагательное]
...

// суффиксы
суффикс=["н", прилагательное]
...

// окончания
окончание=["ый", прилагательное]
...


Анализ производим справа налево или используем обратный словарь русского языка.

Нашли окончание "ый" -> определили, что слово является прилагательным -> ищем в суффиксах для прилагательных -> находим "н" ->
ищем корень для прилагательных -> находим "крас" и т.д.

Это очень схематично. На самом деле все намного сложнее.
Если интересно, то в библиотеке можно найти автора, который приводит схемы, таблицы, и вообще как это все делается.
Интересовался в школе еще, но забил за ненадобностью

I>Задание: необходимо разбить слово на составные части (приставка, корень, суффикс, окончание).
Задача не решаема алгоритмически.

5er>Нашли окончание "ый" -> определили, что слово является прилагательным
Ага. Хан Батый, например.

Похожее тестовое задание в свое время делал для Консультант Плюс. Давался месяц, у них было свое используемое решение, за улучшение которого на сколько — то процентов был бы респект. В общем типо Netflix Prize для особых талантов.