diff options
Diffstat (limited to 'challenge-082')
| -rw-r--r-- | challenge-082/colin-crain/perl/ch-1.pl | 86 | ||||
| -rw-r--r-- | challenge-082/colin-crain/perl/ch-2.pl | 124 | ||||
| -rw-r--r-- | challenge-082/colin-crain/raku/ch-1.raku | 77 | ||||
| -rw-r--r-- | challenge-082/colin-crain/raku/ch-2.raku | 75 |
4 files changed, 362 insertions, 0 deletions
diff --git a/challenge-082/colin-crain/perl/ch-1.pl b/challenge-082/colin-crain/perl/ch-1.pl new file mode 100644 index 0000000000..3cf9a0516b --- /dev/null +++ b/challenge-082/colin-crain/perl/ch-1.pl @@ -0,0 +1,86 @@ +#! /opt/local/bin/perl +# +# factor_hardly_knew_her.pl +# +# TASK #1 › Common Factors +# Submitted by: Niels van Dijke +# You are given 2 positive numbers $M and $N. +# +# Write a script to list all common factors of the given numbers. +# +# Example 1: +# Input: +# $M = 12 +# $N = 18 +# +# Output: +# (1, 2, 3, 6) +# +# Explanation: +# Factors of 12: 1, 2, 3, 4, 6 +# Factors of 18: 1, 2, 3, 6, 9 +# +# Example 2: +# Input: +# $M = 18 +# $N = 23 +# +# Output: +# (1) +# +# Explanation: +# Factors of 18: 1, 2, 3, 6, 9 +# Factors of 23: 1 +# +# method: +# When a number is said to be a factor of another number, the +# meaning is that number times another number will equal the third. +# Reciprocally, both the number tested and the multiplier are both +# factors of third. +# +# As such when factoring, we need only check for numbers up to the +# square root of our target, if, when we find a pair of numbers that +# fit, we log both to out result list. +# +# Once we have the factors for one of our numbers, the best way to +# determine the common elements between two arrays (when we don't +# care about duplicates) is to use a hash. The factors of the first +# input number are hashed and the the sorted list of factors for the +# second number are filtered for presence in the hash before being +# output. +# +# 2020 colin crain +## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## + + + +use warnings; +use strict; +use feature ":5.26"; + +## ## ## ## ## MAIN: + +my $M = shift || 1440; +my $N = shift || 1530; + +my %lookup = map { $_ => undef } factor($M); +my @out = grep { exists $lookup{$_} } sort {$a-$b} factor($N); + +say "input :\n\tN = $N\n\tM = $M"; +say "output: ( @out )"; + + +## ## ## ## ## SUBS: + +sub factor { + my $num = shift; + my @out; + my $sq = int sqrt $num; + for (1..$sq) { + if ($num % $_ == 0) { + push @out, $_; + push @out, $num / $_ unless $_**2 == $num; + } + } + return @out; +}
\ No newline at end of file diff --git a/challenge-082/colin-crain/perl/ch-2.pl b/challenge-082/colin-crain/perl/ch-2.pl new file mode 100644 index 0000000000..8c07680219 --- /dev/null +++ b/challenge-082/colin-crain/perl/ch-2.pl @@ -0,0 +1,124 @@ +#! /opt/local/bin/perl +# +# ab_interneg.pl +# +# TASK #2 › Interleave String +# Submitted by: Mohammad S Anwar +# You are given 3 strings; $A, $B and $C. +# +# Write a script to check if $C is created by interleave $A and $B. +# +# Print 1 if check is success otherwise 0. +# +# Example 1: +# Input: +# $A = "XY" +# $B = "X" +# $C = "XXY" +# +# Output: 1 +# EXPLANATION +# "X" (from $B) + "XY" (from $A) = $C +# +# Example 2: +# Input: +# $A = "XXY" +# $B = "XXZ" +# $C = "XXXXZY" +# +# Output: 1 +# EXPLANATION +# "XX" (from $A) + "XXZ" (from $B) + "Y" (from $A) = $C +# +# Example 3: +# Input: +# $A = "YX" +# $B = "X" +# $C = "XXY" +# +# Output: 0 +# +# METHOD: +# This is a really interesting problem. At first look it has +# presents a very complex solution space, but because all of the +# strings maintain their ordering throughout the actual decision +# making never gets beyond binary choices. The key to cracking +# it is to entertain a complete idea of what "interleaving" is. +# +# Interleaving is the process of taking two strings and, from +# the beginnings of both, selecting and gathering partitions of +# first one string and then the other, assembling a constructed +# third string from the two until all characters from both +# inputs are utilized. +# +# Ok, but what does that mean to us? +# +# If we start with the two strings, we are given the choice to +# take the first letter from either string to begin our common +# concatenation. After that character is added, we are given the +# choice of continuing to add the next letter from our string or +# switch and add the first letter from the other string. When a +# letter is selected, the position to be added next from that +# string is advanced; if one string becomes exhausted, the +# assembly continues with the last part of the remaining string. +# The process continues until there are no more options for +# characters to be added. +# +# Practically, we can physically remove letters from the strings +# as we use them, which lightens the bookkeeping load. This +# includes the target string we're validating; when a character +# is chosen that letter is removed from the remaining string +# left to match. We don't need to keep a record of the string +# we're assembling, because if we run out of letters between our +# two input strings and the target simultaniously we've matched +# our last letter. The interleaving is has been successful, and +# we already know what the result looks like. +# + +# +# +# 2020 colin crain +## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## + + + +use warnings; +use strict; +use feature ":5.26"; +no warnings 'recursion'; + +## ## ## ## ## MAIN: + +my $VERBOSE = 1; + +my ($A, $B, $C) = @_; + +## let's not bother with command line input this time, shall we? +$A = "AXXZ"; +$B = "XXYZ"; +$C = "AXXYXZXZ"; +say 0 and exit if length($A)+length($B)!=length($C); + +say interleave($A, $B, $C); + +## ## ## ## ## SUBS: + +sub interleave { + my ($A, $B, $C) = @_; + say "A $A \nB $B \nC $C\n" if $VERBOSE; + + return 1 unless ( $A or $B or $C ); ## we've used all our letters + + for ($A,$B) { + if (substr($_, 0, 1) eq substr($C, 0, 1) ) { + my $taken = substr $_, 1; + my $other = $_ eq $A ? $B : $A; + my $target = substr $C, 1; + say "took ", substr($_, 0, 1), " target now $target\n" if $VERBOSE; + return 1 if interleave($taken, $other, $target); + } + } + say "backtracking..." if $VERBOSE; + + return 0; +}
\ No newline at end of file diff --git a/challenge-082/colin-crain/raku/ch-1.raku b/challenge-082/colin-crain/raku/ch-1.raku new file mode 100644 index 0000000000..d6ab95481f --- /dev/null +++ b/challenge-082/colin-crain/raku/ch-1.raku @@ -0,0 +1,77 @@ +#!/usr/bin/env perl6 +# +# +# factor_hardly_knew_her.raku +# +# TASK #1 › Common Factors +# Submitted by: Niels van Dijke +# You are given 2 positive numbers $M and $N. +# +# Write a script to list all common factors of the given numbers. +# +# Example 1: +# Input: +# $M = 12 +# $N = 18 +# +# Output: +# (1, 2, 3, 6) +# +# Explanation: +# Factors of 12: 1, 2, 3, 4, 6 +# Factors of 18: 1, 2, 3, 6, 9 +# +# Example 2: +# Input: +# $M = 18 +# $N = 23 +# +# Output: +# (1) +# +# Explanation: +# Factors of 18: 1, 2, 3, 6, 9 +# Factors of 23: 1 +# +# method: +# When a number is said to be a factor of another number, the +# meaning is that number times another number will equal the third. +# Reciprocally, both the number tested and the multiplier are both +# factors of third. +# +# As such when factoring, we need only check for numbers up to the +# square root of our target, if, when we find a pair of numbers that +# fit, we log both to out result list. +# +# Once we have the factors for one of our numbers, the best way to +# determine the common elements between two arrays (when we don't +# care about duplicates) is to use a hash. The factors of the first +# input number are hashed and the the sorted list of factors for the +# second number are filtered for presence in the hash before being +# output. +# +# +# +# 2020 colin crain +## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## + + + +unit sub MAIN (Int $M = 18, Int $N = 36) ; + +my %bag = bag factor($M); +my @out = factor($N).unique + .sort + .grep: {%bag{$_}:exists}; + +say "input :\n\tM = $M\n\tN = $N"; +say "output : ", @out; + +sub factor (Int $num) { + gather { + for (1..$num.sqrt.Int).grep({$num %% $_}) { + take $_; + take $num div $_; + } + } +} diff --git a/challenge-082/colin-crain/raku/ch-2.raku b/challenge-082/colin-crain/raku/ch-2.raku new file mode 100644 index 0000000000..cac6a3f7bf --- /dev/null +++ b/challenge-082/colin-crain/raku/ch-2.raku @@ -0,0 +1,75 @@ +#!/usr/bin/env perl6 +# +# +# ab_interneg.raku +# +# TASK #2 › Interleave String +# Submitted by: Mohammad S Anwar +# You are given 3 strings; $A, $B and $C. +# +# Write a script to check if $C is created by interleave $A and $B. +# +# Print 1 if check is success otherwise 0. +# +# Example 1: +# Input: +# $A = "XY" +# $B = "X" +# $C = "XXY" +# +# Output: 1 +# EXPLANATION +# "X" (from $B) + "XY" (from $A) = $C +# +# Example 2: +# Input: +# $A = "XXY" +# $B = "XXZ" +# $C = "XXXXZY" +# +# Output: 1 +# EXPLANATION +# "XX" (from $A) + "XXZ" (from $B) + "Y" (from $A) = $C +# +# Example 3: +# Input: +# $A = "YX" +# $B = "X" +# $C = "XXY" +# +# Output: 0 +# +# +# 2020 colin crain +## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## + + + +unit sub MAIN (Str $A = "AXXZ", Str $B = "XXYZ", Str $C = "AXXYXZXZ") ; + +my $VERBOSE = True; ## visually examine progress + +say 0 and exit if $A.chars + $B.chars != $C.chars; + +say "\noutput: ", interleave($A, $B, $C); + + +## ## ## ## ## SUBS: + +sub interleave (Str $A, Str $B, Str $C) { + + say "\nA $A \nB $B \nC $C" if $VERBOSE; + + return 1 unless any( $A, $B, $C ); ## we've used all our letters + + for $A,$B { + when $_.starts-with: $C.substr(0, 1) { + my $taken = $_.substr(1); + my $other = $_ eq $A ?? $B !! $A; + my $target = $C.substr(1); + say "took " ~ $_.substr(0, 1) ~ " target now $target" if $VERBOSE; + return 1 if interleave($taken, $other, $target); + } + } + return 0; +} |