Modify a given number to find the required sum?

A friend of mine sent me this question. I haven't really been able to come up with any kind of algorithm to solve this problem.

You are provided with a no. say 123456789 and two operators * and +. Now without changing the sequence of the provided no. and using these operators as many times as you wish, eva开发者_如何学Pythonluate the given value:

eg: given value 2097

Solution: 1+2+345*6+7+8+9

Any ideas on how to approach problems like these?

One of the easiest ways to do it is using shell expansion in BASH:

#!/bin/sh

for i in 1{,+,*}2{,+,*}3{,+,*}4{,+,*}5{,+,*}6{,+,*}7{,+,*}8{,+,*}9; do
    if [ $(( $i )) == 2097 ]; then
        echo $i = 2097
    fi
done

which gives:

$ sh -c '. ./testequation.sh'
12*34+5*6*7*8+9 = 2097
12*3*45+6*78+9 = 2097
1+2+345*6+7+8+9 = 2097

There are not that many solutions - this python program takes under a second to bruteforce them all

from itertools import product

for q in product(("","+","*"), repeat=8):
    e = ''.join(i+j for i,j in zip('12345678',q))+'9'
    print e,'=',eval(e)

Here is a sample run through grep

$ python sums.py | grep 2097
12*34+5*6*7*8+9 = 2097
12*3*45+6*78+9 = 2097
1+2+345*6+7+8+9 = 2097

General solution is a simple modification

from itertools import product

def f(seq):
    for q in product(("","+","*"), repeat=len(seq)-1):
        e = ''.join(i+j for i,j in zip(seq[:-1],q))+seq[-1]
        print e,'=',eval(e)

This isn't the easiest way, but I tried to write "optimized" code : genereting all the 3^(n-1) strings is expensive, and you've to evaluate a lot of them; I still used bruteforce, but cutting unproductive "subtrees" ( and the source is C, as requested in the title)

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"

#define B 10

void rec_solve(char *, char *, int, char, int, char, int, char *);

int main(int argc, char** argv) {
    char *n, *si = malloc(0);
    if (argc < 2) {
        printf("Use : %s num sum", argv[0]);
    } else {
        n = calloc(strlen(argv[1]), sizeof (char));
        strncpy(n, argv[1], strlen(argv[1]));
        rec_solve(n, si, 0, '+', 0, '+', atoi(argv[2]), n);
    }
    return 0;
}

void rec_solve(char *str, char *sig, int p, char ps, int l, char ls, int max, char *or) {
    int i, len = strlen(str), t = 0, siglen = strlen(sig), j, k;
    char *mul;
    char *add;
    char *sub;

    if (p + l <= max) {
        if (len == 0) {
            k = (ls == '+') ? p + l : p*l;

            if ((k == max) && (sig[strlen(sig) - 1] == '+')) {
                for (i = 0; i < strlen(or) - 1; i++) {
                    printf("%c", or[i]);
                    if (sig[i] && (sig[i] != ' '))
                        printf("%c", sig[i]);
                }
                printf("%c\n", or[i]);
            }
        } else {
            for (i = 0; i < len; i++) {
                t = B * t + (str[i] - '0');

                if (t > max)
                    break;

                sub = calloc(len - i - 1, sizeof (char));
                strncpy(sub, str + i + 1, len - i - 1);

                mul = calloc(siglen + i + 1, sizeof (char));
                strncpy(mul, sig, siglen);

                add = calloc(strlen(sig) + i + 1, sizeof (char));
                strncpy(add, sig, siglen);

                for (j = 0; j < i; j++) {
                    add[siglen + j] = ' ';
                    mul[siglen + j] = ' ';
                }

                add[siglen + i] = '+';
                mul[siglen + i] = '*';

                switch (ps) {
                    case '*':
                        switch (ls) {
                            case '*':
                                rec_solve(sub, add, p*l, '*', t, '+',max, or);
                                rec_solve(sub, mul, p*l, '*', t, '*',max, or);
                                break;
                            case '+':
                                rec_solve(sub, add, p*l, '+', t, '+',max, or);
                                rec_solve(sub, mul, p*l, '+', t, '*',max, or);
                                break;
                        }
                    case '+':
                        switch (ls) {
                            case '*':
                                rec_solve(sub,add,p, '+',l*t,'+',max, or);
                                rec_solve(sub,mul,p, '+',l*t,'*',max, or);
                                break;
                            case '+':
                                rec_solve(sub,add,p + l,'+',t,'+',max, or);
                                rec_solve(sub,mul,p + l,'+',t,'*',max, or);
                                break;
                        }
                        break;
                }
            }
        }
    }
}

Here's an implementation of a non-recursive C bruteforce version that will work for any set of digits (with reasonable values in the 32-bit range and not just for the example above). Now complete. :)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* simple integer pow() function */
int pow(int base, int pow)
{
    int i, res = 1;
    for (i = 0; i < pow; i++)
        res *= base;
    return res;
}

/* prints a value in base3 zeropadded */
void zeropad_base3(int value, char *buf, int width)
{
    int length, dif;

    _itoa(value, buf, 3);
    length = strlen(buf);
    dif = width - length;

    /* zeropad the rest */
    memmove(buf + dif, buf, length+1);
    if (dif)
        memset(buf, '0', dif);
}

int parse_factors(char **expr)
{
    int num = strtol(*expr, expr, 10);
    for ( ; ; )
    {
        if (**expr != '*')
            return num;
        (*expr)++;
        num *= strtol(*expr, expr, 10);
    }
}

/* evaluating using recursive descent parser */
int evaluate_expr(char* expr)
{
    int num = parse_factors(&expr);
    for ( ; ; )
    {
        if (*expr != '+')
            return num;
        expr++;
        num += parse_factors(&expr);
    }
}

void do_puzzle(const char *digitsString, int target)
{
    int i, iteration, result;
    int n = strlen(digitsString);
    int iterCount = pow(3, n-1);
    char *exprBuf = (char *)malloc(2*n*sizeof(char));
    char *opBuf = (char *)malloc(n*sizeof(char));

    /* try all combinations of possible expressions */
    for (iteration = 0; iteration < iterCount; iteration++)
    {
        char *write = exprBuf;

        /* generate the operation "opcodes" */
        zeropad_base3(iteration, opBuf, n-1);

        /* generate the expression */
        *write++ = digitsString[0];
        for (i = 1; i < n; i++)
        {
            switch(opBuf[i-1])
            {
            /* case '0' no op */
            case '1': *write++ = '+'; break;
            case '2': *write++ = '*'; break;
            }
            *write++ = digitsString[i];
        }
        *write = '\0';

        result = evaluate_expr(exprBuf);
        if (result == target)
            printf("%s = %d\n", exprBuf, result);
    }

    free(opBuf);
    free(exprBuf);
}

int main(void)
{
    const char *digits = "123456789";
    int target = 2097;
    do_puzzle(digits, target);
    return 0;
}

12*34+5*6*7*8+9 = 2097
12*3*45+6*78+9 = 2097
1+2+345*6+7+8+9 = 2097

You could work backwards and try to test for all possibilities that could give solution;

e.g:

1 (something) 9 = 10

1*9=10 - false

1/9=10 - false

1-9=10 - false

1+9=10 - True

So, basically brute force - but it is re-usable code given that the input could be different.