Slagalica Kviz

[OgnjenM]

Radim na igri slicnoj popularnoj igri/kvizu Slagalica. Zapravo zavrsio sam kompletno projekat sve super radi, tu je i multiplejer. E sada kako sam sve zavrsio tako sam poceo da vise sminkam i poliram igru.
Primjetio sam da mi se ne svidja trenutno kako radi kod mene igra "Najduza Rec".

Igrac izvlaci 12 nasumicnih slova i od njih pravi najduzu rec, a u pozadini program trazi sam rijesenje od zadatih slova. Tako trenutno radi algoritam, medjutim ne svidja mi se. Jer se zna desiti da igrac dobije nasumicna slova na takav nacin da najduza rec bude maksimalno od 4,5,6 slova, samim tim je i teze igracu.

Npr, igraci su dobili sledeca slova:
O F Z F A J E V V D H C
Najduza rijec koju je program nasao u bazi je [Baza ima preko 50 hiljada reci]:
ZAVOJ

Citao sam malo po forumima kakav je algoritam kod originalne slagalice i postoje dva nagadjanja:

1. Daje se jednak broj nasumicnih samoglasnika i suglasnika
2. Najduza rec je vec zadata unaprijed od racunara i zapravo se njena slova izbacuju (sto bi znacilo da "nasumicno" biranje slova i nije nasumicno) i onda se doda ostatak slova ako izabrana rec se sastoji manje od 12 slova.

Ima li neko mozda informaciju da li je nesto tacno odo ovo dvoje navedenih gore, ili mozda ima nekakvu ideju?

[mciggzy]

Meni se ne svidja ideja da se uzme unapred dugacka rec. nekad je to ocigledno I bas trazis tu rec. Bolje da uzmes raspodelu prema ucestalosti slova u srpskom jeziku. Nemam je, ali postoji srpski scrabble pa kontam da je isti odnos slova ;D

[Teva]

Ja bih analizirao taj skup od 50k reči i uzeo sve reči dužine 8+ i izračunao verovatnoću pojavljivanja svakog slova u tim rečima i onda koristio te verovatnoće u favorizovanju određenih slova u "slučajnom" izboru.

I onda na osnovu izračunatih verovatnoća izračunaš neki trešhold i biraš 8,9 slova sa verovatnoćom koja je ista ili veća od tog trešholda, i ostala 3,4 nasumice... Zbog prirode našeg jezika će samoglasnici imati veću verovatnoći od suglasnika, pa će ti trebati i neka provera da bude određen procenat samoglasnika u odnosu na suglasnike.

Cenim da će dosta da ti popravi prosečan slučaj da bude veći broj reči u opticaju favorizovanjem slova kao što su t,n,s,a,i,o,m,r umesto f, dž, š, i sl :)

Mislim da i prava slagalica ima sličan sistem, stim što verovatno imaju neke malo ozbiljnije pretpostavke o jeziku, tipa 4 prednjenepčana, 4 usna, 4 strujna slova i sl :)

[OgnjenM]

Hvala na odgovorima, pomoglo je dosta. Zadovoljan rezultatom. Sada provjeravam ucestalost slova u rijecima i na osnovu toga izbacuje nasumicna slova prateci pravilo da bude balans izmedju samoglasnika i suglasnika.

[OgnjenM]

Probao sam da prebacim trenutni kod C# na server (PHP). Ovakav isti kod (C#) na uredjajima radi uncinkovito i veoma brzo. Dok PHP je dosta sporiji otprilike mu treba 15-20 sekundi da pronadje najduzu rijec. Ucitavanje rijecnika je 2 sekunde ostalo je utroseno na pronalazenje. Da li neko mozda ima ideju kako bih mogao ubrzati taj proces?


parse_dictionary.php

<?php

$ouput = array();
$mysqli = new mysqli('localhost','root','','multiquiz_db');
$mysqli->set_charset('utf8');
if ($result = $mysqli->query("SELECT word FROM words_live")) {
while($row = $result->fetch_array(MYSQL_ASSOC)) {
//echo(mb_convert_encoding($row['word'], 'HTML-ENTITIES', 'utf-8'));
array_push($ouput, $row['word']);
}

//echo utf8_decode(json_encode($ouput));
}

$result->close();
$mysqli->close();

?>


Trie.php
<?php

class Trie
{
public $children = array();
public $value = null;
public $word = null;

public function __construct($value = null)
{
$this->value = $value;
}

public function adda($array)
{
$this->addb($array, 0);
}

public function addb($array, $offset)
{
foreach ($this->children as $child)
{
if($child->value == $array[$offset])
{
$child->addb($array, $offset + 1);
return;
}
}

$trieNode = new Trie($array[$offset]);
array_push($this->children, $trieNode);

if($offset < count($array) - 1)
{
$trieNode->addb($array, $offset+1);
}
else
{
$trieNode->word = implode(" ", $array);
}
}
}
?>

Index.php
<?php
include 'Trie.php';
include 'parse_dictionary.php';
ini_set('memory_limit', '1024M'); // or you could use 1G
header('Content-Type: text/html; charset=utf-8');
mb_internal_encoding("UTF-8");
class LongestWord
{
public $root = null;

public function __construct($ouput)
{
$this->root = new Trie();
foreach ($ouput as $word)
{
//echo($word);
//echo(str_split_unicode($word)[0]);
$this->root->adda(str_split_unicode($word));
}
}

public function search($cs)
{
return $this->visit($this->root, $cs);
}

function visit($n, $allowedCharacters)
{
$bestMatch = null;
if(count($n->children) == 0)
{
$bestMatch = $n->word;
}

foreach($n->children as $child)
{
if($this->contains($allowedCharacters, $child->value))
{
$result = $this->visit($child, $this->remove($allowedCharacters, $child->value));

if($bestMatch == null || $result != null && strlen($bestMatch) < strlen($result))
{
$bestMatch = $result;
}
}
}
return $bestMatch;
}

function remove($allowedCharacters, $value)
{
$newDict = $allowedCharacters;
if(($key = array_search($value, $newDict)))
{
unset($newDict[$key]);
}

return $newDict;
}

function contains($allowedCharacters, $value)
{
foreach($allowedCharacters as $x)
{
if($value == $x)
{
// echo $value . "=====". $x. "|||||||";
return true;
}
else
{
//echo $value . "!!===". $x. "|||||||";
}
}
return false;
}
}

function str_split_unicode($str, $l = 0) {
if ($l > 0) {
$ret = array();
$len = mb_strlen($str, "UTF-8");
for ($i = 0; $i < $len; $i += $l) {
$ret[] = mb_substr($str, $i, $l, "UTF-8");
}
return $ret;
}
return preg_split("//u", $str, -1, PREG_SPLIT_NO_EMPTY);
}


$chars = 'IIOIOFNČGDĆJ';
$testCharacters = str_split_unicode($chars);
$lw = new LongestWord($ouput);
echo($lw->search($testCharacters));

?>

[borisbex]

Jeste da je tema mnogo stara, ali slučajno sam naišao na ove linkove za igre iz popularne slagalice (meni i dalje najomiljeniji kviz), Najduža reč i Moj broj, meni lepo rade:

Najduža reč:

https://latinicnocirilicnikonvertor.weebly.com/najdu381a-re268.html

Moj broj:

https://latinicnocirilicnikonvertor.weebly.com/moj-broj.html