Tehtävät1 - Tietorakenteet

HUOM! Varsinkin ensimmäiset tehtävät on helppo ratkaista generatiivisen tekoälyn avulla. Koeta kuitenkin itse hahmotella ratkaisua ennen kuin turvaudut tekoälyyn. Myös tekoälyn avulla koodia tekevältä ohjelmoijalta vaaditaan koodin ymmärtämistä ja kykyä omaan ajatteluun.

Tehtävä 1

Tee viisi funktiota jotka käsittelevät taulukossa olevia tikanheiton tuloksia. Tee funktiot: 1) setScore(scores, newscore) lisää uuden tuloksen taulukkoon, 2) getScores(scores) palauttaa kaikki tulokset, 3) latest(scores) palauttaa viimeisimmän tuloksen. Tee funktio niin, että alkuperäinen taulukko ei muutu, eli älä poista viimeistä alkiota taulukosta. 4) highest(scores) palauttaa parhaan tuloksen (vihje: Math.max) ja 5) topThree(scores) palauttaa kolme parasta tulosta (vihje: sort(comparefunction) ja slice). Huomaa että taulukon järjestäminen sort -funktiolla muuttaa alkuperäisen taulukon lopullisesti uuteen järjestykseen. Tee funktio siten että alkuperäisen taulukon järjestys säilyy (vihje: tee scores -taulukosta uusi taulukko (klooni) ja sorttaa se).

Kun lähdet suorittamaan funktioita, tee ensin taulukko nimeltään scores, jossa on muutamia tuloksia väliltä 0-50. Voit aloittaa lisäämällä setScore:lla taulukkoon uuden arvon. Sitten voit kutsua muita funktioita ja tulostaa niiden paluuarvot. Exporttaa funktiot tiedoston lopussa jotta testitiedosto voi käyttää niitä (module.exports = {setScore, getScores, jne...}).

Lopputulos voisi näyttää suunnilleen tältä. Tee tehtävä tähän projektiin jossa olevien testien tulee mennä läpi.

➤Video jossa havainnollistetaan testien hyödyntämistä tehtävän ratkaisussa.

Tehtävä 2

Tässä on kolme Map-tietorakennetta joissa on kolmen kaupan tiedot: kaupan nimi ja sen tuotteiden hinnat. Tee kolme funktiota joiden avulla saat lopputulokseksi seuraavanlaisen mapin: Map { 'ykauppa' => 26 }. Avain on kaupan nimi ja arvo on pienin hintojen summa. Eli selvitämme mikä kauppa on halvin.

Ohje: 1) sum(shop)-funktiolla palautat kaupan tuotteiden summan (vihje: map.values()). 2) createSumMap(key, ...shops)-funktio palauttaa uuden mapin jossa on avain-arvo -pareina kaupat ja niiden tuotteiden summat: Map{'xkauppa'=>35, 'ykauppa' => 26, 'zkauppa' => 50}.  createSumMap käyttää sum-funktiota. (vihje: käy mapit läpi forEachilla ja kerää tiedot uuteen mappiin) 3) minValueMap(mapX)-funktiolla luot edellisen funktion palauttamasta mapista lopullisen mapin (vihje: käy läpi kohdassa 2) luodun mapin avaimet ja arvot forEachilla ja etsi pienin summa ja sitä vastaava kaupan nimi).

Lopputulos voisi näyttää suunnilleen tältä. Tee tehtävä tähän projektiin jossa olevien testien tulee mennä läpi.

Tehtävä 3

Yrityksessä X on kolme koodaria jotka osaavat seuraavia ohjelmointikieliä:

Tee Set-tietorakenteet coderA, coderB ja coderC  joissa ovat koodarien osaamat kielet. Laita setit taulukkoon coders. Tee taulukossa olevista seteistä uusi setti johon kokoat kaikki eri kielet mitä kyseiset kolme koodaria osaavat, eli teet joukoista unionin. Unionista tutkit löytyykö yrityksestä Go -kielen osaajaa. Vihje: Implementing basic set operations.

Ohje: 1) union(coders)-funktiolla palautat settien unionin. Luo uusi tyhjä setti. Käy taulukossa olevat setit läpi  ja lisää jokainen setin alkio uuteen settiin jonka lopuksi palautat. 2) haveCodeSkill (coders, language)-funktio palauttaa true tai false sen perusteella sisältävätkö coders-taulukon setit tietyn ohjelmointikielen. Käytä tässä funktiossa union(coders)-funktiota.

Lopputulos voisi näyttää  suunnilleen tältä. Tee tehtävä tähän projektiin jossa olevien testien tulee mennä läpi.

Tehtävä 4

Edellisessä tehtävässä käytettiin JS:n valmista Set-luokkaa, mutta tietorakenneluokan voi tehdä itsekin yllättävän helposti. JS:n valmis Set()-luokka on tehty linkitetyn listan päälle, mutta käytämme tässä taulukkoa, koska se on helpompaa. Tekemämme setti toimii aivan kuten MDN:n Set()-luokka, mutta on hitaampi, koska pohjana on taulukko. HUOM! Tehtävässä ei käytetä MDN:n valmiin Set() -luokan metodeja, vaan käsitellään ainoastaan  itse luodun setin sisällä olevaa taulukkoa.

Tee uusi JS-luokka jonka nimi on MySet. Tee luokkaan konstruktori jossa otetaan vastaan parametrina valmis taulukko, tai jos sitä ei ole annettu alustetaan tyhjä taulukko, johon setti luodaan. Vastaan otettava valmis taulukko menee konstruktorissa läpi funktiosta, joka tekee taulukon alkioista uniikkeja, eli poistaa ylimääräiset samanlaiset alkiot. Tee konstruktoriin myös ominaisuus eli property size johon tulee setin koko. Luokassa on siis kaksi ominaisuutta: arr ja size. Tee luokkaan viisi metodia: 1) checkUnique(arr) palauttaa taulukon, jonka alkiot ovat uniikkeja, 2) add(data) palauttaa true tai false, 3) remove(data) palauttaa true tai false, 4) has(data) palauttaa true tai false ja 5) union(setA, ...sets) palauttaa unionisetin. Luo kolme MySet-oliota ja kokeile kaikkia metodeja. Exporttaa testiä varten koko luokka.

Ohje: 1) Tee checkUnique(arr)-metodissa uusi taulukko jonne lisäät sisään tulevan arr-taulukon alkiot jos ne eivät jo ole siellä. Lopuksi palautat taulukon. 2) add-metodi lisää alkion taulukkoon vain jos missään indeksissä ei jo ole samaa alkiota. 3) remove-metodi tutkii missä taulukon indeksissä alkio on ja poistaa sen kyseisestä indeksistä. 4) has-metodi tutkii onko taulukossa indeksiä jossa alkio on. 5) union-metodi voi ottaa vastaan kaksi tai useampia settejä. Unioni syntyy lisäämällä muiden settien alkiot ensimmäiseen settiin tuplasilmukan avulla. Huomaa että sisemmässä silmukassa pitää käydä läpi setin sisältämää taulukkoa (s.arr).

Lopputulos voisi näyttää suunnilleen tältä.  Tee tehtävä tähän projektiin jossa olevien testien tulee mennä läpi.

Tehtävä 5

Tee kolme funktiota joissa käytetään jono -tietorakennetta (queue-fifo): 1) makeQueue(arr) luo jonon taulukosta ja palauttaa sen. 2) checkQueue(myqueue, stopper) purkaa jonosta alkioita niin kauan kunnes vastaan tulee stopper -alkio. Se palauttaa jäljelle jäävän jonon jossa stopper -alkio on ensimmäisenä. 3) clearQueue(queue) joka tyhjentää jäljelle jääneen jonon, laittaa alkiot taulukkoon ja palauttaa taulukon. Tulosta funktioiden 1) ja 2) palauttamat jonot console.log:lla ja tulosta lopuksi funktion 3) palauttama taulukko. Rakenna ensimmäinen jono taulukosta jossa on muutama kpl numeroita 1-9 ja taulukon keskivaiheilla yksi numero joka on >= 10 . Laita stopperin arvoksi 10 eli jos alkio on >=10 niin siihen lopetetaan jonon purku.

Lopputulos voisi näyttää suunnilleen tältä. Tee tehtävä tähän projektiin jossa olevien testien tulee mennä läpi.

Tehtävä 6

Toteuta pino -tietorakenteen (stack-lifo) avulla funktio joka ottaa argumentikseen merkkijonon ja palauttaa sen käännettynä väärinpäin. Esim. reverseString('myymälä') palauttaa 'älämyym'. Ohje: lisää merkkijonon merkit pinoon ja sen jälkeen kerää ne pinosta uuteen merkkijonoon jonka palautat. Jatka tekemällä toinen funktio nimeltään isPalindrome, joka käyttää edellistä funktiota ja palauttaa true tai false sen mukaan onko merkkijono palindromi. Palindromi on muiden paitsi tyhjien merkkien (whitespace) osalta sama merkkijono huolimatta siitä luetaanko se alusta loppuun vai lopusta alkuun.

Lopputulos voisi näyttää suunnilleen tältä. Tee tehtävä tähän projektiin jossa olevien testien tulee mennä läpi.

Tehtävä 7

Toteuta "virtuaalinen musiikkisoitin" linkitetyn listan avulla. Käytä simple-double-linked-list -kirjastoa ja luo  lista jossa on neljä musiikkikappaletta aakkosjärjestyksessä esittäjän perusteella.  Alkio on merkkijono kuten: 'Matti ja Teppo - Mä joka päivä töitä teen'.  Kappale "soitetaan" tulostamalla alkio.  Lisää listaan keskelle yksi kappale ja poista sen jälkeinen kappale. "Soita" kappaleet ensin alusta loppuun ja sitten toisinpäin. Muista että listasta et voi poimia alkiota suoraan mistä tahansa paikasta, vaan alkion luokse pitää "kulkea" viemällä osoitin siitä paikasta (nodesta) missä ollaan seuraavaan tai edelliseen paikkaan.

Tee funktiot: 1) listFromArray(arr) joka luo listan taulukon alkioista. 2) print(list) joka tulostaa listan alkiot allekkain. Huomaa, että kirjasto sisältää jo Print() -metodin, mutta tehdään kuitenkin oma funktio. 3) printReverse(list) joka tulostaa listan alkiot allekkain käänteisessä järjestyksessä. Tämä on lähes samanlainen kuin edellinen funktio. 4) insertToIndex(list, index, item) jolla lisäät alkion listassa paikkaan jotka on numeroitu alusta lähtien 0, 1, 2 ...jne. Teemme siis listaan omat indeksit. 5) removeFromIndex(list, index) jolla poistat alkion listasta.

Tekemissäsi funktioissa käytät simple-double-linked-list-kirjaston funktioita. Huomaa että kirjastossa on metodit kirjoitettu isolla alkukirjaimella mikä on Eslint-sääntöjen vastaista. Kun laitat /* eslint-disable new-cap */ -määrityksen tiedoston alkuun, virheilmoitus poistuu.

Lopputulos voisi näyttää suunnilleen tältä. Tee tehtävä tähän projektiin jossa olevien testien tulee mennä läpi.

Tehtävä 8

Toteuta graph-data-structure-kirjastolla tässä kuvassa esitetty verkko. 1) Tee values-taulukko joka sisältää taulukoita joissa on jokaisessa kolme alkiota: alkusolmu, loppusolmu ja niiden välinen etäisyys. 2) Tee funktio createGraph(values) jolla luot kaksiulotteisesta taulukosta verkon ja palautat sen. 3) Tee funktio shortestDist(graph, x, y) jolla palautat pienimmän mahdollisen etäisyyden verkon graph solmujen x ja y välillä. Funktio on hyvin helppo toteuttaa kirjaston valmiin metodin ja propertyn avulla. 4) Tulosta verkko serialize() -metodilla. 5) Suorita verkolle topologicalSort() -metodi ja tulosta sen lopputulos. Kirjoita kommenttiin miksi topologinen lajittelu tuottaa saamasi lopputuloksen. 6) Tulosta lyhin etäisyys solmujen 'a' ja 'e' välillä.

Lopputulos voisi näyttää suunnilleen tältä. Tee tehtävä tähän projektiin jossa olevien testien tulee mennä läpi.

Tehtävä 9

Toteuta yksinkertainen binäärihakupuu bst-js-kirjaston avulla. Tee funktio createTree(root, values) jolla luot puun. Puun juuressa on alkio 10 ja puussa ovat alkiot: 2,6,23,1,12,21,5. Tulosta puu console.logilla ja kopioi tuloste tiedostoon tuloste.txt. Tutki tulostetta klikkailemalla aaltosulkeita. Millainen sen rakenne on? Piirrä binäärihakupuu merkkien avulla kuten bst-js:n dokumentaatiossa on tehty. Voit piirtää puun käsin eli piirtoa varten ei tarvitse tehdä funktiota. Suorita vielä puun kaikkien alkioiden leveyshaku ja syvyyshaku kirjaston funktioilla breadthFirst ja depthFirst. Tulosta hakujen tulokset. Mihin periaatteisiin haut perustuvat?

Luo itse projektikansio dst9, jonne teet test-kansion, .eslintrc -tiedoston ja package.json -tiedoston aiempien tehtävien mallin mukaan. Test -kansioon teet dst9test.js -tiedoston, jonne teet yksinkertaiset testit, joilla varmistetaan että createTree(root, values)-funktio on olemassa ja se toimii kuten pitää. Lisäksi teet tiedoston tuloste.txt, jonne tulee puun console.log()-tuloste, numeroilla ja kenoviivoilla tehty piirros puusta ja vastaukset yllä esitettyihin kysymyksiin.

Kun dst9.js -koodi ajetaan, lopputulos näyttää suunnilleen tältä.

Tehtävä 10

Etsi webistä tietoa jostakin tietorakenteesta jota tällä kurssilla ei ole esitelty. Selvitä onko se jonkin kurssilla esitellyn tietorakenteen muunnos? Esitä sen JS-toteutus (löytyy esim. npmjs.com:ista) ja selvitä millaisissa käyttötarkoituksissa siitä voi olla hyötyä. Esim. heap(keko), tuple(monikko) tai matrix(matriisi).