Fraction reduction: Difference between revisions
Content deleted Content added
Alextretyak (talk | contribs) Added 11l |
|||
Line 1,522: | Line 1,522: | ||
Took 42.251172302s |
Took 42.251172302s |
||
</pre> |
</pre> |
||
=={{header|Groovy}}== |
|||
{{trans|Java}} |
|||
<lang groovy>class FractionReduction { |
|||
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) { |
|||
println(" When $commonDigit is removed, $numerator/$denominator = $numRemoved/$denRemoved") |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
println("Number of fractions where cancellation is valid = $solutions.") |
|||
List<Integer> sorted = new ArrayList<>(cancelCount.keySet()) |
|||
Collections.sort(sorted) |
|||
for (int removed : sorted) { |
|||
println(" The digit $removed was removed ${cancelCount.get(removed)} times.") |
|||
} |
|||
println() |
|||
} |
|||
private static int[] powers = [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> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
<lang haskell>import Control.Monad (guard) |
<lang haskell>import Control.Monad (guard) |