Thread: Cryptarithmetic puzzle

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    16

    c++ program not working

    Solved. Thanks for everyone's help >3
    Last edited by Guru_; 08-27-2009 at 08:29 PM.

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    GOOD / 4 should be TOO.

    (I've been told I have an extremely good grasp of the obvious)
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It should be doable this way. I got 8 solutions this way, although some don't make sense (T and G shouldn't be zero) and there's only one where all letters represent a different digit.

    If you don't get the answer, may-be the problem is what you do inside the loops.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Apr 2009
    Posts
    16
    I only get 2 solutions.

    This is what I have for part of the loop.
    if((100*T+10*O+O)==1000*G+100*O+10*O+D)

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Don't you want something like this?
    Code:
    if((100*T+10*O+O) * 4 ==1000*G+100*O+10*O+D)
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Registered User
    Join Date
    Apr 2009
    Posts
    16
    Forgot the 4. There should be only solution but the answer I'm getting doesnt match.

  7. #7
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I get two solutions from my methods, and presumably the first one is invalid (it starts with a 0). I first used an extremely inefficient brute force method, the bulk of which looks like this:
    Code:
        for(T = 0; T <= 9; T ++) {
            for(O = 0; O <= 9; O ++) {
                for(G = 0; G <= 9; G ++) {
                    for(D = 0; D <= 9; D ++) {
                        /* ... */
                    }
                }
            }
        }
    It's really, really inefficient and you probably shouldn't use it. I know it only loops 10**4 = 10,000 times, but still. It's ugly.

    Then I wrote a nice recursive solution which worked like this: a list of numbers, from 0 to 9, was created by the caller. Each recursive call would loop through the "remaining" numbers, swap the current number with the last one, and then recurse, telling its recursive instance that there was one less number. This process continued until there were four "saved" numbers, at which point the numbers were examined to see if they met the TOO*4 = GOOD criteria. Example:
    Code:
    Square brackets indicate "unused" and "saved" sections of the array, respectively.
    [0 1 2 3 4 5 6 7 8 9][]
    Say the loop picks 7. 7 and 9 will be swapped, and the unused size decremented.
    [0 1 2 3 4 5 6 9 8][7]
    The process continues . . . pick 5.
    [0 1 2 3 4 8 6 9][5 7]
    Pick 4.
    [0 1 2 3 9 8 6][4 5 7]
    Pick 1.
    [0 6 2 3 9 8][1 4 5 7]
    Now 1 4 5 7 are T O G and D, and we can see if they work out.
    So I created a really stupid brute force solution and a far-too-complicated recursive solution. Maybe you can come up with something in between . . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  8. #8
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    T = 4
    o = 9
    d = 6
    g = 1

    499 + 499 + 499 + 499 = 1996
    TOO + TOO + TOO + TOO = GOOD

  9. #9
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    I got 8 solutions, 3 of which involve zero.

    (edit: only 1 solution with no zeros and no dups)
    Last edited by Dino; 08-27-2009 at 05:02 PM.
    Mainframe assembler programmer by trade. C coder when I can.

  10. #10
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    @abachler: Blast, you gave it away! Now I suppose I can post my code:
    Code:
    #include <stdio.h>
    
    void brute_force(void) {
        int T, O, G, D;
        
        for(T = 0; T <= 9; T ++) {
            for(O = 0; O <= 9; O ++) {
                if(O == T) continue;  /* aviod duplicate numbers */
                
                for(G = 0; G <= 9; G ++) {
                    if(G == O || G == T) continue;
                    
                    for(D = 0; D <= 9; D ++) {
                        if(D == G || D == O || D == T) continue;
                        
                        int too = T*100 + O*10 + O;
                        int good = G*1000 + O*100 + O*10 + D;
                        
                        if(too * 4 == good) {
                            printf("%d%d%d * 4 = %d%d%d%d\n", T, O, O, G, O, O, D);
                        }
                    }
                }
            }
        }
    }
    
    void swap(int *x, int *y) {
        int temp = *x;
        *x = *y;
        *y = temp;
    }
    
    void recursive(int *number, size_t numbers, size_t saved) {
        size_t x;
        
        if(saved == 4) {
            int T = number[numbers];
            int O = number[numbers + 1];
            int G = number[numbers + 2];
            int D = number[numbers + 3];
            
            int too = T*100 + O*10 + O;
            int good = G*1000 + O*100 + O*10 + D;
            
            if(too * 4 == good) {
                printf("%d%d%d * 4 = %d%d%d%d\n", T, O, O, G, O, O, D);
            }
        }
        else if(numbers > 0) {
            for(x = 0; x < numbers; x ++) {
                swap(number + x, number + numbers - 1);
                recursive(number, numbers - 1, saved + 1);
                swap(number + x, number + numbers - 1);
            }
        }
    }
    
    int main() {
        int numbers[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        
        printf("Brute force:\n");
        brute_force();
        
        printf("Recursive:\n");
        recursive(numbers, sizeof(numbers) / sizeof(*numbers), 0);
        
        return 0;
    }
    [Highlighted with codeform.]

    I got 8 solutions, 3 of which involve zero.
    Yes, that's what I got too, before I thought to eliminate duplicate numbers. I'm guessing that's part of the problem since there's only supposed to be one solution.

    The answers when you don't disregard duplicates are:
    000 * 4 = 0000
    166 * 4 = 0664
    333 * 4 = 1332
    499 * 4 = 1996
    500 * 4 = 2000
    666 * 4 = 2664
    833 * 4 = 3332
    999 * 4 = 3996
    Last edited by dwks; 08-27-2009 at 05:00 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  11. #11
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    I didn't even type any code, I just used a calculator and my brain (ok mostly the calculator). Took all of 15 seconds.

  12. #12
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I was going to solve it in just a little more than that amount of time with Python, but I figured that was cheating.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  13. #13
    Registered User
    Join Date
    Apr 2009
    Posts
    16
    [QUOTE=dwks;888729]I get two solutions from my methods, and presumably the first one is invalid (it starts with a 0). I first used an extremely inefficient brute force method, the bulk of which looks like this:
    Code:
        for(T = 0; T <= 9; T ++) {
            for(O = 0; O <= 9; O ++) {
                for(G = 0; G <= 9; G ++) {
                    for(D = 0; D <= 9; D ++) {
                        /* ... */
                    }
                }
            }
        }
    I actually used a code similar to this but I get 2 of the answers.
    Last edited by Guru_; 08-27-2009 at 05:47 PM.

  14. #14
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    If y'all start at 1 instead of 0 in your loops, you can omit the checking for a zero in the answer set.
    Mainframe assembler programmer by trade. C coder when I can.

  15. #15
    Registered User
    Join Date
    Apr 2009
    Posts
    16
    Quote Originally Posted by dwks View Post
    @abachler: Blast, you gave it away! Now I suppose I can post my code:



    Yes, that's what I got too, before I thought to eliminate duplicate numbers. I'm guessing that's part of the problem since there's only supposed to be one solution.

    The answers when you don't disregard duplicates are:
    I don't end up with the same results.
    Last edited by Guru_; 08-27-2009 at 08:29 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 12
    Last Post: 06-06-2008, 05:26 PM
  2. Crossword Puzzle Program
    By Loctan in forum C++ Programming
    Replies: 2
    Last Post: 07-31-2006, 11:08 PM
  3. Solution to Google Puzzle 3,3,8,8=24
    By LuckY in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 06-01-2006, 09:12 AM
  4. Cryptarithmetic puzzle :(
    By Moni in forum C Programming
    Replies: 15
    Last Post: 07-22-2004, 02:09 AM