Bonusviikko 2

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

Tehtävät liittyvät viikkojen 8-12 aiheisiin.

Tehtävä 1

Talossa on hajonnut vesiputkia. Tehtävänäsi on laskea, kuinka kauan kestää, ennen kuin koko talo (kaikki lattiaruudut) on veden vallassa.

Talon pohjapiirros annetaan samassa muodossa kuin tehtävissä 2 ja 3 viikolla 9, mutta merkki P tarkoittaa hajonnutta putkea. Vesi etenee talossa niin, että jos tietyssä lattiaruudussa on vettä, seuraavalla kierroksella myös kaikissa ruudun naapuriruuduissa on vettä.

Toteuta metodi int putkirikko(char[][] talo), joka laskee montako kierrosta menee kaikkien lattiaruutujen peittymiseen.

Voit olettaa, että hajonneista putkista on yhteys kaikkiin talon lattiaruutuihin.

Esimerkki 1

##########
#.#...##.#
#.#P#...P#
#.....##.#
##########

Kesto: 5

Seuraavaan kuvaan on merkitty ajanhetket, joina vesi saavuttaa talon lattiaruudut yllä olevassa tapauksessa:

##########
#5#123##1#
#4#P#321P#
#32123##1#
##########

Esimerkki 2

Pohjapiirros:

##########
#.#...##P#
#.#P#P...#
#P....##.#
##########

Kesto: 2

Tehtävä 2

Tämä tehtävä käsittelee lukuja, jotka saadaan kertomalla lukuja 2 ja 3. Ensimmäiset tällaiset luvut ovat:

• 2
• 3
• 4 = 2·2
• 6 = 2·3
• 8 = 2·2·2
• 9 = 3·3
• 12 = 2·2·3

Tehtäväsi on selvittää järjestyksessä n. tällainen luku.

Toteutus

Toteuta seuraava metodi:

long etsiTulo(int n)

Parametri n määrittää, monesko luku metodin tulee palauttaa. Kaikissa testeissä n on välillä 1..1000 ja vastaus mahtuu long-muuttujaan.

Esimerkit

Tehtävä 3

Ratsu liikkuu shakkilaudalla kulkemalla kaksi ruutua johonkin suuntaan (vasen, oikea, ylös alas), ja sitten yhden ruudun edellisen suunnan kanssa suorassa kulmassa olevaan suuntaan. Seuraavassa on piirretty ratsun (R) kaikki mahdolliset seuraavat ruudut (x):

........
........
..x.x...
.x...x..
...R....
.x...x..
..x.x...
........

Tehtävänäsi on etsiä ratsun lyhin reitti annetusta 8x8 shakkilaudan ruudusta toiseen. Toteuta metodi int ratsu(int x0, int y0, int x1, int y1), joka palauttaa lyhimmän reitin pituuden lähtöruudusta (x0,y0) maaliruutuun (x1,y1).

Esimerkkejä

ratsu(0,0,1,2)=1

0.......
........
.1......
........
........
........
........
........

ratsu(0,0,7,7)=6 (samanpituisia reittejä on toki useita)

0.......
........
.1......
...2....
.....3..
.......4
.....5..
.......6

Tehtävä 4

Sinulla on tiedot henkilöiden välisistä ystävyyssuhteista, ja tehtäväsi on etsiä kaksi henkilöä, jotka ovat mahdollisimman kaukana toisistaan ystäväverkostossa. Tämä liittyy väitteeseen, että kaikki maailman ihmiset tuntevat toisensa 7 henkilön kautta.

Oletetaan esimerkiksi, että henkilöt ovat A, B ja C. Tiedetään, että A tuntee B:n ja B tuntee C:n. Nyt kaukaisimmat henkilöt ovat A ja C, joiden etäisyys on 2.

Toteutus

Toteuta seuraava metodi:

int kaukaisimmat(int n, int[] mista, int[] minne)

Parametri n on henkilöiden määrä, kokonaisluku välillä 1..100. Taulukot mista ja minne kuvaavat ystävyyssuhteet, ja niissä on 1..10⁵ alkiota. Voit olettaa, että ystäväverkosto on yhtenäinen.

Metodin tulee palauttaa, mikä on suurin etäisyys kahden henkilön välillä ystäväverkostossa.

Esimerkit

Tehtävä 5

Uolevi on kokenut lentomatkaaja ja kertoo usein tarinoita matkoistaan. Mutta Maijan mielestä jotkin Uolevin tarinat kuulostavat epäilyttäviltä.

Oletetaan esimerkiksi, että lentoasemia on 4 ja lentoyhteyksiä on 2: asemalta 1 pystyy lentämään asemille 2 ja 3. Uolevi väittää:

1. "Lensin asemalta 1 asemalle 2 käyttäen 1 lentoa."
2. "Lensin asemalta 1 asemalle 1 käyttäen 4 lentoa."
3. "Lensin asemalta 1 asemalle 2 käyttäen 2 lentoa."
4. "Lensin asemalta 1 asemalle 4 käyttäen 3 lentoa."

Väite 1 voi olla totta, koska asemalta 1 on lentoyhteys asemalle 2. Väite 2 voi myös olla totta, koska Uolevi on voinut lentää 1->2->1->2->1 käyttäen 4 lentoa. Väite 3 on valetta, koska asemalle 2 voi päästä 1 tai 3 lennolla mutta ei 2 lennolla. Väite 4 on valetta, koska asemalle 4 ei pääse mitenkään, erityisesti ei 3 lentoa käyttäen.

Toteutus

Tehtäväsi on toteuttaa luokka Lentoreitit, joka tarjoaa seuraavat metodit:

• Lentoreitit(int n, int[] mista, int[] minne):
  konstruktorille annetaan tiedot kaikista lentoreiteistä
• boolean mahdollinen(int alku, int loppu, int lennot):
  metodin tulee tutkia Uolevin väite: "lähdin liikkeelle paikasta alku ja saavuin lennot lennon jälkeen paikkaan loppu"

Lentoasemien määrä n on välillä 1..100, ja asemat on numeroitu kokonaisluvuin 1..n. Lentoyhteyksien määrä on välillä 1..10⁵. Kaikki yhteydet ovat kaksisuuntaisia.

Uolevin väitteitä on välillä 1..10⁵, ja jokaisessa väitteessä alku ja loppu ovat lentoasemien numerot ja lennot on kokonaisluku välillä 1..10⁹. Jos väite voi olla totta, metodin tulee palauttaa true, ja jos väite on varmasti valetta, metodin tulee palauttaa false.

Esimerkki

Seuraava koodi testaa luokkaa:

Lentoreitit x = new Lentoreitit(4, new int[] {1, 1}, new int[] {2, 3});
System.out.println(x.mahdollinen(1, 2, 1));
System.out.println(x.mahdollinen(1, 1, 4));
System.out.println(x.mahdollinen(1, 2, 2));
System.out.println(x.mahdollinen(1, 4, 3));

Koodin tulostuksen tulisi olla seuraava:

true
true
false
false