1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
|
#!perl
###############################################################################
=comment
Perl Weekly Challenge 146
=========================
TASK #2
-------
*Curious Fraction Tree*
Submitted by: Mohammad S Anwar
Consider the following Curious Fraction Tree:
1/1
---------------------------------------
| |
| |
1/2 2/1
------------------- -------------------
| | | |
| | | |
1/3 3/2 2/3 3/1
--------- --------- --------- ---------
| | | | | | | |
| | | | | | | |
1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
You are given a fraction, member of the tree created similar to the above
sample.
Write a script to find out the parent and grandparent of the given member.
Example 1:
Input: $member = '3/5';
Output: parent = '3/2' and grandparent = '1/2'
Example 2:
Input: $member = '4/3';
Output: parent = '1/3' and grandparent = '1/2'
=cut
###############################################################################
#--------------------------------------#
# Copyright © 2022 PerlMonk Athanasius #
#--------------------------------------#
#==============================================================================
=comment
Assumption
----------
The input numerator and denominator must be positive (non-zero) integers and
relative primes (i.e., coprimes).
Output
------
Standard output displays the parent and grandparent (if any) of the given
fraction, as per the Examples.
In my view, however, a more interesting output is a display of all the nodes
which form a path from the root to the given fraction. To see this additional
output, set the constant $SHOW_PATH to a true value.
Algorithm
---------
As explained in [1], the children of each node a/b in the Curious Fraction Tree
are a/(a+b) (left) and (a+b)/b (right). Left children are always less than one,
and right children are always greater than one. Therefore, the parent of any
given fraction n/d may be found as follows:
IF n = d = 1 THEN n/d is the root node, and has no parent
ELSE
IF n < d THEN n/d is a left child, and its parent is n/(d - n)
ELSE n/d is a right child, and its parent is (n - d)/d
ENDIF
ENDIF
Of course, the grandparent of any fraction is simply the parent of its parent.
Reference
---------
[1] James Tanton, "Fractions are Hard! 5.3 A Curious Fraction Tree".
https://gdaymath.com/lessons/fractions/5-3-a-curious-fraction-tree/
=cut
#==============================================================================
use strict;
use warnings;
use Const::Fast;
use Math::Prime::Util qw( gcd );
use Regexp::Common qw( number );
const my $SHOW_PATH => 1;
const my $USAGE =>
"Usage:
perl $0 <num> <den>
<num> Numerator: positive integer
<den> Denominator: positive integer, coprime to the numerator\n";
#------------------------------------------------------------------------------
BEGIN
#------------------------------------------------------------------------------
{
$| = 1;
print "\nChallenge 146, Task #2: Curious Fraction Tree (Perl)\n\n";
}
#==============================================================================
MAIN:
#==============================================================================
{
my ($num, $den) = parse_command_line();
print "Input: member = '$num/$den'\n";
my ($pa, $pb);
print 'Output: ';
if (get_parent( $num, $den, \$pa, \$pb ))
{
my ($ga, $gb);
if (get_parent( $pa, $pb, \$ga, \$gb))
{
print "parent = '$pa/$pb' and grandparent = '$ga/$gb'\n";
}
else
{
print "parent = '1/1' (root) and there is no grandparent\n";
}
}
else
{
print "root has no parent (or grandparent)\n";
}
if ($SHOW_PATH)
{
my $path = get_all_ancestors( $num, $den );
printf "\nPath from root:\n%s\n", join ' --> ', @$path;
}
}
#------------------------------------------------------------------------------
sub get_parent
#------------------------------------------------------------------------------
{
my ($n, $d, $pa, $pb) = @_;
my $has_parent = 1;
if ($n == $d)
{
$has_parent = 0;
}
elsif ($n < $d)
{
$$pa = $n;
$$pb = $d - $n;
}
else # $n > $d
{
$$pa = $n - $d;
$$pb = $d;
}
return $has_parent;
}
#------------------------------------------------------------------------------
sub get_all_ancestors
#------------------------------------------------------------------------------
{
my ($n, $d ) = @_;
my @path = "$n/$d";
my ($pa, $pb);
while (get_parent( $n, $d, \$pa, \$pb ))
{
push @path, "$pa/$pb";
$n = $pa;
$d = $pb;
}
@path = reverse @path;
return \@path;
}
#------------------------------------------------------------------------------
sub parse_command_line
#------------------------------------------------------------------------------
{
my $args = scalar @ARGV;
$args == 2 or error( "Expected 2 command line arguments, found $args" );
for (@ARGV)
{
/ ^ $RE{num}{int} $ /x
or error( qq["$_" is not a valid integer] );
$_ > 0 or error( "$_ is not positive" );
}
my ($num, $den) = @ARGV;
gcd( $num, $den ) == 1
or error( "The numerator and denominator are not coprimes" );
return ($num, $den);
}
#------------------------------------------------------------------------------
sub error
#------------------------------------------------------------------------------
{
my ($message) = @_;
die "ERROR: $message\n$USAGE";
}
###############################################################################
|
