Problem

Imam tri besede, katere se morajo sekati. Da zadostim temu pogoju bo ena od njih postavljena vodoravno, dve pa navpično tako, da se bosta sekali z vodoravno postavljeno besedo. Podobno kot v križanki.

Začetek reševanja

Najprej bom pregledal, če ima vodoravna beseda kaj skupnih črk z obema navpičnima. Naprimer beseda 'avto' kot vodoravna in besedi 'klop' in 'kovanec' imata skupen presek. Zakaj? Črka 'a' iz besede avto je vsebovana v 'kovanec' prav tako pa je črka 'o' iz besede avto vsebovana v 'klop'.

Izbor pravega preseka

Če vzamem za vodoravno besedo 'Sonja' in za navpični 'kol' in 'vol' presek ne obstaja. Zakaj? 'S' ni vsebovan v nobeni od obeh besed. 'O' je v obeh a ga lahko uporabim samo v eni. 'n','j' in 'a' tudi nista vsebovani v 'kol' in 'vol'. Poiskusim torej drugače. Za vodoravno izberem 'vol' za navpični pa 'Sonja' in 'kol'. 'v' ni vsebovan v nobeni od navpičnih. 'o' je vsebovan v obeh. Denimo da ga uporabim za presek s 'Sonja'. Ostane le še črka 'l'. Ta ima presek z 'kol'. Tako sem dobil rešitev.

Izpis

Najprej ustvarim niz samih pik iste dolžine kot je vodoravna beseda. Za obe navpični besedi izračunam kje se začneta in kje končata. Ugotoviti moram tudi koliko vrstic potrebujem za izpis. Prek vrstic za izpis se zapeljem z zanko. Če sem v vrstici, v kateri bi morala biti vodoravna beseda jo samo izpišem. Če sem v vrstici v kateri bi morala biti vsebovana katerakoli črka iz navpične besede, jo vstavim na pravo mesto.

Predstavitev preseka

Presek vodoravne in dveh navpičnih besed predstavim z tabelo dolžine štiri. To je tabela oblike: [0,3,4,5]. Vzemimo primer:

• Vodoravna beseda: farmacija
• Prva navpična beseda: miš
• Druga navpična beseda: lonec

Tabela [0,3,4,5] pove, da se črka z indeksom 0 v besedi 'miš' torej črka 'm' prekriva z črko z indeksom 3 besede 'farmacija'. Prav tako se peta črka besede 'lonec' prekriva z šesto črko besede 'farmacija'.

Uporabljene spremenljivke

TabelaIndeksov je prej opisana tabela dolžine štiri. I bo indeks črke vodoravne besede. Pravkar bo pazil, da nebom ene črke vodoravne besede uporabil za dve vodoravni. EnaIndeks in dvaIndeks bosta povedali katera črka navpične besede je vsebovana v vodoravni. V predstavitveni tabeli sta to torej prvi in tretji element.

Že v opisu rešitve sem pokazal primer kjer vodoravna in navpicni besedi nimata ustreznega preseka, če pa zamenjam eno navpično z vodoravno pa se presek pojavi. Ta problem rešuje spodnja koda:

Koda preverja če sta obe navpični besedi našli presek z vodoravno. Če sta lahko križanko izpišem. Sicer Zamenjoam eno navpično z vodoravno in postopek ponovim. Če se presek ne pojavi tudi ne obstaja. V tem primeru izpišem opozorilo.

Vrnimo se nazaj k prej opisanem primeru:

• Vodoravna beseda: farmacija
• Prva navpična beseda: miš
• Druga navpična beseda: lonec

In opisu preseka: [0,3,4,5] Pri iskanju začetnega indeksa obeh navpičnih besed bo najlažje če iskanje ponazorim na pirmeru:

• zacetek = max(0,4) = 4;
• zacetek1 = zacetek - 0 = 4; prva beseda se začne v peti vrstici

• zacetek2 = zacetek - 4 = 0; druga beseda se začne v prvi vrstici

  

  Iskanje konca izpisa besede:

• konec1 = navpicna1.length + zacetek = 7; prva beseda se konča v osmi vrstici
• konec2 = 5 + 0 = 5; druga navpična beseda se konča v šesti vrstici

Ko vem v kateri vrstici se katera beseda začne in kje konča, se lahko lotim z ispisovanjem. Zanka teče od 0 do maksimuma obeh koncev. V prejšnjem primeru se je ena beseda končala v 8. druga pa v 5. vrstici. Smiselno je da izpišem vse do 8. vrstice.

V zanki za vsako besedo preverim če jo moram v tej vrstici izpisati. Torej če velja začetek1 <= i <= konec1. Če to velja iz navpične besede poiščem ustrezno črko: navpicna1[i - zacetek1]. To črko vstavim v vrstico samih pik (vrstica.insert). Ker metoda .insert samo doda znak moram vrstico samih pik primerno skrajšati (vrstica.Remove)

Če sem v ustrezni vrstici, izpišem kar vodoravno besedo.

Pri zagonu programa mora uporabnik najprej izbrati če bi testne primere vnesel sam. Sicer jih računalnik izbere sam. Po pritisku črke 'd' lahko uporabnik vse tri besede sam vnese. Prikaže se rezultat t.j. tri besede, ki se sekajo tako tok v križanki.

Računalnik lahko testne primere izbere kar sam. Ključni so trije primeri:

• vodoravno: konkurenca
• navpično 1: glas
• navpično 2: pločevina

Pri tem pimeru presek obstaja, tako da tu preverjam zgolj pravilnost izračuna preseka in izpis. Na primeru je vidno, da je program vse operacije izvedel pravilno saj se vse tri besede pravilno sekajo.

• vodoravno: miš
• navpično 1: farmacija
• navpično 2: lonec

Pri tem primeru ima vodoravna beseda 'miš' presek z 'farmacija' nima pa preseka z 'lonec'. Program mora zato poiskati alternativno rešitev. Če je vodoravna beseda 'farmacija', 'miš' in 'lonec' pa navpični pa presek obstaja. Program izpiše alternativno rešitev.

V primeru, da tri besede nimajo nobenega skupnega preseka v nobeni možni permutaciji, pa program izpiše opozorilo.