Merge pull request #12185 from ysth/challenge-325-ysth

challenge 325 python and perl solutons by ysth

6 files changed, 234 insertions, 0 deletions

diff --git a/challenge-325/ysth/blog.txt b/challenge-325/ysth/blog.txt
new file mode 100644
index 0000000000..68b53a61f1
--- /dev/null
+++ b/challenge-325/ysth/blog.txt
@@ -0,0 +1 @@
+https://blog.ysth.info/idiomatic-perl-solutions-to-the-weekly-challenge-325-task-1/
diff --git a/challenge-325/ysth/blog1.txt b/challenge-325/ysth/blog1.txt
new file mode 100644
index 0000000000..423c4f4020
--- /dev/null
+++ b/challenge-325/ysth/blog1.txt
@@ -0,0 +1 @@
+https://blog.ysth.info/python-solution-to-the-weekly-challenge-325-task-2/
diff --git a/challenge-325/ysth/perl/ch-1.pl b/challenge-325/ysth/perl/ch-1.pl
new file mode 100644
index 0000000000..32d9cfc265
--- /dev/null
+++ b/challenge-325/ysth/perl/ch-1.pl
@@ -0,0 +1,136 @@
+use 5.036;
+
+use Benchmark 'cmpthese';
+use File::Slurp 'read_file', 'write_file';
+use List::Util 'max';
+use Inline 'C';
+
+my $binary_array;
+if (@ARGV) {
+    $binary_array = [ map $_ eq 1 ? 1 : 0, @ARGV ];
+}
+else {
+    # read or make some data
+    my $FILENAME = 'digits.txt';
+    my $digits;
+    if (-r $FILENAME) {
+        chomp($digits = read_file($FILENAME));
+    }
+    else {
+        # a million random 0s and 1s.
+        $digits = join "", map int 2*rand, 1..1e6;
+        # ignore failure
+        eval { write_file($FILENAME, $digits) };
+    }
+    $binary_array = [ split //, $digits ];
+}
+
+my %code = (
+    naive_regex => sub { naive_regex($binary_array) },
+    better_regex => sub { better_regex($binary_array) },
+    loop_sentinel => sub { loop_sentinel($binary_array) },
+    loop => sub { loop($binary_array) },
+    mapping => sub { mapping($binary_array) },
+    one_pass_regex => sub { one_pass_regex($binary_array) },
+    inlinec_loop => sub { inlinec_loop($binary_array) },
+);
+
+# test first
+my $expected = naive_regex($binary_array);
+say $expected;
+while (my ($name, $sub) = each %code) {
+    $sub->($binary_array) == $expected
+        or delete $code{$name}, say "$name incorrect\n";
+}
+
+cmpthese(-2, \%code);
+
+sub naive_regex ($binary_array) {
+    join('', @$binary_array) =~ /(1+)(?!.*?\1)/
+        ? length $1
+        : 0
+}
+
+sub better_regex ($binary_array) {
+    join('', @$binary_array) =~ /(?<!1)(1++)(?!.*?\1)/
+        ? length $1
+        : 0
+}
+
+sub one_pass_regex ($binary_array) {
+    join('', @$binary_array) =~ /(1++)(?:.*?(*MARK:go)\1(*SKIP:go)(*FAIL)|)/
+        ? length $1
+        : 0
+}
+
+sub loop ($binary_array) {
+    my $current_sequence = 0;
+    my $longest_sequence = 0;
+    for my $value (@$binary_array) {
+        if ($value) {
+            ++$current_sequence;
+        }
+        else {
+            if ($longest_sequence < $current_sequence) {
+                $longest_sequence = $current_sequence;
+            }
+            $current_sequence = 0;
+        }
+    }
+    if ($longest_sequence < $current_sequence) {
+        $longest_sequence = $current_sequence;
+    }
+    return $longest_sequence;
+}
+
+sub loop_sentinel ($binary_array) {
+    my $current_sequence = 0;
+    my $longest_sequence = 0;
+    # slightly simpler code, but at the cost of loading the array onto the stack
+    for my $value (@$binary_array, 0) {
+        if ($value) {
+            ++$current_sequence;
+        }
+        else {
+            if ($longest_sequence < $current_sequence) {
+                $longest_sequence = $current_sequence;
+            }
+            $current_sequence = 0;
+        }
+    }
+    return $longest_sequence;
+}
+
+sub mapping ($binary_array) {
+    my $count = 0;
+    # suppress "Found = in conditional, should be =="
+    no warnings 'syntax';
+    max( map { $_ ? ++$count : ($count = 0) || () } @$binary_array )
+}
+
+__END__
+__C__
+int inlinec_loop(SV *array) {
+    int longest_sequence = 0;
+    if (SvROK(array) && SvTYPE(SvRV(array)) == SVt_PVAV) {
+        AV *av = (AV *)SvRV(array);
+        int max_element = av_len(av);
+        int current_sequence = 0;
+        for (int i = 0; i <= max_element; ++i) {
+            int value = SvIV(*av_fetch(av, i, 0));
+            if (value) {
+                ++current_sequence;
+            }
+            else {
+                if (longest_sequence < current_sequence) {
+                    longest_sequence = current_sequence;
+                }
+                current_sequence = 0;
+            }
+        }
+        if (longest_sequence < current_sequence) {
+            longest_sequence = current_sequence;
+        }
+    }
+    return longest_sequence;
+}
diff --git a/challenge-325/ysth/perl/ch-2.pl b/challenge-325/ysth/perl/ch-2.pl
new file mode 100644
index 0000000000..e22bdc0269
--- /dev/null
+++ b/challenge-325/ysth/perl/ch-2.pl
@@ -0,0 +1,20 @@
+use 5.036;
+
+my @prices = map int, @ARGV;
+
+my @sale_prices;
+my @seen_prices;
+
+for my $price (reverse @prices) {
+    # find the index where all the seen prices are lower or equal to this price
+    my ($seen_price_index) = grep $seen_prices[$_] > $price, 0..$#seen_prices;
+    $seen_price_index //= @seen_prices;
+    my $discount = $seen_price_index > 0 ? $seen_prices[$seen_price_index - 1] : 0;
+    if ($seen_price_index == 0 || $seen_prices[$seen_price_index-1] != $price) {
+        splice @seen_prices, $seen_price_index, @seen_prices-$seen_price_index, $price;
+    }
+    unshift @sale_prices, $price - $discount;
+}
+
+say 'prices: ', join ', ', @prices;
+say 'sale prices: ', join ', ', @sale_prices;
diff --git a/challenge-325/ysth/python/ch-1.py b/challenge-325/ysth/python/ch-1.py
new file mode 100644
index 0000000000..97aa83a7a3
--- /dev/null
+++ b/challenge-325/ysth/python/ch-1.py
@@ -0,0 +1,58 @@
+import sys
+
+#https://stackoverflow.com/questions/65271060/is-there-a-built-in-way-to-use-inline-c-code-in-python
+
+# cffi? https://stackoverflow.com/questions/65271060/is-there-a-built-in-way-to-use-inline-c-code-in-python
+# python benchmarks
+
+# ch-2: perl using List::BinarySearch and Judy1
+
+def make_regex_search(r):
+    def regex_search(binary_list):
+        match = r.search(''.join(['1' if value==1 else '0' for value in binary_list]))
+        result = 0 if not match else len(match.group(1))
+        return result
+    return regex_search
+
+import re
+naive_regex = make_regex_search(re.compile('(1+)(?!.*?\\1)'))
+
+better_regex = make_regex_search(re.compile('(?<!1)(1++)(?!.*?\\1)'))
+
+# re does not support branch reset or SKIP, re and regex do not support MARK
+import pcre2
+one_pass_regex = make_regex_search(pcre2.compile('(?|(1++).*?(*MARK:go)\\1(*SKIP:go)(*FAIL)|(1++))'))
+
+def loop(binary_list):
+    current_sequence = 0;
+    longest_sequence = 0;
+    for value in binary_list:
+        if value:
+            current_sequence += 1
+        else:
+            if longest_sequence < current_sequence:
+                longest_sequence = current_sequence
+            current_sequence = 0
+    if longest_sequence < current_sequence:
+        longest_sequence = current_sequence
+    return longest_sequence
+
+def loop_sentinel(binary_list):
+    current_sequence = 0;
+    longest_sequence = 0;
+    for value in (*binary_list, 0):
+        if value:
+            current_sequence += 1
+        else:
+            if longest_sequence < current_sequence:
+                longest_sequence = current_sequence
+            current_sequence = 0
+    return longest_sequence
+
+#binary_list = [1 if value=='1' else 0 for value in sys.argv[1:]]
+from digits import digits as binary_list
+print(loop(binary_list))
+print(loop_sentinel(binary_list))
+print(naive_regex(binary_list))
+print(better_regex(binary_list))
+print(one_pass_regex(binary_list))
diff --git a/challenge-325/ysth/python/ch-2.py b/challenge-325/ysth/python/ch-2.py
new file mode 100644
index 0000000000..f151496925
--- /dev/null
+++ b/challenge-325/ysth/python/ch-2.py
@@ -0,0 +1,18 @@
+import sys
+import bisect
+
+prices = [int(value) for value in sys.argv[1:]]
+
+
+sale_prices = []
+seen_prices = []
+for price in reversed(prices):
+    seen_price_index = bisect.bisect_right(seen_prices, price)
+    discount = seen_prices[seen_price_index-1] if seen_price_index > 0 else 0
+    if seen_price_index == 0 or seen_prices[seen_price_index-1] != price:
+        seen_prices[seen_price_index:] = [price]
+    sale_prices.insert(0, price - discount)
+
+
+print("prices: ", prices)
+print("sale prices ", sale_prices)