# Program Question

• 01-09-2011, 06:09 AM
WickedBetrayal
Program Question
I do not want to seem as if I just want an answer to a homework problem. But I just want to know what exactly I could do to write code to accomplish the task.

I am in a Java with Data Structures course and my professor gave me this:

Solve A/BC + D/EF + G/HI = 1 where A, B,C,... I are {1,2,3,...9} and each digit is used exactly once. Here BC, EF, HI are concatenations rather than multiplications. e.g. If B = 3 and C = 5, BC would be the number 35 (not the product 3x5 = 15). (The solution is unique up to ordering of the fractions.)

I would really appreciate some help.

Thanks,

Jim
• 01-09-2011, 07:01 AM
WickedBetrayal
this is what i have so far:
Code:

```public class StringProblem {   public static void main(String[] args) {     double a = 1;     double d = 4;     double g = 7;     String b = "2";     String c = "3";     String e = "5";     String f = "6";     String h = "8";     String i = "9";     String first = b+c;     String second = e+f;     String third = h+i;     double bc = Integer.parseInt(first);     double ef = Integer.parseInt(second);     double hi = Integer.parseInt(third);     double answer = (a/bc) + (d/ef) + (g/hi);     System.out.println(answer);   } }```
• 01-09-2011, 09:39 AM
JosAH
Quote:

Originally Posted by WickedBetrayal
I do not want to seem as if I just want an answer to a homework problem. But I just want to know what exactly I could do to write code to accomplish the task.

I am in a Java with Data Structures course and my professor gave me this:

Solve A/BC + D/EF + G/HI = 1 where A, B,C,... I are {1,2,3,...9} and each digit is used exactly once. Here BC, EF, HI are concatenations rather than multiplications. e.g. If B = 3 and C = 5, BC would be the number 35 (not the product 3x5 = 15). (The solution is unique up to ordering of the fractions.)

I would really appreciate some help.

Thanks,

Jim

First let's get rid of those ugly divisions: your problem is equvalent to the problem: A*EF*HI+D*BC*HI+G*BC*EF == BC*EF*HI. Variables A .. I are a permutation of the values 1 ... 9. We have to find a permutation such that the equality holds. The equation makes sense in mathematical notation as:

A*(10*E+F)*(10*H+I)+D*(10*B+C)*(10*H+I)+G*(10*B+C) *(10*E+F) ==
(10*B+C)*(10*E+F)*(10*H+I)

(I hope I got that right ;-)

Finding permutations isn't a trivial task but very well doable. The next method finds a next permutation (if there is one) given a current permutation in lexicographical order. Let a current permutation be P0 P1 P2 ... Pn;

the steps are:

Code:

```1) find a largest i such that Pi < P(i+1) 2) if no such i exists there is no next permutation 3) find a largest j such that j > i and Pj > Pi (such a value j always exists) 4) swap values Pi and Pj 5) reverse the subsequence P(i+1) .. Pn```
Those five steps produce a next permutation given a curent one: P1 ... Pn.

You have to check all permutations starting at permutation 1, 2, 3 ... 9 and evaluate the equality above. If it holds you have found values for A ... I.

kind regards,

Jos
• 01-12-2011, 11:16 PM
nve5009
I'm also having problems with this. I understand doing the A*EF*HI+D*BC*HI+G*BC*EF == BC*EF*HI to get ride of the divisions. Could you explain how A*(10*E+F)*(10*H+I)+D*(10*B+C)*(10*H+I)+G*(10*B+C) *(10*E+F) ==
(10*B+C)*(10*E+F)*(10*H+I) is equal to the other equation.

Also, the first step you said to do is find a largest i such that Pi < P(i+1). Does that mean I must increase all the variables by 1? How am I supposed to set up the first permutation? Do I just set A to 1, B to 2, and so on?

Sorry I'm very confused. I'd appreciate any help. Thank You.
• 01-13-2011, 08:02 AM
JosAH
Quote:

Originally Posted by nve5009
I'm also having problems with this. I understand doing the A*EF*HI+D*BC*HI+G*BC*EF == BC*EF*HI to get ride of the divisions. Could you explain how A*(10*E+F)*(10*H+I)+D*(10*B+C)*(10*H+I)+G*(10*B+C) *(10*E+F) ==
(10*B+C)*(10*E+F)*(10*H+I) is equal to the other equation.

If e.g. BC == 12 then B == 1 and C == 2; so mathemaTically 10*B+C == 10*1+2 == 12. The first notation is a symbolic notation, while the second is a methematical notation.

Quote:

Originally Posted by nve5009
Also, the first step you said to do is find a largest i such that Pi < P(i+1). Does that mean I must increase all the variables by 1? How am I supposed to set up the first permutation? Do I just set A to 1, B to 2, and so on?

Sorry I'm very confused. I'd appreciate any help. Thank You.

If you have a permutation, say, 14532, finding a largest i such that Pi < P(i+1) results in i == 1 because 4 < 5 and 4 is located at position 1. Next you have to find a largest j such that Pj > Pi. Pi == 4 and if j == 2 then Pj == 5 and 5 > 4. Swap Pi and Pj, so we get 15432 and next we have to reverse the subsequence starting at position i+1: 432, reversed we get 15234. Got it?

You do have to set up the first permutation yourself, which is easy: 123456789

kind regards,

Jos

edit: After rereading my own pseudo code I noticed that it was quite terse, so here is a Java implementation. This class permutes a char array with five elements:

Code:

```import java.util.Arrays; public class T {         private static void swap(char[] s, int i, int j) {                 char t = s[i];                 s[i] = s[j];                 s[j] = t;         }         public static char[] permute(char[] s) {                 int i, j;                 for (i = s.length - 1; --i >= 0;)                         if (s[i] < s[i + 1])                                 break;                 if (i < 0)                         return null;                 for (j = s.length; --j > i;)                         if (s[i] < s[j])                                 break;                 swap(s, i, j);                 for (j = s.length; ++i < --j;)                         swap(s, i, j);                 return s;         }         public static void main(String[] args) {                 char[] names = "ABCDE".toCharArray();                 do {                         System.out.println(Arrays.toString(names));                 } while (permute(names) != null);         } }```
• 01-13-2011, 06:09 PM
nve5009
thanks for the response. I think I understand what to do now. I'll post again if I have anymore problems but thanks a lot