Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Chippy

complicated

This topic is 5155 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, here''s what''s up. I am just learning C++, but I learn by going ahead of myself. So here''s what I have, and the idea I have to solve it. Have you ever seen a problem like this: she x he ______ haho The idea of this is to change each letter into a number, so you have an actual equation that really works. You could take any equation, assign each number a letter, and give the letters out. Say you have: 2456 +465 _____ 2921 you could assign each number a letter: 2=a 4=b 5=c 6=d 9=e 1=f We would then turn out: abcd +bdc _____ aeaf Now you should have an idea as to the problem, because in this case we do NOT know that A is 2 etc.. All we know is: abcd +bdc ______ aeaf Well, I would like to make a program that solves this. I have come up with a way to do this, but the people I have asked I have not been able to explain this to properly. First we are asked in input the first line: abcd Then the operation: + then the second line: bdc And finnally the product: aeaf (Of course, the following is in a loop) The program would now have to find that in this certain equation we have a, b, c, d, e and f. Finnally we need to assign a number to each number, and then run it to see if this is the proper set of numbers. If it isnt, we then need to change ONE letter, then run the program again, so we then test every single possible combination. So it would start with say: a= 1 b= 2 c= 3 d= 4 e= 5 f= 6 And then run the operation: 1234 +243 ______ 1516 Now it needs to check if this operation works, probably by checking the result of 1234 + 243 with the product 1516. It would the find that that is not correct. So we add one number onto the last letter. a= 1 b= 2 c= 3 d= 4 e= 5 f= 7 (We change this one) Then try it again. And continue this, only after running from 7-0 (we cannot use 1-5, as they are already taken by other numbers) on the letter f, we move on to other letters. At this point it comes to my attention that in this is missing something, as we have not checked f with the other numbers. I believe the solution for this is we now must change e to 6, leaving the numbers 5, 8, 9, and 0 for f. I believe a good way to simplify this is by making all the letters into a certain number. Say we start with: 1 2 3 4 5 6 a b c d e f Our number is 123456. At the end of the loop, if the equation is not correct, we add 1 to the number. 123457 and so on. We would then also have to build in somehow something to make sure the same number is not there twice, but this is not neccesary. This about concludes what I can think of. I thank you for reading this, and if you don''t get a certain part I will change that if you post with what you dont get. Thanks!

Share this post


Link to post
Share on other sites
Advertisement
Sounds like homework. I had this exact assignment in my second CS class.

"First we are asked in input the first line:"

The plural 'we' kind of gives me the impression its homework for you too.

[edited by - haro on June 10, 2004 8:07:49 PM]

Share this post


Link to post
Share on other sites
perhaps not quite what you are looking for, but google around for basic "Genetic Algorithms". They do what you are describing, but in a "more interesting" way.

Share this post


Link to post
Share on other sites
lol its not
this is something i want to do in my own time
im actually just getting our of grade 9 this year, and my math teacher has put up these types of questions before.
the idea is for my learning of c++, and im integrating my obsession with riddles

Share this post


Link to post
Share on other sites
ok, i shall look for Algorithms, in the meatime does anyone have any ideas?? its mostly the coding i need, i dont know how to code a lot of that stuff

Share this post


Link to post
Share on other sites
int a, b, c, d, e, f;

for(a = 0; a <= 9; a++)
{
for(b = 0; b <= 9; b++)
{
if(b == a)
continue;

for(c = 0; c <= 9; c++)
{
if((c == a) || (c == b))
continue;

for(d = 0; d <= 9; d++)
{
if((d == a) || (d == b) || (d == c))
continue;

for(e = 0; e <= 9; e++)
{
if((e == a) || (e == b) || (e == c) || (e == d))
continue;

for(f = 0; f <= 9; f++)
{
if((f == a) || (f == b) || (f == c) || (f == d) || (f == e))
continue;

if((1000 * a + 100 * b + 10 * c + d) + (100 * b + 10 * d + c) == (1000 * a + 100 * e + 10 * a + f))
{
cout << "Solution is a, b, c, d, e, f = " << a << ", " << b << ", " << c << ", " << d << ", " << e << ", " << f << endl;
}
}
}
}
}
}
}

Share this post


Link to post
Share on other sites
quote:
Original post by Aprosenf
..code dump..



Hmmm.. that code doesn''t really work at all, but more importantly is the fact that your idea is not really correct either. The idea is to make a general purpose solution as stated in the OP''s original post. This means that you should be able to take up to 10 digits of input in arbitrarily long blocks:

AABGHDCEFGHASSE
+
DCBAHIEFDCBA
+
AAAAAABBBBBCCCDDDDEEEFFFGGGHHHIII
=
ABCDEFGHIJABCDEFGJHEAFDCGHACCCCEE

Obviously you can see that brute forcing everything will leave you old and grey in some cases ( imagine that only with more and longer keys ). A decent implementation should be able to solve most of any reasonable input set in a matter of milliseconds. A bad implementation would take years for the same data sets.

Anyhow, there is a term for these sorts of problems. I cannot recall it at all.

Share this post


Link to post
Share on other sites
quote:
Original post by leiavoia
perhaps not quite what you are looking for, but google around for basic "Genetic Algorithms". They do what you are describing, but in a "more interesting" way.


Problems can have hundreds of solutions or even zero. Also it is really difficult to determine "how far off" an answer is. Even if a solution has all digits correct except for one, it is possible that every single value is actually incorrect. A genetic algorithm approach seems to probably be a bad idea here.

Share this post


Link to post
Share on other sites
hmmm, well, the idea with this was to return only the ones that matched exactly
so if theres a ton of solutions it returns all of them, and if none it returns none of them

Share this post


Link to post
Share on other sites
AFAIK, the most efficient way to solve this problem is using a Constraint Satisfaction algorithm. Example:

she
+ he
====
haho

Set up constraints:

1. e + e = o (or o + 10)
2. either h + h = h (or h + 10) or h + h + 1 = h (or h + 10)
3. s + 1 = ha

- For each value 0..9 of s:
- For each value 0..9 of h not violating constraints:
- For each value 0..9 of e not violating constraints:
- For each value 0..9 of o not violating constraints:
- test if equation holds, and if it does, return the bindings

There are heuristics (such as most-constrained-variable first) which govern the order in which you assign values, and these can make the answer appear much faster.

Good luck!

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!