php - Validate A Game Board, And Fast

Question

I am creating a multiplayer Battleship game using an Apache/PHP server (yes, I know Node would be much better for this, but I'll get around to learning it later). Anyways, I am at the point in which both players are uploading their game boards to start the game. While my client side JavaScript would obviously properly compile and validate boards before sending them off to the server, that is still vulnerable to cheating, so the server must also double check. However, on the server, speed and efficiency is everything.

As of now, this is the process my server follows:

1. Server receives the board as a JSON encoded multidimensional array via an AJAX request.

   $board = json_decode($_REQUEST["board"]);
   

2. Server validates the structure of the passed input.

   $validate = array(gettype($board) == "array", count($board) == 10);
   for($i = 0; $i < count($board); $i++) {
      array_push($validate, count($board[$i]) == 10);
      for($ii = 0; $ii < count($board[$i]); $ii++) {
          array_push($validate, gettype($board[$i][$ii]) == "integer");
      }
   }
   if(in_array(0, $validate)) throwError();
   

3. In the array, numbers zero through five represent blank, aircraft carrier, battleship, cruiser, submarine, and destroyer tiles respectively. I count the proper quantity of each.

    $valueCount = array_count_values(array_merge($board[0], $board[1], $board[2], $board[3], $board[4], $board[5], $board[6], $board[7], $board[8], $board[9]));
    $template = array("0"=>83,"1"=>5, "2"=>4, "3"=>3, "4"=>3, "5"=>2);
    if($template != $valueCount) throwError();
   

4. I need to ensure that ship tiles are only vertical or horizontal lines.

    $shipsValid = array(false, false, false, false, false);
    $transpose = array_map(null, $board[0], $board[1], $board[2], $board[3], $board[4], $board[5], $board[6], $board[7], $board[8], $board[9]);
    for($i = 0; $i < 9; $i++) {
        $temp1 = array_count_values($board[$i]);
        $temp2 = array_count_values($transpose[$i]);
        if($temp1["1"] == 5 || $temp2["1"] == 5) shipsValid[0] = true;
        if($temp1["2"] == 4 || $temp2["2"] == 4) shipsValid[1] = true;
        if($temp1["3"] == 3 || $temp2["3"] == 3) shipsValid[2] = true;
        if($temp1["4"] == 3 || $temp2["4"] == 3) shipsValid[3] = true;
        if($temp1["5"] == 2 || $temp2["5"] == 2) shipsValid[4] = true;
    }
    if(in_array(0, $shipsValid)) throwError();
   

5. I need to ensure ships are continuous with no gaps.

   ??????????????????????????
   

With enough work, I could have completed step five, but it would have been grossly inefficient, looping through everything repeatedly. So, in conclusion, how can I make what I have designed more efficient, and how I complete the final step (5) to validating the uploaded board?

Example Board (Valid):

    "[[0,1,1,1,1,1,0,0,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,3,3,3,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,5,0,0,0,4,4,4,0],
    [0,0,5,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0]]"

Example Board (Invalid, for many reasons):

    "[[0,1,1,0,1,1,0,0,0,1],
    [0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,2,0,0],
    [0,6,6,6,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,4,4,4,4,4],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0]]"

Answer 1

This solution is ugly and not clearly explained inline, but it does set the time record here with an average of 47.99473047 μs to validate a correct board on my server. I do apologize for the excessive use of inline logic structures; its kinda my coding style.

function quit() {
    echo "invalid request";
    exit();
}

$board = json_decode($_REQUEST["board"]);
if(gettype($board) != "array"|| count($board) != 10) quit();
foreach($board as $row) {
   if(gettype($row) != "array"|| count($row) != 10) quit();
   foreach($row as $cell) if(gettype($cell) != "integer") quit();
}
$strand = array_merge($board[0], $board[1], $board[2], $board[3], $board[4], $board[5], $board[6], $board[7], $board[8], $board[9]);
$fleet = array(array_keys($strand, 0), array_keys($strand, 1), array_keys($strand, 2), array_keys($strand, 3), array_keys($strand, 4), array_keys($strand, 5));
if(count($fleet[0]) != 83 || count($fleet[1]) != 5 || count($fleet[2]) != 4 || count($fleet[3]) != 3 || count($fleet[4]) != 3 || count($fleet[5]) != 2 || count($fleet) != 6) quit();
foreach($fleet as $ship) if($ship != $fleet[0]) for($i = 0; $i < count($ship); $i++) if($ship[0] + 10 * $i != $ship[$i]  && $ship[$i] - $ship[0] != $i) quit();

echo "success";
exit();

This process first checks that the array is properly structured (10 by 10 with integer values). It then combines all the arrays into one long array and fetches the keys of the values 0 through 5. I then check that the proper amount of each number (for each ship) occurs in the keys. Lastly, I check that keys for 1 through 5 occur sequentially or by tens, which would mean that they are horizontal or vertical.

It feels kinda weird answering my own question, but I'm open to other ideas and optimizations on top of my own.