The weekly challenge 357 - Task 2: Unique Fraction Generator

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-357/#TASK2
 3 #
 4 # Task 2: Unique Fraction Generator
 5 # =================================
 6 #
 7 # Given a positive integer N, generate all unique fractions you can create using integers from 1 to N and follow the rules below:
 8 #
 9 # - Use numbers 1 through N only (no zero)
10 # - Create fractions like numerator/denominator
11 # - List them in ascending order (from smallest to largest)
12 # - If two fractions have the same value (like 1/2 and 2/4),
13 #   only show the one with the smallest numerator
14 #
15 # Example 1
16 #
17 # Input: $int = 3
18 # Output: 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1
19 #
20 # Example 2
21 #
22 # Input: $int = 4
23 # Output: 1/4, 1/3, 1/2, 2/3, 3/4, 1/1, 4/3, 3/2, 2/1, 3/1, 4/1
24 #
25 #
26 # Example 3
27 #
28 # Input: $int = 1
29 # Output: 1/1
30 #
31 #
32 # Example 4
33 #
34 # Input: $int = 6
35 # Output: 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4,
36 #         4/5, 5/6, 1/1, 6/5, 5/4, 4/3, 3/2, 5/3, 2/1,
37 #         5/2, 3/1, 4/1, 5/1, 6/1
38 #
39 #
40 # Example 5
41 #
42 # Input: $int = 5
43 # Output: 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1,
44 #         5/4, 4/3, 3/2, 5/3, 2/1, 5/2, 3/1, 4/1, 5/1
45 #
46 ############################################################
47 ##
48 ## discussion
49 ##
50 ############################################################
51 #
52 # We create all possible fractions and add them to an array, unless
53 # the fraction can be reduced. In order to determine whether a
54 # fraction can be reduced, we calculate the greatest common
55 # divisor of the two numbers via Euclid's algorithm and check
56 # whether or not it is equal to 1.
57 # By storing each fraction as a tuple (modelled as an array of two
58 # values) of its value and the fraction as a string, we can easily
59 # sort by the value and later print the string representation.
60 #
61 
62 use v5.36;
63 
64 unique_fraction_generator(3);
65 unique_fraction_generator(4);
66 unique_fraction_generator(1);
67 unique_fraction_generator(6);
68 unique_fraction_generator(5);
69 
70 sub unique_fraction_generator($int) {
71     say "Input: $int";
72     my @result = ();
73     foreach my $i (1..$int) {
74         foreach my $j (1..$int) {
75             push @result, [$i/$j, "$i/$j"] unless can_be_reduced($i, $j);
76         }
77     }
78     say "Output: " . join(", ", map { $_->[1] } sort { $a->[0] <=> $b->[0] } @result);
79 }
80 
81 sub can_be_reduced($i, $j) {
82     while($j != 0) {
83         if($i > $j) {
84             $i = $i - $j;
85         } else {
86             $j = $j - $i;
87         }
88     }
89     return $i > 1;
90 }