5
\$\begingroup\$

I've created a simple hangman solver at solver.lukesalamone.com, and although I'd consider myself proficient in webdev I am by no means an expert. The trick with this is that since HTTP is stateless, I can't really think of a better way to look words up than to start from scratch each time (and lookup is performed with ajax EVERY time the input changes). So any special data structures would need to be created from the input each time, an overhead which isn't really worth it.

I'm especially interested in any ways to optimize my backend lookup code:

/*  lookup.php  */

$length = $_POST['length'];
$proto = $_POST['proto'];
$dead = $_POST['dead'];
$live = str_replace("*", "", $proto);

// check that $length is number

// load appropriate dictionary into $dict
$dict = file("dicts/" . $length . "_letters.txt", FILE_IGNORE_NEW_LINES);
$words = array();

// loop through each word in dictionary
foreach($dict as $word){
    $flag = true;
    // check that word matches proto
    for($i=0; $i<strlen($proto); $i++){
        if($proto[$i] == "*"){          // wildcard
            for($j=0; $j<strlen($live); $j++){
                if($word[$i] == $live[$j]){     // disallow a*** matching abba
                    $flag = false;
                    continue 3;
                }
            }
            continue;
        }
        if($proto[$i] == $word[$i]){    // correct, go to next letter
            //error_log($proto[$i] . " = " . $word[$i]);
            continue;
        } else{                         // incorrect
            //error_log($proto[$i] . " != " . $word[$i]);
            $flag = false;
            continue 2;
        }
    }

    if($flag){
        array_push($words, $word);
    }

}// end foreach loop
unset($word);

$deadWords = array();

//remove words with dead letters
foreach ($words as $word){
    for ($i=0; $i < strlen($dead); $i++) { 
        if(strpos($word, $dead[$i]) !== false){
            error_log("adding " . $word . " to deadWords");
            array_push($deadWords, $word);
            continue 2;
        }
    }

}
unset($word);

$words = array_values(array_diff($words, $deadWords));

// probably limit returned words to 500 or so

$alphabet = "abcdefghijklmnopqrstuvwxyz";
$letters = array_fill_keys(str_split($alphabet), 0);

// count occurrances of each letter by word
foreach($words as $word){
    // check for each letter in each word
    for($i=0; $i<26; $i++){
        if(strpos($word,$alphabet[$i]) !== false){
            $letters[ $alphabet[$i] ]++;
        }
    }
}// end foreach loop
unset($word);

arsort($letters, SORT_NUMERIC);

// normalize numbers to size of words
$num_words = count($words);
foreach($letters as $l => $v){
    $letters[$l] = $letters[$l] / $num_words;
}


//remove letters with zero frequency
foreach($letters as $l=>$v){
    if($v == 0 || $v == 1){
        $letters = array_diff($letters, array($l=>$v));
    }
}
unset($l);

$ret = array("words"=>$words, "letters"=>$letters);
echo json_encode($ret);

Here is the JS on my front end

var length;
var response;
var blocking = false;

$(document).ready(function(){
    setProto();
    var height = Math.ceil($(window).height() / 40);
    var width = Math.ceil($(window).width() / 40);

    document.getElementById("length").oninput = function(){
        if( !isNaN(parseInt( $("#length").val() )) ){
            length = parseInt($("#length").val());
        }
        setProto();
        evaluate();
    }
    document.getElementById("proto").oninput = evaluate;
    document.getElementById("dead").oninput = evaluate;

    $(".headings h2").click(function(e){
        dataSelect(e.target);
    });

    $(".reset button").click(reset);
});

var evaluate = function(){
    if(blocking) return;
    if( $("#length").val() == "") return;
    if( !checkProto() ) return;

    $(".bottom-row").removeClass("hidden");
    $("#loading").removeClass("hidden");
    for(var i=0; i<4; i++){
        $(".column" + i).html("");
    }

    blocking = true;

    // send ajax request
    $.ajax({
        url: 'lookup.php',
        type: 'post',
        data: { 'length':length, 
                'proto':getProto(),
                'dead':$("#dead").val()},
        success: function(data, status) {
            data = JSON.parse(data);
            response = data;

            var j=0;
            var norm;
            for(var key in response.letters){
                if(norm == null){
                    norm = 0.95 / response.letters[key];
                }
                var percent = (response.letters[key] * 100).toFixed(2);
                var str = key + " : " + percent + "%";
                var entry = document.createElement("div");
                var label = document.createElement("span");
                var bar = document.createElement("div");
                $(entry).addClass("letter-entry");
                $(label).html(str);
                $(bar).attr("style", "width:" + percent*norm + "%");
                $(entry).append( $(label) );
                $(entry).append( $(bar) );
                $(".column" + j%2).append( $(entry) );
                j++;
            }

            for(var i=0; i<data.words.length; i++){
                var word = document.createElement("a");
                var lbrk = document.createElement("br");
                $(word).html(data.words[i]);
                $(word).attr("href", "http://dictionary.com/browse/" + data.words[i]);
                $(word).attr("target", "_blank");
                $(".column" + (i%2 + 2) ).append( $(word) );
                $(".column" + (i%2 + 2) ).append( $(lbrk) );
            }
            $("#possible").html(data.words.length + " Possible Words");
        }, error: function(xhr, desc, err) {
            console.log(xhr);
            console.log("Details: " + desc + "\nError:" + err);
        }, complete: function(){
            $("#loading").addClass("hidden");
            blocking = false;   
        }
    }); // end ajax call
};

function setProto(){
    if(length == 0) length = 4;
    for(var i=0; i<8; i++){
        if(i<length){
            $($("#proto").children()[i]).css("display", "block");
        }else{
            $($("#proto").children()[i]).css("display", "none");
        }
    }
}

function getProto(){
    var ret = "";
    for(var i=0; i<length; i++){
        if($($("#proto").children()[i]).val() == ""){
            ret += "*";
        } else{
            ret += $($("#proto").children()[i]).val();
        }
    }
    return ret.toLowerCase();
}

// return true if proto is not all asterisks
function checkProto(){
    var proto = getProto();
    for(var i=0; i<proto.length; i++){
        if(proto.charAt(i) != "*"){
            return true;
        }
    }
    return false;
}

function dataSelect(target){
    if($(target).hasClass("selected")) return;

    $("#likely").toggleClass("selected");
    $("#possible").toggleClass("selected");

    if(target.id == "likely"){
        $("#lettergraph").removeClass("hidden");
        $("#wordlist").addClass("hidden");
    }else{
        $("#lettergraph").addClass("hidden");
        $("#wordlist").removeClass("hidden");
    }
}

var reset = function(){
    length = 4;
    $("#length").val(4);
    for(var i=0; i<length; i++){
        $($("#proto").children()[i]).val("");
    }
    $(".bottom-row").addClass("hidden");
    $("#dead").val("");
    setProto();
}
\$\endgroup\$
  • \$\begingroup\$ Why are you using continue so much? \$\endgroup\$ – Caperneoignis May 31 '16 at 23:39
  • \$\begingroup\$ I didn't know there was any other logical way of doing what I needed to do. In the top loop I need to iterate through each word in the dictionary, and then I need to iterate through each letter in that word to check against the prototype the user has submitted. For the continue 3 line for example I need to throw out the word but not break out of the dictionary iteration. \$\endgroup\$ – Luke May 31 '16 at 23:45
  • \$\begingroup\$ Then use a while loop with a bool flag that exits out of the loop but stays in the foreach dictionary loop. You can also look up red, black recursion, although I'm not sure you can do that in php with anti-base cases. But generally you want to avoid continues and breaks. A while loop can do those just as easy, and also is easier to understand at a glance. \$\endgroup\$ – Caperneoignis May 31 '16 at 23:50
  • \$\begingroup\$ If there is an else after the if there's no need for a continue inside the if. And the continue 2, continue 3 seem like overusing continue. But there are perfectly valid cases where continue is the right thing to use. \$\endgroup\$ – coyotte508 Jun 2 '16 at 15:42
1
\$\begingroup\$
$length = $_POST['length'];
$proto = $_POST['proto'];
$dead = $_POST['dead'];

Consider adding more normalization to this. For example, trim will strip off leading and trailing whitespace.

foreach($dict as $word){
    $flag = true;
    // check that word matches proto
    for($i=0; $i<strlen($proto); $i++){
        if($proto[$i] == "*"){          // wildcard
            for($j=0; $j<strlen($live); $j++){
                if($word[$i] == $live[$j]){     // disallow a*** matching abba
                    $flag = false;
                    continue 3;
                }
            }
            continue;
        }
        if($proto[$i] == $word[$i]){    // correct, go to next letter
            //error_log($proto[$i] . " = " . $word[$i]);
            continue;
        } else{                         // incorrect
            //error_log($proto[$i] . " != " . $word[$i]);
            $flag = false;
            continue 2;
        }
    }

    if($flag){
        array_push($words, $word);
    }

}// end foreach loop

You don't need $flag here with the way that you are using continue.

$protoLength = strlen($proto);
$deadLength = strlen($dead);

foreach ($dict as $word) {
    for ($i = 0; $i < $protoLength; $i++) {
        if ($proto[$i] == "*") {          // wildcard
            // disallow a*** matching abba
            if (strpos($live, $word[$i]) !== false) {
                continue 2;
            }
        } else if ($proto[$i] != $word[$i]) {
            continue 2;
        }
    }

    for ($i=0; $i < $deadLength; $i++) { 
        if (strpos($word, $dead[$i]) !== false){
            error_log("adding " . $word . " to deadWords");
            continue 2;
        }
    }

    array_push($words, $word);
}

This will do the same thing without all the $flag setting since you skip to the next iteration every time you set $flag to false.

Adding an else saves having to do a continue in the first if. And you never needed the second if. You're really just checking the false case.

I wouldn't put strlen in a loop check, as I'm not convinced that PHP will optimize it out rather than calling it on each iteration. Doing it this way ensures that it will only get checked once.

A strpos call is going to be more efficient than a for loop.

I moved the dead letter check into the same loop. This way we never add a dead word to the list rather than removing them later.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

With a common english dictionary wordlist being 1.2MB in size, i would suggest loading the wordlist from the server and solving it in javascript.

Aside of that: a more efficient way of solving this would be to construct a regex from your input, then looping over the wordlist.

if (strlen($dead)) {
    $letterMask = '[^'.$dead.']';
} else {
    $letterMask = '.'; //match any char
}

$regex = '/' . str_replace('*', $letterMask, $proto).'/'; // 
$words = [];
foreach ($dict as word) {
    if (preg_match($regex, $word)) {
        $words[] = $word;
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Using a regex is a good idea, but why would I want clients to download a 1.2 MB file every time? That makes no sense. Download time is orders of magnitude greater than computation time, so I'd rather send the minimum amount of info over the wire. \$\endgroup\$ – Luke Jun 2 '16 at 16:27
  • \$\begingroup\$ They would only need to download it once they open the page. And you can set cache-headers, so they dont even download it again when visiting the page a second time... The upside is that the expensive processing is done on client side, and your server does not get overwhelmed easily. \$\endgroup\$ – Fivetide Jun 2 '16 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.