The problem here is basically the same as in this post, but I wanted to make the implementation more general and modular.

The principle is the same: you have a starting node, for example a numerical value, and you can use a discrete set of functions. Each function takes the first value as parameter and produce an output. Again each output became the new input of each function.

The following tree shows the principle:

Given should be: starting node, searched node, functions list, max number of steps. If the algorithm will not find the searched node/value, then it will stop after the given number of steps. If it finds the node, it stops and don’t go on.

The algorithm implemented in PHP can be divided in two functions.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
function search($funcs,$start,$comp,$n) { $res[0]=$start; for($i=0;$i $res_v){ foreach($funcs as $func_k => $func_v){ $res[$c]=call_user_func($func_v,$res_v); $GLOBALS["path"][$res[$c]][$func_v]=$res_v; if($res[$c]==$comp) break 3; $c++; } } } function paths($end,$c=0,$paths=null){ $count=count($GLOBALS["path"][$end]); $i=0; foreach($GLOBALS["path"][$end] as $func => $prev){ if($c>$i && $count>$c){$i++;continue;} $paths[]=$func; if(isset($GLOBALS["path"][$prev])) return paths($prev,$c,$paths); } $paths=array_reverse($paths); return $paths; } |

Let’s see how to use them with an example. We can customized as many functions as we want. Here I just wrote three simple functions to apply:

1 2 3 4 5 6 7 8 9 |
function x2($x){ return $x*2; } function x3($x){ return $x*3; } function x5($x){ return $x*5; } |

After this, starting from the number 5 we want to stop at 450.

1 2 3 4 5 6 7 8 |
$start=5; $stop=450; $max_steps=5; $funcs=array("x2","x3","x5");//functions list search($funcs,$start,$stop,$max_steps); $paths=paths($stop,0);//find the FIRST path from 5 to 450 $paths=paths($stop,1);//find the SECOND path from 5 to 450 (if not exists, the first will be returned!) |

To display the given “path” of applied functions starting from 5 till 450 we can easily use the following line:

1 |
echo "<pre>".print_r($paths)."</pre>"; |

## Leave a Reply