Reimplementation of "The Mysterious Program." https://stripe-ctf.com/

bst-timing.php

<?php
$words = file('/usr/share/dict/words');

function generateBTree($input) {
	$tree = [];

	$p = $tree;

	foreach($input as &$word) {
		$word = trim($word);
		$p = &$tree;

		$chars = str_split($word);
		$len = count($chars) - 1;

		foreach($chars as $i=>$c) {
			if (!isset($p[$c])) {
				$p[$c] = $i < $len ? [] : ['TERMINAL' => true];
			}
			$p = &$p[$c];
		}
	}

	return $tree;
}

function findInBTree($search, $tree, $terminal = true) {
	$chars = str_split($search);
	$len = count($chars) - 1;

	$p = &$tree;

	foreach($chars as $i=>$c) {
		if (!isset($p[$c])) return false;

		if ($i === $len && !isset($p[$c]['TERMINAL'])) return false;

		$p = &$p[$c];
	}

	return true;
}

if (file_exists('tree.export.php')) {
	include('tree.export.php');
} else {
	$tree = generateBTree($words);
	file_put_contents('tree.export.php', "<?php\n\$tree=" . var_export($tree, true) . ';');
}

$in = file('php://STDIN');

echo "Running no-print test\n";

$s_time = microtime(true);
foreach($in as &$word) {
	$word = trim($word);
	$search_word = strtolower($word);

	$found = findInBTree($search_word, $tree);
}
$e_time = microtime(true);

$np_time = $e_time - $s_time;

echo "Running print test\n";

$s_time = microtime(true);
foreach($in as &$word) {
	$word = trim($word);
	$search_word = strtolower($word);

	$found = findInBTree($search_word, $tree);

	echo ($found ? $word : ('<' . $word . '>')) . "\n";
}
$e_time = microtime(true);

$p_time = $e_time - $s_time;

echo "\n=============================\n";
echo "No print: $np_time\nprint:$p_time\n";