/phone-numbers-encoding

Primary LanguageRust

Задача

Дано следующее кодирование цифр в буквы (каждой цифре соответствует одна или более буква, регистр буквы значения не имеет):

  • 0: e
  • 1: j n q
  • 2: r w x
  • 3: d s y
  • 4: f t
  • 5: a m
  • 6: c i v
  • 7: b k u
  • 8: l o p
  • 9: g h z

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

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

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

Результат кодирование состоит из одного или нескольких слов, разделенных пробелами. Кодирование выполняется последовательно, одно слово за другим, слева направо. Если в определенный момент никакое слово из словаря не подходит, то можно скопировать одну цифру из телефонного номера (вставить её на место одного из слов). Две и более цифры друг за другом не допустимы.

In a partial encoding that currently covers k digits, digit k+1 is encoded by itself if and only if, first, digit k was not encoded by a digit and, second, there is no word in the dictionary that can be used in the encoding starting at digit k+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: использована цифра 4, хотя на её место подходят слова Torf fort Tor
  • 1078-913-5: je Bo" 9 1 da: две последовательные цифры
  • 04824: 0 Tor: не все цифры номера использованы
  • 5624-82: mir Torf: букв в выводе больше чем исходных цифр (использовано больше цифр, чем в номере)

Совет

Если программа выводит лишние ответы (по сравнению с эталонным output.txt), проверьте ваш алгоритм кодирования: вставлять цифру из иходного номера можно только в том случае, если ни одно из слов словаря не подходит.

Для проверки предоставлены файлы input.txt, output.txt и dictionary.txt

Ограничения

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

Программа должна быть корректной, так как будет протестирована на большем объеме входных данных.

Программа должна быть эффективной как по использованию времени процессора, так и по использованию памяти.