Word game solver

wordgamesolver.php

<?php

$begin_time = microtime( true );

$material = <<<EOF
N1 	E1 	F3 	W3 	J4
S1 	E1 	O1 	I1 	H3
B2 	V3 	Y3 	T1 	N1
G2 	R1 	O1 	T1 	D2
U1 	A1 	D2 	L1 	M2
EOF;

$bag = <<<BAG
E1 U1 N1 M2 R1 E1 G2 Y3 O1 O1 U1 D2 O1 L1 X4 I1 R1 A1 I1 H3 L1 E1 E1
BAG;

$my_total_score    = 191.5;
$their_total_score = 107;
$it_is_my_turn     = true;

$original_my_score    = $my_total_score;
$original_their_score = $their_total_score;
$original_turn        = $it_is_my_turn;

$material = trim( strtolower( $material ) );

$rows = explode( "\n", $material );
$table = array();
$row_counter = 0;
$wild_card = false;
foreach ( $rows as $row ) {
	$cell_counter = 0;
	$cells = explode( "\t", $row );
	foreach ( $cells as $cell ) {
		$letter = substr( $cell, 0, 1 );
		if ( $letter === 'q' ) $letter = 'Qu';
		if ( $letter === '.' ) $letter = '';
		if ( $letter === '*' ) $wild_card = true;
		$table[ $row_counter ][ $cell_counter ] = $letter;
		$cell_counter++;
	}
	$row_counter++;
}

global $highest_score;
$highest_score = 0;

global $words;
$untrimmed_words = file( 'words_alpha.txt' );

foreach ( $untrimmed_words as $word ) {
	$words[ trim( $word ) ] = true;
}
unset( $untrimmed_words );

echo "Trimmed the word list.\n";

global $three_letters;
foreach ( array_keys( $words ) as $word ) {
	$three_letters[ substr( $word, 0, 3 ) ] = true;
}

echo "Generated three-letter words.\n";

global $four_letters;
foreach ( array_keys( $words ) as $word ) {
	$four_letters[ substr( $word, 0, 4 ) ] = true;
}

echo "Generated four-letter words.\n";

global $five_letters;
foreach ( array_keys( $words ) as $word ) {
	$five_letters[ substr( $word, 0, 5 ) ] = true;
}

echo "Generated five-letter words.\n";

global $six_letters;
foreach ( array_keys( $words ) as $word ) {
	$six_letters[ substr( $word, 0, 6 ) ] = true;
}

echo "Generated six-letter words.\n";

global $seven_letters;
foreach ( array_keys( $words ) as $word ) {
	$seven_letters[ substr( $word, 0, 7 ) ] = true;
}

echo "Generated seven-letter words.\n";

global $eight_letters;
foreach ( array_keys( $words ) as $word ) {
	$eight_letters[ substr( $word, 0, 8 ) ] = true;
}

echo "Generated eight-letter words.\n";

global $nine_letters;
foreach ( array_keys( $words ) as $word ) {
	$nine_letters[ substr( $word, 0, 9 ) ] = true;
}

echo "Generated nine-letter words.\n";

echo "\n";

global $point_values;
$point_values = array(
	'a' => 1,
	'b' => 2,
	'c' => 2,
	'd' => 2,
	'e' => 1,
	'f' => 3,
	'g' => 2,
	'h' => 3,
	'i' => 1,
	'j' => 4,
	'k' => 4,
	'l' => 1,
	'm' => 2,
	'n' => 1,
	'o' => 1,
	'p' => 2,
	'q' => 4,
	'r' => 1,
	's' => 1,
	't' => 1,
	'u' => 1,
	'v' => 3,
	'w' => 3,
	'x' => 4,
	'y' => 3,
	'z' => 5,
	'*' => 0,
);

global $words_found;
$words_found = array();

generate_words( $table, $words_found, false );
usort( $words_found, 'word_cmp' );

$original_words_found = $words_found;
$original_table       = $table;
$original_bag         = $bag;

$best_opening_move  = '';
$best_opening_score = -99999999;

$i = 0;
foreach ( $original_words_found as $best_word ) {
	$table          = $original_table;
	$bag            = $original_bag;
	$opening_coords = $best_word['coords'];

	fill_the_board( $table, $bag, $best_word['coords'] );

	$continue = true;
	$first_go = true;
	$my_total_score    = $original_my_score;
	$their_total_score = $original_their_score;
	$words_found       = $original_words_found;
	$it_is_my_turn     = $original_turn;

	do {
		if ( ! $first_go ) {
			generate_words( $table, $words_found, false );
			usort( $words_found, 'word_cmp' );
			if ( ! empty( $words_found ) ) {
				$best_word = array_shift( $words_found );	
			}
			fill_the_board( $table, $bag, $best_word['coords'] );
		}

		if ( ! empty ( $words_found ) ) {
			if ( $it_is_my_turn ) {
				$my_total_score += $best_word['score'];	
				$coords = replace_coords( $best_word['coords'] );
				echo 'I play ' . $best_word['word'] . ' (' . $coords . ') for ' . $best_word['score'] . ' points (total ' . $my_total_score . ")\n";
				$it_is_my_turn = false;
			} else {
				$their_total_score += $best_word['score'];	
				$coords = replace_coords( $best_word['coords'] );
				echo 'They play ' . $best_word['word'] . ' (' . $coords . ') for ' . $best_word['score'] . ' points (total ' . $their_total_score . ")\n";
				$it_is_my_turn = true;
			}
			$words_found = array();
			$first_go = false;
		} else {
			$continue = false;
			$total_score = $my_total_score - $their_total_score;

			if ( $total_score > $best_opening_score ) {
				$best_opening_move  = replace_coords( $opening_coords );
				$best_opening_score = $total_score;
			}

			echo "\nFINAL RESULT: $total_score – ME $my_total_score, THEY $their_total_score - BEST MOVE SO FAR: $best_opening_move\n\n";

			$first_go = true;
		}
	} while ( $continue );

}

function print_table( $table ) {
	for ( $x = 0; $x < 5; $x++ ) {
		for ( $y = 0; $y < 5; $y++ ) {
			echo $table[ $x ][ $y ];
		}
		echo "\n";
	}
}

function replace_coords( $coords ) {
	return str_replace( array( '0', '1', '2', '3', '4' ), array( 'a', 'b', 'c', 'd', 'e' ), $coords );
}
/*
generate_words( $table, $words_found, true );

usort( $words_found, 'word_cmp' );

$total_words = array();
$best_result = -99999;

$counter = 20;
foreach ( $words_found as $word ) {
	$counter--;
	if ( $counter < 1 ) break;
	$myword = $word['word'];
	$score  = $word['score'];
	$coords = $word['coords'];
	
	if ( $score < $best_result ) {
		echo "No point looking at $myword.\n";
		continue;
	}

	$new_table = $table;
	fill_the_board( $new_table, $bag, $word['coords'] );
	$next_move_words_found = array();
	echo "Generating next move words for $myword... ";
	$debug = false;
	generate_words( $new_table, $next_move_words_found, $debug );
	echo "done, $counter to go.\n";
	usort( $next_move_words_found, 'word_cmp' );
	$word = array_shift( $next_move_words_found );

	$their_word  = $word['word'];
	$their_score = $word['score'];
	$total_score = $score - $their_score;

	$coords = str_replace( array( '0', '1', '2', '3', '4' ), array( 'a', 'b', 'c', 'd', 'e' ), $coords );
	$text = "$myword ($coords) – my score: $score – opponent word: $their_word - total score: $total_score \n";

	if ( $total_score > $best_result ) {
		echo $text;
		$best_result = $total_score;
	}
	$total_words[] = array(
		'score' => $total_score,
		'text'  => $text,
	);
}

usort( $total_words, 'word_cmp' );

echo "\nBest results:\n";
$counter = 5;
while ( $counter > 0 && ! empty( $total_words ) ) {
	$row = array_shift( $total_words );
	echo $row['text'];
	$counter--;
}
*/
$end_time = microtime( true );
$time = round( $end_time - $begin_time, 2 );
echo "\nTime spent: $time s\n";


function fill_the_board( &$board, &$bag, $moves ) {
	$bag_letters = explode( ' ', strtolower( $bag ) );
	$moves = str_split( $moves, 2 );
	do {
		$move = array_shift( $moves );
		$x    = substr( $move, 0, 1 );
		$y    = substr( $move, 1, 1 );

		if ( ! empty( $bag_letters ) ) {
			$letter = array_shift( $bag_letters );
			$letter = substr( $letter, 0, 1 );
			if ( $letter === 'Q' ) $letter = 'Qu';
			$board[ $x ][ $y ] = $letter;
		} else {
			$board[ $x ][ $y ] = '';
		}
	} while ( ! empty( $moves ) );
	$bag = implode( ' ', $bag_letters );
}

function word_cmp( $a, $b ) {
	return $a['score'] < $b['score'];
}

function score_word( $word ) {
	global $point_values;
	$score = 0;
	$multiplier = 1;
	for ( $i = 0; $i < strlen( $word ); $i++ ) {
		$letter = substr( $word, $i, 1 );
		if ( $letter == '2' ) {
			$multiplier *= 2;
		} elseif ( $letter == '3' ) {
			$multiplier *= 3;
		} else {
			$score += $point_values[ $letter ];
		}
	}

	$word = str_replace( array( '2', '3' ), '', $word );
	$word = str_replace( 'qu', 'q', $word );
	if ( strlen( $word ) >= 7 ) {
		$multiplier *= 2;
	}
	if ( strlen( $word ) < 3 ) {
		$multiplier = 1;
	}

	$score *= $multiplier; 

	return $score;
}

function generate_words( $data, &$words_found, $verbose = false ) {
	global $coordinates_checked;
	$coordinates_checked = array();
	$counter = 1;
	for ( $r = 0; $r < 5; $r++ ) {
		for ( $c = 0; $c < 5; $c++ ) {
			if ( $verbose ) echo "Working on square $counter\n";
			$counter++;
			$letter = get_letter( $r, $c, $data );
			if ( ! empty( $letter ) ) {
				$coords = $r . $c;
				traverse_board( $r, $c, $data, 1, $letter, $coords, $words_found, $verbose );
			}
		}
	}
}

function get_letter( $r, $c, $data ) {
	$letter = $data[ $r ][ $c ];
	if ( ! empty( $letter ) ) {
		if ( $r == 0 && $c == 0 ) $letter .= '2';
		if ( $r == 0 && $c == 4 ) $letter .= '3';
		if ( $r == 4 && $c == 0 ) $letter .= '3';
		if ( $r == 4 && $c == 4 ) $letter .= '2';
	}
	return $letter;
}

function traverse_board( $r, $c, $data, $depth, $word, $coordinates, &$words_found, $verbose = true ) {
	global $words, $three_letters, $four_letters, $five_letters, $six_letters, $seven_letters, $eight_letters, $nine_letters, $highest_score, $coordinates_checked;
	$data[ $r ][ $c ] = '-';
	$test_word = str_replace( array( '2', '3' ), '', $word );

	// If partial word doesn't appear in the list of existing prefixes, we can
	// stop going further down this rabbit hole.
	if ( strlen( $test_word ) == 3 && ! test_word( $test_word, $three_letters, 3 ) ) return;
	if ( strlen( $test_word ) == 4 && ! test_word( $test_word, $four_letters, 4 ) ) return;
	if ( strlen( $test_word ) == 5 && ! test_word( $test_word, $five_letters, 5 ) ) return;
	if ( strlen( $test_word ) == 6 && ! test_word( $test_word, $six_letters, 6 ) ) return;
	if ( strlen( $test_word ) == 7 && ! test_word( $test_word, $seven_letters, 7 ) ) return;
	if ( strlen( $test_word ) == 8 && ! test_word( $test_word, $eight_letters, 8 ) ) return;
	if ( strlen( $test_word ) == 9 && ! test_word( $test_word, $nine_letters, 9 ) ) return;

	if ( $depth > 1 ) {
		if ( ! isset( $coordinates_checked[ $coordinates ] ) ) {
			$coordinates_checked[ $coordinates ] = true;
		}
		if ( test_word( $test_word, $words ) ) {
			$score = score_word( $word );
			$words_found[] = array(
				'word'   => $word,
				'score'  => $score,
				'coords' => $coordinates,
			);
			if ( $score > $highest_score ) {
				$highest_score = $score;
				if ( $verbose ) {
					echo "$word ($score)\n";	
				}
			}
		}
	}
	$neighbours = get_neighbours( $r, $c, $data );
	if ( empty ( $neighbours ) ) return;
	foreach ( $neighbours as $coords ) {
		$coords = explode( '+', $coords );
		$new_letter = get_letter( $coords[0], $coords[1], $data );
		$new_word = $word . $new_letter;
		$new_coordinates = $coordinates . $coords[0] . $coords[1];
		if ( isset( $coordinates_checked[ $new_coordinates ] ) ) continue;
		traverse_board( $coords[0], $coords[1], $data, $depth + 1, $new_word, $new_coordinates, $words_found, $verbose );
	}
	return;
}

function test_word( $word, $list ) {
	if ( strpos( $word, '*' ) !== false ) {
		$pattern = '/^' . str_replace( '*', '.+', $word ) . '$/';
		global $words;
		$matches = preg_grep( $pattern, array_keys( $words ) );
		if ( count( $matches ) > 0 ) {
			return true;
		}
	} else {
		return isset( $list[ $word ] );
	}
	return false;	
}

function get_neighbours( $r, $c, $data ) {
	$neighbours = array();
	for ( $rx = $r-1; $rx <= $r+1; $rx++ ) {
		for ( $cy = $c-1; $cy <= $c+1; $cy++ ) {
			if ( $rx == $r && $cy == $c ) continue;
			if ( $rx < 0 || $rx > 4 || $cy < 0 || $cy > 4 ) continue;
			$coordinates = $r . $c . $rx . $cy;
			$forbidden_moves = array(
				'0011', '1100',
				'4031', '3140',
				'0110', '1001',
				'0314', '1403',
				'3041', '4130',
				'3443', '4334',
				'0413', '1304',
				'4433', '3344',
			);
			if ( in_array( $coordinates, $forbidden_moves ) ) continue; 
			if ( $data[ $rx ][ $cy ] == '-' ) continue;
			if ( $data[ $rx ][ $cy ] ) {
				$neighbours[] = $rx . '+' . $cy;
			} else {
				$new_neighbours = get_neighbours_simple( $rx, $cy, $data );	
				$checked_these = array();
				do {
					$count_neighbours = count( $new_neighbours );
					$temp_neighbours = $new_neighbours;
					foreach ( $new_neighbours as $coords ) {
						if ( isset( $checked_these[ $coords ] ) ) {
							continue;
						}
						list( $x, $y ) = explode( '+', $coords );
						$checked_these[ $coords ] = true;
						if ( empty( $data[ $x ][ $y ] ) ) {
							$more_neighbours = get_neighbours_simple( $x, $y, $data );
							$temp_neighbours = array_merge( $temp_neighbours, $more_neighbours );
						}
					}
					$new_neighbours = array_unique( $temp_neighbours );
				} while ( count($new_neighbours ) > $count_neighbours );
				$non_empty_neighbours = array();
				foreach ( $new_neighbours as $coords ) {
					list( $x, $y ) = explode( '+', $coords );
					if ( ! empty( $data[ $x ][ $y ] ) ) {
						$non_empty_neighbours[] = $coords;
					}
				}
				$neighbours = array_merge( $neighbours, $non_empty_neighbours );
			}
		}
	}
	return $neighbours;
}

function get_neighbours_simple( $x, $y, $data ) {
	$neighbours = array();
	for ( $xx = $x - 1; $xx <= $x + 1; $xx++ ) {
		for ( $yy = $y - 1; $yy <= $y + 1; $yy++ ) {
			if ( $xx == $x && $yy == $y ) continue;
			if ( $xx < 0 || $xx > 4 || $yy < 0 || $yy > 4 ) continue;
			$coordinates = $x . $y . $xx . $yy;
			$forbidden_moves = array(
				'0011', '1100',
				'4031', '3140',
				'0110', '1001',
				'0314', '1403',
				'3041', '4130',
				'3443', '4334',
				'0413', '1304',
				'4433', '3344',
			);
			if ( in_array( $coordinates, $forbidden_moves ) ) continue; 
			if ( $data[ $xx ][ $yy ] !== '-' ) {
				$neighbours[] = $xx . '+' . $yy;
			}
		}
	}
	return $neighbours;
}

/**
 * Generates all letter combinations in the word list up to five letters and
 * returns them in the order of descending commonness.
 */
function generate_letter_combos( ) {
	global $words;

	foreach ( array_keys( $words ) as $word ) {
		for ( $i = 0; $i < strlen( $word ); $i++ ) {
			$remaining_letters = strlen( substr( $word, $i ) );

			$singles = trim( substr( $word, $i, 1 ) );
			if ( ! isset( $letter_combos[ $singles ] ) ) $letter_combos[ $singles ] = 0;
			$letter_combos[ $singles ]++;

			if ( $remaining_letters < 2 ) continue;

			$pair = trim( substr( $word, $i, 2 ) );
			if ( ! isset( $letter_combos[ $pair ] ) ) $letter_combos[ $pair ] = 0;
			$letter_combos[ $pair ]++;

			if ( $remaining_letters < 3 ) continue;

			$triplet = trim( substr( $word, $i, 3 ) );
			if ( ! isset( $letter_combos[ $triplet ] ) ) $letter_combos[ $triplet ] = 0;
			$letter_combos[ $triplet ]++;

			if ( $remaining_letters < 4 ) continue;

			$four_letter = trim( substr( $word, $i, 4 ) );
			if ( ! isset( $letter_combos[ $four_letter ] ) ) $letter_combos[ $four_letter ] = 0;
			$letter_combos[ $four_letter ]++;

			if ( $remaining_letters < 5 ) continue;

			$five_letter = trim( substr( $word, $i, 5 ) );
			if ( ! isset( $letter_combos[ $five_letter ] ) ) $letter_combos[ $five_letter ] = 0;
			$letter_combos[ $five_letter ]++;
		}
	}

	arsort( $letter_combos );
	$letter_combos = array_keys( $letter_combos );

	return $letter_combos;
}