SPOJ.com - Problem PROG0389

PROG0389 - Lingo

no tags

Lingo is a game in which a word has to be guessed. The amount of letters of the word is given, and usually also the first letter is known. To guess the word, the player can say a word of the right amount of letters. The computer then indicates which letters are correct and in the right place and which letters occur in the word that needs to be guessed, but aren't in the right place. In the example underneath the two kinds of tips are respectively indicated with a red and a yellow color.

If you weren't already familiar with the game, you could play it online here as an example to train yourself. But be careful, it may be addictive.

Assignment

Write a function lingo with two parameters: guessed and searched. Strings should be given to both parameters that respectively contain a word that was given by the user and the hidden word the user must find. You may assume that both strings consist of lowercase letters and have the same length. The function must print a string as a result that contains a word that the user has given, but of which the letters that are correct and in the right place are between square brackets and the letters that do occur in the word to be guessed but are not in the correct place between round brackets. Here, we should observe the rules below:

One letter from the searched word can never lead to multiple markings in the guessed word. If a letter occurs multiple times in the word searched, the letters that are in the right place should be marked before the letters that are not in the right place.
If a certain letter from the searched word occurs two or more times in the word guessed, and one of them is in the right place, this position should be marked.
If a certain letter from the searched word occurs twice or more in the guessed word, but all of them are in the wrong place, the leftmost position should be marked.
Consecutive letters that are between two square brackets, should all be placed between one pair of square brackets.
Consecutive letters that are between two round brackets, should all be placed between one pair of round brackets.

Example

>>> lingo('camelot', 'cembalo')
'[c](a)[m](elo)t'
>>> lingo('inquisition', 'reconquista')
'(inqu)i(s)i(t)i(o)n'
>>> lingo('python', 'embryo')
'p(y)th(o)n'
>>> lingo('megalomaniacally', 'circumstantiated')	 
'(me)g(a)loma(ni)a(c)[a]lly'

Lingo is een spelletje waarbij een woord moet geraden worden. Het aantal letters van dit woord is gegeven, en doorgaans wordt ook de eerste letter gegeven. Om het woord te achterhalen kan de speler een woord met het juiste aantal letters opgeven. De computer geeft dan aan welke letters correct zijn en op de juiste plaats staan, en welke letters wel voorkomen in het woord dat moet geraden worden, maar niet op de juiste plaats staan. In onderstaand voorbeeld worden deze twee soorten tips respectievelijk aangeduid met een rode en een gele kleur.

Als je nog niet met dit spelletje vertrouwd zou zijn, dan kan je het bijvoorbeeld hier eens online spelen om het in de vingers te krijgen. Maar pas op, het kan verslavend werken.

Opgave

Schrijf een functie lingo met twee parameters: geraden en gezocht. Aan beide parameters moeten strings doorgegeven worden die respectievelijk een woord bevatten dat de gebruiker heeft opgegeven, en het verborgen woord dat door de gebruiker moet gezocht worden. Je mag ervan uitgaan dat beide strings enkel bestaan uit kleine letters en even lang zijn. De functie moet een string als resultaat teruggeven die het woord bevat dat de gebruiker heeft opgegeven, maar waarvan de letters die correct zijn en op de juiste plaats staan tussen vierkante haakjes staan en de letters die wel in het te raden woord voorkomen maar niet op de juiste plaats staan tussen ronde haakjes staan. Hierbij moeten de volgende regels in acht genomen worden:

Eenzelfde letter uit het gezochte woord kan nooit leiden tot meerdere markeringen in het geraden woord. Als een bepaalde letter meerdere keren voorkomt in het gezochte woord, dan moeten letters die in het geraden woord op de juiste plaats staan prioritair gemarkeerd worden boven letters die niet op de juiste plaats staan.
Als een bepaalde letter uit het gezochte woord twee of meer keer voorkomt in het geraden woord, en bij één van die voorkomens staat de letter ook op de juiste positie, dan moet deze positie gemarkeerd worden.
Als een bepaalde letter uit het gezochte woord twee of meer keer voorkomt in het geraden woord, maar alle voorkomens staan op de verkeerde positie, dan moet de meest links van deze posities gemarkeerd worden.
Opeenvolgende letters die allemaal tussen vierkante haakjes staan, moeten samen tussen één paar vierkante haakjes geplaatst worden.
Opeenvolgende letters die allemaal tussen ronde haakjes staan, moeten samen tussen één paar ronde haakjes geplaatst worden.

Voorbeeld

>>> lingo('camelot', 'cembalo')
'[c](a)[m](elo)t'
>>> lingo('inquisition', 'reconquista')
'(inqu)i(s)i(t)i(o)n'
>>> lingo('python', 'embryo')
'p(y)th(o)n'
>>> lingo('megalomaniacally', 'circumstantiated')	 
'(me)g(a)loma(ni)a(c)[a]lly'

Submit solution!

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