Viikko 9: TMC-tehtävät

Tehtävien deadline: ma 30.3. klo 01:59

Näissä tehtävissä sovelletaan syvyys- ja leveyssuuntaista hakua.

Tehtävä 1

Tee metodi boolean tietoverkko(boolean[][] verkko), jolle annetaan kuvaus tietoverkosta ja joka tarkistaa, pystyvätkö kaikki verkon koneet viestimään keskenään. Toisin sanoen ohjelman tulee tarkistaa, onko verkko yhtenäinen.

Verkossa on n konetta, jotka on numeroitu kokonaisluvuin 0...n-1. Voit olettaa, että n on korkeintaan 1000.

Verkon kuvaus on vierusmatriisi, eli kaksiulotteinen taulukko verkko, jossa verkko[i][j] on true jos koneitten i ja j välillä menee yhteys.

Esimerkki 1

Tämän verkon vierusmatriisi:

  3
 /|\
4 | 0
 \|/ \
  1---2

on:

ja verkko on yhtenäinen.

Esimerkki 2

Tämän verkon vierusmatriisi:

on:

ja verkko ei ole yhtenäinen.

Tehtävä 2

Saat talon pohjapiirustuksen. Tehtävänäsi on laskea, montako huonetta talossa on. Huone tarkoittaa yhtenäistä seinien rajaamaa lattiatilaa.

Toteuta metodi int huoneet(char[][] talo), joka palauttaa huoneitten lukumäärän. Pohjapiirroksessa merkki '#' tarkoittaa seinää ja merkki '.' lattiaa.

Huom: juuri kartan reunojen ulkopuolella on (implisiittiset) seinät. Siis esimerkiksi seuraavassa kartassa on kaksi huonetta:

.
#
.

Esimerkki 1

##########
#.###....#
#..#####.#
#...#.##.#
##########

Huoneita: 3

Esimerkki 2

##########
#.#...##.#
#.#.#....#
#.....##.#
##########

Huoneita: 1

Tehtävä 3

Tällä kertaa huoneitten laskemisen sijaan on tehtävänä laskea huoneitten koot. Toteuta metodi ArrayList<Integer> koot(char[][] talo) joka palauttaa huoneitten koot (jossain järjestyksessä) ArrayListissä.

Talon pohjapiirros annetaan ohjelmalle samassa muodossa kuin edellisessä tehtävässä.

Esimerkki 1

Pohjapiirros:

##########
#.###....#
#..#####.#
#...#.##.#
##########

Huoneiden koot: 6,6,1

Tässä talossa on kaksi huonetta, joiden koko on 6 ruutua, ja yksi huone, jonka koko on 1 ruutu.

Esimerkki 2

Pohjapiirros:

##########
#.#..#.#.#
######.###
#..#.#.#.#
##########

Huoneiden koot: 3,2,2,1,1,1,1

Tehtävä 4

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ä 5

HUOMAUTUS! Ennen tämän tehtävän tekemistä kannattaa tutustua Floyd-Warshallin algoritmiin. Vaikka se tuleekin myöhemmin kurssilla painotettujen verkkojen yhteydessä, tarjoaa se kätevän tavan laskea tarpeeksi pienien verkkojen lyhimmät etäisyydet kaikille verkon solmupareille. Tämän tehtävän toteutus leveyshaulla on huomattavasti ikävämpää kuin käyttäen Floyd-Warshallia. Voit lukea algoritmista esimerkiksi kisakoodarin käsikirjan luvusta 17.

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

Tehtäväsi on selvittää, mitkä Uolevin tarinoista voivat pitää paikkansa ja mitkä ovat varmasti valetta.

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

"Lensin asemalta 1 asemalle 2 käyttäen 1 lentoa."
"Lensin asemalta 1 asemalle 1 käyttäen 4 lentoa."
"Lensin asemalta 1 asemalle 2 käyttäen 2 lentoa."
"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