Pi pi

problem.txt

The first 12 digits of pi are 314159265358. We can make these digits into an 
expression evaluating to 27182 (first 5 digits of e) as follows:

3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182   

or 

3 + 1 - 415 * 92 + 65358 = 27182

Notice that the order of the input digits is not changed. 
Operators (+,-,/, or *) are simply inserted to create the expression.  

Write a function to take a list of numbers and a target, 
and return all the ways that those numbers can be formed into expressions evaluating to the target

For example: 

f("314159265358", 27182) should print:      

3 + 1 - 415 * 92 + 65358 = 27182 

3 * 1 + 4 * 159 + 26535 + 8 = 27182 

3 / 1 + 4 * 159 + 26535 + 8 = 27182 

3 * 14 * 15 + 9 + 26535 + 8 = 27182 

3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182

solution.php

<?php 

function prune($value, $rest, $target) {
	
	if ($rest > 0){
		
		if (  (($value/$rest) > $target ) || (($value * $rest) < $target) ) return true;
		
	}
	
	return false;
}



function findSolution($source, $target){
	
	$solutions = array();
	$expressions = array();
	$operators = array("+", "-", "/", "*", "");
	
	for ($i=0; $i < strlen($source); $i++) {
		
		$ch = $source[$i];
		$keys = array_keys($expressions);
		
		if (count($keys) == 0){
			$expressions[$ch] = eval("return ($ch);"); //eval only accepts statements, not expressions
			continue;
		}
		
		$new_expression = array();
		$tmp = $source[$i+1];
		
		eval("$eval_tmp = (". $tmp . ");");
		
		$rest_eval = ($i < (strlen($source)-1)) ? (float)($eval_tmp) : 0.0;
		
		print_r($expressions);
		
		foreach ($keys as $key) {
			
				foreach ($operators as $operator){
					
					$new_key = $key + $operator + $ch;
					$value = eval("return ($new_key);");
					
					if (!prune($value, $rest_eval, $target)){
						
						$new_expression[$new_key] = $value;
					}
				}
			
		}
		
		$expressions = $new_expression;
		$new_keys = array_keys($expressions);
		
		foreach ($new_keys as $key) {
			
			if ($expressions[$key] == $target){
				array_push($solutions, $key);
			}
		}
		
		return $solutions;
		
	}
	
}


echo "<pre>";
print_r(findSolution("314159265358", 27182));
echo "</pre>";


?>

solution.py

def prune(value, rest, target):
	# pruning logic here to prevent exponential blow up
	# all pruning logic should go here
	if (rest > 0):
		if ((value / rest) > target) or ((value * rest) < target):
			return True
	return False

def findSolution(source, target):
	solutions = []
	expressions = {}
	operators = ["+","-","/", "*",""]
	for i, ch in enumerate(source):
		keys = expressions.keys()
		if len(keys) == 0:
			expressions[ch] = eval(ch)
			continue
		new_expressions = {}
		rest_eval = float(eval(source[i+1:])) if i < (len(source) - 1) else 0.0
		for key in keys:
			for operator in operators:
				new_key = key + operator + ch
				value = eval(new_key)
				if not prune(value, rest_eval, target):
					new_expressions[new_key] = value
		expressions = new_expressions

	for key in expressions.keys():
		if expressions[key] == target:
			solutions.append(key)
	return solutions


print(findSolution("314159265358", 27182))

I tried the PHP solution and it didn't work -- first erred out on "$eval_tmp" -- when I fixed that it came back with the result "3";