Viikko 5: TMC-tehtävät

Tehtävien deadline: ma-su yö 22.2. 1:59.

Tällä ja kaikilla muillakin viikoilla on algoritmien pystyttävä tuottamaan oikea vastaus alle yhdessä sekunnissa, ellei erikseen muuta mainita. Viikon aiheena on hajautus, ja erilaisten hajautusrakenteiden soveltaminen. Javassa löytyvät valmiit luokat HashMap ja HashSet. Huomaathan merkkijonohajautuksesta kertovan lisämateriaalin. Jos kiinnostaa, niin tässä kerrotaan miten voi generoida yhteentörmäyksiä tietyssä erikoistapauksessa.

Tehtävä 1

Uolevi on äärettömässä ruudukossa ja lähtee liikkeelle ruudusta (0, 0). Hän kulkee joka askeleella yhden ruudun vasemmalle, oikealle, ylöspäin tai alaspäin. Milloin Uolevi palaa ruutuun, jossa hän on ollut aiemmin (mihin tahansa matkan varrella olleeseen ruutuun)?

Toteutus

Toteuta seuraava metodi:

int reitinPituus(String reitti)

Parametri reitti kuvaa Uolevin reitin. Se sisältää järjestyksessä suunnat, joihin Uolevi liikkuu. Jokainen suunta on yksi merkeistä V, O, Y ja A. Merkkijonon pituus on 1..105 merkkiä.

Metodin tulee palauttaa, montako askelta Uolevi liikkuu, ennen kuin hän palaa uudestaan samaan ruutuun. Jos Uolevi ei palaa koskaan samaan ruutuun reitin aikana, metodin tulee palauttaa 0.

Esimerkit

Tehtävä 2

Kannat mukanasi suurta reppua ja haluaisit pystyä selvittämään nopeasti, onko repussasi tiettyä esinettä. Lisäksi reppusi sisältö voi muuttua kun lisäät sinne tavaraa, tai kun otat sieltä jotain pois. Tehtävänäsi on toteuttaa kirjanpitosysteemi repun sisällölle.

Toteutus

Toteuta seuraavat metodit koodipohjan mukana tulevaan luokkaan Reppu:

• Reppu() alustaa tyhjän repun, jossa ei ole mitään
• void lisaa(int x) lisää reppuun esineen x
• void heitaPois(int x) ottaa yhden repussasi olevan esineen x, jos sellainen on olemassa ja heittää sen pois
• boolean sisaltaako(int x) selvittää, onko repussasi esinettä x

Metodien saamat kokonaisluvut, jotka ovat välillä 0..109, vastaavat aina jotain konkreettista asiaa, kuten vaikka kynää tai leipää. Jos lisäät reppuusi kaksi kertaa kynän, sisältää reppusi kaksi kynää, ja yhden kynän pois heittämisen jälkeen repussasi on vielä yksi kynä. Luokan metodeja kutsutaan korkeintaan 500000 kertaa.

Esimerkki

Reppu r = new Reppu();

Nyt sisaltaako(1) pitäisi palauttaa 'false', sillä reppu on tyhjä.

r.lisaa(1);

Nyt sisaltaako(1) on 'true', mutta sisaltaako(2) on 'false'.

r.heitaPois(1);

Nyt sisaltaako(1) on jälleen 'false'.

r.lisaa(1000);
r.lisaa(1000);

Nyt sisaltaako(1000) on 'true'.

r.heitaPois(1000);

sisaltaako(1000) on vieläkin 'true', ainoastaan toinen '1000' heitettiin pois.
        

Tehtävä 3

Lue lisämateriaalista merkkijonohajautuksesta. Saat syötteenä kaksi merkkijonoa a ja b. Tehtävänäsi on selvittää "Rolling Hash" -hajautustekniikkaa käyttäen, onko merkkijono a merkkijonon b osajono (substring).

Toteutus

Toteuta seuraava metodi:

boolean onkoOsajono(String a, String b)

Merkkijonojen a ja b pituudet ovat välillä 1..200000 ja ne koostuvat merkeistä A..Z. Huomaathan, että potenssien laskeminen Math.pow käyttäen ei tule toimimaan tehtävässä. Liukulukujen laskutoimituksissa esiintyy suurilla luvuilla epätarkkuutta, jonka takia hajautusfunktiota ei saa laskettua oikein niitä käyttäen.

Esimerkit

Tehtävä 4

Sinulle on annettu DNA-ketju, joka muodostuu merkeistä A, C, G ja T. Tehtäväsi on selvittää, kuinka pitkä on lyhin DNA-ketju, joka ei ole annetun ketjun osajonona.

Esimerkiksi DNA-ketju ACGTACGT sisältää osajonona kaikki 1:n pituiset DNA-ketjut eli A, C, G ja T. Kahden pituiset osajonot ovat järjestyksessä AC, CG, GT, TA, AC, CG ja GT, eli esimerkiksi ketju AA puuttuu osajonoista. Niinpä lyhimmän ketjun pituus on 2.

Toteutus

Toteuta seuraava metodi:

int lyhinPuuttuva(String mjono)

Merkkijono mjono on DNA-ketju, jonka pituus on 1..105 merkkiä.

Metodin tulee palauttaa lyhimmän ketjun pituus, joka ei ole osajonona annetussa ketjussa.

Esimerkit

Tehtävä 5

Sinulle on annettu DNA-ketju, joka muodostuu merkeistä A, C, G ja T. Tehtäväsi on selvittää, kuinka pitkä on pisin DNA-ketju, joka esiintyy annetussa ketjussa vähintään kahdesti osajonona.

Esimerkiksi DNA-ketjun ACGTACGT tapauksessa, pisin tällainen DNA-ketju on ACGT, joten vastaus tässä tapauksessa olisi 4. Toisaalta merkkijonon AAAA tapauksessa, pisin kelpaava jono on AAA, joten vastaus olisi 3.

Toteutus

Toteuta seuraava metodi:

int pisinToisto(String mjono)

Merkkijono mjono on DNA-ketju, jonka pituus on 1..200000 merkkiä. Tehtävän aikaraja on poikkeuksellisesti 2 sekuntia.

Vihje: binäärihausta saattaa olla apua.

Esimerkit