SPOJ.com - Problem PROG0372

PROG0372 - Cryptograms

no tags

A cryptogram is a type of puzzle that consists of a short piece of encrypted text. Though once used in more serious applications, they are now mainly printed for entertainment in newspapers and magazines. Generally the cipher used is simple enough that the cryptogram can be solved by hand. In its simplest form, a substitution cipher is used that encrypts the text by replacing each letter in the alphabet with a different letter. An uppercase letter and its corresponding lowercase counterpart are thereby always mapped onto the same letter, where the use of uppercase and lowercase is maintained. Characters that represent no letters of the alphabet remain unchanged in the ciphertext. To solve the puzzle, one must figure out the mapping of the letters using in the coding scheme, such that the original lettering can be recovered.

Example cryptogram.

Assignment

Write a function cryptogram that takes two string arguments that have an equal length. The first string represents the encrypted text given as the cryptogram puzzle. The second string represents a partial solution of the cryptogram. In that solution, some of the letter occurrences have already been replaced by their corresponding letter used in the mapping scheme. Letters that have not been replaced yet in the partial solution, are indicated by a question mark (?). The function must return a string that replaces as many characters as possible in the partial solution by their corresponding letter (while maintaining the use of uppercase and lowercase letters), based on the letters that have already been replaced.

Example

>>> puzzle = 'Qmvrbwlf xwkd iopzlw vf zml pcwvfxzvyl.'
>>> solution = 'Ch?ld??? ??ow fas??r ?n ??? ?p?i?gt?me.'
>>> cryptogram(puzzle, solution)
'Children grow faster in the springtime.'

>>> puzzle = 'Zhp suxobpuw sbmtkopw Nxwkdnx.'
>>> solution = '?h? p?n???a? ?rod?ces I???l??.'
>>> cryptogram(puzzle, solution)
'?he pancreas prod?ces Ins?lin.'

>>> puzzle = 'Jujso ldmtq wyjqi tvadi ltek tq lads tw t wcqnej xjee.'
>>> solution = '?v?ry ??ma? ?p??? ?bout h??f ?? ???? ?s ? ??ng?e c?l?.'
>>> cryptogram(puzzle, solution)
'Every human spent about half an hour as a s?ngle cell.'

>>> puzzle = "V atult'a amrdd qvl zr nrbrqbrn zx v wumvl v medr vivx."
>>> solution = "? ????k's ???l? ??n ?? ??t???ed ?y a hum?? ? ?i?? ?w??."
>>> cryptogram(puzzle, solution)
"A skunk's smell ?an ?e dete?ted ?y a human a mile away."

Een cryptogram is een soort puzzel waarbij een korte gecodeerde tekst gegeven wordt. Bij het coderen werden alle letters van het alfabet één-op-één afgebeeld op een andere letter van het alfabet. Een hoofdletter en zijn corresponderende kleine letter worden daarbij steeds op dezelfde letter afgebeeld, waarbij het gebruik van hoofdletters en kleine letters behouden blijft. Karakters die geen letters voorstellen blijven ongewijzigd in de gecodeerde tekst. Om de puzzel op te lossen moet de gebruikte afbeelding van de letters achterhaald worden, zodat de oorspronkelijke tekst terug kan gereconstrueerd worden. Ondanks het feit dat cryptogrammen ooit gebruikt werden voor meer serieuze toepassingen, vinden we ze de dag van vandaag hoofdzakelijk terug in kranten en tijdschriften waar ze tot ontspanning dienen voor de lezers.

Voorbeeld van een cryptogram.

Opgave

Schrijf een functie cryptogram waaraan twee stringargumenten moeten doorgegeven worden die even lang zijn. De eerste string stelt de gegeven tekst voor uit de opgave van een cryptogrampuzzel. De tweede string stelt een gedeeltelijke oplossing van het cryptogram voor. Hierbij werden sommige voorkomens van letters reeds vervangen door hun corresponderende letter. Letters van de gedeeltelijke oplossing die nog niet werden vervangen, worden aangegeven door een vraagteken (?). De functie moet een string teruggeven die zoveel mogelijk vraagtekens uit de gedeeltelijke oplossing vervangt door hun corresponderende letter (met behoud van hoofdletters en kleine letters), op basis van de letters die reeds werden vervangen.

Voorbeeld

>>> opgave = 'Qmvrbwlf xwkd iopzlw vf zml pcwvfxzvyl.'
>>> oplossing = 'Ch?ld??? ??ow fas??r ?n ??? ?p?i?gt?me.'
>>> cryptogram(opgave, oplossing)
'Children grow faster in the springtime.'

>>> opgave = 'Zhp suxobpuw sbmtkopw Nxwkdnx.'
>>> oplossing = '?h? p?n???a? ?rod?ces I???l??.'
>>> cryptogram(opgave, oplossing)
'?he pancreas prod?ces Ins?lin.'

>>> opgave = 'Jujso ldmtq wyjqi tvadi ltek tq lads tw t wcqnej xjee.'
>>> oplossing = '?v?ry ??ma? ?p??? ?bout h??f ?? ???? ?s ? ??ng?e c?l?.'
>>> cryptogram(opgave, oplossing)
'Every human spent about half an hour as a s?ngle cell.'

>>> opgave = "V atult'a amrdd qvl zr nrbrqbrn zx v wumvl v medr vivx."
>>> oplossing = "? ????k's ???l? ??n ?? ??t???ed ?y a hum?? ? ?i?? ?w??."
>>> cryptogram(opgave, oplossing)
"A skunk's smell ?an ?e dete?ted ?y a human a mile away."

Submit solution!

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