Задачка

[thedeemon]

Давно хотел предложить общественности порешать такую вот задачку и собрать свежую статистику по языкам.





Дана такая таблица соответствий букв и цифр:

E | J N Q | R W X | D S Y | F T | A M | C I V | B K U | L O P | G H Z
e | j n q | r w x | d s y | f t | a m | c i v | b k u | l o p | g h z
0 |   1   |   2   |   3   |  4  |  5  |   6   |   7   |   8   |   9

Мы хотим использовать ее для записи телефонных номеров словами, чтобы их проще было запоминать.

Функциональные требования

Ваша задача состоит в написании программы, которая для заданного телефонного номера находит все возможные его записи словами и выводит их. Телефонный номер - это произвольная(!) строка из цифр, дефисов (-) и слэшей (/). Дефисы и слэши при переводе в слова не кодируются. Все слова берутся из словаря, который дан в отсортированном по алфавиту ASCII файле (одно слово на строку).

Примечание: словарь немецкий и содержит умляуты, закодированные символом двойные кавычки ("). Этот символ должен быть проигнорирован.

Выводить нужно только такие кодировки (представления номера), которые возможны для этого словаря и в точности соответствуют номеру. Т.е. для некоторых номеров ничего не будет выведено. Слова в словаре содержат буквы (большие и маленькие, но сортировка к регистру нечувствительна), дефисы (-) и двойные кавычки ("). Для кодирования используются только буквы, но слова должны быть выведены точно в том виде, в каком они даны в словаре. Словарь не содержит слов, начинающихся не с буквы.

Кодировка телефонного номера может состоять из одного или нескольких слов, разделенных пробелами. Кодировка создается слово за словом слева направо. Если (и только если) в какой-то определенный момент ни одно слово из словаря не может быть вставлено, можно скопировать одну цифру из номера в кодировку. Две последовательные цифры не разрешаются. Другими словами: в незавершенной кодировке, которая в данный момент покрывает К цифр номера, (К+1)-я цифра номера кодируется сама собой тогда и только тогда, когда К-я цифра номера не была закодирована цифрой и ни одно слово из словаря не может быть использовано для кодирования цифр номера, начиная с (К+1)-й.

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

Словарь для примера:
an
blau
Bo"
Boot
bo"s
da
Fee
fern
Fest
fort
je
jemand
mir
Mix
Mixer
Name
neu
o"d
Ort
so
Tor
Torf
Wasser

Список телефонных номеров:
112
5624-82
4824
0721/608-4067
10/783--5
1078-913-5
381482
04824

Соответствующий вывод программы (на экран):
5624-82: mir Tor
5624-82: Mix Tor
4824: Torf
4824: fort
4824: Tor 4
10/783--5: neu o"d 5
10/783--5: je bo"s 5
10/783--5: je Bo" da
381482: so 1 Tor
04824: 0 Torf
04824: 0 fort
04824: 0 Tor 4

Любой другой вывод (не считая порядка следования строк) считается ошибочным.

Примеры неправильных ответов:
562482: Mix Tor (неверное форматирование номера)
10/783--5: je bos 5 (неверное форматирование второго слова)
4824: 4 Ort, (потому что вместо первой цифры можно было задействовать слова Torf, fort, Tor)
1078-913-5: je Bo" 9 1 da (две последовательных цифры в кодировке)
04824: 0 Tor (кодировка не покрывает весь номер)
5624-82: mir Torf (слишком длинная кодировка)

Количественные требования

Длина слов в словаре: не более 50 символов.
Число слов в словаре: не более 75000.
Длина одного номера: не более 50 символов.
Число телефонных номеров во входном списке: не ограничено.

Качественные требования

Работайте так, как делаете в продакшене. В частности, хорошо комментируйте код.

Основной фокус в процессе создания программы должен быть на ее корректности. Выводите ответ строго по формату, не выводите ничего лишнего.

Ваша программа должна быть эффективной в том смысле, что на каждом шаге добавления слова к кодировке только небольшая часть словаря должна быть проанализирована. Также, программа должна быть эффективной по памяти и не использовать 75000*50 байт для хранения словаря, если он содержит много гораздо более коротких слов. Словарь должен быть целиком размещен в памяти, но входная последовательность слов не должна, т.к. может быть сколь угодно длинной.

Ваша программа не обязана быть устойчивой к некорректным входным данным словаря или телефонных номеров.

Словарь, входные данные и образец выходных данных можно взять тут (307 KB).

Решать можно на любом языке программирования. Если решите, в комментарии к этому посту просьба написать используемый язык, число строк в решении (всего, и без пустых и комментариев), количество часов, потраченных на решение и ссылку на исходники. Приводить идею или исходники решения прямо в комментариях не надо - не портите удовольствие другим. В интернетах эта задача давно известна и решений выложено много, их приводить не надо и подсматривать туда тоже. Известна старая статистика, по которой у разных людей на разных языках на задачу уходило от 2 до 10 часов и от 20 до 500 строк кода.

Comments

[voidex.livejournal.com]

Пиарь у _adept_'а, что ли

[http://users.livejournal.com/_adept_/]

Язык: Haskell
Строк: 129 / 23 / 49 ( это всего / пустых / комментариев )
Часов на решение: 1 (35 мин на код и тесты, 25 на документирование)
Исходники: http://adept.homeunix.net/Phones.hs

[thedeemon.livejournal.com]

Отлично, спасибо!

[thedeemon.livejournal.com]

Все верно, оттуда и взял. Но нужна свежая статистика и языки, присоединяйтесь!