diff options
52 files changed, 3008 insertions, 1349 deletions
diff --git a/challenge-074/yet-ebreo/perl/ch-1.pl b/challenge-074/yet-ebreo/perl/ch-1.pl new file mode 100644 index 0000000000..7e2dc4c342 --- /dev/null +++ b/challenge-074/yet-ebreo/perl/ch-1.pl @@ -0,0 +1,12 @@ +#! /usr/bin/perl +use strict; +use feature 'say'; + +my @list = (1, 3, 1, 2, 4, 5); +my %h; + +$h{$_}++ for @list; + +my $r = (sort { $h{$b}-$h{$a} } keys %h)[0]; + +print ( ($h{$r}> @list/2) ? $r : -1 )
\ No newline at end of file diff --git a/challenge-074/yet-ebreo/perl/ch-2.pl b/challenge-074/yet-ebreo/perl/ch-2.pl new file mode 100644 index 0000000000..01b4ad6b01 --- /dev/null +++ b/challenge-074/yet-ebreo/perl/ch-2.pl @@ -0,0 +1,13 @@ +#! /usr/bin/perl +use strict; +use warnings; +use feature 'say'; + + +my $p; +for my $c (($ARGV[0] || "ababc") =~ /./g) { + $p .= $c; + 1 while $p=~s/(.)(.*)\1/$2/; + print ((substr $p,-1) || "#"); + +}
\ No newline at end of file diff --git a/challenge-075/ash/blog.txt b/challenge-075/ash/blog.txt new file mode 100644 index 0000000000..804c56654c --- /dev/null +++ b/challenge-075/ash/blog.txt @@ -0,0 +1 @@ +https://andrewshitov.com/2020/08/29/coins-sum-the-raku-challenge-week-75-task-1/ diff --git a/challenge-075/ash/blog1.txt b/challenge-075/ash/blog1.txt new file mode 100644 index 0000000000..e1998ba852 --- /dev/null +++ b/challenge-075/ash/blog1.txt @@ -0,0 +1 @@ +https://andrewshitov.com/2020/08/29/largest-rectangle-histogram-the-raku-challenge-week-75-task-2/ diff --git a/challenge-075/ash/cpp/ch-2.cpp b/challenge-075/ash/cpp/ch-2.cpp new file mode 100644 index 0000000000..130f41839e --- /dev/null +++ b/challenge-075/ash/cpp/ch-2.cpp @@ -0,0 +1,41 @@ +/* + Task 2 from https://perlweeklychallenge.org/blog/perl-weekly-challenge-075/ + + Comments: https://andrewshitov.com/2020/08/29/largest-rectangle-histogram-the-raku-challenge-week-75-task-2/ + + How to compile: + $ g++ --std=c++17 ch-2.cpp +*/ + +#include <iostream> +#include <vector> + +using namespace std; + +int main() { + vector<int> hist = {3, 2, 3, 5, 7, 5}; + + int max_area = 0; + int max_start; + int max_end; + + for (auto start = 0; start <= hist.size(); start++) { + for (auto end = start + 1; end < hist.size(); end++) { + auto min_height = INT_MAX; + for (auto i = start; i != end; i++) { + if (hist[i] < min_height) min_height = hist[i]; + } + + auto area = min_height * (1 + end - start); + + if (area > max_area) { + max_area = area; + max_start = start; + max_end = end; + } + } + } + + cout << "The biggest rectangle is between the columns " << max_start << " and " << max_end + << " and its area is " << max_area << ".\n"; +} diff --git a/challenge-075/ash/raku/ch-1.raku b/challenge-075/ash/raku/ch-1.raku new file mode 100644 index 0000000000..681643dc6a --- /dev/null +++ b/challenge-075/ash/raku/ch-1.raku @@ -0,0 +1,26 @@ +#!/usr/bin/env raku + +# Task 1 from +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075/ + +# Comments: https://andrewshitov.com/2020/08/29/the-raku-challenge-week-75/ + +my @coins = 1, 2, 4; +my $sum = 6; + +my @wallet; +@wallet.append: $_ xx ($sum div $_) for @coins; + +# say @wallet; + +.say for @wallet.combinations.unique(:as(*.Str)).grep({$sum == [+] $_}); + +# Output: +# +# $ raku ch-1.raku +# (2 4) +# (1 1 4) +# (2 2 2) +# (1 1 2 2) +# (1 1 1 1 2) +# (1 1 1 1 1 1) diff --git a/challenge-075/ash/raku/ch-2.raku b/challenge-075/ash/raku/ch-2.raku new file mode 100644 index 0000000000..7253841f3f --- /dev/null +++ b/challenge-075/ash/raku/ch-2.raku @@ -0,0 +1,44 @@ +#!/usr/bin/env raku + +# Task 2 from +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-075/ + +# Comments: https://andrewshitov.com/2020/08/29/largest-rectangle-histogram-the-raku-challenge-week-75-task-2/ + +# my @hist = 2, 1, 4, 5, 3, 7; +my @hist = 3, 2, 3, 5, 7, 5; + +my $max = 0; +my @max; + +for ^@hist -> $start { + for $start ^..^ @hist -> $end { + my $area = min(@hist[$start .. $end]) * (1 + $end - $start); + # say "$start..$end = $area"; + if $area > $max { + $max = $area; + @max = $start, $end; + } + } +} + +say "The biggest rectangle is between the columns @max[0] and @max[1] and its area is $max."; + +# Output: +# $ raku ch-2.raku +# 0..1 = 4 +# 0..2 = 6 +# 0..3 = 8 +# 0..4 = 10 +# 0..5 = 12 +# 1..2 = 4 +# 1..3 = 6 +# 1..4 = 8 +# 1..5 = 10 +# 2..3 = 6 +# 2..4 = 9 +# 2..5 = 12 +# 3..4 = 10 +# 3..5 = 15 +# 4..5 = 10 +# The biggest rectangle is between the columns 3 and 5 and its area is 15. diff --git a/challenge-075/cheok-yin-fung/BLOG.txt b/challenge-075/cheok-yin-fung/BLOG.txt new file mode 100644 index 0000000000..34c511b87d --- /dev/null +++ b/challenge-075/cheok-yin-fung/BLOG.txt @@ -0,0 +1 @@ +http://blogs.perl.org/users/c_y_fung/2020/08/tc.html diff --git a/challenge-075/cheok-yin-fung/common-lisp/ch-1.lsp b/challenge-075/cheok-yin-fung/common-lisp/ch-1.lsp new file mode 100644 index 0000000000..df5a342a93 --- /dev/null +++ b/challenge-075/cheok-yin-fung/common-lisp/ch-1.lsp @@ -0,0 +1,61 @@ +; Perl Weekly Challenge #075 Task 1 Coins Sum +; task statement: +; You are given a set of coins @C, assuming you have +; infinite amount of each coin in the set. +; Write a script to find how many ways you make +; sum $S using the coins from the set @C. +; Usage: (coins-sum (list $S @C)) + +(defun same-combination (l1 l2) + (setf current T) + (setf l2-car (car l2)) + (if (member l2-car l1) + (setf new-l1 (remove l2-car l1 :count 1)) + (setf current nil)) + (setf new-l2 (rest l2)) + (cond + ((equal current nil) nil) + ((and (equal new-l1 nil) (equal new-l2 nil)) t) + (t (same-combination new-l1 new-l2) )) +) + +(setf *print-array* T) + +(defun COINS-SUM (urinput) + (setf COINS (rest urinput) + TARGET (car urinput) + ARR NIL ) + +; initialize the array for dynamic programming + (setf vec-for-dp (make-array (+ 1 TARGET) :initial-element NIL)) + + + (loop for i from 1 to TARGET + do ( + if (some (lambda (x) (equal i x)) COINS) + (setf (aref vec-for-dp i) (list ( list i) )))) + + + (loop for i from 1 to TARGET + do ( dolist (element COINS) + (setf temp (- i element)) + (if ( > temp 0) + (progn + (dolist (partition (aref vec-for-dp temp)) + (setf newpartition + (append partition (list element))) + (if (NOTANY + (lambda (x) + (same-combination newpartition x)) + (aref vec-for-dp i) ) + (push newpartition (aref vec-for-dp i)) + )))))) + +; print the combinations of coins + (format t (write-to-string (aref vec-for-dp target))) +; print the answer + (format t (write-to-string (length (aref vec-for-dp target)))) +) + + + diff --git a/challenge-075/cheok-yin-fung/java/coinssum.class b/challenge-075/cheok-yin-fung/java/coinssum.class Binary files differnew file mode 100644 index 0000000000..674b401cb4 --- /dev/null +++ b/challenge-075/cheok-yin-fung/java/coinssum.class diff --git a/challenge-075/cheok-yin-fung/java/coinssum.java b/challenge-075/cheok-yin-fung/java/coinssum.java new file mode 100644 index 0000000000..99856867fe --- /dev/null +++ b/challenge-075/cheok-yin-fung/java/coinssum.java @@ -0,0 +1,90 @@ +// # Perl Weekly Challenge #075 Task 1 Coins Sum, Java Program +// task statement: +// You are given a set of coins @C, assuming you have +// infinite amount of each coin in the set. +// Write a script to find how many ways you make +// sum $S using the coins from the set @C. + +import java.util.Scanner; +import java.util.ArrayList; +import java.util.Vector; +import java.util.Collections; +import java.util.Arrays; + +public class coinssum { + static public void main(String[] args) { + // int[] coins = new int[] {1, 2, 4}; + // int total = 5; + + Scanner scn = new Scanner(System.in); + System.out.println("Input expected sum of coins:"); + int total = scn.nextInt(); + System.out.println("Input number of varieties of coins:"); + int size = scn.nextInt(); + int[] coins = new int[size]; + System.out.println("Input values of the coins:"); + for (int k = 0; k < size; k++) { + coins[k] = scn.nextInt(); + } + + +// initialize the "ArrayList" for dynamic programming + ArrayList<Vector>[] arr_for_dp = new ArrayList[total+1]; + + int j = 0; + for (int i=0; i <= total; i++) { + arr_for_dp[i] = new ArrayList<Vector>(); + if (i == coins[j]) { + Vector temp = new Vector(); + temp.addElement(new Integer(coins[j])); + arr_for_dp[i].add( temp ); + if (j < coins.length-1) { + j++; + } + } + } + + for (int i=0; i<=total; i++) { + for (int k=0; k < coins.length; k++) { + if (i-coins[k] > 0) { + for (int p=0; p < arr_for_dp[i-coins[k]].size(); p++) { + Vector partition = arr_for_dp[i-coins[k]].get(p); + Vector partition_p = new Vector<Integer>(); + partition_p = (Vector)partition.clone(); + partition_p.addElement(coins[k]); + Collections.sort(partition_p); + if ((!arr_for_dp[i].contains(partition_p))) { + arr_for_dp[i].add(partition_p); + } + + } + } + } + } + + + int ans = arr_for_dp[total].size(); + if ( ans > 0) { + for (int f=0; f<ans; f++) { + Vector testvector = arr_for_dp[total].get(f); + System.out.println(testvector); + } + } + + + System.out.println(ans); + + } + + + + +} + + + +//references: +//textbook +//https://www.w3schools.com/java/java_arraylist.asp +//https://www.geeksforgeeks.org/array-of-arraylist-in-java/ +//https://www.cis.upenn.edu/~bcpierce/courses/629/jdkdocs/api/java.util.Vector.html diff --git a/challenge-075/cheok-yin-fung/java/histogram.class b/challenge-075/cheok-yin-fung/java/histogram.class Binary files differnew file mode 100644 index 0000000000..83eefe0814 --- /dev/null +++ b/challenge-075/cheok-yin-fung/java/histogram.class diff --git a/challenge-075/cheok-yin-fung/java/histogram.java b/challenge-075/cheok-yin-fung/java/histogram.java new file mode 100644 index 0000000000..cd5c66d844 --- /dev/null +++ b/challenge-075/cheok-yin-fung/java/histogram.java @@ -0,0 +1,78 @@ +import java.util.Scanner; + +public class histogram { + static public void main(String[] args) { + int maxarea = 0; + int max_element = 0; + // int[] A = new int[] {3, 2, 3, 5, 7, 5}; + // int[] A = new int[] {2, 1, 4, 5, 3, 7}; + // int[] A = new int[] {1, 2, 3, 4, 5}; + Scanner scn = new Scanner(System.in); + System.out.println("Input number of items of the histogram:"); + int size = scn.nextInt(); + int[] A = new int[size]; + System.out.println("Input items of the histogram:"); + for (int k = 0; k < size; k++) { + A[k] = scn.nextInt(); + if (A[k] > max_element) { + max_element = A[k]; + } + } + for (int winsize = 1; winsize <= A.length; winsize++) { + for (int i = 0; i+winsize-1 < A.length; i++) { + int area; + int minele = 128; + int[] Baby = new int[winsize]; + for (int j = 0; j < winsize; j++) { + Baby[j] = A[i+j]; + if (Baby[j] < minele) { + minele = Baby[j]; + } + } + area = winsize*minele; +// the followings need import java.util.Arrays and java.util.Collections +// List b = arrays.asList(ArrayUtils.toObject(Baby)); +// area = winsize*(Collections.min(b)); + if (area>maxarea) { + maxarea = area; + } + } + } + + System.out.println("\n"+maxarea + "\n"); + + // print the histogram + + for (int r = max_element; r > 0; r--) { + System.out.print(r+" "); + for (int k = 0; k < size; k++) { + char temp; + if (A[k] >= r) { + temp = '#'; + } else { + temp = ' '; + } + System.out.print(temp+" "); + } + + System.out.println(); + } + System.out.print("_ "); + for (int s = 0; s < size; s++) { + System.out.print("_ "); + } + System.out.println(); + System.out.print(" "); + for (int k = 0; k < size; k++) { + System.out.print(A[k]+" "); + } + System.out.println(); + + } +} + + +// references: +// textbook +// https://stackoverflow.com/questions/2795350/how-to-put-a-scanner-input-into-an-array-for-example-a-couple-of-numbers +// https://stackoverflow.com/questions/1484347/finding-the-max-min-value-in-an-array-of-primitives-using-java diff --git a/challenge-075/cheok-yin-fung/perl/ch-1.pl b/challenge-075/cheok-yin-fung/perl/ch-1.pl new file mode 100644 index 0000000000..ec5ed93822 --- /dev/null +++ b/challenge-075/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,90 @@ +#!/usr/bin/perl +# Perl Weekly Challenge #075 Task 1 Coins Sum +# task statement: +# You are given a set of coins @C, assuming you have +# infinite amount of each coin in the set. +# Write a script to find how many ways you make +# sum $S using the coins from the set @C. +# Usage: ch-1a.pl $S @C +use strict; +use warnings; +use Data::Dumper; +#use Test::More tests => 4; + +my $S; +my @C; +if ($ARGV[1]) {$S = shift @ARGV; @C = @ARGV;} else {$S = 6; @C = (1,2,4);} + + +sub contain { + my @small = @{ $_[0] }; + my $size_of_smaller_arr = scalar @small; + my @set_of_partitions = @{ $_[1] }; + my $size_of_the_set_of_parts = scalar @set_of_partitions; + my $index = 0; + my $tf_found = undef; + while ( not($tf_found) && ($index < $size_of_the_set_of_parts) ) { + my @a_partition = @{ $set_of_partitions[$index] }; + my $k = 0; + $tf_found = ( scalar @a_partition == scalar @a_partition ); + while ($tf_found && ($k < $size_of_smaller_arr)) { + $tf_found = $tf_found && ($a_partition[$k] == $small[$k]); + $k++; + } + $index++; + } + return $tf_found; +} + +sub coins_sum { + my $total = shift @_; + my @coins = @_; + my @EMPTYARR = []; + my @arr_for_dp = (); + + # initialize the array for dynamic programming + $arr_for_dp[0] = (@EMPTYARR); + for my $i (1..$total) { + @{$arr_for_dp[$i]} = (); + } + for my $coin_v (@coins) { + push @{$arr_for_dp[$coin_v]}, [$coin_v] if $coin_v <= $total; + # the "if" condition avoids array overflow + } + + + for my $i (1..$total) { + for my $coin_v (@coins) { + if ($i-$coin_v > 0) { + for my $r (@{$arr_for_dp[$i-$coin_v]}) { + my @temp = @{$r}; + push @temp, $coin_v; + @temp = sort {$a <=> $b } @temp; + if (!contain([@temp], $arr_for_dp[$i])) { + push @{$arr_for_dp[$i]}, [@temp] ; + } + } + } + } + } + + #print the combinations of coins + for my $partition (@{$arr_for_dp[$total]}) { + print join " ", @{$partition}; + print "\n"; + } + + print "\n"; + #return answer + return scalar @{$arr_for_dp[$total]}; +} + +print "total number of ways: ", coins_sum($S, @C); +print "\n"; + +=pod +ok coins_sum(6, 1, 2, 4) == 6, "test 1"; +ok coins_sum(5, 1, 2, 3, 5) == 6, "test 2"; +ok coins_sum(5, 1, 2, 3, 4, 5) == 7, "test 3"; +ok coins_sum(20, 1, 2, 4) == 36, "test 4"; +=cut diff --git a/challenge-075/cheok-yin-fung/perl/ch-1a.pl b/challenge-075/cheok-yin-fung/perl/ch-1a.pl new file mode 100644 index 0000000000..84134b8610 --- /dev/null +++ b/challenge-075/cheok-yin-fung/perl/ch-1a.pl @@ -0,0 +1,59 @@ +#!/usr/bin/perl +# Perl Weekly Challenge #075 Task 1 Coins Sum +# task statement: +# You are given a set of coins @C, assuming you have +# infinite amount of each coin in the set. +# Write a script to find how many ways you make +# sum $S using the coins from the set @C. +# Usage: ch-1a.pl $S @C +use strict; +use warnings; +#use Test::More tests => 3; +use Integer::Partition; + +sub okcoins { + my @coins = @{$_[0]}; + my @partition = @{$_[1]}; + my $ans = 1; + my $psize = scalar @partition; + my %ecoins; + for (@coins) { + $ecoins{$_} = 1; + } + my $i = 0; + while ($ans && ($i < $psize)) { + $ans = $ans && exists $ecoins{$partition[$i]}; + $i++; + } + return $ans; +} + +sub main { + my ($sum, @coins) = @_; + my @out = (); + my $objIP = Integer::Partition->new($sum , {lexicographic => 1}); + while (my $p = $objIP->next) { + my @p_order = reverse @$p; + if (okcoins(\@coins, \@p_order)) { + push @out, \@p_order; + print join ' ', @p_order; + print "\n"; + } + } + print "\n"; + return scalar @out; +} + +my $S; +my @C; + +if ($ARGV[1]) {$S = shift @ARGV; @C = @ARGV;} else {$S = 3; @C = (1,2);} + +print "total number of ways: ", main($S, @C); +print "\n"; + +=pod +ok main(6, 1, 2, 4) == 6, "test 1"; +ok main(5, 1, 2, 3, 5) == 6, "test 2"; +ok main(5, 1, 2, 3, 4, 5) == 7, "test 3"; +=cut diff --git a/challenge-075/cheok-yin-fung/perl/ch-2.pl b/challenge-075/cheok-yin-fung/perl/ch-2.pl new file mode 100644 index 0000000000..4429637893 --- /dev/null +++ b/challenge-075/cheok-yin-fung/perl/ch-2.pl @@ -0,0 +1,85 @@ +#!/usr/bin/perl +# Perl Weekly Challenge #075 Task 2 Largest Rectangle Histogram +# Usage: ch-2.pl [ARRAY] +#use Test::Simple tests=>2; +use List::Util qw/max/; +use strict; +use warnings; + +my @A; + +if (@ARGV) {@A = @ARGV;} else {@A = (3, 2, 3, 5, 7, 5);} + +sub subtract1 { + my @in = @_; + my @temp = map { $_ != 0 ? $_-1 : 0 } @in; + return @temp; +} + +sub subtract_to_max { + my @in = @{$_[0]}; + my $MAX_ = max @in; + my @out = (\@in); + my @temp = @in; + for (1..$MAX_-1) { + @temp = subtract1 @temp; + my @newa = @temp; + unshift @out, \@newa; + } + return @out; +} + + +sub print_A { + my $MAX_ = max @A; + my $i = $MAX_; + for (subtract_to_max(\@A)) { + my @in = @{$_}; + print "$i "; + print join " ", map { $_ != 0 ? "#" : " " } @in; + print "\n"; + $i--; + } + print "_ " for @A; + print "_ \n "; + print join " ", @A; + print "\n"; +} + +sub lrh { + my @histogram = subtract_to_max(\@_); + my $length = scalar @_; + my %areas; + my $MAX_ = max @_; + + for my $i (0..$MAX_-1) { + my $j = 0; + my ($h, $t); #head, tail + while ($j < $length) { + if ($histogram[$i][$j] != 0) { + $h = $j; + for (my $k=$j ; ($k < $length) && ($histogram[$i][$k] != 0) ;$k++) { + $t = $k; + $j++; + } + } + if ( defined($h) && defined($t)) && (!exists $areas{"$h,$t"}) ) { + $areas{"$h,$t"} = ($t-$h+1)*($MAX_-$i); + } + $j++; + + } + } + + return max values %areas; +} + +print_A; +print "\n"; +print lrh(@A); +print "\n"; + +=pod +ok ( lrh(2, 1, 4, 5, 3, 7) == 12 ), "example 1" ; +ok ( lrh(3, 2, 3, 5, 7, 5) == 15 ), "example 2" ; +=cut diff --git a/challenge-075/cheok-yin-fung/python/ch-1.py b/challenge-075/cheok-yin-fung/python/ch-1.py new file mode 100644 index 0000000000..ff0c56a241 --- /dev/null +++ b/challenge-075/cheok-yin-fung/python/ch-1.py |