From f36775cda293f2897e5a20b9ee59aa047bdbed46 Mon Sep 17 00:00:00 2001 From: dcw Date: Sun, 2 Jan 2022 22:14:41 +0000 Subject: imported my solutions to this week's tasks, although task 2 is an implementation of the task rather than an implementation of the eertree data structure --- challenge-145/duncan-c-white/README | 88 ++++++++++++++----------- challenge-145/duncan-c-white/perl/ch-1.pl | 56 ++++++++++++++++ challenge-145/duncan-c-white/perl/ch-2.pl | 105 ++++++++++++++++++++++++++++++ 3 files changed, 212 insertions(+), 37 deletions(-) create mode 100755 challenge-145/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-145/duncan-c-white/perl/ch-2.pl diff --git a/challenge-145/duncan-c-white/README b/challenge-145/duncan-c-white/README index fe2fd0f394..bdbeb3c3a5 100644 --- a/challenge-145/duncan-c-white/README +++ b/challenge-145/duncan-c-white/README @@ -1,57 +1,71 @@ -TASK #1 - Semiprime +TASK #1 - Dot Product -Write a script to generate all Semiprime number <= 100. +You are given 2 arrays of same size, @a and @b. -For more information about Semiprime, please checkout the wikipedia page -https://en.wikipedia.org/wiki/Semiprime +Write a script to implement Dot Product. -In mathematics, a semiprime is a natural number that is the product of -exactly two prime numbers. The two primes in the product may equal each -other, so the semiprimes include the squares of prime numbers. +Example: -Example + @a = (1, 2, 3); + @b = (4, 5, 6); - 10 is Semiprime as 10 = 2 x 5 - 15 is Semiprime as 15 = 3 x 5 + $dot_product = (1 * 4) + (2 * 5) + (3 * 6) => 4 + 10 + 18 => 32 -MY NOTES: Sounds easy, using my existing factors function, and -my existing prime generation code. +MY NOTES: Very easy. -TASK #2 - Ulam Sequence +TASK #2 - Palindromic Tree -You are given two positive numbers, $u and $v. +You are given a string $s. -Write a script to generate Ulam Sequence having at least 10 Ulam numbers -where $u and $v are the first 2 Ulam numbers. +Write a script to create a Palindromic Tree for the given string. -For more information about Ulam Sequence, please checkout the website -https://en.wikipedia.org/wiki/Ulam_number +I found this blog exaplaining Palindromic Tree in detail: -The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 = -1 and U2 = 2. Then for n > 2, Un is defined to be the smallest integer -that is the sum of two distinct earlier terms in exactly one way and -larger than all earlier terms. +https://medium.com/@alessiopiergiacomi/eertree-or-palindromic-tree-82453e75025b -Example 1 +Example 1: - Input: $u = 1, $v = 2 - Output: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18 + Input: $s = 'redivider' + Output: r redivider e edivide d divid i ivi v -Example 2 +Example 2: - Input: $u = 2, $v = 3 - Output: 2, 3, 5, 7, 8, 9, 13, 14, 18, 19 + Input: $s = 'deific' + Output: d e i ifi f c -Example 3 +Example 3: - Input: $u = 2, $v = 5 - Output: 2, 5, 7, 9, 11, 12, 13, 15, 19, 23 + Input: $s = 'rotors' + Output: r rotor o oto t s +Example 4: -MY NOTES: hmm.. sounds relatively straightforward. I'm slightly puzzled -by "in exactly one way", but the wikipedia gives an example that clarifies it. -So presumably we're going to check each distinct pair of earlier terms, -checking whether the sum of that pair is an Ulam number at all, whether it's -greater than the last term we've found, and then pick the smallest of all -such numbers found. Obviously O(N**2) or worse. + Input: $s = 'challenge' + Output: c h a l ll e n g + +Example 5: + + Input: $s = 'champion' + Output: c h a m p i o n + +Example 6: + + Input: $s = 'christmas' + Output: c h r i s t m a + +MY NOTES: hmm.. I read the blog, but what on earth is it +talking about, it's not very clear? the underlying paper +https://arxiv.org/pdf/1506.04862.pdf is a lot clearer, but +still way too detailed for 10pm on a Sunday. + +Looking at the examples given above, the output seems to be +a list of palindromic substrings not previously encountered, +in the natural order found by sequencing through every starting +position in the word and trying increasingly long substrings +for "Palindromic"-ness. + +So, could we solve the "generate the output from the input" +problem, entirely ignoring the whole "build a weird tree" +part of it? Presumably a lot less efficient than their +clever eertree/Palindrome tree thingy, but who cares. diff --git a/challenge-145/duncan-c-white/perl/ch-1.pl b/challenge-145/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..db3ad4e9d7 --- /dev/null +++ b/challenge-145/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,56 @@ +#!/usr/bin/perl +# +# TASK #1 - Dot Product +# +# You are given 2 arrays of same size, @a and @b. +# +# Write a script to implement Dot Product. +# +# Example: +# +# @a = (1, 2, 3); +# @b = (4, 5, 6); +# +# $dot_product = (1 * 4) + (2 * 5) + (3 * 6) => 4 + 10 + 18 => 32 +# +# MY NOTES: Very easy. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; + +my $debug=0; +die "Usage: dot-product [--debug] A1,A2.. B1,B2..\n" unless + GetOptions( "debug"=>\$debug ) && @ARGV==2; + +# +# my $dp = dotproduct( $a, $b ); +# Produce and return the dot product of arrays @$a and @$b +# +sub dotproduct ($$) +{ + my( $a, $b ) = @_; + my $na = @$a; + my $nb = @$b; + + die "dot-product: A and B arrays must be same size (A has $na, B has $nb)\n" + unless $na==$nb; + + my $result = 0; + foreach my $i (0..$na-1) + { + $result += $a->[$i] * $b->[$i]; + } + return $result; +} + + +my @a = split( /,/, shift ); +my @b = split( /,/, shift ); + + +my $dp = dotproduct( \@a, \@b ); +say $dp; diff --git a/challenge-145/duncan-c-white/perl/ch-2.pl b/challenge-145/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..847172e56e --- /dev/null +++ b/challenge-145/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,105 @@ +#!/usr/bin/perl +# +# TASK #2 - Palindromic Tree +# +# You are given a string $s. +# +# Write a script to create a Palindromic Tree for the given string. +# +# I found this blog exaplaining Palindromic Tree in detail: +# +# https://medium.com/@alessiopiergiacomi/eertree-or-palindromic-tree-82453e75025b +# +# Example 1: +# +# Input: $s = 'redivider' +# Output: r redivider e edivide d divid i ivi v +# +# Example 2: +# +# Input: $s = 'deific' +# Output: d e i ifi f c +# +# Example 3: +# +# Input: $s = 'rotors' +# Output: r rotor o oto t s +# +# Example 4: +# +# Input: $s = 'challenge' +# Output: c h a l ll e n g +# +# Example 5: +# +# Input: $s = 'champion' +# Output: c h a m p i o n +# +# Example 6: +# +# Input: $s = 'christmas' +# Output: c h r i s t m a +# +# MY NOTES: hmm.. I read the blog, but what on earth is +# it talking about? the underlying paper https://arxiv.org/pdf/1506.04862.pdf +# is a lot clearer, but way too detailed for 10pm on a Sunday. +# +# looking at the examples given above, the output seems to be +# a list of palindromic substrings not previously encountered, +# in the natural order found by sequencing through every starting +# position in the word and trying increasingly long substrings +# for "Palindromic"-ness. +# +# So, could we solve the "generate the output from the input" +# problem, entirely ignoring the whole "build a weird tree" +# part of it? Presumably a lot less efficient than their +# clever eertree/Palindrome tree thingy, but who cares. +# +# So let's give that a try. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Data::Dumper; +use Function::Parameters; + + +my $debug=0; + +# +# my @pals = palindomes( $s ); +# Generate and return the list of all subpalindromes of $s +# in the desired order. +# +fun palindomes( $s ) +{ + my @result; + my %seen; + my $len = length($s); + + for( my $i=0; $i < $len; $i++ ) + { + my $ch = substr($s,$i,1); + push @result, $ch unless $seen{$ch}++; + for( my $j=$i+1; $j < $len; $j++ ) + { + my $substr = substr($s,$i,1+$j-$i); + next unless reverse($substr) eq $substr; + say "debug: i=$i, j=$j, substr=$substr" if $debug; + push @result, $substr unless $seen{$substr}++; + } + } + return @result; +} + + + +die "Usage: palindrome-trees [--debug] string\n" unless + GetOptions( "debug"=>\$debug ) && @ARGV==1; +my $s = shift; + +my @pals = palindomes( $s ); + +say join( ' ', @pals ); -- cgit