<html>
<head>
<link rel="stylesheet" type="text/css" href="http://yui.yahooapis.com/2.6.0/build/fonts/fonts-min.css" />
<link rel="stylesheet" type="text/css" href="http://yui.yahooapis.com/2.6.0/build/treeview/assets/skins/sam/treeview.css" />
<script type="text/javascript" src="http://yui.yahooapis.com/2.6.0/build/yahoo-dom-event/yahoo-dom-event.js"></script>
<script type="text/javascript" src="http://yui.yahooapis.com/2.6.0/build/treeview/treeview-min.js"></script>
<title>MIU Problem</title>
</head>
<body class="yui-skin-sam">
<div id="treeDiv1">
<?php
// String ends in I
define('RULE_ONE', '/I$/');
// String begins with an M
define('RULE_TWO', '/^M/');
// String has instance of 'III'
define('RULE_THREE', '/III/');
// String has instance of 'UU'
define('RULE_FOUR', '/UU/');
define('MAX_SIZE','20');
define('START', 'MI');
define('GOAL', 'MU');
define('REPLACE_LIMIT','1');
$theorems = array();
$axiom = START;
print "<ul>\n";
print "<li>" . $axiom . "</li>\n";
solve($axiom);
print "</ul>\n";
function solve($string) {
global $theorems;
if($string == GOAL) print 'We found MU!';
if(!isset($theorems[$string])) {
print "<ul>\n";
$theorems[$string] = true;
ruleOne($string);
ruleTwo($string);
ruleThree($string);
ruleFour($string);
print "</ul>\n";
}
}
function ruleOne($string) {
if(preg_match(RULE_ONE, $string) && strlen($string) < MAX_SIZE) {
$newString = $string . 'U';
print "<li>" . $newString . " by rule one.</li>\n";
solve($newString);
}
}
function ruleTwo($string) {
if(preg_match(RULE_TWO, $string) && strlen($string) < MAX_SIZE) {
$newString = $string . substr($string, 1);
print "<li>" . $newString . " by rule two.</li>\n";
solve($newString);
}
}
function ruleThree($string) {
if(preg_match(RULE_THREE, $string) && strlen($string) < MAX_SIZE) {
$newString = preg_replace(RULE_THREE, 'U', $string, REPLACE_LIMIT);
print "<li>" . $newString . " by rule three.</li>\n";
solve($newString);
}
}
function ruleFour($string) {
if(preg_match(RULE_FOUR, $string) && strlen($string) < MAX_SIZE) {
$newString = preg_replace(RULE_FOUR, '', $string, REPLACE_LIMIT);
print "<li>" . $newString . " by rule four.</li>\n";
solve($newString);
}
}
?>
</div>
<script>
var tree = new YAHOO.widget.TreeView("treeDiv1");
tree.render();
</script>
</body>
</html>