среда, 9 сентября 2009 г.

Code Jam

Недавно прошел первый квалификационный раунд конкурса Google Code Jam. Я в нем не участвовал, но, ради развлечения, решил одну из задач - alien language. Суть задачи такова: у нас есть две последовательности строк. Первая, состоит из N разных строк одинаковой длины(abc, cda, ...). Вторая - из М строк вида: (abc)cd, где в скобках перечислены все возможные значения, которые являются шаблонами для поиска в первой последовательности. К примеру, шаблону (abc)cd, будут соответствовать три строки - acd, bcd и ccd. Цель - посчитать количество строк из первой последовательности, которые соответствуют каждому из шаблонов из второй последовательности.
Решение в лоб - создать хэш таблицу из элементов первой последовательности. Затем для каждого из шаблонов, получить список всех возможных строк, которые соответствуют данному шаблону. После этого нужно выполнить поиск каждой из созданных строк в хэш таблице. Нам нужно определить количество удачных операций поиска для каждого из шаблонов.
Не трудно понять, что уже при достаточно небольшой длине строки, мы получим комбинаторный взрыв. Количество вариантов, которые нужно проверить будет огромным. Самое простое решение задачи - преобразовать каждый из шаблонов в регулярное выражение, а затем посчитать количество совпадений. Но, это совсем не интересно :) Вместо этого, я построил свой алгоритм, который не перебирает все возможные строки, подходящие к шаблону. Он ищет(и считает) совпадения в дереве, каждый узел которого может содержать до 26-ти потомков(на рисунке). Каждый из потомков соответствует одному из символов английского алфавита. Первому уровню дерева(узел показан зеленым цветом) соответствуют первые символы всех строк входной последовательности. Второму уровню(показан синим) - вторые символы, и так далее... Соответственно, что-бы проверить, есть-ли строка "abc" среди входных данных, нужно проверить, есть-ли в корневом узле дерева, поддерево, соответствующее символу 'a', затем, рекурсивно, найти в этом поддереве потомка, соответствующего символу 'b' и тд. Затем, если мы прошли ветвь дерева, соответствующую строке "abc", мы легко можем перейти к ветви, соответствующей подстроке "abd" либо "abb". В общем, алгоритм обхода дерева достаточно очевиден.
Работает это правильно и достаточно шустро. Я не измерял время работы, но по ощущениям, большой набор данных, был обработан не больше чем за две секунды :)

11 комментариев:

Alexander Smal комментирует...

Как то уж очень сложно. Решение в лоб - просто сравнить каждое слово с шаблоном, а уж точно не генерировать все возможные слова. Решение поумнее - превратить шаблон во что-то более удобное (ака прекомпиляция шаблона).

Вот мое решение: прекомпилируем шаблон в табличку 26 * (длина слова). И проставляем единички где надо.
http://pastebin.com/m509ce9db

Cyril комментирует...

Поздравляю! Вы изобрели бор :)

Александр комментирует...

Да, я тоже простецки все сделал. Разобрал шаблоны просто в представление в памяти (map'ы) чтобы линейно не искать каждый раз. И потом просто для каждого слова проверял по map'у есть какая-то буква или нет.

Lazin комментирует...

Вот мое решение: прекомпилируем шаблон в табличку 26 * (длина слова). И проставляем единички где надо.
http://pastebin.com/m509ce9db

Да, ваш вариант более правильный. Зато мой вариант позволяет не только считать совпадения, но и искать их. Хотя в данной задаче это совершенно не нужно :)
Поздравляю! Вы изобрели бор :)
Спасибо, буду знать как это называется xD

Alexander Smal комментирует...

Дык и мой позволяет искать совпадения - я для каждой строчки проверяю, совпадает она или нет. Или я что-то неправильно понял?

Lazin комментирует...

> Или я что-то неправильно понял?
это я неправильно понял алгоритм, пардон ))

Анонимный комментирует...

2Lazin: уточните свой алгоритм - вы строите дерево по множеству слов или по множеству шаблонов? Если первый вариант, то каким образом обрабатывается каждый шаблон?

Анонимный комментирует...

2Lazin: уточните свой алгоритм - вы строите дерево по множеству слов или по множеству шаблонов? Если первый вариант, то каким образом обрабатывается каждый шаблон?

Анонимный комментирует...
Этот комментарий был удален администратором блога.
Lazin комментирует...

Вот мое решение: прекомпилируем шаблон в табличку 26 * (длина слова). И проставляем единички где надо.
http://pastebin.com/m509ce9db

Да, ваш вариант более правильный. Зато мой вариант позволяет не только считать совпадения, но и искать их. Хотя в данной задаче это совершенно не нужно :)
Поздравляю! Вы изобрели бор :)
Спасибо, буду знать как это называется xD

Alexander Smal комментирует...

Как то уж очень сложно. Решение в лоб - просто сравнить каждое слово с шаблоном, а уж точно не генерировать все возможные слова. Решение поумнее - превратить шаблон во что-то более удобное (ака прекомпиляция шаблона).

Вот мое решение: прекомпилируем шаблон в табличку 26 * (длина слова). И проставляем единички где надо.
http://pastebin.com/m509ce9db