68 97 119 105 100 32 82 121 108 107 111

Domino tiling library

21 kwietnia 2024 | Dawid Ryłko
Strona główna projektu "Domino Tiling" na GitHub.

Poprzednim 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.
Struktura projektu Domino tiling

Readme

W projekcie znajduje się również plik README.md, który zawiera informacje o projekcie, instalacji, użyciu oraz benchmarkach.

Readme projektu Domino tiling

Jak zacząć?

  1. Sklonuj repozytorium:
git clone https://github.com/dawidrylko/domino-tiling.git
  1. 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.


Profile picture

Dawid Ryłko

Software Engineer | Frontend Architect