Solved. Thanks for everyone's help >3
Printable View
Solved. Thanks for everyone's help >3
GOOD / 4 should be TOO.
(I've been told I have an extremely good grasp of the obvious)
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 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)
Don't you want something like this?
Code:if((100*T+10*O+O) * 4 ==1000*G+100*O+10*O+D)
Forgot the 4. There should be only solution but the answer I'm getting doesnt match.
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:
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. :)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 ++) {
/* ... */
}
}
}
}
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:
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 . . . .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.
T = 4
o = 9
d = 6
g = 1
499 + 499 + 499 + 499 = 1996
TOO + TOO + TOO + TOO = GOOD
I got 8 solutions, 3 of which involve zero.
(edit: only 1 solution with no zeros and no dups)
@abachler: Blast, you gave it away! :p Now I suppose I can post my code:
[Highlighted with codeform.]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;
}
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.Quote:
I got 8 solutions, 3 of which involve zero.
The answers when you don't disregard duplicates are:
Quote:
000 * 4 = 0000
166 * 4 = 0664
333 * 4 = 1332
499 * 4 = 1996
500 * 4 = 2000
666 * 4 = 2664
833 * 4 = 3332
999 * 4 = 3996
I didn't even type any code, I just used a calculator and my brain (ok mostly the calculator). Took all of 15 seconds.
I was going to solve it in just a little more than that amount of time with Python, but I figured that was cheating. :)
[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:
I actually used a code similar to this but I get 2 of the answers.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 ++) {
/* ... */
}
}
}
}
If y'all start at 1 instead of 0 in your loops, you can omit the checking for a zero in the answer set.