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:
Server receives the board as a JSON encoded multidimensional array via an AJAX request.
$board = json_decode($_REQUEST["board"]);
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();
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();
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();
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]]"
json_decode() call needed)
The following are my two valid test $board strings. Between the two of them, all ships occur in both orientations.
Test #1:
[[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]]
Test #2:
[[0,1,0,0,0,0,0,0,0,0],[0,1,0,0,2,2,2,2,0,0],[0,1,0,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0],[0,1,3,0,0,0,0,0,0,0],[0,0,3,0,0,0,0,0,0,0],[0,0,3,0,0,0,0,0,0,0],[0,0,5,5,0,0,4,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,0,4,0,0,0]]
The method to follow is a simple preg_match() call in php. The technique uses lookaheads to validate each ship, followed by a fullstring match that validates the json structure.
This technique is most commonly used when validating passwords, where a string must be generally validated for length and/or valid characters, but also checked for minimum occurrences of characters or ranges of characters (e.g. password must be a minimum of 8 characters and include a lowercase, uppercase, number, and a symbol).
The brilliance in my method is not just that it is a single call, but that it can also be seamlessly called to validate the data in javascript as well.
Now for the patterns (seatbelts on, please):
(1590 characters) (Test#1: 371 steps; Test#2 446 steps)
/(?=^[^1]*(?:1,1,1,1,1|1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1)[^1]*$)(?=^[^2]*(?:2,2,2,2|2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2)[^2]*$)(?=^[^3]*(?:3,3,3|3\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+3\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+3)[^3]*$)(?=^[^4]*(?:4,4,4|4\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+4\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+4)[^4]*$)(?=^[^5]*(?:5,5|5\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+5)[^5]*$)^\[\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\]\]$/
(306 characters) (Test#1: 576 steps; Test#2 698 steps)
/(?=^[^1]*(?:1,1,1,1,1|1(?:(?:\D+[^1]){9}\D+1){4})[^1]*$)(?=^[^2]*(?:2,2,2,2|2(?:(?:\D+[^2]){9}\D+2){3})[^2]*$)(?=^[^3]*(?:3,3,3|3(?:(?:\D+[^3]){9}\D+3){2})[^3]*$)(?=^[^4]*(?:4,4,4|4(?:(?:\D+[^4]){9}\D+4){2})[^4]*$)(?=^[^5]*(?:5,5|5(?:\D+[^5]){9}\D+5)[^5]*$)(?:(?:^\[|)\[[0-5](?:,[0-5]){9}\](?:,|\]$)){10}/
The reason the first pattern is faster is because I have removed all inessential non-capture groups. The cost, in terms of "Brevity", is drastic. "Readability" is extremely poor in both of patterns. Both patterns maintain the same "Accuracy", but the first pattern wins on "Efficiency" by some margin.
All lookaheads have the same basic structure and obey the game rules/requirements:
(?= #lookahead, but don't "consume" any characters in the process
^ #from the start of the string
[^5]* #quickly, greedily match all characters that are not a 5
(?: #non-capture group to isolate the "alternatives"
5,5 #literally match a 2-peg row
| # or
5\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+5 #match two 5 pegs that have nine non-5 pegs between them
) #end non-capture group
[^5]* #quickly, greedily match all characters that are not a 5 (ensure there are no more 5's in the string)
$ #all the way to the end of the string
) #end the lookahead
The general board structure & pegs matching:
^ #from the start of the string
\[ #match the opening outer bracket
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\], #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\], #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\], #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\], #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\], #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\], #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\], #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\], #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\], #match a row of 0, 1, 2, 3, 4, or 5's
\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\] #match a row of 0, 1, 2, 3, 4, or 5's
\] #match the closing outer bracket
$ #to the end of the string
PHP Code: (Demo)
$pattern='/(?=^[^1]*(?:1,1,1,1,1|1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+[^1]\D+1)[^1]*$)(?=^[^2]*(?:2,2,2,2|2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+[^2]\D+2)[^2]*$)(?=^[^3]*(?:3,3,3|3\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+3\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+[^3]\D+3)[^3]*$)(?=^[^4]*(?:4,4,4|4\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+4\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+[^4]\D+4)[^4]*$)(?=^[^5]*(?:5,5|5\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+[^5]\D+5)[^5]*$)^\[\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\],\[[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5],[0-5]\]\]$/';
echo preg_match($pattern,$_REQUEST["board"]) ? 'success' : 'invalid';