["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
@sens: w ogóle przynam, że trochę się jebie z optymalizacją. xD
Tu koleś super opisał spoko algorytm:
https://www.youtube.com/watch?v=zWIsnrxL-Zc
Ja w sumie przepisywałem na mój ulubiony JS i zrobiłem to samo + klocki z cachem.
- Ustalam, że ma być 5 wierszy i 6 kolumn
- Dziele słowa na 5 literowe i 6 literowe
- Wstawiam w 1 wiersz wszystkie możliwe 6 literowe słowa (załóżmy 10 000 słów)
- Wstawiam w 2 wiersz wszystkie możliwe 6 literowe słowa (10k * 10k = 100 000 000 kombinacji)
- Sprawdzam po kolei słowa w kolumnach i jak trafię na 2 literowy początek który nie ma 5 literowego słowa (5, bo tyle wierszy) odrzucam
- Sporo 2 literowych przechodzi, dodaje w 3 wierszu 6 literowe słowo (10k * 10k * 10k to maks ale robi się zabójczo)
- Sprawdzając 3 literowe wiele już ginie, do sprawdzenia w 4 i 5 jest już mało (nadal sprawdzanie to wstawianie do pozostałych tablic tych 10k słów)
Koleś tam waliduje wstawiając litera po literze u mnie w sumie też to jest wstawiam słowo ale patrze kolumnami i jak odkryję, że początku gk niema to w cachu już jest m qk: false i kolejna z tych 10k*10k kombinacji tylko bierze boolean.
Muszę jeszcze to zoptymalizować i jakoś to wiercić mniejszymi paczkami, bo algorytm niby powinien działać, ale w pewnym momencie brakuje RAMu. :D
opisał
@Deykun: zrobił 18 minutowy filmik zamiast jkak prawdziwy programista opublikować to jako tekst, żeby można było sobie szybko skimnąć
@sens:
Kolego tłumaczy algorytm i pułapki które rozwiązuje, a w linku jest jego repo w C++.
Połowa filmu to kompilacja różnych kwadratów.
a nie lepiej liniowo wstawiać?
No masz rację, dobra optymalizacja i potem obrócić jakbym chciał bokiem. Też odrzucania obróconych nie pisałem, bo dopiero to stawiam. (chociaż pewnie tego nie będę robił, bo chcę mieć tablice do nowej gierki ;D i w niej orientacja ma znaczenie).
Tu jest gra 5x5 po angielsku:
https://squareword.org/
Ale bardzo źle komunikuje wpisane słowa, u mnie ta logika będzie odrobinę inna ale też dopieszczone będzie że w trakcie wpisywania pokaże, że czegoś brakuje albo jakaś litera nie pasuje.
BTW. Koleś tam rzuca chyba gdzieś, że w angielskim sprawdza 200k słów. Ja w angielskim słowniku diffle mam 367k słów. W Polskim 3230k. I wynik wyżej to ograniczenie do chyba top 10% - 20% najpopularniejszych. XD
@Deykun: optymalizacja dla polskiego - wypierdalać słowa z literkami ą, ę, y bo się żadne słowa nie zaczynają od nich
@sens: chociaż w sumie to nie musi się zaczynać jakieś słowo mimo że jest dana literka to sory, źle powiedziałem
No ale na pewno nie może być jako pierwsze
@sens:
Dobrze mówisz. Jest coś takiego nawet jak w 1 słowie wstawię tylko słowa na literę a to potem ANEKS będzie weryfikował słowa zaczynające się na N, E, K, S pionowo.
I masz rację, że można coś odrzucić.
Obecnie jak będzie słowo WĘDZI to Ę odrzuca i weryfikuje dla każdego ĘA ĘB ĘC a mogło by być mądre i już Ę wykryć, że są tylko 2 walid początki. ĘA sprawdzam tylko raz, ale sprawdzam Ę* dla wszystkich liter w polskim alfabecie pewnie niepotrzebnie.
Technicznie można zrobić cache dla 1-2 literowych słów przed i odrzucić ĘA ĘB ĘC etc zanim dołoży się drugie słowo.
Tak w sumie to to męczę się z tym ale właśnie tak jak piszesz to jest spoko temat na kminienie, bo jakiś trik przyśpiesza kompilacje.
W sumie lubię takie problemy rozwiązywać.
BTW. już wypracowałem progress bar na każdym dodanym słowie co pozowli mi estymować koniec kroku w trakcie + na koniec będę miał meta informacje ile odrzucono w pierwszym, drugim, trzecim wierszu. To jest spoko informacja.
@Deykun: https://paste.ofcode.org/aY2aRy985cBLTuzwLtBA29
takie coś wysrałem na szybko, oczywiście moja "optymalizacja" polega głównie na obcinaniu zbyt dużych tablic xD ale nadal, coś tam potrafi wygenerować w krótkim czasie. Przy obcinaniu do 3000 elementów na iterację, to w 3,5 sekuny mi generuje ok. 10 kwadratow 6x6 (nie licząc parsowania słownika, które i tak należy sobie skeszować)
(a samo sprawdzanie jeśli by je zaimplementować, będzie oczywiście poprawne i błyskawiczne)
moje spostrzeżenie jest takie – zawczasu sobie zrobić drzewka Trie (u mnie reprezentowane przez te dwa słowniki wordsr i wordsc) dla długości od 3 do ~7
@sens: w następnym kroku można sobie np. powracać do obciętych tablic jeżeli nie będzie żadnego wyniku
mój sposób ma nawet jakiś sens, bo szukanie tego jest oczywiście wydajniejsze przy DFS, a obcinanie iteracji robi z tego taki pseudo-dfs
@sens:
Trochę po robiłem i stwierdziłem, że mogę trochę zwiększyć liczbę słów i... xd
Tu odwrócona po takim samym czasie, a ma jeszcze 2 wiersze do uzupełnienia. ;d
To był input ~110k-120k+ najpopularniejszych słów ogólnie (potem zlimitowany do 6 i 3 znakowych list). Teraz pchnąłe, i 2h zeszło do 25min w 4 kroku.