Cryptarithmetic puzzle :(

This is a discussion on Cryptarithmetic puzzle :( within the C Programming forums, part of the General Programming Boards category; Hi there...I am in a great danger !!! I have to write a program just in 14hours....not finding any ref. ...

  1. #1
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104

    Cryptarithmetic puzzle :(

    Hi there...I am in a great danger !!!

    I have to write a program just in 14hours....not finding any ref. code for that.....can anyone help a bit???

    http://www.rci.rutgers.edu/~cfs/305_...blemSolve.html

    Something like this!

    SEND

    +MORE
    ----------------------
    MONEY
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  2. #2
    scr
    scr is offline
    Registered User
    Join Date
    Jul 2004
    Posts
    3

    ...

    Maybe can you explain us, what exactly your program should do?
    You posted here, like we have the same exercise, so please relax, write down what *should* your program do, and we'll try to help you out.

  3. #3
    Registered User
    Join Date
    Oct 2003
    Posts
    106

    no code solution

    I found a set of values which is a solution, but only one solution in an infinite set. The problem was to find one solution, so the problem is solved:

    N=0
    A=1
    L=2
    G=3
    R=4
    B=5
    T=20

    I don't think you should create a program to get a solution, just use algebra.

  4. #4
    Registered User
    Join Date
    Oct 2003
    Posts
    106

    Completion of the precedent reply

    I didn't give the values for O and E: you can use an arbitrary value, different for the values choosen before(to satisfy the problem's requests), such as O=100 E=200

  5. #5
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    It said that you have to use values from 0-9, and each number must be assigned to one letter, and vice versa, and D=5.

    Solution:
    D=5
    O=2
    N=6
    A=4
    L=8
    R=7
    B=3
    T=0
    G=1
    E=9
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  6. #6
    Registered User
    Join Date
    Oct 2003
    Posts
    106

    Correction

    I made an error, here is the final solution:
    N=0
    A=1
    L=2
    G=3
    R=4
    B=5
    T=15
    O=100
    E=200

    I'm sorry for the error I made before...

  7. #7
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    It's an invalid solution. See my above post.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  8. #8
    Registered User
    Join Date
    Oct 2003
    Posts
    106

    About solution.

    treat each char as a integer variable, you get an equation:
    15+N+2A+2L+G=R+B+T
    Now, to solve this linear equation is impossible because you should have more indipendent relations between the variables, as much relations as variables-1.

    We need only one solution, not every solution, so we can give an arbitrary value to each variable-1, not to all, so we can reach a simple equation like T+n1=n2=>T=n2-n1, where n1 and n2 are the sums of the members of the equation.

    Just choose variable's values so that n2>n1.
    BrownB

    PS I found no errors on my last post..perhaps I should look better

  9. #9
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Well, the error is pretty blatant.

    Find an assignment of the integers 0-9 to the letters...
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  10. #10
    Registered User
    Join Date
    Oct 2003
    Posts
    106

    OOps..

    Absolutely true!...

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    [edit]
    Hm... I'll have to give this a bit more thought.
    [/edit]

    [edit2]
    Good luck. Though there is a lot on the subject, were you to spend a moment looking for it.
    [/edit2]

    Quzah.
    Last edited by quzah; 07-21-2004 at 03:09 AM.
    Hope is the first step on the road to disappointment.

  12. #12
    Goscinny or Uderzo?
    Join Date
    Jun 2004
    Posts
    33
    now there's a problem that could eat up your day if you let it... not that I've spent any time on it (Just in case someone feels like spending a day at it, I'd love to see if anyone can write an algorithm to solve it!)
    Quantum materiae materietur marmota monax si marmota monax materiam possit materiari?

    (How much wood would a wood chuck cut if a wood chuck could chuck wood?)

  13. #13
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    Sorry...yes...you are correct...I should have write the whole thing in a programmers manner

    The problem statement:

    The following:



    S E N D

    + M O R E

    --------------

    M O N E Y



    is a cryptarithmetic problem. Each letter must be given a digit value (0 through 9), with M ≠ 0. No two letters must have the same value. The sum of the digits must be as shown in the problem. The solution of the above problem is:

    D = 7, E = 5, M = 1, N = 6, O = 0, R = 8, S = 9, Y =2.

    Indeed:



    9 5 6 7

    + 1 0 8 5

    ------------

    1 0 6 5 2

    -------------------------------------

    Algorithm:

    http://sentinel.cs.cf.ac.uk/Dave/AI2/node28.html

    Constraint satisfaction problem (CSP)

    states are sets of variables
    goal test is set of constraints on values of variables.
    each variable has domain (D) which is set of possible values.(discrete/continuous)
    unary constraint specifies allowable subset of domain for each variable
    binary constraint between 2 variables specifies allowable combinations (subset of cross-product)
    solution specifies state of values such that all constraints are met
    constraints may be absolute or just preferences


    Can be solved via general search, but special purpose algorithms generally perform better



    Discrete/finite domain like 8-queens

    may be able to list solutions/constraints
    max depth of tree is number of variables
    solutions are at max depth
    backtracking search backtracks as soon as constraint is violated
    forward checking looks ahead to detect unsolvability. Delete from domains of uninstantiated variables any values that conflict with current assignment. If any domain becomes empty, backtrack immediately.
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  14. #14
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    noone reads the math forums Look here they also have more here (the first three)

  15. #15
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    Thanks for the math forum link
    Yes...sometimes programming and algorithms make us too much involved...that we forget...these lies on Mathematics
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 8 Puzzle game solver with the Best-First algoritm
    By LordMX in forum C Programming
    Replies: 17
    Last Post: 08-11-2008, 10:00 AM
  2. Replies: 12
    Last Post: 06-06-2008, 05:26 PM
  3. Crossword Puzzle Program
    By Loctan in forum C++ Programming
    Replies: 2
    Last Post: 07-31-2006, 11:08 PM
  4. 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21