["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
w następnym kroku można sobie np. powracać do obciętych tablic jeżeli nie będzie żadnego wyniku
Dojrzałem żeby zrozumieć i też pewnie będę to implementował, będzie zwracało ostatni step i będzie można zacząć już 4 wierszami np. i znacznie większą liczbą słów.
["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
@sens:
Już ostatni, może wrzucę jeszcze jak zacznę robić większe siatki i znajdę fajne. dx
Optymalizacyjne wiele się nie poprawiłem, ale już w sumie mogę szukać wszystkiego jak chcę, sprawdzam kwadrat z podyktowanym początkiem typu litera "a", "b" etc. i to mi odciąża mocno 1 wiersz który jest seedem mam tracking prędkości i odrzuconych w danym kroku i mogę dobrze estymować czy nie przyjebałem z liczbą słów.
Dla litery "a" znalazłem 62 unikalne siatki 5x5 (31, bo odbite po przekątnej są).
Dla 5x5 w 1h 1m 32s znalazłem 3418 tablic
{
"size": { "rows": 5, "columns": 5 },
"words": { "passed": 34482, "usedForRows": 3499, "usedForColumns": 3499 },
"boards": {
"all": 3418,
"allWordsUnique": 2,
"allWordsMirrored": 3162,
"someWordsDuplicated": 254
},
"durationInSeconds": 3693,
"timePerRow": [
{ "row": 2, "durationInSeconds": 29, "boards": 203778 },
{ "row": 3, "durationInSeconds": 1571, "boards": 263418 },
{ "row": 4, "durationInSeconds": 2037, "boards": 6679 },
{ "row": 5, "durationInSeconds": 55, "boards": 3418 }
]
}
I te 2 unikalnę to 1 jedna odbita po przękątnej:["t", "r", "u", "s", "t"],["w", "a", "c", "k", "a"],["i", "m", "i", "o", "n"],["s", "i", "e", "c", "i"],["t", "ę", "c", "z", "a"]
["k", "u", "r", "w", "o"],["u", "d", "e", "r", "z"],["r", "e", "j", "o", "n"],["w", "r", "o", "g", "a"],["o", "z", "n", "a", "k"]
["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
@sens:
Z takich optymalizacji to też myślałem, że można by to puścić gdzieś github akcji i niech chmura liczy. 🧅
["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
@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.
["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
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.
["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
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ć.
["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
@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.
["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
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
["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
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.
["s", "e", "k", "s"],["e", "t", "a", "t"],["n", "a", "r", "a"],["s", "p", "a", "ł"]
Słowa poziomo i pionowo mają @sens ;D
@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.
["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