The challenge
You will have a list of rationals in the form
{ {numer_1, denom_1} , ... {numer_n, denom_n} }
or
[ [numer_1, denom_1] , ... [numer_n, denom_n] ]
or
[ (numer_1, denom_1) , ... (numer_n, denom_n) ]
where all numbers are positive ints. You have to produce a result in the form:
(N_1, D) ... (N_n, D)
or
[ [N_1, D] ... [N_n, D] ]
or
[ (N_1', D) , ... (N_n, D) ]
or
{{N_1, D} ... {N_n, D}}
or
"(N_1, D) ... (N_n, D)"
depending on the language (See Example tests)
in which D is as small as possible and
N_1/D == numer_1/denom_1 ... N_n/D == numer_n,/denom_n.
Example:
convertFracs [(1, 2), (1, 3), (1, 4)] `shouldBe` [(6, 12), (4, 12), (3, 12)]
Note:
Due to the fact that the first translations were written long ago – more than 6 years – these first translations have only irreducible fractions.
Newer translations have some reducible fractions. To be on the safe side it is better to do a bit more work by simplifying fractions even if they don’t have to be.
Note for Bash:
input is a string, e.g "2,4,2,6,2,8" output is then "6 12 4 12 3 12"
The solution in Java code
Option 1:
import static java.math.BigInteger.valueOf;
import static java.util.Arrays.stream;
import static java.util.stream.Collectors.joining;
import java.util.function.LongBinaryOperator;
class Fracts {
static LongBinaryOperator gcd = (a, b) -> valueOf(a).gcd(valueOf(b)).longValue();
static LongBinaryOperator lcm = (a, b) -> b / gcd.applyAsLong(a, b) * a;
static String convertFrac(long[][] lst) {
if (lst.length == 0) return "";
long lcm = stream(lst).map(r -> r[1]).reduce(lst[0][1], Fracts.lcm::applyAsLong);
long gcd = stream(lst).map(r -> lcm * r[0] / r[1]).reduce(lcm, Fracts.gcd::applyAsLong);
var str = stream(lst).mapToLong(r -> lcm * r[0] / r[1] / gcd).mapToObj(Long::toString);
return "(" + str.collect(joining("," + lcm / gcd + ")(")) + "," + lcm / gcd + ")";
}
}
Option 2:
public class Fracts {
public static String convertFrac(long[][] list) {
reduceFractions(list);
long lcm = calculateTotalLcm(list);
StringBuilder result = new StringBuilder();
for(long[] fraction : list) {
long ratio = lcm / fraction[1];
result.append('(')
.append(fraction[0] * ratio).append(',').append(fraction[1] * ratio)
.append(')');
}
return result.toString();
}
private static void reduceFractions(long[][] list) {
for(int i = 0; i < list.length; i++) {
long[] fraction = list[i];
long gcd = gcd(fraction[0], fraction[1]);
fraction[0] = fraction[0] / gcd;
fraction[1] = fraction[1] / gcd;
}
}
private static long calculateTotalLcm(long[][] list) {
long lcm = 1L;
for(long[] fraction : list) {
lcm = lcm(lcm, fraction[1]);
}
return lcm;
}
private static long lcm(long a, long b) {
return a * b / gcd(a,b);
}
private static long gcd(long a, long b) {
if(b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
}
Option 3:
import java.util.Arrays;
public class Fracts {
public static String convertFrac(long[][] lst) {
StringBuilder result = new StringBuilder();
long[] d = new long[lst.length];
for(int i = 0; i<lst.length;i++){
long[] r = lst[i];
long gcd = gcd(r[0],r[1]);
r[0]/=gcd; r[1]/=gcd;
d[i] = r[1];
}
long lcm = 1;
for(long de : d) {
lcm = (lcm*de)/gcd(lcm,de);
}
for(long[] r : lst) {
long f = lcm/r[1];
result.append("("+String.format("%d,%d",r[0]*f,r[1]*f)+")");
}
return result.toString();
}
public static long gcd(long a, long b) {
if(b==0) return a;
return gcd(b,a%b);
}
}
Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class FractsTest {
@Test
public void test_fractions() throws Exception {
long[][] lst;
lst = new long[][] { {1, 2}, {1, 3}, {10, 40} };
assertEquals("(6,12)(4,12)(3,12)", Fracts.convertFrac(lst));
}
}
Additional test cases
import static org.junit.Assert.*;
import org.junit.Test;
public class FractsTest {
private static String Array2D2String(long[][] lst) {
String s = "["; int l = lst.length;
for (int i = 0; i < l; i++) {
long[] a = lst[i];
s += "[" + a[0] + ", " + a[1];
if (i < l-1) s += "], ";
else s += "]";
}
return s += "]";
}
private static void testing(long[][] lst, String expected) {
System.out.println("Testing " + Array2D2String(lst));
String actual = Fracts.convertFrac(lst);
System.out.println("Actual " + actual);
System.out.println("Expect " + expected);
System.out.println("-");
assertEquals(expected, actual);
}
@Test
public void test() {
long[][] lst = new long[][] { {1, 2}, {1, 3}, {1, 4} };
testing(lst, "(6,12)(4,12)(3,12)");
lst = new long[][] { {69, 130}, {87, 1310}, {30, 40} };
testing(lst, "(18078,34060)(2262,34060)(25545,34060)");
lst = new long[][] { };
testing(lst, "");
lst = new long[][] { {77, 130}, {84, 131}, {3, 4} };
testing(lst, "(20174,34060)(21840,34060)(25545,34060)");
lst = new long[][] { {6, 13}, {187, 1310}, {31, 41} };
testing(lst, "(322260,698230)(99671,698230)(527930,698230)");
lst = new long[][] { {8, 15}, {7, 111}, {4, 25} };
testing(lst, "(1480,2775)(175,2775)(444,2775)");
lst = new long[][] { {1, 2}, {1, 3}, {1, 4} };
testing(lst, "(6,12)(4,12)(3,12)");
lst = new long[][] { {77, 130}, {840, 1310}, {3, 4} };
testing(lst, "(20174,34060)(21840,34060)(25545,34060)");
lst = new long[][] { {1, 100}, {30, 10000}, {1, 2500}, {1, 20000} };
testing(lst, "(200,20000)(60,20000)(8,20000)(1,20000)");
lst = new long[][] { {1, 1}, {3, 1}, {4, 1}, {5, 1} };
testing(lst, "(1,1)(3,1)(4,1)(5,1)");
lst = new long[][] { {3, 1} };
testing(lst, "(3,1)");
lst = new long[][] { {77, 130}, {84, 131}, {30, 40} };
testing(lst, "(20174,34060)(21840,34060)(25545,34060)");
lst = new long[][] { {1, 100}, {3, 1000}, {1, 2500}, {1, 20000} };
testing(lst, "(200,20000)(60,20000)(8,20000)(1,20000)");
}
private static int randInt(int min, int max) {
return (int)(min + Math.random() * ((max - min) + 1));
}
//
private static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
private static long lcm(long a, long b) {
return a * b / gcd(a, b);
}
private static String convertFracHD(long[][] lst) {
long lcmall = 1;
long[][] newlst = new long[lst.length][2];
for (int i = 0; i < lst.length; i++) {
long g = gcd(lst[i][0], lst[i][1]);
newlst[i][0] = lst[i][0] / g;
newlst[i][1] = lst[i][1] / g;
}
//System.out.println(Arrays.deepToString(newlst));
for (long[] item : newlst) {
lcmall = lcm(lcmall, item[1]);
}
String result = "";
for (long[] item : newlst) {
result += "(" + (item[0] * lcmall / item[1]) + "," + lcmall + ")";
}
return result;
}
//
private static long[][] doEx(int n) {
long[][] out = new long[n][2];
int j = 0;
while (j < n) {
out[j][0] = randInt(10, 80);
out[j][1] = randInt(2, 5) * out[j][0];
j += 1;
}
return out;
}
@Test
public void test1() {
System.out.println("Random Tests ****");
for (int i = 0; i < 100; i++) {
long[][] v = doEx(randInt(5, 10));
String exp = convertFracHD(v);
testing(v, exp);
}
}
}