Igre Slagalice
Druge igre
Slagalica
Zar ne bi bilo bolje, bez obzira što bi bilo manje atraktivno, da "nasumična" slova u slagalici zaista budu nasumična? A ne da se sve svodi u stvari na puko rješavanje običnog anagrama. Kad vidim da je među slovima T i I, znam da je u pitanju infinitiv, ili ako ima S i T znam da je skoro sigurno krajnje rješenje imenica. Ja koliko sam shvatio, nek me neko ispravi ako griješim, kompjuter da recimo riječ od obično recimo 10 slova + kompjuterski nasumično 2 slova čime omogućava takmičaru statistički da da riječ dužu od kompjutera, što je u 98% nemoguće.
Često znam da i odustanem u startu kad znam da sam riješio anagram i ne pokušavam da nađem dužu riječ od kompjutera. Mislim da je izvorna slagalica, kako pričaju neki stariji igrači, upravo bila takva, i iako često su konačna rješenja bila često kraća, ipak je po meni bilo pravednije i maštovitost takmičara je više dolazila do izražaja. Ali to je samo moje mišljenje ...
|
Sinn 2010-12-03 |
|
Cilj je valjda ove verzije slagalice, da liči na TV Slagalicu sa RTS-a, a jeste bilo ranije tako kao što si napisao, slično kao u kvizu "Brojke i slova". A negde sam ranije pročitao, ne znam da li je tačno, da u slagalici koriste tekst na srskom jeziku u kojem računar izabere početno slovo i onda od tog slova iz teksta se izvuku još 11 koja ga slede.
|
baron-samedi 2010-12-03 |
|
baron-samedi napisa...
Cilj je valjda ove verzije slagalice, da liči na TV Slagalicu sa RTS-a, a jeste bilo ranije tako kao što si napisao, slično kao u kvizu "Brojke i slova". A negde sam ranije pročitao, ne znam da li je tačno, da u slagalici koriste tekst na srskom jeziku u kojem računar izabere početno slovo i onda od tog slova iz teksta se izvuku još 11 koja ga slede.
... Ne znam kako tačno radi algoritam u emisiji, ali je simptomatično da se uvek može pronaći reč od 10, 11 ili 12 slova. Moja pretpostavka je da se reč unapred odredi, a to što igrači viču STOP utiče samo na redosled slova (algoritam verovatno vrti tih 12 slova koja su unapred odabrana i onda STOP odredi koje od njih će se pojaviti u tom trenutku).
Sistem na sajtu radi slično, s' tim da nema stopiranja, već se odmah ispise nasumično odabrana permutacija. Da budemo realni, STOP je u emisiji potreban, da bi igrači videli slova jedno po jedno i zapisali ih na papir. Neki igrači možda imaju i sisteme kako da ih grupišu na papiru.
Moguća alternativa jeste da se različitim slovima odredi "težina" pa da bude veća ili manja verovatnoća da se određena slova pojave - problem je što algoritam koji pronalazi najdužu reč od ponuđenih slova uopšte nije jednostavan. Tačnije, jeste ga manje-više jednostavno napraviti, ali napraviti tako da u nekom razumnom vremenu nađe reč za oko 50 igrača koji simultano igraju na sajtu bi zahtevalo mnogo više računarskih resursa od ovih sa kojima trenutno raspolažemo. Mislim da je slična priča i u TV emisiji. Čak i da imaju takav algoritam i odvojen računar za to, bilo bi vrlo "tesno" da računar nađe reč pre takmičara. Broj varijacija bez ponavljanja za skup veličine 12 sa odrabirom 1-12 elemenata uopšte nije mali (oko 1.5 milijardi ako sam dobro izračunao), a svaku od njih treba proveriti naspram baze reči. Recimo, mom Core2Duo računaru treba preko 20 minuta da pronađe reč za odabrana slova, čak i kada celu bazu drži u memoriji. Naravno, to je brute-force, verovatno bi se moglo optimizovati raznim heuristikama, prepoznavanjem istih slova i sl. ali i dalje bi bio izazov. Sem toga, trebao bi im i kompletan Srpski rečnik u elektronskom obliku, što, koliko ja znam, ne postoji.
|
Supervizor 2010-12-03 |
|
Ovo je vec negdje bilo, ali ne mogu da nadjem tu temu pa da nastavim....
Elem, napravio sam gresku kod pravljenja nove asocijacije. Zaboravio sam da ubacim rjesenja sa malim slovima, samo velika. I da bude crnje u drugoj sam to uradio napola 
Pomoc!!!
|
Dragana-Goran Kalinic 2010-12-05 |
|
Dragana-Goran Kalinic napisa...
Ovo je vec negdje bilo, ali ne mogu da nadjem tu temu pa da nastavim....
Elem, napravio sam gresku kod pravljenja nove asocijacije. Zaboravio sam da ubacim rjesenja sa malim slovima, samo velika. I da bude crnje u drugoj sam to uradio napola
Pomoc!!!
... Nije problem, dobijamo puno takvih. Ispravićemo...
|
Supervizor 2010-12-06 |
|
Juče sam u igri Slagalica stavio ženski rod tražene riječi i nije mi priznato (ili sam možda zamijenio koje slovo?).
|
Sens 2010-12-14 |
|
|
vkrnac 2010-12-15 |
|
vkrnac napisa...
... http://www.slagalica.tv/forum/tema/51/#poruka3665
|
Supervizor 2010-12-15 |
|
Supervizor napisa...
Ma kakvi reci cu ti odmah da krajnje jednostavno napraviti algoritam koji ce naci najduzu rec za ispod sekunde. A ne treba ti kompletan recnik vec samo kvalitetna baza nekog spellchecker-a za srpski (moze se prilicno lako izguglati sam fajl).
Programiranje ti verovatno nije jaca strana pa evo hint-a, ne prolazis za svaku permutaciju kroz bazu, nego samo jednom prodjes kroz bazu i proveris za svaku rec dal moze da se ispise sa 12 ponudjenih slova. Kompleksnost je O(12*n), gde je n broj termina u bazi koji je u svakom slucaju ispod pola miliona ;).
|
Sentinel 2010-12-16 |
|
Sentinel napisa...
A ne treba ti kompletan recnik vec samo kvalitetna baza nekog spellchecker-a za srpski (moze se prilicno lako izguglati sam fajl).
... baza koju imamo već sadrži kompletan spellchecker iz OpenOffice paketa, kao i harvestovan sadržaj nekoliko sajtova koji sadrže razne rečnike. Ali to je možda 50% ukupnog fonda reči. Bilo bi zanimljivo da vidimo koja se to još baza može izguglati, ja nisam našao ništa kvalitetnije od ove iz OOo. Ako ima, šalji link.
|
Supervizor 2010-12-16 |
|
Sentinel napisa...
... dobra ideja, samo je i dalje sporo, tj. 12 * 390.000 je oko 4.5 miliona. Jeste da je manje od moje prvobitne ideje, ali i dalje je puno. Da ne pričam da je server i ovako opterećen na 80% dobar deo dana.
|
Supervizor 2010-12-16 |
|
Ako bi reci u recniku mogle biti rastavljene na slova, onda bi, uz jedan prolazak kroz bazu reci, kompleksnost bila jednaka broju svih slova u recima.Ovo, ja, cisto laicki.
|
raborg 2010-12-16 |
|
Supervizor napisa...
Sentinel napisa...
... dobra ideja, samo je i dalje sporo, tj. 12 * 390.000 je oko 4.5 miliona. Jeste da je manje od moje prvobitne ideje, ali i dalje je puno. Da ne pričam da je server i ovako opterećen na 80% dobar deo dana.
... osmislio sam sada algoritam kojem treba maksimalno 4096 pretraga nad bazom da nađe reč.
Ideja je da se za svaku reč u bazi napravi "hash" slova, tako da su slova složena po azbučnom redu. Zatim se uzimaju ponuđena slova igre i isto tako slažu i traži se taj hash. Ako ga nema, oduzimamo jedno slovo i tražimo reč sa 11 slova. Ako nema ni te, oduzimamo po 2 slova, itd. U najgorem slučaju bi bilo 4096 pretraga, ali realno će biti mnogo manje jer će reč od 4 ili 5 slova skoro uvek moći da se nađe.
|
Supervizor 2010-12-16 |
|
raborg napisa...
Ako bi reci u recniku mogle biti rastavljene na slova, onda bi, uz jedan prolazak kroz bazu reci, kompleksnost bila jednaka broju svih slova u recima.Ovo, ja, cisto laicki.
... da, pročitao sam sada još jednom ovo što je Sentinel napisao, to je praktično isto to. A reč se može rastaviti na slova kada se iščita iz baze.
|
Supervizor 2010-12-16 |
|
Supervizor napisa...
... osmislio sam sada algoritam kojem treba maksimalno 4096 pretraga nad bazom da nađe reč... U najgorem slučaju bi bilo 4096 pretraga, ali realno će biti mnogo manje jer će reč od 4 ili 5 slova skoro uvek moći da se nađe.
...Ne svidja mi se uopste ova (kao i bilo koja druga na temu kako prevariti sistem) rasprava,ali kad vec raspravljate,da priupitam - zasto bi u bazi reci uopste i postojale one koje su manje od 8,pa cak i od 9 slova?
Pre sam za opciju koju je pominjao Sladjan da se umesto sadasnjeg Skocka sa 6 znakova na 4 mesta,koji je postao rutina,uvede varijanta da se 8 znakova rasporede na 5 mesta,iz npr. 8 pokusaja,kao sto je nekada bilo u Slagalici... Pitanje je koliko je to izvodljivo,i imaju li snage Kalimist,Crni,Raborg i ostali koji to umeju da kombinuju,provere - postoji li sablon i za takvu igru?
|
NeparniValjak 2010-12-16 |
|
NeparniValjak napisa...
... ne pričamo uopšte o varanju sistema.
Pričamo o tome da se promeni igra tako da ne budu više unapred definisane reči od 10,11,12 slova, već da stvarno bude izabrano 12 nasumičnih slova i da onda i računar i takmičar traže najdužu reč. Zato nam sada postaju interesantne i reči od manje slova, jer će se realno desiti situacija da ne može da se sastavi duža reč.
|
Supervizor 2010-12-16 |
|
Supervizor napisa...
Sentinel napisa...
A ne treba ti kompletan recnik vec samo kvalitetna baza nekog spellchecker-a za srpski (moze se prilicno lako izguglati sam fajl).
... baza koju imamo već sadrži kompletan spellchecker iz OpenOffice paketa, kao i harvestovan sadržaj nekoliko sajtova koji sadrže razne rečnike. Ali to je možda 50% ukupnog fonda reči. Bilo bi zanimljivo da vidimo koja se to još baza može izguglati, ja nisam našao ništa kvalitetnije od ove iz OOo. Ako ima, šalji link.
Da OO spellchecker je dobar. Imas jos GNU aspell (nekih 280k odrednica) i spellchecker extenziju za Firefox (nekih 230k odrednica). To bi vec trebalo da je dobra osnova.
Postoji i mnogo veci i bolji srpski elektronski recnik, ali nije bas lako provaliti format u bazi.
|
Sentinel 2010-12-16 |
|
A da vi predjete na privatnu komunikaciju?
|
Dvorska budala 2010-12-16 |
|
Supervizor napisa...
Ideja je da se za svaku reč u bazi napravi "hash" slova, tako da su slova složena po azbučnom redu. Zatim se uzimaju ponuđena slova igre i isto tako slažu i traži se taj hash. Ako ga nema, oduzimamo jedno slovo i tražimo reč sa 11 slova. Ako nema ni te, oduzimamo po 2 slova, itd. U najgorem slučaju bi bilo 4096 pretraga, ali realno će biti mnogo manje jer će reč od 4 ili 5 slova skoro uvek moći da se nađe.
U opstem slucaju trebace ti vise od 4096 pretraga, tj. ukupan broj pretraga je 1+11+11*10/2+11*10*9/6+...
A cak i da je samo 100 pretraga opet je mnooogo sporije od onog sto sam ti gore naveo (jer je svaka pretraga kompleksnosti minimum log2(n)) gde u sustini radis samo jednu jedinu pretragu kroz bazu (kompleksnosti k*n, k<12). Ako hoces poslacu ti kod, koji nalazi najduzu rec za ispod 50ms na bazi od pola miliona odrednica (na obicnom core duo).
Teoretski i to se jos moze ubrzati ako se baze pretrazuje samo po onim pocetnim slovima koja se nalaze u 12. Time se vreme pretrage moze smanjiti na ispod 10ms, ali to su vec finise za kojima nema potrebe.
|
Sentinel 2010-12-16 |
|
Pa sto protiv? Prijedlog je takav da oni sto vole da varaju ne citaju kako da naprave isti program? A mozda vi volite da varuckate, a? 
|
Dvorska budala 2010-12-17 |
|
Sentinel napisa...
... OOo i Firefox koriste aspell bazu. Međutim, ta baza ima reči u svim oblicima (padeži, rod, glagolska vremena, itd.) tako da je realno broj reči možda oko 100.000, što je mnogo manje od ukupnog fonda reči našeg jezika.
|
Supervizor 2010-12-17 |
|
Sentinel napisa...
... da, ajde nastavi do kraja, videćeš da kada se dođe do 6 broj kombinacija se umanjuje i na kraju se dobije 4096
Sentinel napisa...
... i...? log2 od 390,000 je oko 18 i nešto. Znači 4096*18 = 73.728 readova u najgorem slučaju. A tvoj algoritam zahteva prolazak cele baze, odnosno 390.000 readova u najgorem slučaju. Da ne pričam da tvom algoritmu treba ili I/O ili memorija. Dok moj drži samo index, tvoj čita celu bazu.
Nema potrebe da mi šalješ algoritam, jer moj algoritam pronalazi isto ispod 50ms, tako da se time ništa neće dokazati.
Ako imaš neku bazu reči da ponudiš, vrlo rado ću je dodati u postojeću bazu na sajtu.
|
Supervizor 2010-12-17 |
|
Bacago napisa...
Pa sto protiv? Prijedlog je takav da oni sto vole da varaju ne citaju kako da naprave isti program? A mozda vi volite da varuckate, a?
... Mi pričamo o algoritmima. Oni koji hoće da varaju su mogli doći do algoritma i sami bez problema. Problem nije algoritam, već baza reči.
|
Supervizor 2010-12-17 |
|
Supervizor napisa...
Da u pravu si za 4092=2^12. U nekom prosecnom slucaju bice oko 2000. Medjutim imas i toliko puta da generises hash tj. pozivas hash funkciju cije generisanje trazi vremena. I sam hash index ti je bar ~32^12 sto je 60bita ili skoro 8B dakle drzis u memoriji 390000*8B=3.1MB, ja drzim oko 3.5MB, znaci manje vise isto.
U svakom slucaju cak i da 50 ljudi pristupa u svakom trenutku, trebace ti ispod 2 sekunde da pronadjes sva resenja, sto je pretpostavljam vise nego izvodljivo za resurse koje imate.
A za bazu naveo sam ti ovo sto ima free i sto nije kriptovano/komplikovano da se procita, ovo sto ja imam je oko 400k odrednica, znaci manje vise isto sto i ti imas.
|
Sentinel 2010-12-17 |
|
Sentinel napisa...
... resursi koje imamo su već dobro napregnuti, naročito od 19 do 20h. A 2 sekunde za generisanje stranice je čitava večnost za jedan web sajt, bar po mom standardu koji želim da sajt postigne. Stranica mora da se generiše za manje do 1 sekunde. Mada, u pravu si, situacija nije tako strašna kao što je delovalo na prvi pogled, već sa 70-80% jačim serverom nego što sada imamo bi bilo izvodljivo. Ostaje naravno pitanje da li to uopšte treba raditi ili da se trudimo da sajt bude sličan TV emisiji...
|
Supervizor 2010-12-17 |
|