From 45b61fa12dcdd1075ef4f23583384c15643c602f Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Tue, 9 Feb 2021 00:00:49 +0000 Subject: Add Perl, C, C++ and Basic solutions to challenge 99 --- challenge-099/paulo-custodio/basic/ch-1.bas | 62 ++++++++++++++++++++++++++++ challenge-099/paulo-custodio/basic/ch-2.bas | 46 +++++++++++++++++++++ challenge-099/paulo-custodio/c/ch-1.c | 64 +++++++++++++++++++++++++++++ challenge-099/paulo-custodio/c/ch-2.c | 54 ++++++++++++++++++++++++ challenge-099/paulo-custodio/cpp/ch-1.cpp | 62 ++++++++++++++++++++++++++++ challenge-099/paulo-custodio/cpp/ch-2.cpp | 52 +++++++++++++++++++++++ challenge-099/paulo-custodio/perl/ch-1.pl | 43 +++++++++++++++++++ challenge-099/paulo-custodio/perl/ch-2.pl | 61 +++++++++++++++++++++++++++ challenge-099/paulo-custodio/t/test-1.yaml | 37 +++++++++++++++++ challenge-099/paulo-custodio/t/test-2.yaml | 14 +++++++ challenge-099/paulo-custodio/test.pl | 7 ++++ 11 files changed, 502 insertions(+) create mode 100644 challenge-099/paulo-custodio/basic/ch-1.bas create mode 100644 challenge-099/paulo-custodio/basic/ch-2.bas create mode 100644 challenge-099/paulo-custodio/c/ch-1.c create mode 100644 challenge-099/paulo-custodio/c/ch-2.c create mode 100644 challenge-099/paulo-custodio/cpp/ch-1.cpp create mode 100644 challenge-099/paulo-custodio/cpp/ch-2.cpp create mode 100644 challenge-099/paulo-custodio/perl/ch-1.pl create mode 100644 challenge-099/paulo-custodio/perl/ch-2.pl create mode 100644 challenge-099/paulo-custodio/t/test-1.yaml create mode 100644 challenge-099/paulo-custodio/t/test-2.yaml create mode 100644 challenge-099/paulo-custodio/test.pl diff --git a/challenge-099/paulo-custodio/basic/ch-1.bas b/challenge-099/paulo-custodio/basic/ch-1.bas new file mode 100644 index 0000000000..255f3147ce --- /dev/null +++ b/challenge-099/paulo-custodio/basic/ch-1.bas @@ -0,0 +1,62 @@ +' TASK #1 › Pattern Match +' Submitted by: Mohammad S Anwar +' You are given a string $S and a pattern $P. +' +' Write a script to check if given pattern validate the entire string. +' Print 1 if pass otherwise 0. +' +' The patterns can also have the following characters: +' +' ? - Match any single character. +' * - Match any sequence of characters. +' Example 1: +' Input: $S = "abcde" $P = "a*e" +' Output: 1 +' Example 2: +' Input: $S = "abcde" $P = "a*d" +' Output: 0 +' Example 3: +' Input: $S = "abcde" $P = "?b*d" +' Output: 0 +' Example 4: +' Input: $S = "abcde" $P = "a*c?e" +' Output: 1 + +function match(s as string, p as string) as boolean + dim i as integer + do + if s="" and p="" then ' string and pattern finished + match=true + exit function + elseif s="" or p="" then ' string or pattern finished + match=false + exit function + elseif left(p,1)="?" then ' match any character + s=mid(s,2) + p=mid(p,2) + elseif left(p,1)="*" then ' match any sub-sequence + p=mid(p,2) + for i=1 to len(s) + if match(mid(s,i), p) then + match=true + exit function + end if + next i + match=false + exit function + elseif left(s,1)<>left(p,1) then ' chars different + match=false + exit function + else + s=mid(s,2) + p=mid(p,2) + end if + loop +end function + +' main +if match(command(1), command(2)) then + print "1" +else + print "0" +end if diff --git a/challenge-099/paulo-custodio/basic/ch-2.bas b/challenge-099/paulo-custodio/basic/ch-2.bas new file mode 100644 index 0000000000..b2733f8867 --- /dev/null +++ b/challenge-099/paulo-custodio/basic/ch-2.bas @@ -0,0 +1,46 @@ +' TASK #2 › Unique Sub-sequence +' Submitted by : Mohammad S Anwar +' You are given two strings $S and $T. +' +' Write a script to find out count of different unique sub-sequences matching +' $T without changing the position of characters. +' +' Example 1: +' Input : $S = "littleit', $T = 'lit' +' Output : 5 +' +' 1: [lit] tleit +' 2: [li] t[t] leit +' 3: [li] ttlei[t] +' 4: litt[l] e[it] +' 5: [l] ittle[it] +' Example 2: +' Input : $S = "london', $T = 'lon' +' Output : 3 +' +' 1: [lon] don +' 2: [lo] ndo[n] +' 3: [l] ond[on] + +function count_subsequences(s as string, t as string) as integer + dim matching as integer, notmatching as integer + do + if t="" then ' t is empty, matched + count_subsequences=1 + exit function + elseif s="" then ' s is empty, did not match + count_subsequences=0 + exit function + elseif left(s,1)=left(t,1) then ' same char, check two paths + matching=count_subsequences(mid(s,2), mid(t,2)) + notmatching=count_subsequences(mid(s,2), t) + count_subsequences=matching + notmatching + exit function + else ' different char, keep pattern + s=mid(s,2) + end if + loop +end function + +' main +print trim(str(count_subsequences(command(1), command(2)))) diff --git a/challenge-099/paulo-custodio/c/ch-1.c b/challenge-099/paulo-custodio/c/ch-1.c new file mode 100644 index 0000000000..a22c7d91e2 --- /dev/null +++ b/challenge-099/paulo-custodio/c/ch-1.c @@ -0,0 +1,64 @@ +/* +TASK #1 › Pattern Match +Submitted by: Mohammad S Anwar +You are given a string $S and a pattern $P. + +Write a script to check if given pattern validate the entire string. +Print 1 if pass otherwise 0. + +The patterns can also have the following characters: + +? - Match any single character. +* - Match any sequence of characters. +Example 1: +Input: $S = "abcde" $P = "a*e" +Output: 1 +Example 2: +Input: $S = "abcde" $P = "a*d" +Output: 0 +Example 3: +Input: $S = "abcde" $P = "?b*d" +Output: 0 +Example 4: +Input: $S = "abcde" $P = "a*c?e" +Output: 1 +*/ + +#include +#include +#include + +bool match(const char* s, const char* p) { + while (true) { + if (!*s && !*p) // string and pattern finished + return true; + else if (!*s || !*p) // either string or pattern finished + return false; + else if (*p == '?') { // match any character + s++; p++; + } + else if (*p == '*') { // match any sub-sequence + p++; + for (int i = 0; s[i]; i++) { + if (match(s + i, p)) + return true; + } + return false; + } + else if (*p != *s) { // chars different + return false; + } + else { // search next char + s++; p++; + } + } +} + +int main(int argc, char* argv[]) { + if (argc == 3) + printf("%d\n", match(argv[1], argv[2]) ? 1 : 0); + else { + fputs("Usage: ch-1 string pattern", stderr); + return EXIT_FAILURE; + } +} diff --git a/challenge-099/paulo-custodio/c/ch-2.c b/challenge-099/paulo-custodio/c/ch-2.c new file mode 100644 index 0000000000..5582d110a4 --- /dev/null +++ b/challenge-099/paulo-custodio/c/ch-2.c @@ -0,0 +1,54 @@ +/* +TASK #2 › Unique Sub-sequence +Submitted by : Mohammad S Anwar +You are given two strings $S and $T. + +Write a script to find out count of different unique sub-sequences matching +$T without changing the position of characters. + +Example 1: +Input : $S = "littleit', $T = 'lit' +Output : 5 + + 1: [lit] tleit + 2: [li] t[t] leit + 3: [li] ttlei[t] + 4: litt[l] e[it] + 5: [l] ittle[it] +Example 2: +Input : $S = "london', $T = 'lon' +Output : 3 + + 1: [lon] don + 2: [lo] ndo[n] + 3: [l] ond[on] +*/ + +#include +#include +#include + +int count_subsequences(const char* s, const char* t) { + while (true) { + if (!*t) // t is empty, matched + return 1; + else if (!*s) // s is empty, did not match + return 0; + else if (*s == *t) { // same char, check two paths matching and not matching + int matching = count_subsequences(s + 1, t + 1); + int not_matching = count_subsequences(s + 1, t); + return matching + not_matching; + } + else // different char, keep pattern + s++; + } +} + +int main(int argc, char* argv[]) { + if (argc == 3) + printf("%d\n", count_subsequences(argv[1], argv[2])); + else { + fputs("Usage: ch-2 string test", stderr); + return EXIT_FAILURE; + } +} diff --git a/challenge-099/paulo-custodio/cpp/ch-1.cpp b/challenge-099/paulo-custodio/cpp/ch-1.cpp new file mode 100644 index 0000000000..5fe6d95de2 --- /dev/null +++ b/challenge-099/paulo-custodio/cpp/ch-1.cpp @@ -0,0 +1,62 @@ +/* +TASK #1 › Pattern Match +Submitted by: Mohammad S Anwar +You are given a string $S and a pattern $P. + +Write a script to check if given pattern validate the entire string. +Print 1 if pass otherwise 0. + +The patterns can also have the following characters: + +? - Match any single character. +* - Match any sequence of characters. +Example 1: +Input: $S = "abcde" $P = "a*e" +Output: 1 +Example 2: +Input: $S = "abcde" $P = "a*d" +Output: 0 +Example 3: +Input: $S = "abcde" $P = "?b*d" +Output: 0 +Example 4: +Input: $S = "abcde" $P = "a*c?e" +Output: 1 +*/ + +#include + +bool match(const char* s, const char* p) { + while (true) { + if (!*s && !*p) // string and pattern finished + return true; + else if (!*s || !*p) // either string or pattern finished + return false; + else if (*p == '?') { // match any character + s++; p++; + } + else if (*p == '*') { // match any sub-sequence + p++; + for (int i = 0; s[i]; i++) { + if (match(s + i, p)) + return true; + } + return false; + } + else if (*p != *s) { // chars different + return false; + } + else { // search next char + s++; p++; + } + } +} + +int main(int argc, char* argv[]) { + if (argc == 3) + std::cout << (match(argv[1], argv[2]) ? 1 : 0) << std::endl; + else { + std::cerr << "Usage: ch-1 string pattern" << std::endl; + return EXIT_FAILURE; + } +} diff --git a/challenge-099/paulo-custodio/cpp/ch-2.cpp b/challenge-099/paulo-custodio/cpp/ch-2.cpp new file mode 100644 index 0000000000..cf0cfbd04a --- /dev/null +++ b/challenge-099/paulo-custodio/cpp/ch-2.cpp @@ -0,0 +1,52 @@ +/* +TASK #2 › Unique Sub-sequence +Submitted by : Mohammad S Anwar +You are given two strings $S and $T. + +Write a script to find out count of different unique sub-sequences matching +$T without changing the position of characters. + +Example 1: +Input : $S = "littleit', $T = 'lit' +Output : 5 + + 1: [lit] tleit + 2: [li] t[t] leit + 3: [li] ttlei[t] + 4: litt[l] e[it] + 5: [l] ittle[it] +Example 2: +Input : $S = "london', $T = 'lon' +Output : 3 + + 1: [lon] don + 2: [lo] ndo[n] + 3: [l] ond[on] +*/ + +#include + +int count_subsequences(const char* s, const char* t) { + while (true) { + if (!*t) // t is empty, matched + return 1; + else if (!*s) // s is empty, did not match + return 0; + else if (*s == *t) { // same char, check two paths matching and not matching + int matching = count_subsequences(s + 1, t + 1); + int not_matching = count_subsequences(s + 1, t); + return matching + not_matching; + } + else // different char, keep pattern + s++; + } +} + +int main(int argc, char* argv[]) { + if (argc == 3) + std::cout << count_subsequences(argv[1], argv[2]) << std::endl; + else { + std::cerr << "Usage: ch-2 string test" << std::endl; + return EXIT_FAILURE; + } +} diff --git a/challenge-099/paulo-custodio/perl/ch-1.pl b/challenge-099/paulo-custodio/perl/ch-1.pl new file mode 100644 index 0000000000..effafe2108 --- /dev/null +++ b/challenge-099/paulo-custodio/perl/ch-1.pl @@ -0,0 +1,43 @@ +#!/usr/bin/perl + +# TASK #1 › Pattern Match +# Submitted by: Mohammad S Anwar +# You are given a string $S and a pattern $P. +# +# Write a script to check if given pattern validate the entire string. +# Print 1 if pass otherwise 0. +# +# The patterns can also have the following characters: +# +# ? - Match any single character. +# * - Match any sequence of characters. +# Example 1: +# Input: $S = "abcde" $P = "a*e" +# Output: 1 +# Example 2: +# Input: $S = "abcde" $P = "a*d" +# Output: 0 +# Example 3: +# Input: $S = "abcde" $P = "?b*d" +# Output: 0 +# Example 4: +# Input: $S = "abcde" $P = "a*c?e" +# Output: 1 + +use strict; +use warnings; +use 5.030; + +@ARGV==2 or die "Usage: ch-1.pl STRING PATTERN\n"; +my($S, $P) = @ARGV; + +# make an equivalent regular expression +my $rx = $P; +for ($rx) { + s/(\W)/\\$1/g; # escape all non-word chars + s/\\\*/.*/g; # replace * (now \*) by .* + s/\\\?/./g; # replace ? (now \?) by . +} + +# and match it +say $S =~ /^$rx$/ ? 1 : 0; diff --git a/challenge-099/paulo-custodio/perl/ch-2.pl b/challenge-099/paulo-custodio/perl/ch-2.pl new file mode 100644 index 0000000000..d0a8c71867 --- /dev/null +++ b/challenge-099/paulo-custodio/perl/ch-2.pl @@ -0,0 +1,61 @@ +#!/usr/bin/perl + +# TASK #2 › Unique Subsequence +# Submitted by: Mohammad S Anwar +# You are given two strings $S and $T. +# +# Write a script to find out count of different unique subsequences matching +# $T without changing the position of characters. +# +# Example 1: +# Input: $S = "littleit', $T = 'lit' +# Output: 5 +# +# 1: [lit] tleit +# 2: [li] t [t] leit +# 3: [li] ttlei [t] +# 4: litt [l] e [it] +# 5: [l] ittle [it] +# Example 2: +# Input: $S = "london', $T = 'lon' +# Output: 3 +# +# 1: [lon] don +# 2: [lo] ndo [n] +# 3: [l] ond [on] + +use strict; +use warnings; +use 5.030; + +@ARGV==2 or die "Usage: ch-1.pl STRING TEST\n"; +say count_subsequences(@ARGV); + + +sub count_subsequences { + my($s, $t) = @_; + my $count = 0; + my @s = split(//, $s); + my @t = split(//, $t); + count_subsequences_sub(\@s, \@t, \$count); + return $count; +} + +sub count_subsequences_sub { + my($s, $t, $count) = @_; + my @s = @$s; + my @t = @$t; + + if (!@t) { + $$count++; + } + elsif (!@s) { + } + elsif ($s[0] eq $t[0]) { # this char matches + count_subsequences_sub([@s[1..$#s]], [@t[1..$#t]], $count); + count_subsequences_sub([@s[1..$#s]], [@t], $count); + } + else { + count_subsequences_sub([@s[1..$#s]], [@t], $count); + } +} diff --git a/challenge-099/paulo-custodio/t/test-1.yaml b/challenge-099/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..308a277832 --- /dev/null +++ b/challenge-099/paulo-custodio/t/test-1.yaml @@ -0,0 +1,37 @@ +- setup: + cleanup: + args: abcde "a*e" + input: + output: | + 1 + +- setup: + cleanup: + args: abcde "a*d" + input: + output: | + 0 + +- setup: + cleanup: + args: abcde "?b*d" + input: + output: | + 0 + +- setup: + cleanup: + args: abcde "a*c?e" + input: + output: | + 1 + +- setup: + cleanup: + args: abcdef "a*c?e" + input: + output: | + 0 + + + diff --git a/challenge-099/paulo-custodio/t/test-2.yaml b/challenge-099/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..ff48c2404f --- /dev/null +++ b/challenge-099/paulo-custodio/t/test-2.yaml @@ -0,0 +1,14 @@ +- setup: + cleanup: + args: littleit lit + input: + output: | + 5 + +- setup: + cleanup: + args: london lon + input: + output: | + 3 + diff --git a/challenge-099/paulo-custodio/test.pl b/challenge-099/paulo-custodio/test.pl new file mode 100644 index 0000000000..01ed2b83cd --- /dev/null +++ b/challenge-099/paulo-custodio/test.pl @@ -0,0 +1,7 @@ +#!/usr/bin/perl + +use strict; +use warnings; +use 5.030; + +require '../../challenge-001/paulo-custodio/test.pl'; -- cgit