From 71140c73eefc5acc997ceb2d40b8d612e56ca4e2 Mon Sep 17 00:00:00 2001 From: Bob Lied Date: Sun, 2 Feb 2025 09:29:03 -0600 Subject: Week 306 solutions --- challenge-306/bob-lied/README | 6 +-- challenge-306/bob-lied/perl/ch-1.pl | 87 +++++++++++++++++++++++++++++++++++++ challenge-306/bob-lied/perl/ch-2.pl | 78 +++++++++++++++++++++++++++++++++ 3 files changed, 168 insertions(+), 3 deletions(-) create mode 100644 challenge-306/bob-lied/perl/ch-1.pl create mode 100644 challenge-306/bob-lied/perl/ch-2.pl diff --git a/challenge-306/bob-lied/README b/challenge-306/bob-lied/README index 77992b92ee..3a6c40ed45 100644 --- a/challenge-306/bob-lied/README +++ b/challenge-306/bob-lied/README @@ -1,4 +1,4 @@ -Solutions to weekly challenge 305 by Bob Lied +Solutions to weekly challenge 306 by Bob Lied -https://perlweeklychallenge.org/blog/perl-weekly-challenge-305/ -https://github.com/boblied/perlweeklychallenge-club/tree/master/challenge-305/bob-lied +https://perlweeklychallenge.org/blog/perl-weekly-challenge-306/ +https://github.com/boblied/perlweeklychallenge-club/tree/master/challenge-306/bob-lied diff --git a/challenge-306/bob-lied/perl/ch-1.pl b/challenge-306/bob-lied/perl/ch-1.pl new file mode 100644 index 0000000000..e00b286920 --- /dev/null +++ b/challenge-306/bob-lied/perl/ch-1.pl @@ -0,0 +1,87 @@ +#!/usr/bin/env perl +# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu: +#============================================================================= +# Copyright (c) 2025, Bob Lied +#============================================================================= +# ch-1.pl Perl Weekly Challenge 306 Task 1 Odd Sum +#============================================================================= +# You are given an array of positive integers, @ints. +# Write a script to return the sum of all possible odd-length subarrays of +# the given array. A subarray is a contiguous subsequence of the array. +# Example 1 Input: @ints = (2, 5, 3, 6, 4) +# Output: 77 +# Odd length sub-arrays: +# (2) => 2 (5) => 5 (3) => 3 (6) => 6 (4) => 4 +# (2, 5, 3) => 10 (5, 3, 6) => 14 (3, 6, 4) => 13 +# (2, 5, 3, 6, 4) => 20 +# Sum => (2 + 5 + 3 + 6 + 4) + (10 + 14 + 13) + 20 => 77 +# +# Example 2 Input: @ints = (1, 3) +# Output: 4 +#============================================================================= + +use v5.40; + +use List::Util qw/sum0/; + +use Getopt::Long; +my $Verbose = false; +my $DoTest = false; + +GetOptions("test" => \$DoTest, "verbose" => \$Verbose); +my $logger; +{ + use Log::Log4perl qw(:easy); + Log::Log4perl->easy_init({ level => ($Verbose ? $DEBUG : $INFO ), + layout => "%d{HH:mm:ss.SSS} %p{1} %m%n" }); + $logger = Log::Log4perl->get_logger(); +} +#============================================================================= + +exit(!runTest()) if $DoTest; + +say oddSum(@ARGV); + +#============================================================================= +# This implements the operations literally, but loops repeatedly over +# sub-arrays. It is possible to figure out how many times each element +# appears in the sum as a function of its position and the length of the +# array, which will be much more efficient. +sub oddSum(@ints) +{ + my $sum = sum0 @ints; + for my $group ( map { 1 + 2*$_ } 1 .. int((@ints-1)/2) ) + { + $logger->debug("group=$group"); + for (my $i = 0; $i <= @ints-$group; $i++ ) + { + $sum += $ints[$_] for ( $i .. ($i + $group - 1) ); + } + } + return $sum; +} + +# The number of times each element appears forms a pattern similar to +# Pascal's triangle: + +# array # Position under sliding window X times +# length # +# 2 # 1 1 +# 3 # 2 2 2 +# 4 # 2 3 3 2 +# 5 # 3 4 5 4 3 +# 6 # 3 5 6 6 5 3 +# 7 # 4 6 8 8 8 7 4 +# 8 # 4 7 9 10 10 9 7 4 +# 9 # 5 8 11 12 13 12 11 8 5 +# 10 # 5 9 12 14 15 15 14 12 9 5 + +sub runTest +{ + use Test2::V0; + + is( oddSum(2,5,3,6,4), 77, "Example 1"); + is( oddSum(1,3 ), 4, "Example 2"); + + done_testing; +} diff --git a/challenge-306/bob-lied/perl/ch-2.pl b/challenge-306/bob-lied/perl/ch-2.pl new file mode 100644 index 0000000000..3edcf03f4f --- /dev/null +++ b/challenge-306/bob-lied/perl/ch-2.pl @@ -0,0 +1,78 @@ +#!/usr/bin/env perl +# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu: +#============================================================================= +# Copyright (c) 2025, Bob Lied +#============================================================================= +# ch-2.pl Perl Weekly Challenge 306 Task 2 Last Element +#============================================================================= +# You are given a array of integers, @ints. +# Write a script to play a game where you pick two biggest integers in +# the given array, say x and y. Then do the following: +# a) if x == y then remove both from the given array +# b) if x != y then remove x and replace y with (y - x) +# At the end of the game, there is at most one element left. +# Return the last element if found otherwise return 0. +# Example 1 Input: @ints = (3, 8, 5, 2, 9, 2) +# Output: 1 +# Step 1: pick 8 and 9 => (3, 5, 2, 1, 2) +# Step 2: pick 3 and 5 => (2, 2, 1, 2) +# Step 3: pick 2 and 1 => (1, 2, 2) +# Step 4: pick 2 and 1 => (1, 2) +# Step 5: pick 1 and 2 => (1) +# +# Example 2 Input: @ints = (3, 2, 5) +# Output: 0 +# Step 1: pick 3 and 5 => (2, 2) +# Step 2: pick 2 and 2 => () +#============================================================================= + +use v5.40; + +use Getopt::Long; +my $Verbose = false; +my $DoTest = false; + +GetOptions("test" => \$DoTest, "verbose" => \$Verbose); +my $logger; +{ + use Log::Log4perl qw(:easy); + Log::Log4perl->easy_init({ level => ($Verbose ? $DEBUG : $INFO ), + layout => "%d{HH:mm:ss.SSS} %p{1} %m%n" }); + $logger = Log::Log4perl->get_logger(); +} +#============================================================================= + +exit(!runTest()) if $DoTest; + +say lastElem(@ARGV); + +#============================================================================= +sub lastElem(@ints) +{ + @ints = sort { $b <=> $a } @ints; + while ( @ints > 1 ) + { + if ( $ints[0] == $ints[1] ) + { + shift @ints; shift @ints; + next; + } + else + { + $ints[1] = $ints[0] - $ints[1]; + shift @ints; + @ints = sort { $b <=> $a } @ints; + } + } + return scalar(@ints); +} + +sub runTest +{ + use Test2::V0; + + is( lastElem(3,8,5,2,9,2), 1, "Example 1"); + is( lastElem(3,2,5), 0, "Example 2"); + + done_testing; +} -- cgit