Anonymous user
Fraction reduction: Difference between revisions
→{{header|Julia}}
Line 1,230:
</pre>
=={{header|Java}}==
<lang java>
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class FractionReduction {
public static void main(String[] args) {
for ( int size = 2 ; size <= 5 ; size++ ) {
reduce(size);
}
}
private static void reduce(int numDigits) {
System.out.printf("Fractions with digits of length %d where cancellation is valid. Examples:%n", numDigits);
// Generate allowed numerator's and denominator's
int min = (int) Math.pow(10, numDigits-1);
int max = (int) Math.pow(10, numDigits) - 1;
List<Integer> values = new ArrayList<>();
for ( int number = min ; number <= max ; number++ ) {
if ( isValid(number) ) {
values.add(number);
}
}
Map<Integer,Integer> cancelCount = new HashMap<>();
int size = values.size();
int solutions = 0;
for ( int nIndex = 0 ; nIndex < size - 1 ; nIndex++ ) {
int numerator = values.get(nIndex);
// Must be proper fraction
for ( int dIndex = nIndex + 1 ; dIndex < size ; dIndex++ ) {
int denominator = values.get(dIndex);
for ( int commonDigit : digitsInCommon(numerator, denominator) ) {
int numRemoved = removeDigit(numerator, commonDigit);
int denRemoved = removeDigit(denominator, commonDigit);
if ( numerator * denRemoved == denominator * numRemoved ) {
solutions++;
cancelCount.merge(commonDigit, 1, (v1, v2) -> v1 + v2);
if ( solutions <= 12 ) {
System.out.printf(" When %d is removed, %d/%d = %d/%d%n", commonDigit, numerator, denominator, numRemoved, denRemoved);
}
}
}
}
}
System.out.printf("Number of fractions where cancellation is valid = %d.%n", solutions);
List<Integer> sorted = new ArrayList<>(cancelCount.keySet());
Collections.sort(sorted);
for ( int removed : sorted ) {
System.out.printf(" The digit %d was removed %d times.%n", removed, cancelCount.get(removed));
}
System.out.println();
}
private static int[] powers = new int[] {1, 10, 100, 1000, 10000, 100000};
// Remove the specified digit.
private static int removeDigit(int n, int removed) {
int m = 0;
int pow = 0;
while ( n > 0 ) {
int r = n % 10;
if ( r != removed ) {
m = m + r*powers[pow];
pow++;
}
n /= 10;
}
return m;
}
// Assumes no duplicate digits individually in n1 or n2 - part of task
private static List<Integer> digitsInCommon(int n1, int n2) {
int[] count = new int[10];
List<Integer> common = new ArrayList<>();
while ( n1 > 0 ) {
int r = n1 % 10;
count[r] += 1;
n1 /= 10;
}
while ( n2 > 0 ) {
int r = n2 % 10;
if ( count[r] > 0 ) {
common.add(r);
}
n2 /= 10;
}
return common;
}
// No repeating digits, no digit is zero.
private static boolean isValid(int num) {
int[] count = new int[10];
while ( num > 0 ) {
int r = num % 10;
if ( r == 0 || count[r] == 1 ) {
return false;
}
count[r] = 1;
num /= 10;
}
return true;
}
}
</lang>
{{out}}
<pre>
Fractions with digits of length 2 where cancellation is valid. Examples:
When 6 is removed, 16/64 = 1/4
When 9 is removed, 19/95 = 1/5
When 6 is removed, 26/65 = 2/5
When 9 is removed, 49/98 = 4/8
Number of fractions where cancellation is valid = 4.
The digit 6 was removed 2 times.
The digit 9 was removed 2 times.
Fractions with digits of length 3 where cancellation is valid. Examples:
When 3 is removed, 132/231 = 12/21
When 3 is removed, 134/536 = 14/56
When 3 is removed, 134/938 = 14/98
When 3 is removed, 136/238 = 16/28
When 3 is removed, 138/345 = 18/45
When 9 is removed, 139/695 = 13/65
When 4 is removed, 143/341 = 13/31
When 6 is removed, 146/365 = 14/35
When 9 is removed, 149/298 = 14/28
When 9 is removed, 149/596 = 14/56
When 9 is removed, 149/894 = 14/84
When 5 is removed, 154/253 = 14/23
Number of fractions where cancellation is valid = 122.
The digit 3 was removed 9 times.
The digit 4 was removed 1 times.
The digit 5 was removed 6 times.
The digit 6 was removed 15 times.
The digit 7 was removed 16 times.
The digit 8 was removed 15 times.
The digit 9 was removed 60 times.
Fractions with digits of length 4 where cancellation is valid. Examples:
When 3 is removed, 1234/4936 = 124/496
When 9 is removed, 1239/6195 = 123/615
When 4 is removed, 1246/3649 = 126/369
When 9 is removed, 1249/2498 = 124/248
When 9 is removed, 1259/6295 = 125/625
When 9 is removed, 1279/6395 = 127/635
When 3 is removed, 1283/5132 = 128/512
When 9 is removed, 1297/2594 = 127/254
When 9 is removed, 1297/3891 = 127/381
When 9 is removed, 1298/2596 = 128/256
When 9 is removed, 1298/3894 = 128/384
When 9 is removed, 1298/5192 = 128/512
Number of fractions where cancellation is valid = 660.
The digit 1 was removed 14 times.
The digit 2 was removed 25 times.
The digit 3 was removed 92 times.
The digit 4 was removed 14 times.
The digit 5 was removed 29 times.
The digit 6 was removed 63 times.
The digit 7 was removed 16 times.
The digit 8 was removed 17 times.
The digit 9 was removed 390 times.
Fractions with digits of length 5 where cancellation is valid. Examples:
When 9 is removed, 12349/24698 = 1234/2468
When 5 is removed, 12356/67958 = 1236/6798
When 3 is removed, 12358/14362 = 1258/1462
When 3 is removed, 12358/15364 = 1258/1564
When 3 is removed, 12358/17368 = 1258/1768
When 3 is removed, 12358/19372 = 1258/1972
When 3 is removed, 12358/21376 = 1258/2176
When 3 is removed, 12358/25384 = 1258/2584
When 9 is removed, 12359/61795 = 1235/6175
When 2 is removed, 12364/32596 = 1364/3596
When 9 is removed, 12379/61895 = 1237/6185
When 2 is removed, 12386/32654 = 1386/3654
Number of fractions where cancellation is valid = 5087.
The digit 1 was removed 75 times.
The digit 2 was removed 40 times.
The digit 3 was removed 376 times.
The digit 4 was removed 78 times.
The digit 5 was removed 209 times.
The digit 6 was removed 379 times.
The digit 7 was removed 591 times.
The digit 8 was removed 351 times.
The digit 9 was removed 2988 times.
</pre>
=={{header|Julia}}==
<lang julia>using Combinatorics
Line 1,355 ⟶ 1,548:
12386/32654 = 1386/3654 (2 crossed out)
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
| |||