otahontas/exact-cover-solver

Exact cover solver with Dancing Links and Algorithm X, written in pure python

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

exact-cover-solver's Issues

Vertaisarvio

-Todella mielenkiintoinen ongelma ja algoritmi, tuli vietettyä hetki jos toinenkin Wikipediassa ja Youtubessa tutustumassa tämän sovelluksiin.

-Testikattavuus & koodin laadun seuranta näkyvissä suoraan Githubissa, erittäin kätevää

-koodin selkeys ja kommentointi esimerkillistä

-nimeäminen hyvin selkeää, erityisesti testien nimeämisestä pitää itsekin ottaa mallia

-En saanut ikävä kyllä ohjelmaa ajettua käyttöohjeiden perusteella ilman kokemusta Pythonista :(

-En saanut ohjelmaa ajettua Windowsilla: asensin Pythonin ja Pypyn, mutta ohjeissa jumahdin kohtaan 'source' is not recognized as an internal or external command,operable program or batch file.

-En saanut ohjelmaa ajettua Debianilla, sopivan Python-version asentaminen ei onnistunut tässä ajassa

-Ubuntulla onnistui siihen asti, että kosahti XWindow:n puuttumiseen. Tämä onnistui freesissä virtuaalikoneessa seuraavasti:

sudo apt upgrade && sudo apt update
sudo apt install python3
sudo apt install pypy3
sudo apt install python3-pip
git clone https://github.com/otahontas/exact-cover-solver
cd exact-cover-solver/
pypy3 -m venv venv
source venv/bin/activate
pypy3 -m pip install --upgrade pip
pypy3 -m pip install .
pypy3 exact_cover_solver/main.py
sudo apt-get install python3-tk
sudo apt install pypy3-tk
pypy3 exact_cover_solver/main.py

Käyttöohjeet voisivat tältä osin kaivata vähän täydennystä, että kokemattomammaltakin onnistuisi.

Harmi etten päässyt ohjelmaa kokeilemaan, mutta repon perusteella epäilen kyllä lukeneeni jotain "näin saat arvosanan 6" -malliprojektia enkä vertaisarvioitavaa repoa :)

Specify universe elements in each creator module (like sudoku uses Union[str, int] etc.)

add automatic doc building to github pages

Code review

Vertaisarvio 1

Arvioitu commit: b9008a2

Ladattu: 25.11.2020

Poetryn käyttö

En saanut poetryllä jostain syystä mitään antamiasi komentoja toimimaan, vaan sain aina vastaukseksi:

OSError

[Errno 2] No such file or directory

Sain koodin sekä testit kuitenkin ajettua käyttämällä python3/pypy3/pytestiä.

Testaus

Testikattavuus näyttää olevan hyvällä mallilla. Joitain osia sieltä täältä ei oltu testattu, mutta tärkeimmät, eli algoritmit sekä tietorakenteet, olivat lähes sadassa prosentissa. Testit näyttävät myös olevan järkevästi kirjoitettu ja ne testaavat oikeita asioita.

Koodi

Koodista huomaa, ettet ole ihan ensimmäistä kertaa ohjelmoimassa. Eri toiminnallisuudet on jaettu järkeviin kokonaisuuksiin omiin moduuleihinsa, mikä tekee koodin löytämisestä helppoa vaikkei projekti olisi ennalta tuttu. Myös Pythonin eri ominaisuuksia, joita aloittelija ei välttämättä keksisi käyttää, on käytetty kattavasti. Näistä esimerkkejä ovat mm. tyyppivinkit, testien fixturet sekä muut decoratorit. Myös projektin readme on toteutettu hyvin.

Ehdotuksia

Ensimmäinen "ongelma", mikä pisti silmään lähes jokaisessa tiedostossa, on koodin pötköisyys. Mielestäni koodia on vaikea lukea, kun kaikki rivit ovat kiinni toisissaan. Jos verrataan esimerkiksi seuraavaa koodipätkää tiedostosta dlxmatrix.py

for set_number, set_elements in enumerate(self._set_collection):
    previous = None
    first = None
    for element in set_elements:
        column = find_column(element)
        cell = DataObject(column, row=set_number)
        prev_up = column.up
        prev_up.down = cell
        cell.up = prev_up
        cell.down = column
        column.up = cell
        if previous:
            previous.right = cell
            cell.left = previous
        else:
            first = cell
        previous = cell
        column.size += 1
    previous.right = first
    first.left = previous

ja samaa koodipätkää hieman jäsenneltynä

for set_number, set_elements in enumerate(self._set_collection):
    previous = None
    first = None

    for element in set_elements:
        column = find_column(element)
        cell = DataObject(column, row=set_number)

        prev_up = column.up
        prev_up.down = cell

        cell.up = prev_up
        cell.down = column
        column.up = cell

        if previous:
            previous.right = cell
            cell.left = previous
        else:
            first = cell

        previous = cell
        column.size += 1

    previous.right = first
    first.left = previous

niin huomataan, että jälkimmäinen on (ainakin minun mielestäni) helpompi lukea.

Vaikka käyttöliittymä ei olekaan tämän kurssin keskiössä, mainitsen käyttöliittymäkoodistasi yhden ongelman joka tuli vastaan.
Olet käyttänyt tiedostossa exact_cover_solver/ui/__init__.py metodin _update_view parametreissä nimeä next, mikä yliajaa Pythonin sisäänrakennetun funktion next. Vaikka tämä ei olekaan ongelma tässä tilanteessa, ei kielen sisäänrakennettujen avainsanojen yliajaminen (yleensä) ole järkevää, ja se saattaa johtaa bugeihin.

Mitään tämän suurempia ongelmia en koodista löytänyt, eikä minulla valitettavasti ole ollut tällä viikolla aikaa hirveästi tähän paneutua. Projekti näyttää olevan sinun osaltasi kuitenkin jo hyvällä mallilla.

check if there's better place to host app than heroku

share pytest fixtures between tests

set max size for sudoku

make lists tuples if they're not modifying & check that certain stuff is final

set min amount for sudoku clues

change docs lang to eng after completing the course

define subset names too (for sudoku it will be Tuple[str, int, int]

check that project works also for WSL / windows

Add deployment to heroku after succesful merge to master

Create better docs adding system (with pdoc or something else)

Add class attributes and __init__ docstrings: https://google.github.io/styleguide/pyguide.html#384-classes