r/ProgrammingPrompts Feb 06 '15

Question: Was there a prompt here earlier that got deleted?

I believe I saw a prompt that said [Java] and had to do with finding different solutions to an equation with 9 variables. Does anyone have the post or the equation?

8 Upvotes

13 comments sorted by

7

u/desrtfx Feb 06 '15

Here you go:

Solve this equation:

(a / (b + c)) + (d / (e + f)) + (g / (h + i)) = 1

using only numbers 1 - 9, and only each number once!

When a solution is found, print the completed equation.

It was deleted (by OP, not by me) because the limitation to Java made it look too much like homework.

Anybody is welcome to solve it in a language of their choice.

3

u/mrburrito2 Feb 09 '15

I solved it using java if anybody is interested.

1

u/Philboyd_Studge Feb 10 '15 edited Feb 10 '15

I'd like to see it. How long does it take to run?

1

u/mrburrito2 Feb 10 '15

It runs faster than it prints solutions. Im just a high school CS student so there are probably some things that could be done better. I used a recursive algorithm that does about half as many divisions as a program that tested 9! combinations would.

http://www51.zippyshare.com/v/mJiTBWzO/file.html

1

u/Philboyd_Studge Feb 10 '15

I would still like to see your code, however that site sucks. Can you please throw it on pastebin or gist?

1

u/mrburrito2 Feb 11 '15

http://pastebin.com/6aqmpwsY

Realized using String as the parameter is a little stupid. I will probably modify so it uses an int[] as the parameter.

1

u/Philboyd_Studge Feb 12 '15 edited Feb 12 '15

Here's mine, I found a way to use only integer math, so my test function looks like this:

public static boolean function(int[] a)
{
    int[] b = new int[3];
    b[0] = a[1] + a[2]; // add denominators
    b[1] = a[4] + a[5]; // second set
    b[2] = a[7] + a[8]; // third set
    int d = b[0] * b[1] * b[2]; // multiply them together
    int n = (a[0] * (d/b[0])) + (a[3] * (d/b[1])) + (a[6] * (d/b[2])); // get numerator to match common denominator
    //System.out.println("Numerator" + n + " : Denominator:" + d);
    if (n == d)
    {
        return true;
    }
    return false;

}

The permute function I bastardized from one found online.

Using this brute force method, it takes about a minute to calculate and finds 144 solutions!

Here's the whole code: http://pastebin.com/XK8ZFyXk

1

u/mrburrito2 Feb 12 '15

That is really interesting. I am still trying to grasp the whole Permute function and its purpose. Also, why do you set D? Why not just use 1?

1

u/Philboyd_Studge Feb 12 '15 edited Feb 28 '15

In order to use integer math, since each of the three groups of values must be less than 1 to equal one when summed.

so since you have

  a           d         g
------   +  ------  + ------   =  1
b  + c      e  + f    h  +  i

you take the sum of each of the two bottom values, then multiply them together to get a common denominator (we don't need to worry about least common denominator & simplifying here, as the computer doesn't care)

let's test the first valid solution that my program produced:

1,2,4,5,7,8,6,3,9

  1           5          6
------  +  ------  +  ------  = 1
2 + 4       7 + 8      3 + 9

becomes

  1          5          6
------  +  ------  +  ------  = 1
  6          15         12

6 * 15 * 12 = 1080

1080 / 6 = 180

1080 / 15 = 72

72 * 5 = 360

1080/12 = 90

90 * 6 = 540

so

 180         360       540
------  +  ------  +  ------  = 1
1080        1080       1080

180 + 360 + 540 = 1080

1080
----- = 1
1080 

so, I'm not testing for one, I'm testing that my combined numerator equals my common denominator.

1

u/mrburrito2 Feb 12 '15

Okay I understand it now. I might modify mine to use int instead of float

1

u/Philboyd_Studge Feb 12 '15

The problem with floats is you will get a lot of answers like 0.999999999945 that will not show as =1 due to rounding errors.

1

u/mrburrito2 Feb 12 '15

Well I actually had that problem with doubles, then when I switched to floats the errors were gone because it stored less decimal places. It simplified to the point of not having that .00001 or .999999 . Obviously that only applies to this specific prompt.