Domino tiling library
21 kwietnia 2024 | Dawid RyłkoPoprzednim razem popełniłem artykuł dotyczący układania płytek domino na kwadratowej planszy o wymiarach 2n x 2n. Zamysł był prosty: zaimplementować algorytm, który dla danej planszy zwróci wszystkie możliwe układy płytek domino.
Zgłębiając temat, zauważyłem, że jest on znacznie szerszy i ciekawszy, niż początkowo myślałem. Na początku powstał algorytm, który dla danej planszy zwracał wszystkie możliwe układy płytek domino. Wszystko działało dobrze, ale maksymalny rozmiar planszy wynosił 12 x 12
. Następnie opracowałem wersję algorytmu opartą na BigInt
, która pozwala na obsługę większych plansz. Dodatkowo, zostały dodane benchmarki oraz testy.
Nadszedł więc czas, aby odseparować Domino tiling
do osobnego projektu.
Struktura projektu
domino-tiling/
├── benchmark/
├── helpers/
├── test-data/
├── benchmarkRunner.js
├── dominoTilingSolver-BigInt.js
├── dominoTilingSolver.js
└── testRunner.js
Aktualnie projekt składa się z kilku modułów:
benchmark
- katalog zawierający wyniki benchmarków.helpers
- katalog zawierający pomocnicze funkcje.test-data
- katalog zawierający dane testowe.benchmarkRunner.js
- moduł umożliwiający przeprowadzenie benchmarków algorytmów.dominoTilingSolver.js
- główny moduł zawierający algorytm rozwiązujący problem układania płytek domino na planszy 2n x 2n.dominoTilingSolver-BigInt.js
- wariant algorytmu pozwalający na obsługę większych plansz.testRunner.js
- moduł umożliwiający przeprowadzenie testów algorytmów.
Readme
W projekcie znajduje się również plik README.md
, który zawiera informacje o projekcie, instalacji, użyciu oraz benchmarkach.
Jak zacząć?
- Sklonuj repozytorium:
git clone https://github.com/dawidrylko/domino-tiling.git
- Uruchom projekt:
npm start
Ta komenda uruchomi benchmark 1000 razy. Jeśli chcesz uruchomić inną ilość iteracji, użyj komendy:
node benchmarkRunner.js -n <k>
Co dalej?
Na pewno chciałbym dodać więcej testów oraz benchmarków. W zamyśle jest także opracowanie algorytmu, który będzie generować sekwencję:
1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, 112202208776036178000000, 2444888770250892795802079170816, 548943583215388338077567813208427340288, 1269984011256235834242602753102293934298576249856
Zapraszam do testowania oraz zgłaszania propozycji nowych funkcjonalności. Projekt jest dostępny na GitHubie.