Puzzle Challenge from old "Isaac Asimov" magazine (1986)!

[vincenz0h]

Hello, I've just recently begun teaching myself PHP. I've developed a couple programs, but nothing very sophisticated. Today I was pondering what kind of project/exercise I should do in order to grow my skills. I happened to be reading an old "Issac Asimov" short story sci-fi magazine (Feb 1986) that I found in a trash pile (a whole stack of them actually! "Analog" as well) and came across the following challenge:

 

"To honor the year '86, here are two challenging problems to be answered next month. If you have a programmable computer you may be able to solve them with a program, but first some background.

 

An old number recreation has to do with adding plus or minus signs within the sequence 123456789, or within its reversal 987654321, to make the total a specified number. For instance, the only way to make the rising sequence total 100 with as few as three signs is 123-45-67+89=100.

 

Your two tasks are : (1) Add no more than four plus or minus signs to 123456789 to make the total 86, (2) add no more than five plus or minus signs to 987654321 to make the total 86. Each task has only one solution. Although a minus sign is sometimes permitted in front of the first number, I'll save you wasted hours by saying that this is not required for the unique solutions to either problem.

 

 

I thought the part about "if you have a programmable computer..." was quite charming and thought "hey, I have a programmable computer!" LOL    So I gave it a shot.

 

I quickly whipped up a program that found the solution (okay, maybe not quickly, but hey, I did it) and actually found that their solution for the number 100 had a typo in one of the signs!

 

I wanted to post my script here... but not before letting other people have a crack at it! ... that is... IF you happen to have a programmable computer!

[JasonLewis]

Aw dang, mine isn't programmable.

[vincenz0h]

okay ya slags... I think it's been long enough for you to give this a try... so here's my solution:

 

<?php

// Define an array containing 9 elements: 1, 2, 3, 4, 5, 6, 7, 8, 9.
$numarr=array("1"=>"1","2"=>"2","3"=>"3","4"=>"4","5"=>"5","6"=>"6","7"=>"7","8"=>"8","9"=>"9");


$sum=0;	
while ($sum!=86){

// The elements of $numarr are then concatenated, in order, into strings 
// of random length with the maximum length of the strings being 4 characters.

$i=1;					// $i is used as the index counter for $numarr, 
				// and denotes the first element of the string

$count=0;				// $count is used to index how many strings (ie. spaces between strings) we have.

while ($i<=9 && $count<=4){		// Because we want to use no more than 4 sign, 
				// we want no more than 4 strings to add.
	$count++;
	$strarr[$count]="";		
	$m=rand($i,($i+3));		// $m is the index of the last element that is concatenated into the string.


	if ($m<10 && $count<=4){	// If $m is set beyond the last index in the array, or if 
				// this is the 4th string, then $m is set to 9, and all of the 
				// remaining elements in $numarr will create the last string.

		while ($i<=$m){
			$strarr[$count] .= $numarr[$i];		// Each element of $numarr is concatenated into a string
			$i++;					// which is then stored as a string in $strarr
		}

	} else {
		$m=9;

		while ($i<=$m){
			$strarr[$count] .= $numarr[$i];	
			$i++;
		}
	}
}

// Now we have a second array of numbers that can be summed together.

print "\n\n";


$sum=0;		// We want to reset our variable $sum to 0
		// in order to clear the results from the last iteration.

$j=1;		// $j serves as an index for our number strings.


while ($j<=($count)){	


	// the sign of the string is chosen at random, and the string is 
	// then either added or subtracted to the existing sum accordingly.

	$z=rand(0,1);	
	switch($z){
		case 0:		
			$sum=$sum+$strarr[$j];
			print "+";		// the sign is printed
			break;
		case 1:
			$sum=$sum-$strarr[$j];
			print "-";		
			break;
	}

	print $strarr[$j];		// the string being added/subtracted is printed
	$j++;
}

print "=$sum";			// The sum is printed
}

// The output of this program will be a list of all results from this random process.
// The very last output will be the solution to the puzzle; "+12+34-56+7+89=86"


?>

[ignace]

Now that you have solved that you may want to try The million dollar problems (you get a million dollar if you can solve one of them)

[Daniel0]

Now that you have solved that you may want to try The million dollar problems (you get a million dollar if you can solve one of them)

 

You can try to prove that P = NP and compete with Deolalikar who is trying to prove that P != NP

[Alex]

Now that you have solved that you may want to try The million dollar problems (you get a million dollar if you can solve one of them)

 

You can try to prove that P = NP and compete with Deolalikar who is trying to prove that P != NP

Things aren't looking so good for him, http://www.newscientist.com/article/dn19313-tide-turns-against-milliondollar-maths-proof.html