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?

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.

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

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 ;
        }
}

---

Quote:

---

Originally Posted by Todd Burch

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. ;)

You are right, there should be no number with leftmost zeros, thus, there would be only one solution. Thanks all.