Perl Weekly Challenge 146: the first challenge of the year!
It is sad that, after more than two years of me doing Raku, I still don’t have any production code project to work on. Therefore, in order to keep my coding and Raku-ing (is that a term?) knowdledge, I try to solve every Perl Weekly Challenge tasks.In the following, the assigned tasks for Challenge 146.
And this week, as for the previous PWC, I had time to quickly implement the tasks also on PostgreSQL
plpgsql language:
PWC 146 - Task 1
The first task was about computing the1001-nth prime number, and I decided to implement it by storing the prime numbers into an array, of course lazily, and then pick up the selected value:
sub MAIN( Int $which where { $which > 0 } = 1001 ) {
my @primes = lazy { ( 1 .. Inf ).grep( *.is-prime ); }
@primes[ $which ].say;
}
Quite simple and staightforward.
PWC 146 - Task 2
The second task was about implementing a search script against a fraction tree. I decided to implement first aNode class to represent a single element of the tree:
class Node {
has Rat $.member;
has Int $.level;
has Node $.left;
has Node $.right;
has Node $.parent is rw;
submethod BUILD( Rat :$member, Int :$level = 1, Int :$stop-at = 4 ) {
$!member = $member;
$!level = $level;
if ( $level < $stop-at ) {
my $sum = $!member.numerator + $!member.denominator;
$!left = Node.new: member => $member.numerator / $sum,
level => $level + 1,
stop-at => $stop-at;
$!right = Node.new: member => $sum / $member.denominator,
level => $level + 1,
stop-at => $stop-at;
}
}
method adjust() {
$!left.parent = self if $!left;
$!right.parent = self if $!right;
$!left.adjust if $!left;
$!right.adjust if $!right;
}
method search-from-here ( Rat $needle ) {
return self if $!member ~~ $needle;
if ( $!left ) {
my $left = $!left.search-from-here( $needle );
return $left if $left;
}
if ( $!right ) {
my $right = $!right.search-from-here( $needle );
return $right if $right;
}
return Nil;
}
method Str(){ $!member.numerator ~ '/' ~ $!member.denominator }
}
When a
Node is built, it is attached to its children, $!left and $!right, at least up to a specific deep level.
The adujust method links back every children to its parent, because this cannot be done during the construction of the tree since the parent is still not a Node.
The search-from-here method is the core of the program, and does a deep-first approach in searching for the specified $needle across a node, its left children and then right children.
Therefore, the final program becomes:
sub MAIN( Rat $member ) {
my $level = 1;
my $root = Node.new: member => 1.Rat;
$root.adjust;
my Node $which = $root.search-from-here( $member );
"Not found $member " and exit if ! $which;
"Node $member found: { $which.Str } with parent { $which.parent.Str } and grandparent { $which.parent.parent.Str }".say;
}
First the root node is built, and then
adjust is invoked to fully backlink every node.
Then the $which node is the result of searching from the root node into the tree, and the remaining is just printing out the result.
PWC 146 - Task 1 in PostgreSQL
The PostgreSQL implementation is made up by two parts:- a function
f_is_primeto check if a value is prime; - a recursive CTE to scan over all primes and select the wanted one.
CREATE OR REPLACE FUNCTION
f_is_prime( val int )
RETURNS bool
AS $CODE$
DECLARE
i int;
BEGIN
IF val <= 0 THEN
RAISE EXCEPTION 'Cannot use a number less than 1!';
END IF;
FOR i IN 2 .. ( val - 1 ) LOOP
IF val % i = 0 THEN
RETURN false;
END IF;
END LOOP;
RETURN true;
END
$CODE$
LANGUAGE plpgsql;
WITH primes AS (
SELECT n as needle, row_number() OVER( PARTITION BY f_is_prime( n ) ) as idx
FROM generate_series( 1, 10000 ) n
WHERE f_is_prime( n )
ORDER BY n
)
SELECT *
FROM primes
WHERE idx = 1001;
The recusrive CTE is the interesting part. The
primes materializes all primes numbers less than 10000. I use a window function row_number to count the position of each prime number.
Then I select exactly one row, that is the one with the count equal to 1001.
PWC 146 - Task 2 in PostgreSQL
The second task has been a little more complicated to implement in PostgreSQL. I decided to got with the following approach:- create a table that represent the
Nodestructure; - populate the table by means of a function that adds another level to the tree;
- create a function to search for within the tree, and that returns three descriptive tuples.
Let’s start with the table structure:
DROP TABLE IF EXISTS fraction_tree;
CREATE TABLE fraction_tree (
pk int GENERATED ALWAYS AS IDENTITY
, numerator int default 1
, denominator int default 1
, child_of int
, level int default 1
, PRIMARY KEY( pk )
, FOREIGN KEY (child_of) REFERENCES fraction_tree( pk )
);
TRUNCATE TABLE fraction_tree;
ALTER TABLE fraction_tree ALTER COLUMN pk RESTART;
INSERT INTO fraction_tree( numerator, denominator )
VALUES( 1, 1 );
The
fraction_tree table is always “resetted” to the only one value of the root.
Then it comes the function to add a single level to the tree:
CREATE OR REPLACE FUNCTION
f_add_one_level_fraction_tree()
RETURNS INT
AS $CODE$
DECLARE
current_left fraction_tree%rowtype;
current_right fraction_tree%rowtype;
previous_tuple fraction_tree%rowtype;
nodes_added int := 0;
BEGIN
FOR previous_tuple IN SELECT * FROM fraction_tree
WHERE level = ( SELECT max( level ) FROM fraction_tree )
LOOP
current_left.numerator := previous_tuple.numerator;
current_left.denominator := ( previous_tuple.numerator + previous_tuple.denominator );
current_left.child_of := previous_tuple.pk;
current_left.level := previous_tuple.level + 1;
current_left.pk := nextval( 'fraction_tree_pk_seq' );
current_right.numerator := ( previous_tuple.numerator + previous_tuple.denominator );
current_right.denominator := previous_tuple.denominator;
current_right.child_of := previous_tuple.pk;
current_right.level := previous_tuple.level + 1;
current_right.pk := nextval( 'fraction_tree_pk_seq' );
INSERT INTO fraction_tree
OVERRIDING SYSTEM VALUE
SELECT current_left.*;
INSERT INTO fraction_tree
OVERRIDING SYSTEM VALUE
SELECT current_right.*;
nodes_added := nodes_added + 2;
END LOOP;
RETURN nodes_added;
END
$CODE$
LANGUAGE plpgsql;
Every node has its level, so I first select the nodes on the highest level (the leaves), and then iterate on each of them assigning their values to
previous_tuple. For every node found, I do generate its left and right node and insert them into the table.
But doing this population manually is boring, so I placed also a wrapper function that populates the table with the specified depth:
CREATE OR REPLACE FUNCTION
f_populate_fraction_tree( levels int default 4 )
RETURNS int
AS $CODE$
DECLARE
i int := 0;
nodes_added int := 0;
BEGIN
FOR i IN 1 .. levels LOOP
nodes_added := nodes_added + f_add_one_level_fraction_tree();
END LOOP;
RETURN nodes_added;
END
$CODE$
LANGUAGE plpgsql;
Last comes the function to find out a node, its parent and its grandparent. I decided to output a kind of text description of every node, but it is possible to change the result set to whatever information you need.
CREATE OR REPLACE FUNCTION
f_search_for_fraction_tree( numer int, denomin int )
RETURNS TABLE ( description text, fraction text )
AS $CODE$
DECLARE
current_tuple fraction_tree%rowtype;
BEGIN
SELECT 'child', numerator || '/' || denominator
INTO description, fraction
FROM fraction_tree
WHERE numerator = numer
AND denominator = denomin;
IF FOUND THEN
RETURN NEXT;
SELECT 'parent', numerator || '/' || denominator
INTO description, fraction
FROM fraction_tree
WHERE pk = ( SELECT child_of
FROM fraction_tree
WHERE numerator = numer
AND denominator = denomin );
RETURN NEXT;
SELECT 'grandparent', numerator || '/' || denominator
INTO description, fraction
FROM fraction_tree
WHERE pk = ( SELECT child_of
FROM fraction_tree
WHERE pk = ( SELECT child_of
FROM fraction_tree
WHERE numerator = numer
AND denominator = denomin ) );
RETURN NEXT;
END IF;
RETURN;
END
$CODE$
LANGUAGE plpgsql;
The idea is simple: I do search for the current node, and if I found it, I do search for its parent and grandparent. I could have done it with a recursive CTE or some other way, but this seems a quite simple approach.