🔒 Locked

complicated

Started by Chippy Jun 10, 2004 at 7:03 PM 10 replies 550+ views

Original Post

Jun 10, 2004 at 7:03 PM

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!

haro

Jun 10, 2004 at 7:06 PM

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]

leiavoia

Jun 10, 2004 at 7:07 PM

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.

Chippy

Jun 10, 2004 at 7:10 PM

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

Chippy

Jun 10, 2004 at 7:10 PM

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

Aprosenf

Jun 10, 2004 at 7:52 PM

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;
						}
					}
				}
			}
		}
	}
}

haro

Jun 10, 2004 at 10:52 PM

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.

haro

Jun 10, 2004 at 10:59 PM

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.

Chippy

Jun 10, 2004 at 11:03 PM

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

ParadigmShift

Jun 11, 2004 at 12:21 AM

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!

iMalc

Jun 11, 2004 at 3:29 AM

ParadigmShift is right.

You should program some of the basic rules of deduction into the algorithm as a brute force approach is likely to take enourmous amounts of time in some cases.

For adding...
e.g 1: Assume that leading digits cannot be zero.
e.g 2: If adding two numbers of length at most n, and the result is of length n+1 then the first digit of the result must be a one.
e.g 3: If the rightmost digits are the same letter then the rightmost digit in the result is even.

Using rules such as these should make sure your code never even generates some potential answer candidates which cannot possibly be correct.

[edited by - iMalc on June 11, 2004 4:30:22 AM]

Etnu

Jun 11, 2004 at 3:48 AM

It looks like a homework lesson to introduce you to a few key concepts, the primary one being numbers that aren''t in base-10 format, and another being encryption techniques.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.