Exact cover solver

Project for Helsinki University's Data structures and algorithms -project course. Repository docs are written in Finnish.

Exact cover solver -kirjasto ratkoo np-täydellisen täsmäpeiteongelman sekä täsmäpeiteongelmaksi kääntyviä ongelmia, mm. pentomino-pelejä. Ohjelmassa on toteutettu Donald Knuthin Algorithm X dancing links- ja hajautuspohjaisella implementaatiolla.

Dokumentaatio

• Määrittelydokumentti
• Testausdokumentti
• Toteutusdokumentti
• Testikattavuusraportti
• Koodin dokumentaatio

Käyttöohje

• Projektissa laadittua kirjastoa voit käyttää:
  • Herokussa olevan web-appin kautta [huom herokussa ei ole kauhean korkea muistikatto, joten 6x10 pentominoboardin tai vaikeamman sudokun ratkaisujen generointi saattaa kaataa ohjelman] tai
  • asentamalla web-appin lokaalisti Dockerilla: docker run -p 8000:8000 -e PORT=8000 otahontas/exact-cover-solver-web ja avaamalla localhost:8000 selaimessasi
• UI:ssa voit käyttää seuraavia kirjaston tarjoamia ominaisuuksia:
  • Pentomino-ongelmien ratkominen: voit valita neljästä valmiista laudan koosta jonkun, kirjasto laskee mahdolliset ratkaisut ja palauttaa ne näkyviin.
  • Sudokuiden ratkominen: syötä osittain täytetty (mielellään +15 vihjettä, jotta hakuavaruus ei ole todella massiivinen) sudoku, kirjasto laskee mahdolliset ratkaisut ja palauttaa ne näkyviin. Voit myös valita valmiista sudokusta jonkun demomielessä ratkaistavaksi.
• Ohjelmoinnillisesti kirjastoa käytetään sen tarjoaman Solver -luokan kautta, ks. lisää dokumentaatiosta ja toteutusdokumentista

Kehittäminen

• Kloonaa repo, siirry repon juureen

Docker

• Rakenna kehitysympäristö docker-imageen komennolla: docker build . -t exact-cover-solver-dev -f Dockerfile-dev
• Käynnistä docker-container ajamalla docker run -it -v $(pwd):/app exact-cover-solver-dev ja saat listan sopivista komennoista. Repon kansio kiinnitetään dockeriin, jotta mahdolliset muutokset (coverage tms) päivttyvät kansioon.
• Komentoja käytetään argumenttina edelliseen eli docker run -v $(pwd):/app exact-cover-solver-dev <komento>.
• Suorituskykytestit tulee ajaa pypyllä. Ympäristön tähän voit rakentaa ja testit ajaa seuraavasti:

docker build . -t exact-cover-solver-perf-tests -f Dockerfile-perf-tests && docker run exact-cover-solver-perf-tests

Ilman Dockeria

Huolehdi, että vaaditut ohjelma on asennettu:

• Vähintään Python 3.6.9 sekä pypy3.6-7.3.1
  • Ohjelma on toteutettu pythonin standardikirjastolla, joten pypyn käyttö parantaa ohjelman suorituskykyä huomattavasti, jopa 20-kertaisesti. Suorituskykytestit ajetaankin vain pypyä vasten.
  • Jos sinulla ei ole sopivia versioita, voit joko:
    • asentaa pypyn pypy.org -sivulta ja pythonin python.org -sivulta tai
    • asentaa pypyn ja pythonin eri versiot käyttöjärjestelmäsi paketinhallinnasta (brew, apt-get... jne) tai
    • asentaa pyenvin ja ajaa asennuksen jälkeen repon juuressa pyenv install 3.6.9 sekä pyenv install pypy3.6-7.3.1. Ota sitten versiot käyttöön ajamalla pyenv local 3.6.9 pypy3.6-7.3.1.
• Poetry 1.1+, jonka voit asentaa monella eri tapaa, ks. linkatut ohjeet. Jos käytät pyenviä, poetry käyttää automaattisesti oikeaa versiota. Muussa tapauksessa joudut asettamaan version ajamalla projektin juuressa poetry use 3.6.9.

Asennettuasi projektin tarvitsemat paketit jommalla kummalla tavalla, voit käyttää invoken avulla tehtyjä skriptejä. Skriptit saat esille myös ajamalla poetry run invoke --list (tai dockerilla yllä mainitulla komennolla).

Testit

Aja testit komennolla:

poetry run invoke test

Komento printtaa yleisen koodikattavuusraportin terminaaliin. Tarkemman, html-muotoisen raportin saat ajamalla poetry run invoke cov, minkä jälkeen raportti löytyy polusta htmlcov/index.html.

Suorituskykytestit

Ks. testausdokumentti

Koodityylit

Tarkista koodityylit ja tyypitykset komennolla:

poetry run invoke lint

Koodityylit ja tyypitykset tarkistetaan flake8 -, black ja mypy -työkaluilla. Tarkemmin nämä sisältävät tarkistukset:

• pep8-tyyliohjeiden noudattamisesta
• virheistä, turhista importeista jne
• koodin liiallisesta haarautumisesta / kompleksisuudesta
• black-formatoijan tyyliohjeiden noudattamisesta
• Google Python Style Guiden noudattamisesta docstringeissä (vain lähdekoodille, testeille ei ajeta docstring-tarkastuksia)
• virheistä staattisen tyypityksen kanssa

Blackin huomaamat virheet voi korjata automaattisesti ajamalla poetry run invoke list. Flaken ja mypyn huomaamat virheet täytyy sen sijaan korjata käsin.

API-dokumentaatio

Ohjelman sisäisessä dokumentaatiossa (docstringit) käytetään Googlen Python Style Guide -konventiota.

Generoi dokumentaatio (vrt. Javadocit) komennolla:

poetry run invoke docs

Tämän jälkeen pdoc-kirjastolla generoitu html-muotoinen dokumentaatio löytyy polusta pdoc/index.html. Huom: docsit sisältävät vain julkisten metodien docstringit, privaattimetodit voit tarkistaa lähdekoodista.

Web (ui + server)

Ks. README web-kansiossa