Thread: Algorithm for: 100234190 = 227

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    130

    Algorithm for: 100234190 = 227

    Hello,

    Few days ago I was thinking about finding algorithm for the following problem, and I got some ideas, but still not covering all the cases:

    The algorithm takes as input:

    100234190 = 227

    The output should be:

    100+2+34+1+90 = 227

    This means that the program should place the "+" sign such that the sum equal 227.

    My attempt:

    1. Check the whole number (100234190) if <= 227
    2. If not, then cut the rightmost digit (10023419), and repeat 1.
    3. Once the condition is achieved, then
    Store the number, say X e.g., that achieved the condition
    do: 227 - X
    re-do steps from 1. using (100234190) but without X, i.e. if X was 100, then
    I will start step 1. again with 234190.

    Note: the algorithm checks about the leftmost zeros, but I did not mention this.

    The algorithm doesn't work for all cases, I think that I need to maintain the sum every each step, but I don't know how.

    Any help?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You're using a greedy algorithm (i.e., choose the largest number that "fits"), but that can't possibly work in this case. Take the same numbers but rearrange them: 2+1+34+100+90
    213410090 = 227. Your algorithm is going to try to work with 213, and is going to die a horrible death.

    If you don't want to try the 2^n different possibilities for all the +'s (and I don't blame you), you're going to have to implement backtracking: once all the possibilities for 213 don't work, cut one more digit off and try 21; when all those possibilities don't work, then try 2.

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    I don't think it would be that expensive of an algorithm to find where to put plus signs in 100234190 to find the sum where it equals 227.

    We know that 100234190 is 9 digits long. Therefore, there can be a maximum of 8 plus signs.

    So, 2^(strlen("100234190")-1), or, 2^8, = 256 iterations (max) and we're done.

    In this particular case, where 100 + 2 + 34 +1 + 90 = 227, we'd find the answer on loop #54.

    Todd
    Mainframe assembler programmer by trade. C coder when I can.

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    There are several solutions to this particular sequence!
    Code:
    100+2+34+1+90 = 227
    	(the above found in loop #54)
    10+023+4+190 = 227
    	(the above found in loop #76)
    10+0+23+4+190 = 227
    	(the above found in loop #108)
    1+002+34+190 = 227
    	(the above found in loop #148)
    1+00+2+34+190 = 227
    	(the above found in loop #180)
    1+0+02+34+190 = 227
    	(the above found in loop #212)
    1+0+0+2+34+190 = 227
    	(the above found in loop #244)
    And the routine.
    Code:
    #include <stdio.h> 
    #include <math.h> 
    #include <string.h> 
    
    int test_solution(char * number, char * total, int value) ; 
    int getsum(char * expression) ; 
    
    int main(void) { 
    
    	char user_string[] = "100234190" ;
    	char user_sum[]    = "227" ; 
    
    	// Calculate the max loops we need to process
    	int maxloops = (int) pow(2.0, (double) strlen(user_string)-1) ; 
    
    	int i ; 
    	int result ; 
    	int found = 0 ;  // flag 
    
    	for (i = 1 ; i <= maxloops ; i++)  { 
    		result = test_solution(user_string,user_sum,i) ;  
    		if (result) { 
    			found = 1 ; 
    			printf("\t(the above found in loop #%d)\n", i) ; 
    			//break ;    // uncomment this to stop at the first solution 
    		}
    	}	
    	if (!found) printf("No solution\n") ; 
    	return 0 ; 
    }
    
    
    int test_solution(char * number, char * total, int value) { 
    
    	int i ; 
    	int sum = atoi(total) ;   
    	int number_index ; 
    	
    	char expression[21] ; 
    	char local_number[21] ; 
    	char * expression_ptr ; 
    	
    	strcpy(local_number,number) ; 
    	
    	for (i = 0 ; i < sizeof(expression)-1 ; i++) expression[i]=0 ; // clear workarea
    
    	number_index = strlen(local_number)-1 ; 
    	
    	expression_ptr = expression + (strlen(local_number)*2) - 1 ;  // work right to left  
    	
    	// Using the bit pattern in "value", insert a plus sign at each binary 1. 
    	while(value != 0) { 
    		*expression_ptr-- = local_number[number_index] ;  
    		local_number[number_index--] = 0 ; // truncate it 
    		if (value & 1) { 
    			*expression_ptr-- = '+' ; 
    		} 
    		value >>= 1 ; 
    	} 
    	// Copy remainder of the number (left-most part) into the expression 
    	for (i = number_index ; i >=0 ; i--)  *expression_ptr-- =  local_number[i] ;  
    	if (getsum(expression_ptr+1) == sum) { 
    		printf("%s = %d\n", expression_ptr+1, sum); 
    		return 1 ; 
    	} 
    	return 0 ; 
    } 
    
    int getsum(char * expression) { 
    	int total = 0 ; 
    	char * plus_position ;  // position of the plus sign 
    	char * current_pointer = expression ; 
    
    	while (1) { 
    		plus_position = strchr(current_pointer, '+') ;    
    		if (plus_position==NULL) { // add the last number 
    			total += atoi(current_pointer) ; 
    			return total ; 
    		}
    		*plus_position = 0 ; 
    		total += atoi(current_pointer) ; 
    		*plus_position = '+' ; 
    		current_pointer = plus_position+1 ; 
    	}
    }
    Mainframe assembler programmer by trade. C coder when I can.

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by Todd Burch View Post
    There are several solutions to this particular sequence!
    Code:
    100+2+34+1+90 = 227
    	(the above found in loop #54)
    10+023+4+190 = 227
    	(the above found in loop #76)
    10+0+23+4+190 = 227
    	(the above found in loop #108)
    1+002+34+190 = 227
    	(the above found in loop #148)
    1+00+2+34+190 = 227
    	(the above found in loop #180)
    1+0+02+34+190 = 227
    	(the above found in loop #212)
    1+0+0+2+34+190 = 227
    	(the above found in loop #244)
    If you also specify a rule that there cannot be leading zero's on a number (i.e. something that introduces 023 or 00 is invalid, but the term 0 is) the number of solutions reduces to 3. If you're looking for a brute-force puzzle solver, you can reasonably expect such an implied rule -- unless the puzzle is created by a pedantic computer scientist.

  6. #6
    Registered User
    Join Date
    Jun 2006
    Posts
    130
    You are right, there should be no number with leftmost zeros, thus, there would be only one solution. Thanks all.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM