PROG0210 - Word search

Een woordzoeker is een puzzel waarbij men een aantal gegeven woorden moet zoeken in een rechthoekig rooster gevuld met letters. Deze woorden kunnen zowel van links naar rechts, van rechts naar links, van boven naar onder als van onder naar boven in het rooster neergeschreven staan. Het is mogelijk dat dezelfde letter voor meerdere woorden moet gebruikt worden. De letters die voor geen enkel van de opgegeven woorden gebruikt worden, lezen van links naar rechts en van boven naar onder als een nieuw woord dat de oplossing van de puzzel vormt.

woordzoeker
Werk de woordzoeker verder af en vind het verborgen woord (SKARN).

Opgave

Definieer een klasse Woordzoeker die minstens ondersteuning biedt voor volgende methoden:

  1. Een initialisatiemethode __init__ waaraan verplicht drie argumenten moeten doorgegeven worden: een aantal rijen $r$, een aantal kolommen $k$ en een string $s$ die enkel bestaat uit letters. Deze methode moet ervoor zorgen dat alle objecten van de klasse Woordzoeker een attribuut rooster hebben, dat een rechthoekig $r \times k$ rooster voorstelt waarin de opgegeven letters worden uitgespeld van links naar rechts en van boven naar onder. Alle letters moeten hierbij omgezet worden naar hoofdletters. Bestudeer onderstaand voorbeeld om te achterhalen wat er moet gebeuren indien de opgegeven string $s$ minder dan $rk$ letters bevat.
  2. Een methode rijen zonder argumenten, die teruggeeft hoeveel rijen het rooster van de woordzoeker telt.
  3. Een methode kolommen zonder argumenten, die teruggeeft hoeveel kolommen het rooster van de woordzoeker telt.
  4. Een methode __str__ zonder argumenten die een stringvoorstelling van de woordzoeker teruggeeft. De opeenvolgende regels van deze stringvoorstelling bestaat uit de opeenvolgende rijen van het rooster, waarbij de letters op eenzelfde rij achter elkaar uitgeschreven worden.
  5. Een methode lees waaraan verplicht de volgende vier argumenten moeten doorgegeven worden: i) een rijnummer, ii) een kolomnummer, iii) een richting en iv) een lengte. Voor rij- en kolomnummers begint men te tellen vanaf 0. De methode moet als resultaat het woord teruggeven dat in het rooster kan gelezen worden in de opgegeven richting beginnend vanaf de cel in de opgegeven rij en kolom. Er zijn vier mogelijke richtingen waarin het woord kan uitgelezen worden, die telkens worden aangegeven met een string van twee letters: LR (van links naar rechts), RL (van rechts naar links), BO (van boven naar onder) en OB (van onder naar boven). De lengte van het uit te lezen woord wordt aangegeven door het vierde argument. De methode moet de lege string teruggeven indien vanaf de opgegeven positie en in de opgegeven richting geen woord van de opgegeven lengte kan uitgelezen worden (omdat tegen de grenzen van het rooster wordt aangelopen).
  6. Een methode zoek waaraan een woord als argument moet doorgegeven worden. De methode moet teruggeven in welke richting en vanaf welke positie in het rooster het woord kan uitgelezen worden. Dit resultaat wordt teruggegeven als een tuple met drie elementen: i) het rijnummer van de startpositie, ii) het kolomnummer van de startpositie en iii) de richting (als een string bestaande uit twee letters). Bij het zoeken naar het opgegeven woord mag geen onderscheid gemaakt worden tussen hoofdletters en kleine letters. De methode moet de waarde None teruggeven indien het opgegeven woord in geen enkel van de vier mogelijke richtingen kan uitgelezen worden.
  7. Een methode oplossing die de oplossing van de woordzoeker in hoofdletters als resultaat teruggeeft. Aan deze methode moet een lijst van woorden als argument doorgegeven worden. De oplossing bestaat dan uit de letters in het rooster die niet gebruikt worden door de opgelijste woorden, gelezen van links naar rechts en van boven naar onder. Merk op dat het best mogelijk is dat de lijst woorden bevat die niet in het rooster voorkomen. Aangezien sommige letters in het rooster door meerdere woorden kunnen gebruikt worden, kan je best op zoek gaan naar de oplossing door alle letters die gebruikt worden door woorden in het rooster te vervangen door de corresponderende kleine letter. De oplossing kan dan uitgelezen worden als de resterende hoofdletters. Voor het opgegeven voorbeeld ziet het rooster na omzetting van de opgegeven woorden naar kleine letters er dan bijvoorbeeld als volgt uit:
    leisteen
    remramSi
    KwackeAu
    Rteiroid
    Nsipsajr
    porfiera
    teilanot
    
    Op basis van dit rooster kan de oplossing van de woordzoeker dan gelezen worden als SKARN.

Voorbeeld

>>> puzzel = Woordzoeker(7, 8, 'LEISTEENREMRAMSIKWACKEAURTEIROIDNSIPSAJRPORFIERATEILANOT')
>>> print(puzzel)
LEISTEEN
REMRAMSI
KWACKEAU
RTEIROID
NSIPSAJR
PORFIERA
TEILANOT
>>> puzzel.lees(5, 3, 'OB', 6)
'FPICRS'
>>> puzzel.lees(3, 4, 'LR', 5)
''
>>> puzzel.zoek('marmer')
(1, 5, 'RL')
>>> puzzel.zoek('bauxiet')
>>> puzzel.oplossing(['arduin', 'dioriet', 'jaspis', 'leisteen', 'marmer', 'porfier', 'tonaliet', 'wacke'])
'SKARN'

>>> puzzel = Woordzoeker(7, 8, 'LEISTEEN')
Traceback (most recent call last):
AssertionError: te weinig letters opgegeven

Added by:Peter Dawyndt
Date:2012-01-31
Time limit:10s-30s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.