SPOJ.com - Problem PROG0363

PROG0363 - Phone words

no tags

Apart from a digit, most telephones also depict a sequence of letters on each key of the device. Usually, the following mapping holds between letters and digits: 2=ABC, 3=DEF, 4=GHI, 5=JKL, 6=MNO, 7=PQRS, 8=TUV, 9=WXYZ. No letters are mapped to the keys 0 and 1. These letters have had several auxiliary uses.

The letters have also been used, mainly in the United States, as a way of remembering telephone numbers easily. For example, these letters were used as a reminder for telephone numbers (mainly in the United States). A company that sales flowers, could for example licence the phone number 1-800-356-9377 and advertise it as the mnemonic phone word 1-800-FLOWERS.

In recent times, the letters on the keys are needed also for entering text on mobile phones, for text messaging, entering names in the phone book, etc. A word is entered on a telephone supporting the T9 system (Text on 9 keys) by a single keypress for each key on which the letter is mapped. To enter the word Hello, one would press the following sequence of keys 4 (GHI), 3 (DEF), 5 (JKL), 5 (JKL) and 6 (MNO). The T9 system will then look up in a dictionary all words corresponding to the sequence of keypresses. If there are multiple words that correspond to the sequence of keypresses, the user can select the intended word from a list. This usually works a lot faster than each individual letter using multiple keypresses as in the MultiTap approach used in conventional mobile phone text entry.

Assignment

For this assignment you are asked to compose a dictionary that can be used by a mobile phone that supports the T9 system. This is done in the following way:

Write a function key that is passed a word containing only letters. The function must return a string of digits, corresponding to the sequence of keypresses that needs to be given to enter a word in a mobile phone that supports the T9 system. The function must treat words case insensitive.
Write a function dictionary that takes a container (e.g. a list, a tuple or a set) of words. The function must return a dictionary, that maps each sequence of keypresses needed to enter any of the given words to the set of all words that can be formed by this sequence of keypresses.

Example

>>> key('FLOWERS')
'3569377'
>>> key('surpassing')
'7877277464'
>>> key('brutifying')
'2788439464'
>>> key('hematurias')
'4362887427'

>>> dictionary(['languisher', 'requesters', 'desecrates', 'impostumes', 'recessions', 'fluoresces', 'franchisee', 'sequesters', 'holinesses', 'perverters', 'bellyacher', 'succincter', 'encourages', 'refinishes', 'lawbreaker', 'blabbering', 'effacement'])
{'5292732537': {'lawbreaker'}, '7378378377': {'sequesters', 'perverters', 'requesters'}, '5264847437': {'languisher'}, '3332236368': {'effacement'}, '4654637737': {'holinesses'}, '3726244733': {'franchisee'}, '7323774667': {'recessions'}, '4676788637': {'impostumes'}, '7334647437': {'refinishes'}, '3373272837': {'desecrates'}, '2355922437': {'bellyacher'}, '2522237464': {'blabbering'}, '7822462837': {'succincter'}, '3626872437': {'encourages'}, '3586737237': {'fluoresces'}}

Op de meeste telefoontoestellen staat er naast een cijfer vaak ook een reeks letters elke toets van het toestel. Doorgaans wordt de volgende afbeelding tussen cijfers en letters gebruikt: 2=ABC, 3=DEF, 4=GHI, 5=JKL, 6=MNO, 7=PQRS, 8=TUV, 9=WXYZ. Op de toetsen 0 en 1 worden geen letters afgebeeld. Dit is ook de afbeelding die we in deze opgave zullen gebruiken. Deze letters werden in het verleden voor verschillende doeleinden gebruikt.

Zo werden deze letters (voornamelijk in de Verenigde Staten) gebruikt als een manier om telefoonnummers makkelijk te kunnen onthouden. Een bedrijf dat bloemen verkocht, kon dan bijvoorbeeld het telefoonnummer 1-800-356-9377 aanvragen en in zijn advertenties gebruik maken van het beter te onthouden telefoonwoord 1-800-FLOWERS.

Meer recent worden de letters op de toetsen gebruikt om tekst in te geven op mobiele telefoontoestellen. Om een woord in te geven, worden bij toestellen die T9 (Tekst op 9 toetsen) gebruiken, achtereenvolgens de toetsen die corresponderen met elke letter van het woord ingegeven. Wil je bijvoorbeeld de tekst Hallo intypen, dan druk je achtereenvolgens één keer op de volgende toetsen: 4 (GHI), 2 (ABC), 5 (JKL), 5 (JKL) en tenslotte 6 (MNO). Het T9-systeem zal daarna in het ingebouwde woordenboek zoeken naar alle mogelijke woorden die met deze cijfercombinatie kunnen gevormd worden. Indien er meerder mogelijkheden zijn, dan moet de gebruiker het bedoelde woord uit de lijst kiezen. Dit werkt doorgaans een stuk sneller dan het kiezen van de individuele letters via MultiTap.

Opgave

Voor deze opgave moet je een woordenboek samenstellen dat gebruikt kan worden door een mobiele telefoon die het T9-systeem gebruikt. Hiervoor ga je als volgt te werk.

Schrijf een functie sleutel waaraan een woord dat enkel bestaat uit letters kan doorgegeven worden. De functie moet een string van cijfers teruggeven, die correspondeert met de reeks toetsen die moet ingegeven worden om het woord in te voeren op een mobiele telefoon die werkt met het T9-systeem. De functie mag hierbij geen onderscheid maken tussen hoofdletters en kleine letters.
Schrijf een functie woordenboek waaraan een container (bv. een lijst, een tuple of een verzameling) van woorden kan doorgegeven worden. De functie moet een dictionary teruggeven, die elke cijfercombinatie die resulteert in één van de gegeven woorden afbeeldt op de verzameling van alle gegeven woorden die door deze combinatie kunnen gevormd worden.

Voorbeeld

>>> sleutel('FLOWERS')
'3569377'
>>> sleutel('levensgang')
'5383674264'
>>> sleutel('zendgebied')
'9363432433'
>>> sleutel('gesitueerd')
'4374883373'

>>> woordenboek(['verwijdert' , 'wanddiktes' , 'nieuwsbron' , 'verwildert' , 'gehamsterd' , 'binoculair' , 'zandfilter'])
{'2466285247': {'binoculair'}, '9263345837': {'zandfilter', 'wanddiktes'}, '8379453378': {'verwildert', 'verwijdert'}, '6438972766': {'nieuwsbron'}, '4342678373': {'gehamsterd'}}

Submit solution!

Added by:	Peter Dawyndt
Date:	2013-04-03
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None