![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonДавно хотел предложить общественности порешать такую вот задачку и собрать свежую статистику по языкам.
Дана такая таблица соответствий букв и цифр:
Мы хотим использовать ее для записи телефонных номеров словами, чтобы их проще было запоминать.
Функциональные требования
Ваша задача состоит в написании программы, которая для заданного телефонного номера находит все возможные его записи словами и выводит их. Телефонный номер - это произвольная(!) строка из цифр, дефисов (-) и слэшей (/). Дефисы и слэши при переводе в слова не кодируются. Все слова берутся из словаря, который дан в отсортированном по алфавиту 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 строк кода.
Дана такая таблица соответствий букв и цифр:
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 строк кода.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-11-16 09:56 am (UTC)Строк: 129 / 23 / 49 ( это всего / пустых / комментариев )
Часов на решение: 1 (35 мин на код и тесты, 25 на документирование)
Исходники: http://adept.homeunix.net/Phones.hs
no subject
Date: 2009-11-16 10:37 am (UTC)no subject
Date: 2009-11-19 03:09 am (UTC)