Old 21st May 2007, 21:46   #1
Triton4
Major Dude
 
Join Date: Feb 2003
Location: CA
Posts: 1,307
Computer programming / Algorithm related question

String of Digits
----------------

We have a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual. For example, consider the string "12" . With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get "1+2", which evaluates to 3. So, in that case, given "12", a minimum of 1 addition is required to get the number 3. As another example, consider "303" and a target sum of 6. The best stategy is not "3+0+3", but "3+03". You can do this because leading zeros do not change the result.

Write an algorithm or flowchart for above problem. It should also give an error message if the sum is not logically possible in any way
Triton4 is offline   Reply With Quote
Old 21st May 2007, 21:57   #2
zootm
Forum King
 
zootm's Avatar
 
Join Date: Jan 2002
Location: the nether reaches of bonnie scotland
Posts: 13,375
This sounds suspiciously like something you're supposed to do yourself.

Also the brute force approach isn't very difficult to work out.

zootm is offline   Reply With Quote
Old 21st May 2007, 22:18   #3
k_rock923
\m/
(Forum King)
 
k_rock923's Avatar
 
Join Date: Jul 2003
Location: /bin/bash
Posts: 7,850
Send a message via AIM to k_rock923
Not difficult at all to brute force it.

Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway.
k_rock923 is offline   Reply With Quote
Old 21st May 2007, 23:35   #4
dlinkwit27
has no CT
(Forum King)
 
dlinkwit27's Avatar
 
Join Date: Sep 2000
Posts: 13,235
Send a message via ICQ to dlinkwit27 Send a message via AIM to dlinkwit27 Send a message via Yahoo to dlinkwit27
Brute force will take exponentially longer with each digit added though.
dlinkwit27 is offline   Reply With Quote
Old 22nd May 2007, 01:10   #5
k_rock923
\m/
(Forum King)
 
k_rock923's Avatar
 
Join Date: Jul 2003
Location: /bin/bash
Posts: 7,850
Send a message via AIM to k_rock923
Well, yeah. But we're not doing his homework for him and if he's this lazy, he won't find a good solution, either.

Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway.
k_rock923 is offline   Reply With Quote
Old 22nd May 2007, 03:18   #6
dlinkwit27
has no CT
(Forum King)
 
dlinkwit27's Avatar
 
Join Date: Sep 2000
Posts: 13,235
Send a message via ICQ to dlinkwit27 Send a message via AIM to dlinkwit27 Send a message via Yahoo to dlinkwit27
Tossing ideas out aren't the same as doing it for him though. He'd still have to code it. I've gotten plenty of HW help from this and other boards. Sometimes you just need a push and then the rest of the dominos fall almost by themselves.

Anyways...

To make it complete, the first thing I would do would be to see if the desired number is smaller than the sum of all the numbers summed together; i.e. don't ask for 9 if the sequence is 325. There is no way to get 9, in fact, the smallest sum of 325 is 10.

Next, I'd make sure the number is larger than the sequence. With a large sequence this would be nearly a given, but again, don't ask for 500 with the 325 sequence, because clearly the largest "sum" for that sequence is 325 (with no "additions"). This would be my first and second step to attempt to ensure that the process is even possible.

Off the top of my head I don't think you would get stuck in an infinite loop in either case, but this just makes the program better.

As for a method other than the brute force method, I'm still thinking about this. This is an intriguing problem and I am actually trying it myself.

/edit
I see now that the problem is merely to design a flowchart or algorithm. Pretty simple to do with a brute force method. I may try to actually code this though.
dlinkwit27 is offline   Reply With Quote
Old 22nd May 2007, 09:36   #7
ujay
Forum King
 
ujay's Avatar
 
Join Date: Jul 2001
Location: London
Posts: 6,072
It should also give an error message if the sum is not logically possible in any way.

You should do this test first.

Check the bounds as suggested by dlink and then use the 'casting out nines' technique to check whether a solution is possible. Note that this will not tell you if a solution actually exists.

This is a particularly useful test where the data is presented as a string since you can use cyclic redundancy to establish the result.

[edit] Thinking about it some more you should check the bounds after this test, not before.

UJ

Last edited by ujay; 22nd May 2007 at 10:22.
ujay is offline   Reply With Quote
Old 22nd May 2007, 15:44   #8
dlinkwit27
has no CT
(Forum King)
 
dlinkwit27's Avatar
 
Join Date: Sep 2000
Posts: 13,235
Send a message via ICQ to dlinkwit27 Send a message via AIM to dlinkwit27 Send a message via Yahoo to dlinkwit27
Also, if you are using a string, remember that '9' - '0' = 9 (and so on)
dlinkwit27 is offline   Reply With Quote
Old 22nd May 2007, 22:39   #9
xzxzzx
Forum King
 
xzxzzx's Avatar
 
Join Date: Aug 2002
Posts: 7,254
I suspect you can't do much better than brute-force here, except for certain special cases, but I could be completely wrong...

Freedom of speech is the basic freedom of humanity. When you've lost that, you've lost everything.
1\/\/4y 34|<$p4y 1gp4y 33714y, 0d4y 0uy4y? | Roses are #FF0000; Violets are #0000FF; chown -R ${YOU} ~/base
The DMCA. It really is that bad. : Count for your life.
xzxzzx is offline   Reply With Quote
Old 23rd May 2007, 18:39   #10
Triton4
Major Dude
 
Join Date: Feb 2003
Location: CA
Posts: 1,307
Ok, I have done some code work in C++ for this problem. Can you check and see if this is ok:

PHP Code:
#include <iostream.h>
#include <string.h>

class SimpleSums
{
private:
    
int sum;
    
public:

    
SimpleSums()
    { }

    
SimpleSums(const chardigitsint sum)
    {
        
char fres[256]={0};
        if(
MinSums(fresdigitssum1))
            
cout<<fres<<endl;
        else
            
cout<<"\nNo solution possible";
    }

    
// Form the number between the two string positions
    
int FormNumber(const chardigitsint aint b)
    {
        
int n 0;
        for(
int j=a;j<b;j++)
        {
            
*= 10;
            
+= digits[j]-'0';
        }    
        return 
n;
    }

    
bool MinSums(char *res, const char *digitsint sumint multiplier)
    {
        
int n FormNumber(digits0strlen(digits));

        if(
n*multiplier == sum)
        {
            
strcpy(resdigits);
            return 
true;
        }
    
        for(
int i=1;i<(int)strlen(digits);i++)
        {
            
FormNumber(digits,0,i);
            
strncpy(res,digits,i);
            
res[i]='+';
        
            if(
MinSums(res+i+1digits+isum-(multiplier*n), 1))
                return 
true;

            
res[i]='*';
        
            if(
MinSums(res+i+1digits+isummultiplier*n))
                return 
true;
        }
        return 
false;
    }
};


void main()
{
    
SimpleSums SS1("123",6);
    
SimpleSums SS2("382834",100);

Triton4 is offline   Reply With Quote
Reply
Go Back   Winamp & Shoutcast Forums > Community Center > General Discussions

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump