Fraction reduction: Difference between revisions
Content added Content deleted
Line 1,230: | Line 1,230: | ||
</pre> |
</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}}== |
=={{header|Julia}}== |
||
<lang julia>using Combinatorics |
<lang julia>using Combinatorics |
||
Line 1,355: | Line 1,548: | ||
12386/32654 = 1386/3654 (2 crossed out) |
12386/32654 = 1386/3654 (2 crossed out) |
||
</pre> |
</pre> |
||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Go}} |
{{trans|Go}} |