From 832f991ce7c04c68d6a40279c17b6c2339f7df74 Mon Sep 17 00:00:00 2001 From: Shawn Date: Mon, 17 Aug 2020 05:08:11 -0700 Subject: Add some patterns to .gitignore --- .gitignore | 2 ++ 1 file changed, 2 insertions(+) diff --git a/.gitignore b/.gitignore index 40a0244345..011bc9efd3 100644 --- a/.gitignore +++ b/.gitignore @@ -3,3 +3,5 @@ .DS_Store .vstags .*.swp +*~ +*.class -- cgit From 076f607237207a664b5cbb8b525f1f91a7d43da9 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Tue, 25 Aug 2020 20:03:13 +0800 Subject: use linux terminal instead of web interface --- challenge-075/cheok-yin-fung/java/histogram.class | Bin 0 -> 1020 bytes challenge-075/cheok-yin-fung/java/histogram.java | 47 ++++++++++++ challenge-075/cheok-yin-fung/perl/ch-1.pl | 59 ++++++++++++++ challenge-075/cheok-yin-fung/perl/ch-2.pl | 89 ++++++++++++++++++++++ challenge-075/cheok-yin-fung/python/ch-2.py | 88 +++++++++++++++++++++ 5 files changed, 283 insertions(+) create mode 100644 challenge-075/cheok-yin-fung/java/histogram.class create mode 100644 challenge-075/cheok-yin-fung/java/histogram.java create mode 100644 challenge-075/cheok-yin-fung/perl/ch-1.pl create mode 100644 challenge-075/cheok-yin-fung/perl/ch-2.pl create mode 100644 challenge-075/cheok-yin-fung/python/ch-2.py diff --git a/challenge-075/cheok-yin-fung/java/histogram.class b/challenge-075/cheok-yin-fung/java/histogram.class new file mode 100644 index 0000000000..5c03517559 Binary files /dev/null and b/challenge-075/cheok-yin-fung/java/histogram.class differ 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..78a29565b0 --- /dev/null +++ b/challenge-075/cheok-yin-fung/java/histogram.java @@ -0,0 +1,47 @@ +import java.util.Scanner; + +// not yet produce the "image" of histogram, 25th Aug + +public class histogram { + static public void main(String[] args) { + int maxarea = 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(); + } + 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(maxarea); + + } +} + + +// references: +// 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..53929b0a6e --- /dev/null +++ b/challenge-075/cheok-yin-fung/perl/ch-1.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-1.pl $S @C +use strict; +use warnings; +#use Test::More tests => 3; +use Integer::Partition; + +sub subarray { + 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 (subarray(\@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..1660ce5c18 --- /dev/null +++ b/challenge-075/cheok-yin-fung/perl/ch-2.pl @@ -0,0 +1,89 @@ +#!/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)) { if(!exists $areas{"$h,$t"}) { + $areas{"$h,$t"} = ($t-$h+1)*($MAX_-$i); + # MORE COMMENTS FOR THE FINAL VERSION + # print "line ", $MAX_-$i, ": [$h..$t]", "\n"; + # print " length * $MAX_-$i = ", $areas{"$h,$t"}; + # print "\n"; + }} + $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-2.py b/challenge-075/cheok-yin-fung/python/ch-2.py new file mode 100644 index 0000000000..c255971db0 --- /dev/null +++ b/challenge-075/cheok-yin-fung/python/ch-2.py @@ -0,0 +1,88 @@ +# Python3 +# Perl Weekly Challenge #075 Task 2 Largest Rectangle Histogram , Python script + +# A = [3, 2, 3, 5, 7, 5] +# A = [2, 1, 4, 3, 5, 7] +# A = [1, 2, 3, 4, 5] + + +length = int(input("Enter number of items of the histogram: \n")) +print("Enter items of the histogram with line breaks") +A = [] +for i in range(length): + A.append(int(input())) + +MAX_ = max(A) +#length = len(A) + +def subtract1(n): + if n > 0: + r = n-1 + else: + r = 0 + return r + +temp = A +temp.append(0) # put a zero at the end for ease + +histogram = [] +pair = [] +areas = [] + +for i in range(MAX_): + histogram.append(temp) + temp = list(map(subtract1, temp)) + +histogram = histogram[::-1] + + + +for i in range(MAX_): + j = 0 + while j < length: + if histogram[i][j] != 0: + h = j + k = j + while True: + t = k + j = j+1 + k = k+1 + if histogram[i][k] == 0: + break + if not([h,t] in pair): + areas.append( (t-h+1)*(MAX_-i) ) + pair.append([h,t]) + j = j+1 + histogram[i].pop(-1) #pop out the assisting zero + + +print("Answer:") +print(max(areas)) +print() + +def zeroornumsign(x): + if x > 0: + return "#" + else: + return " " + +def print_A(): + for i in range( MAX_ ): + print(MAX_-i, end=' ') + templine = list(map(zeroornumsign, histogram[i])); + for j in range(length): + print(templine[j], end=' ') + print() + print(' ', end='') + print("_ " * length) + print(' ', end='') + for i in range(length): + print(str(A[i]), end=' ') + print() + +print_A(); + +#references: +#https://www.csestack.org/unique-elements-from-list-in-python/ +#https://coderwall.com/p/q_rd1q/emulate-do-while-loop-in-python +#https://coderwall.com/p/uhskuq/reverse-array-in-python -- cgit From 3560a64821237620d87e517eaab67ca2dd94bb17 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Tue, 25 Aug 2020 23:18:14 +0800 Subject: edit Python codes; thanks data-scientist Clare --- challenge-075/cheok-yin-fung/python/ch-2.py | 130 +++++++++++++--------------- 1 file changed, 60 insertions(+), 70 deletions(-) diff --git a/challenge-075/cheok-yin-fung/python/ch-2.py b/challenge-075/cheok-yin-fung/python/ch-2.py index c255971db0..a13f885563 100644 --- a/challenge-075/cheok-yin-fung/python/ch-2.py +++ b/challenge-075/cheok-yin-fung/python/ch-2.py @@ -1,74 +1,57 @@ # Python3 # Perl Weekly Challenge #075 Task 2 Largest Rectangle Histogram , Python script +# test cases: +# items = [3, 2, 3, 5, 7, 5] --> 15 +# items = [2, 1, 4, 3, 5, 7] --> 12 +# items = [1, 2, 3, 4, 5] --> 9 -# A = [3, 2, 3, 5, 7, 5] -# A = [2, 1, 4, 3, 5, 7] -# A = [1, 2, 3, 4, 5] - - -length = int(input("Enter number of items of the histogram: \n")) -print("Enter items of the histogram with line breaks") -A = [] -for i in range(length): - A.append(int(input())) - -MAX_ = max(A) -#length = len(A) - -def subtract1(n): - if n > 0: - r = n-1 - else: - r = 0 - return r - -temp = A -temp.append(0) # put a zero at the end for ease - -histogram = [] -pair = [] -areas = [] - -for i in range(MAX_): - histogram.append(temp) - temp = list(map(subtract1, temp)) - -histogram = histogram[::-1] - - - -for i in range(MAX_): - j = 0 - while j < length: - if histogram[i][j] != 0: - h = j - k = j - while True: - t = k - j = j+1 - k = k+1 - if histogram[i][k] == 0: - break - if not([h,t] in pair): - areas.append( (t-h+1)*(MAX_-i) ) - pair.append([h,t]) - j = j+1 - histogram[i].pop(-1) #pop out the assisting zero - - -print("Answer:") -print(max(areas)) -print() - -def zeroornumsign(x): - if x > 0: - return "#" - else: - return " " - -def print_A(): - for i in range( MAX_ ): - print(MAX_-i, end=' ') +def largest_rectangle_histogram(items): + max_item = max(items) + + subtract1 = lambda n: n-1 if n > 0 else 0 + + temp = items + temp = temp + [0] # put a zero at the end for ease + + histogram = [] + pair = [] + areas = [] + + for i in range(max_item): + histogram.append(temp) + temp = list(map(subtract1, temp)) + + histogram = histogram[::-1] + + + + for i in range(max_item): + j = 0 + while j < length: + if histogram[i][j] != 0: + h = j + k = j + while True: + t = k + j = j+1 + k = k+1 + if histogram[i][k] == 0: + break + if not([h,t] in pair): + areas.append( (t-h+1)*(max_item-i) ) + pair.append([h,t]) + j = j+1 + histogram[i].pop(-1) #pop out the assisting zero + + + print("Answer:") + print(max(areas)) + print() + + + zeroornumsign = lambda x: "#" if x > 0 else " " + for i in range( max_item ): + print(max_item-i, end=' ') templine = list(map(zeroornumsign, histogram[i])); for j in range(length): print(templine[j], end=' ') @@ -77,10 +60,17 @@ def print_A(): print("_ " * length) print(' ', end='') for i in range(length): - print(str(A[i]), end=' ') + print(str(items[i]), end=' ') print() -print_A(); + +if __name__ == "__main__": + length = int(input("Enter number of items of the histogram: \n")) + print("Enter items of the histogram with line breaks") + items = [] + for i in range(length): + items.append(int(input())) + largest_rectangle_histogram(items) #references: #https://www.csestack.org/unique-elements-from-list-in-python/ -- cgit From e437aee28cebedf938b935550694a5c0ca3ac01c Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 25 Aug 2020 15:56:17 -0400 Subject: perl solution for challenge 75 task 1 first draft --- challenge-075/walt-mankowski/perl/ch-1.pl | 73 +++++++++++++++++++++++++++++++ 1 file changed, 73 insertions(+) create mode 100644 challenge-075/walt-mankowski/perl/ch-1.pl diff --git a/challenge-075/walt-mankowski/perl/ch-1.pl b/challenge-075/walt-mankowski/perl/ch-1.pl new file mode 100644 index 0000000000..556d2fd271 --- /dev/null +++ b/challenge-075/walt-mankowski/perl/ch-1.pl @@ -0,0 +1,73 @@ +#!/usr/bin/env perl +use strict; +use warnings; +use feature qw(:5.32); +use experimental qw(signatures); + +# TASK #1 › Coins Sum +# Submitted by: Mohammad S Anwar +# +# 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. +# Example: +# +# Input: +# @C = (1, 2, 4) +# $S = 6 +# +# Output: 6 +# There are 6 possible ways to make sum 6. +# a) (1, 1, 1, 1, 1, 1) +# b) (1, 1, 1, 1, 2) +# c) (1, 1, 2, 2) +# d) (1, 1, 4) +# e) (2, 2, 2) +# f) (2, 4) + +my $s = shift @ARGV; +my @c = @ARGV; +my @solutions; + +my @cnt = map {0} 0..$#c; +my $i = $#c; +while (1) { + my $val = value(\@c, \@cnt); + if ($val >= $s) { + if ($val == $s) { + my @tmp = @cnt; + push @solutions, \@tmp; + } + + # rotate "odometer" + $cnt[$#c] = 0; + my $j = $#c - 1; + $cnt[$j]++; + while ($j >= 0 && value(\@c, \@cnt) > $s) { + $cnt[$j] = 0; + $j--; + $cnt[$j]++; + } + last if $j < 0; + } else { + $cnt[$#c]++; + } +} + +# print out the solutions +say "There are " . scalar @solutions . " ways to make sum $s"; +for my $sol (@solutions) { + my @tmp; + for my $i (0..$#c) { + push @tmp, $c[$i] for 0..$sol->[$i]-1; + } + say "@tmp"; +} + +sub value($c, $cnt) { + my $sum = 0; + for my $i (0..$#$c) { + $sum += $c->[$i] * $cnt->[$i]; + } + return $sum; +} -- cgit From 2b008e13c55c5684b84b97a432644bdce52b2dac Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Wed, 26 Aug 2020 05:30:53 +0800 Subject: ch-1.py --- challenge-075/cheok-yin-fung/python/ch-1.py | 58 +++++++++++++++++++++++++++++ 1 file changed, 58 insertions(+) create mode 100644 challenge-075/cheok-yin-fung/python/ch-1.py 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..b933614797 --- /dev/null +++ b/challenge-075/cheok-yin-fung/python/ch-1.py @@ -0,0 +1,58 @@ +# Python3 +# Perl Weekly Challenge #075 Task 1 Coins Sum, Python script + +# coins = [1, 2, 3, 5] +# total = 5 +# --> len(arr_for_dp[total]) == 6 + +# coins = [1, 2, 3, 4, 5] +# total = 5 +# --> len(arr_for_dp[total]) == 7 + +def coins_sum(uinput): + userinput = list(uinput).copy() + total = userinput.pop(0) + coins = userinput + dp_range = [] + arr_for_dp = [ [] ] + + for i_ in range(total): + dp_range.append(i_ + 1) + + + j = 0 + for i in dp_range: + if i == coins[j]: + arr_for_dp.append([ [coins[j]] ]) + if j < len(coins)-1: + j = j+1 + else: + arr_for_dp.append([]) + + for i in dp_range: + for k in range(len(coins)): + if (i-coins[k] > 0): + for p in range(len(arr_for_dp[i-coins[k]])): + partition = arr_for_dp[i-coins[k]][p] + partition_p = list(partition).copy() + partition_p.append(coins[k]) + partition_p = sorted(partition_p) + if not(partition_p in arr_for_dp[i]): + arr_for_dp[i].append(list(partition_p).copy()) + + return arr_for_dp[total] + + +if __name__ == "__main__": + target = int(input("Enter the sum: \n")) + urinput = [target] + coins_sum_len = int(input("Enter number of varieties of coins:\n")) + print("Enter the value of coins with line breaks") + for i in range(coins_sum_len): + urinput.append(int(input())) + + ans = coins_sum( urinput ) + print("===================") + for item in ans: + print(item) + print("answer: ", len(ans)) -- cgit From 792214bce5c2858576e91b6e8a8e270c479ae19b Mon Sep 17 00:00:00 2001 From: drbaggy Date: Wed, 26 Aug 2020 00:12:31 +0100 Subject: wk 75 --- challenge-075/james-smith/README.md | 131 +++++------------------------------- challenge-075/james-smith/ch-1.pl | 29 ++++++++ challenge-075/james-smith/ch-2.pl | 34 ++++++++++ 3 files changed, 81 insertions(+), 113 deletions(-) create mode 100644 challenge-075/james-smith/ch-1.pl create mode 100644 challenge-075/james-smith/ch-2.pl diff --git a/challenge-075/james-smith/README.md b/challenge-075/james-smith/README.md index 6d816375c5..54043e40b0 100644 --- a/challenge-075/james-smith/README.md +++ b/challenge-075/james-smith/README.md @@ -1,129 +1,34 @@ Solutions by James Smith. -# Challenge 1 - Counting letters +# Challenge 1 - Coins Sum -There are two ways to solve this -> split and count or using tr... one is short code - one is longer - but much faster. - -## Version 1 - short code - -Uses lc, split and grep to count the elements and put them in a hash... looping through each file a line at a time with <> - -```perl -use feature 'say'; -use strict; -my %T = map { $_=>0 } foreach 'a'..'z'; -while(<>) { - $T{$_}++ foreach grep { /[a-z]/ } split m{}, lc $_; -} - -say "$_: $T{$_}" foreach 'a'..'z'; -``` - -Running this over 13Mbytes of PHP takes approximately 6.5 seconds... - -## Version 2 - faster code - -Now counting letters in a string is quickest using the tr or y operator - as this requires the number of characters -changed. Without using eval you can't unfortunately sub in a variable into the pattern unlike with m/s... So we -either need to use string eval (which is evIl) or manually replicate the loop - $T{'a'} =~ y/aA/aA/ etc - in this -code... Note we set $/ to undef so that we slurp the whole file in in one go (to improve performance of using tr) -and less modifications to the %T hash... +This is just begging for a recursive solution. ```perl -use feature 'say'; -$/=undef; - -while(<>) { - $T{'a'} += y/aA/aA/; - $T{'b'} += y/bB/bB/; -.. -.. - $T{'y'} += y/yY/yY/; - $T{'z'} += y/zZ/zZ/; +sub csm { + my $t = shift; + return @{$mem{"$t @_"}||=[map {my $a=$_; $t==$a?[$a]: + map {[$a,@{$_}]} csm($t-$a,grep {$a<=$_&&$_<=$t} @_)} @_] }; } - -say $_,': ',$T{$_}||0 foreach 'a'..'z'; - -``` -OK - so didn't want to type 26 lines so used this one liner to do it for me! - -```bash -perl -E 'say " \$t{'"'"'$_'"'"'} += y/$_".uc($_)."/$_".uc($_)."/;" foreach "a".."z";' -``` - -This now runs in approxy 0.25 seconds a big improvement... - -## Version 3 - nicer output... - -The version 3 code just expands the version 2 code - but creates a "histogram" to show the distribution (and at the same time formats the totals better) - -``` -a : 584193 : ########################## -b : 108267 : #### -c : 287124 : ############# -d : 272798 : ############ -e : 877936 : ######################################## -f : 209371 : ######### -g : 152944 : ###### -h : 200641 : ######### -i : 546465 : ######################## -j : 15133 : -k : 50049 : ## -l : 326976 : ############## -m : 214631 : ######### -n : 438874 : ################### -o : 436059 : ################### -p : 282120 : ############ -q : 19825 : -r : 551144 : ######################### -s : 552344 : ######################### -t : 724711 : ################################# -u : 260233 : ########### -v : 68882 : ### -w : 80759 : ### -x : 57019 : ## -y : 115201 : ##### -z : 11021 : ``` -# Challenge 2 - multiplication square... +Notes: -Again going to extend the challenge to make this generic (in case someone wants a different version) + * %mem is a memoisation cache as it helps to not need to re-compute higher totals more than once - speeds up searches for large coin sums... not essential but nice to have -Hidden in the solution above was getting the number of digits for a number (so we can format the totals) - we do this again to get the size of the left hand column and the main table columns. +How it works: -```perl -my $sl = int(log($N)/log(10)+1); ## Get size of integer $N - defines the width of the LH column -my $sr = int(2*log($N)/log(10)+1); ## Get size of $N squared - defines the width of other columns -``` -and we use this to tweak the formats and the padding/line drawing elements! -```perl -#!/usr/bin/perl - -use strict; -use feature 'say'; + * Loop through all coin values available + * if the coin is the same as the amount required return a single array containing that value; + * if not remove that from the amount required and call again. For all values returned prepend the coin value to each array in the list + * when calling again remove any coins which are less than the "current coin" and greater than the amount required -## This solves more than the puzzle - but thought I would make it more generic! +Caveats & assumptions: -## This gets the size of the square that we want to display... + * No input checking is performed - assumes the options passed are all valid and greater than 0; -my $N = shift =~ s{\D}{}gr || 11; ## Default to 11 - but use first parameter as size of square! -my @R = 1..$N; ## Create a "range array" - we use this 4 times!!! +# Challenge 2 - Histogram rectangle -## Get width of columns for use in the renderer.. +Much simpler this time. -my $sl = int( log($N) / log(10) + 1); ## Get size of integer $N - defines the width of the LH column -my $sr = int( 2 * log($N) / log(10) + 1); ## Get size of $N squared - defines the width of other columns -my $fl = sprintf ' %%%dd |', $sl; ## Create a template for the first column.. -my $fr = sprintf ' %%%dd', $sr; ## .... and for the other columns! - -## Finally we render - make a use of sprintf with the templates and '$' x $ to generate padding - -say ' ' x $sl, 'x |', ## Header (LH side) - map { sprintf $fr, $_ } @R; ## (column headers) -say join '-', '-' x $sl, '-+', ## Separator (LH side) - map { '-' x $sr } @R; ## (RH side) -say sprintf( $fl, $a=$_ ), ## Body of table (LH headers) - map { $a>$_ ? ' ' x ($sr+1) : sprintf $fr, $a*$_ } @R ## (content of row) - foreach @R; -``` +First we get the size of the box (max value) and render chart then we look for the maximum rectangle size - which is computed as the maximum value of the distance between any two points (inclusive) multiplied by the lowest value in between the two values. (Maxi-min problem) diff --git a/challenge-075/james-smith/ch-1.pl b/challenge-075/james-smith/ch-1.pl new file mode 100644 index 0000000000..08d9c19862 --- /dev/null +++ b/challenge-075/james-smith/ch-1.pl @@ -0,0 +1,29 @@ +use strict; +use warnings; +use feature qw(say); + +my %mem; ## Used to cache results of CSM to speed things up for large cases... + +## Some test cases - example from challenge itself +say q(); +_dump( csm( 6, qw(1 2 4) ) ); +say q(); + +## All the values up to £2 - using standard UK coins +foreach (1..200) { + _dump( csm( $_, qw(1 2 5 10 20 50 100 200) ) ); + say q(); +} + +# The hardwork - use recursion +sub csm { + my $t = shift; + return @{$mem{"$t @_"}||=[map {my $a=$_; $t==$a?[$a]: + map {[$a,@{$_}]} csm($t-$a,grep {$a<=$_&&$_<=$t} @_)} @_] }; +} + +## Support function to dump values; +sub _dump { + say " @{$_}" foreach @_; +} + diff --git a/challenge-075/james-smith/ch-2.pl b/challenge-075/james-smith/ch-2.pl new file mode 100644 index 0000000000..16bca58aa0 --- /dev/null +++ b/challenge-075/james-smith/ch-2.pl @@ -0,0 +1,34 @@ +use strict; +use warnings; +use feature qw(say); + +say q(); +say lrh(qw(2 1 4 5 3 7)); +say q(); +say lrh(qw(3 2 3 5 7 5)); +say q(); + +## Could import max/min - but these are easy to write ourselves in this case.... + +sub lrh { + my @V = @_; + my ($mx,$y) = 0; + $mx = $mx < $_ ? $_ : $mx foreach @V; +## The following chunk renders the histogram as requested... +## Render output as table.... + say sprintf( ' %2d', $y=$_ ), map { $_ < $y ? q( ) : q( #) } @V foreach reverse 1..$mx; + say q( --), map { q( --) } @V; + say q( ), map { sprintf ' %2d', $_ } @V; + say q(); + +## Now do the calculation of mx area + my $mx_area = 0; + foreach my $s ( 0 .. @V-1 ) { ## Loop through each start of block... + my $mn = $mx; + foreach ( $s .. @V-1 ) { + $mn = $V[$_] if $mn > $V[$_]; ## Loop through ends, keeping track of minimum value + $mx_area = $mn * ($_-$s+1) if $mx_area < $mn * ($_-$s+1); ## And check to see if the area is greater than any other area! + } + } + return $mx_area; +} -- cgit From adc3b4ab064e604f1e7d360e8ff3ad152dfaaa37 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Wed, 26 Aug 2020 09:51:25 +0800 Subject: Java for Task 1 and clean up ch-2.pl --- challenge-075/cheok-yin-fung/java/coinssum.class | Bin 0 -> 1764 bytes challenge-075/cheok-yin-fung/java/coinssum.java | 90 +++++++++++++++++++++++ challenge-075/cheok-yin-fung/perl/ch-2.pl | 8 +- 3 files changed, 92 insertions(+), 6 deletions(-) create mode 100644 challenge-075/cheok-yin-fung/java/coinssum.class create mode 100644 challenge-075/cheok-yin-fung/java/coinssum.java diff --git a/challenge-075/cheok-yin-fung/java/coinssum.class b/challenge-075/cheok-yin-fung/java/coinssum.class new file mode 100644 index 0000000000..ed67045e6a Binary files /dev/null and b/challenge-075/cheok-yin-fung/java/coinssum.class differ 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..23a408fe5a --- /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(); + } + + + + ArrayList[] arr_for_dp = new ArrayList[total+1]; + + int j = 0; + for (int i=0; i <= total; i++) { + arr_for_dp[i] = new ArrayList(); + 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(); + 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 Date: Tue, 25 Aug 2020 22:00:23 -0400 Subject: perl solution for challenge 75 task 2 first draft --- challenge-075/walt-mankowski/perl/ch-2.pl | 107 ++++++++++++++++++++++++++++++ 1 file changed, 107 insertions(+) create mode 100644 challenge-075/walt-mankowski/perl/ch-2.pl diff --git a/challenge-075/walt-mankowski/perl/ch-2.pl b/challenge-075/walt-mankowski/perl/ch-2.pl new file mode 100644 index 0000000000..a64a8aa018 --- /dev/null +++ b/challenge-075/walt-mankowski/perl/ch-2.pl @@ -0,0 +1,107 @@ +#!/usr/bin/env perl +use strict; +use warnings; +use feature qw(:5.32); +use experimental qw(signatures); +use List::Util qw(max sum); + +# TASK #2 › Largest Rectangle Histogram +# Submitted by: Mohammad S Anwar +# +# You are given an array of positive numbers @A. +# +# Write a script to find the larget rectangle histogram created by the given array. +# BONUS: Try to print the histogram as shown in the example, if possible. +# +# Example 1: +# +# Input: @A = (2, 1, 4, 5, 3, 7) +# +# 7 # +# 6 # +# 5 # # +# 4 # # # +# 3 # # # # +# 2 # # # # # +# 1 # # # # # # +# _ _ _ _ _ _ _ +# 2 1 4 5 3 7 +# +# Looking at the above histogram, the largest rectangle (4 x 3) is formed by columns (4, 5, 3 and 7). +# Output: 12 +# +# Example 2: +# +# Input: @A = (3, 2, 3, 5, 7, 5) +# +# 7 # +# 6 # +# 5 # # # +# 4 # # # +# 3 # # # # # +# 2 # # # # # # +# 1 # # # # # # +# _ _ _ _ _ _ _ +# 3 2 3 5 7 5 +# +# Looking at the above histogram, the largest rectangle (3 x 5) is formed by columns (5, 7 and 5). +# Output: 15 + +my @a = @ARGV; + +# build the histogram +my $rows = max(@a); +my $cols = @a; +my @hist; +for my $col (0..$#a) { + for my $row (0..$rows-1) { + $hist[$row][$col] = $row < $a[$col] ? 1 : 0; + } +} + +print_hist(\@hist, \@a, $rows, $cols); + +my $best_area = 0; +my $best_height = -1; +my $best_width = -1; + +for my $height (1..$rows) { + for my $width (1..$cols) { + my $area = $height * $width; + next if $area <= $best_area; + for my $r0 (0..$rows-$height) { + for my $c0 (0..$cols-$width) { + my $sum = 0; + for my $r ($r0..$r0+$height-1) { + $sum += sum($hist[$r]->@[$c0..$c0+$width-1]); + } + if ($sum == $area) { + $best_area = $area; + $best_height = $height; + $best_width = $width; + } + } + } + } +} + +say "The best rectangle is $best_height x $best_width for an area of $best_area"; + +sub print_hist($hist, $a, $rows, $cols) { + for (my $row = $rows-1; $row >= 0; $row--) { + printf "%d", $row+1; + for my $col (0..$cols-1) { + printf " %s", $hist[$row][$col] ? '#' : ' '; + } + print "\n"; + } + + print "-"; + print " -" for 0..$cols-1; + print "\n"; + + print " "; + printf " %d", $a[$_] for 0..$cols-1; + print "\n\n"; +} + -- cgit From 9d7d3140219f3ad3e3b9ca36f71e2518525eb721 Mon Sep 17 00:00:00 2001 From: wambash Date: Wed, 26 Aug 2020 11:37:47 +0200 Subject: Solution challenge 075 in progress --- challenge-075/wambash/raku/ch-1.raku | 69 ++++++++++++++++++++++++++++++++++++ challenge-075/wambash/raku/ch-2.raku | 18 ++++++++++ 2 files changed, 87 insertions(+) create mode 100644 challenge-075/wambash/raku/ch-1.raku create mode 100644 challenge-075/wambash/raku/ch-2.raku diff --git a/challenge-075/wambash/raku/ch-1.raku b/challenge-075/wambash/raku/ch-1.raku new file mode 100644 index 0000000000..a21cc910f4 --- /dev/null +++ b/challenge-075/wambash/raku/ch-1.raku @@ -0,0 +1,69 @@ +use v6; + +class Attempt { + has @.coins; + has @.using; + has $.sum; +} + + +multi iter (Capture $c where *. == 0) { + $c, +} + +multi iter (Capture $c (:@coins,:$sum where * ≥ 0, :$used = bag()) ) { + \(|$c, sum => $sum-@coins.head, used => $used (+) @coins.head), + \(|$c, coins => @coins.skip), +} + + +multi iter (@a) { + @a + andthen .map: |*.&iter + andthen .grep: *..so + andthen .grep: *. ≥ 0 +} + +multi coins-sum (|c where *. == 0 --> Empty) {} +multi coins-sum (|c ) { + my $deep-to-sums-are-zero =c./c..min + c..elems; + (c,), *.&iter ... * + andthen .skip($deep-to-sums-are-zero) + andthen .head; + + #or this one, but it needs cache + #(c,), *.&iter.cache ... *.all. == 0 + #andthen .tail +} + +sub coins-sum-count ( :@coins!, :$sum! ) { + 0 xx *, + -> $a { + my $k=@coins[$++]; + |$a[^$k], $a[$k]+1, { @_[(++$)] + $a[($k+ ++$)] } ... * + } ... * + andthen .[@coins.elems;$sum] +} + +multi MAIN ( :$test!, :$log ) { + use Test; + + my $wi = &iter.wrap: -> $_ { + note .,.,..kxxv when Capture; + callsame() + } if $log; + + is coins-sum(:coins(1,2,4),:6sum).elems,6; + is-deeply coins-sum(:coins(1,13), :26sum).map( *.), ((1=>26).Bag, (13,1=>13).Bag, (13=>2).Bag); + $wi.restore() if $log; + ; + is coins-sum-count(:coins(1,2,4),:6sum) ,6; + is coins-sum-count(:coins(1,2,4,5),:120sum),8333; + for ^10 { + my @coins= (1..20).pick(3); + my $sum = ^100 .roll; + my $count = coins-sum-count(:@coins,:$sum); + is coins-sum(:@coins,:$sum).elems, $count, "elems = count = $count :{:@coins} :{:$sum}"; + } + done-testing(); +} diff --git a/challenge-075/wambash/raku/ch-2.raku b/challenge-075/wambash/raku/ch-2.raku new file mode 100644 index 0000000000..b5baea0626 --- /dev/null +++ b/challenge-075/wambash/raku/ch-2.raku @@ -0,0 +1,18 @@ +use v6; + +sub largest-rectangle-histogram (+@a) { + @a, *.skip ...^ :!elems + andthen .map: { + $_.cache + andthen [\min] $_ + andthen 1..* Z* $_ + andthen .max + } andthen .max +} + +sub MAIN (:$test!) { + use Test; + is largest-rectangle-histogram( 2, 1, 4, 5, 3, 7 ), 12; + is largest-rectangle-histogram( 3, 2, 3, 5, 7, 5 ), 15; + done-testing(); +} -- cgit From 196b6c270e7f0bbe188c40093451fca3dd52c57e Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Wed, 26 Aug 2020 09:15:54 -0400 Subject: python solution for challenge 75 task 1 first draft --- challenge-075/walt-mankowski/python/ch-1.py | 36 +++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100644 challenge-075/walt-mankowski/python/ch-1.py diff --git a/challenge-075/walt-mankowski/python/ch-1.py b/challenge-075/walt-mankowski/python/ch-1.py new file mode 100644 index 0000000000..b070bcb102 --- /dev/null +++ b/challenge-075/walt-mankowski/python/ch-1.py @@ -0,0 +1,36 @@ +from sys import argv +from copy import deepcopy +import numpy as np + +s = int(argv[1]) +c = np.array([int(x) for x in argv[2:]]) +solutions = [] + +cnt = np.array([0 for _ in range(len(c))]) +while (True): + val = np.dot(c, cnt) + if val >= s: + if val == s: + solutions.append(deepcopy(cnt)) + + # rotate "odometer" + cnt[-1] = 0 + j = -2 + cnt[j] += 1 + while j >= -len(cnt) and np.dot(c, cnt) > s: + cnt[j] = 0 + j -= 1 + if j >= -len(cnt): + cnt[j] += 1 + + if j < -len(cnt): + break + else: + cnt[-1] += 1 + +print("There are", len(solutions), "ways to make sum", s) +for sol in solutions: + tmp = [] + for i in range(len(c)): + tmp += [c[i] for _ in range (sol[i])] + print(tmp) -- cgit From adca3826177366da2dee60b9af3a703949b9a747 Mon Sep 17 00:00:00 2001 From: Alex Mauney Date: Wed, 26 Aug 2020 08:46:22 -0700 Subject: Submit solutions --- challenge-075/mathmauney/README | 1 + challenge-075/mathmauney/perl/ch-1.pl | 65 +++++++++++++++++++++++++++++++++++ challenge-075/mathmauney/perl/ch-2.pl | 36 +++++++++++++++++++ 3 files changed, 102 insertions(+) create mode 100644 challenge-075/mathmauney/README create mode 100644 challenge-075/mathmauney/perl/ch-1.pl create mode 100644 challenge-075/mathmauney/perl/ch-2.pl diff --git a/challenge-075/mathmauney/README b/challenge-075/mathmauney/README new file mode 100644 index 0000000000..9856a99b57 --- /dev/null +++ b/challenge-075/mathmauney/README @@ -0,0 +1 @@ +Solution by Alex Mauney (@mathmauney) diff --git a/challenge-075/mathmauney/perl/ch-1.pl b/challenge-075/mathmauney/perl/ch-1.pl new file mode 100644 index 0000000000..95498c6c71 --- /dev/null +++ b/challenge-075/mathmauney/perl/ch-1.pl @@ -0,0 +1,65 @@ +#Tries to solve https://perlweeklychallenge.org/blog/perl-weekly-challenge-075/ as perl coding practice. + +use strict; +use warnings; +use feature qw(say); +use utf8; +use Getopt::Long; +use List::Util qw(sum first max min); +use Data::Dumper; + +my $target; +my @coins; + +GetOptions("target=i", \$target, + "coins=i{1,}" ,\@coins); + +@coins = sort @coins; +my @test_array = ($coins[0]) x 1; + +my $running = 1; +my $solutions = 0; +while ($running) { + if (sum(@test_array) == $target) { + say @test_array; + ++$solutions; + } + if (max(@test_array) == min(@coins) and sum(@test_array) >= $target) { + $running = 0; + } + @test_array = increment_array(@test_array); +} +say $solutions; + +sub increment_array { + my @tarray = @_; + my $running = 1; + my $i = 0; + my $max_idx = scalar @coins - 1; + while ($running) { + my $idx; + $idx = first { $coins[$_] == $tarray[$i] } 0..$#coins; + if ($idx < $max_idx) { + $tarray[$i] = $coins[$idx+1]; + $running = 0; + } elsif ($i+1 == scalar @tarray){ + push @tarray, 1; + @tarray = ($coins[0]) x @tarray; + $running = 0; + } else { + $tarray[$i] = $coins[0]; + } + ++$i; + if ($running == 0) { + my $max = scalar @tarray; + foreach (0..$max-2) { + if ($tarray[$_] < $tarray[$_+1]) { + $i = 0; + $running =1; + last; + } + } + } + } + return @tarray; +} diff --git a/challenge-075/mathmauney/perl/ch-2.pl b/challenge-075/mathmauney/perl/ch-2.pl new file mode 100644 index 0000000000..1f2c8cfe78 --- /dev/null +++ b/challenge-075/mathmauney/perl/ch-2.pl @@ -0,0 +1,36 @@ +#Tries to solve https://perlweeklychallenge.org/blog/perl-weekly-challenge-075/ as perl coding practice. + +use strict; +use warnings; +use feature qw(say); +use utf8; +use Getopt::Long; +use List::Util qw(sum first max min); +use Data::Dumper; + +my @hist; + +GetOptions("histogram=i{1,}", \@hist); + +my $count = 1; +my $max = 0; + +while (max(@hist) > 0) { + my @positives = map {$_ > 0} @hist; + my $l = 0; + my $maxl =0; + foreach (@positives) { + if ($_) { + ++$l; + } else { + $maxl = $l if $l > $maxl; + $l = 0; + } + } + $maxl = $l if $l > $maxl; + my $rect = $maxl * $count; + $max = $rect if $rect > $max; + @hist = map {$_ - 1} @hist; + ++$count +} +say $max; -- cgit From 730915136413554ad43fbfc9d7e4f766291a4ec0 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Wed, 26 Aug 2020 14:35:58 -0400 Subject: python solution for challenge 75 task 2 first draft --- challenge-075/walt-mankowski/python/ch-2.py | 49 +++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) create mode 100644 challenge-075/walt-mankowski/python/ch-2.py diff --git a/challenge-075/walt-mankowski/python/ch-2.py b/challenge-075/walt-mankowski/python/ch-2.py new file mode 100644 index 0000000000..efd720f539 --- /dev/null +++ b/challenge-075/walt-mankowski/python/ch-2.py @@ -0,0 +1,49 @@ +from sys import argv +import numpy as np + +def print_hist(hist, a, rows, cols): + for row in range(rows-1, -1, -1): + print(row+1, end='') + for col in range(cols): + print(f" {'#' if hist[row][col] == 1 else ' '}", end='') + print() + + print('-', end='') + print(" -" * cols) + + print(' ', end='') + for i in range(cols): + print(f' {a[i]}', end='') + print() + print() + +a = [int(x) for x in argv[1:]] + +# build the histogram +rows = max(a) +cols = len(a) +hist = np.zeros([rows, cols]) +for row in range(rows): + for col in range(cols): + if row < a[col]: + hist[row][col] = 1 +print_hist(hist, a, rows, cols) + +best_area = 0 +best_height = -1 +best_width = -1 + +for height in range(1, rows+1): + for width in range(1, cols+1): + area = height * width + if area <= best_area: + continue + for r0 in range(row-height+1): + for c0 in range(0, cols-width+1): + if sum(sum(hist[r0:r0+height,c0:c0+width])) == area: + best_area = area + best_height = height + best_width = width + +print(f'The best rectangle is {best_height} x {best_width} for an aea of {best_area}.') + -- cgit From 59f42083ee3c1c04bf9db831430d5b9d94c446a2 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Wed, 26 Aug 2020 14:45:02 -0400 Subject: use dtype of bool for the histogram --- challenge-075/walt-mankowski/python/ch-2.py | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/challenge-075/walt-mankowski/python/ch-2.py b/challenge-075/walt-mankowski/python/ch-2.py index efd720f539..fb8d13b9c3 100644 --- a/challenge-075/walt-mankowski/python/ch-2.py +++ b/challenge-075/walt-mankowski/python/ch-2.py @@ -5,7 +5,7 @@ def print_hist(hist, a, rows, cols): for row in range(rows-1, -1, -1): print(row+1, end='') for col in range(cols): - print(f" {'#' if hist[row][col] == 1 else ' '}", end='') + print(f" {'#' if hist[row][col] else ' '}", end='') print() print('-', end='') @@ -22,11 +22,11 @@ a = [int(x) for x in argv[1:]] # build the histogram rows = max(a) cols = len(a) -hist = np.zeros([rows, cols]) +hist = np.zeros([rows, cols], dtype=bool) for row in range(rows): for col in range(cols): if row < a[col]: - hist[row][col] = 1 + hist[row][col] = True print_hist(hist, a, rows, cols) best_area = 0 -- cgit From af2739515a0a2fb09b3a6601b539c80bc1a10914 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Thu, 27 Aug 2020 03:50:04 +0800 Subject: edit ch-1.py by advice from friend; complete histogram.java --- challenge-075/cheok-yin-fung/java/histogram.class | Bin 1020 -> 1852 bytes challenge-075/cheok-yin-fung/java/histogram.java | 37 ++++++++++++++++++++-- challenge-075/cheok-yin-fung/python/ch-1.py | 20 ++++++------ 3 files changed, 43 insertions(+), 14 deletions(-) diff --git a/challenge-075/cheok-yin-fung/java/histogram.class b/challenge-075/cheok-yin-fung/java/histogram.class index 5c03517559..83eefe0814 100644 Binary files a/challenge-075/cheok-yin-fung/java/histogram.class and b/challenge-075/cheok-yin-fung/java/histogram.class differ diff --git a/challenge-075/cheok-yin-fung/java/histogram.java b/challenge-075/cheok-yin-fung/java/histogram.java index 78a29565b0..cd5c66d844 100644 --- a/challenge-075/cheok-yin-fung/java/histogram.java +++ b/challenge-075/cheok-yin-fung/java/histogram.java @@ -1,10 +1,9 @@ import java.util.Scanner; -// not yet produce the "image" of histogram, 25th Aug - 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}; @@ -15,6 +14,9 @@ public class histogram { 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++) { @@ -36,12 +38,41 @@ public class histogram { } } } - System.out.println(maxarea); + + 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/python/ch-1.py b/challenge-075/cheok-yin-fung/python/ch-1.py index b933614797..b38387f019 100644 --- a/challenge-075/cheok-yin-fung/python/ch-1.py +++ b/challenge-075/cheok-yin-fung/python/ch-1.py @@ -10,15 +10,14 @@ # --> len(arr_for_dp[total]) == 7 def coins_sum(uinput): - userinput = list(uinput).copy() + userinput = uinput total = userinput.pop(0) coins = userinput dp_range = [] arr_for_dp = [ [] ] - for i_ in range(total): - dp_range.append(i_ + 1) - + dp_range = list((range(1,total+1))) + print(dp_range) j = 0 for i in dp_range: @@ -34,23 +33,22 @@ def coins_sum(uinput): if (i-coins[k] > 0): for p in range(len(arr_for_dp[i-coins[k]])): partition = arr_for_dp[i-coins[k]][p] - partition_p = list(partition).copy() + partition_p = partition.copy() partition_p.append(coins[k]) partition_p = sorted(partition_p) if not(partition_p in arr_for_dp[i]): - arr_for_dp[i].append(list(partition_p).copy()) + arr_for_dp[i].append(partition_p.copy()) return arr_for_dp[total] if __name__ == "__main__": + urinput = []; target = int(input("Enter the sum: \n")) - urinput = [target] - coins_sum_len = int(input("Enter number of varieties of coins:\n")) - print("Enter the value of coins with line breaks") - for i in range(coins_sum_len): - urinput.append(int(input())) + set_of_coins = [int(x) for x in input("Enter the value of coins with spaces seperated:\n").split()] + urinput = [target] + set_of_coins; + print(urinput) ans = coins_sum( urinput ) print("===================") for item in ans: -- cgit From 34c250bacdfc6630633488cdd0fa25132cbe03ab Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Fri, 21 Aug 2020 15:51:04 -0700 Subject: rename source files in c74 Clojure filenames must use underscores; dashes are not allowed. Add a symlink so that the expected convention (using dashes) leads people to the right place. --- .../tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj | 21 +------------ .../tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj | 34 +--------------------- .../tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj | 20 +++++++++++++ .../tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj | 33 +++++++++++++++++++++ 4 files changed, 55 insertions(+), 53 deletions(-) mode change 100644 => 120000 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj mode change 100644 => 120000 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj create mode 100644 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj create mode 100644 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj deleted file mode 100644 index 416d2a1d85..0000000000 --- a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj +++ /dev/null @@ -1,20 +0,0 @@ -(ns tw.weekly.ch-1) - -(defn majority - "Calculate the majority element, which is the element in a list that appears more than floor(size_of_list/2), prefering the least significant digit that matches that criteria. Returns -1 if no such element is found." - [coll] - (let [minimum (Math/floor (/ (count coll) 2)) - maj (->> coll - frequencies - (filter (comp #(> % minimum) second)) - (sort second) - ffirst)] - (or maj -1))) - -(defn -main - "Run Task 1 with a list of integers, defaulting to the sample given in the task description." - [& args] - (let [N (if (not-empty args) - (map clojure.edn/read-string args) - [2, 2, 2, 3, 2, 4, 2])] - (println (majority N)))) diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj new file mode 120000 index 0000000000..924a7a086e --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj @@ -0,0 +1 @@ +ch_1.clj \ No newline at end of file diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj deleted file mode 100644 index 299ab63690..0000000000 --- a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj +++ /dev/null @@ -1,33 +0,0 @@ -(ns tw.weekly.ch-2 - (:require [clojure.string :as str]) - (:require [flatland.ordered.map :as fo])) - -(defn ordered-frequencies - "A modification of clojure.core/frequencies that guarantees the map returns keys in the order seen in the collection. Thus it returns an ordered map from distinct items in coll to the number of times they appear." - [coll] - (persistent! - (reduce (fn [counts x] - (assoc! counts x (inc (get counts x 0)))) - (transient (fo/ordered-map)) coll))) - -(defn find-fnr [string] - "Find the first non-repeating character (FNR) for a string." - (let [counts (ordered-frequencies string) - non-repeaters (filter (comp #(= 1 %) second) counts)] - (-> non-repeaters last first))) - -(defn find-fnr-over-string - "Generate a string comprised of the first non-repeating character (FNR) for successive substrings of a given string." - [string] - (->> string - (reductions str "") - (drop 1) - (map find-fnr) - (map #(or % \#)) - str/join)) - -(defn -main - "Run Task 2 with a string, defaulting to the sample given in the task description." - [& args] - (let [S (or (-> args first) "ababc")] - (println (find-fnr-over-string S)))) diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj new file mode 120000 index 0000000000..5a32e17ef9 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj @@ -0,0 +1 @@ +ch_2.clj \ No newline at end of file diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj new file mode 100644 index 0000000000..416d2a1d85 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj @@ -0,0 +1,20 @@ +(ns tw.weekly.ch-1) + +(defn majority + "Calculate the majority element, which is the element in a list that appears more than floor(size_of_list/2), prefering the least significant digit that matches that criteria. Returns -1 if no such element is found." + [coll] + (let [minimum (Math/floor (/ (count coll) 2)) + maj (->> coll + frequencies + (filter (comp #(> % minimum) second)) + (sort second) + ffirst)] + (or maj -1))) + +(defn -main + "Run Task 1 with a list of integers, defaulting to the sample given in the task description." + [& args] + (let [N (if (not-empty args) + (map clojure.edn/read-string args) + [2, 2, 2, 3, 2, 4, 2])] + (println (majority N)))) diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj new file mode 100644 index 0000000000..299ab63690 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj @@ -0,0 +1,33 @@ +(ns tw.weekly.ch-2 + (:require [clojure.string :as str]) + (:require [flatland.ordered.map :as fo])) + +(defn ordered-frequencies + "A modification of clojure.core/frequencies that guarantees the map returns keys in the order seen in the collection. Thus it returns an ordered map from distinct items in coll to the number of times they appear." + [coll] + (persistent! + (reduce (fn [counts x] + (assoc! counts x (inc (get counts x 0)))) + (transient (fo/ordered-map)) coll))) + +(defn find-fnr [string] + "Find the first non-repeating character (FNR) for a string." + (let [counts (ordered-frequencies string) + non-repeaters (filter (comp #(= 1 %) second) counts)] + (-> non-repeaters last first))) + +(defn find-fnr-over-string + "Generate a string comprised of the first non-repeating character (FNR) for successive substrings of a given string." + [string] + (->> string + (reductions str "") + (drop 1) + (map find-fnr) + (map #(or % \#)) + str/join)) + +(defn -main + "Run Task 2 with a string, defaulting to the sample given in the task description." + [& args] + (let [S (or (-> args first) "ababc")] + (println (find-fnr-over-string S)))) -- cgit From cc17c4c8a86f7530ed9b853afc1d9bd8600e6e7b Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Mon, 24 Aug 2020 11:33:38 -0700 Subject: initial commit for c75 --- challenge-075/tyler-wardhaugh/clojure/LICENSE | 214 +++++++++++++++++++++ challenge-075/tyler-wardhaugh/clojure/README.md | 37 ++++ challenge-075/tyler-wardhaugh/clojure/deps.edn | 14 ++ challenge-075/tyler-wardhaugh/clojure/pom.xml | 39 ++++ .../tyler-wardhaugh/clojure/src/tw/weekly/c75.clj | 12 ++ .../tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj | 1 + .../tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj | 1 + .../tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj | 20 ++ .../tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj | 33 ++++ .../clojure/test/tw/weekly/c75_test.clj | 14 ++ 10 files changed, 385 insertions(+) create mode 100644 challenge-075/tyler-wardhaugh/clojure/LICENSE create mode 100644 challenge-075/tyler-wardhaugh/clojure/README.md create mode 100644 challenge-075/tyler-wardhaugh/clojure/deps.edn create mode 100644 challenge-075/tyler-wardhaugh/clojure/pom.xml create mode 100644 challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/c75.clj create mode 120000 challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj create mode 120000 challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj create mode 100644 challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj create mode 100644 challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj create mode 100644 challenge-075/tyler-wardhaugh/clojure/test/tw/weekly/c75_test.clj diff --git a/challenge-075/tyler-wardhaugh/clojure/LICENSE b/challenge-075/tyler-wardhaugh/clojure/LICENSE new file mode 100644 index 0000000000..7689f30efd --- /dev/null +++ b/challenge-075/tyler-wardhaugh/clojure/LICENSE @@ -0,0 +1,214 @@ +THE ACCOMPANYING PROGRAM IS PROVIDED UNDER THE TERMS OF THIS ECLIPSE PUBLIC +LICENSE ("AGREEMENT"). ANY USE, REPRODUCTION OR DISTRIBUTION OF THE PROGRAM +CONSTITUTES RECIPIENT'S ACCEPTANCE OF THIS AGREEMENT. + +1. DEFINITIONS + +"Contribution" means: + +a) in the case of the initial Contributor, the initial code and +documentation distributed under this Agreement, and + +b) in the case of each subsequent Contributor: + +i) changes to the Program, and + +ii) additions to the Program; + +where such changes and/or additions to the Program originate from and are +distributed by that particular Contributor. A Contribution 'originates' from +a Contributor if it was added to the Program by such Contributor itself or +anyone acting on such Contributor's behalf. Contributions do not include +additions to the Program which: (i) are separate modules of software +distributed in conjunction with the Program under their own license +agreement, and (ii) are not derivative works of the Program. + +"Contributor" means any person or entity that distributes the Program. + +"Licensed Patents" mean patent claims licensable by a Contributor which are +necessarily infringed by the use or sale of its Contribution alone or when +combined with the Program. + +"Program" means the Contributions distributed in accordance with this +Agreement. + +"Recipient" means anyone who receives the Program under this Agreement, +including all Contributors. + +2. GRANT OF RIGHTS + +a) Subject to the terms of this Agreement, each Contributor hereby grants +Recipient a non-exclusive, worldwide, royalty-free copyright license to +reproduce, prepare derivative works of, publicly display, publicly perform, +distribute and sublicense the Contribution of such Contributor, if any, and +such derivative works, in source code and object code form. + +b) Subject to the terms of this Agreement, each Contributor hereby grants +Recipient a non-exclusive, worldwide, royalty-free patent license under +Licensed Patents to make, use, sell, offer to sell, import and otherwise +transfer the Contribution of such Contributor, if any, in source code and +object code form. This patent license shall apply to the combination of the +Contribution and the Program if, at the time the Contribution is added by the +Contributor, such addition of the Contribution causes such combination to be +covered by the Licensed Patents. The patent license shall not apply to any +other combinations which include the Contribution. No hardware per se is +licensed hereunder. + +c) Recipient understands that although each Contributor grants the licenses +to its Contributions set forth herein, no assurances are provided by any +Contributor that the Program does not infringe the patent or other +intellectual property rights of any other entity. Each Contributor disclaims +any liability to Recipient for claims brought by any other entity based on +infringement of intellectual property rights or otherwise. As a condition to +exercising the rights and licenses granted hereunder, each Recipient hereby +assumes sole responsibility to secure any other intellectual property rights +needed, if any. For example, if a third party patent license is required to +allow Recipient to distribute the Program, it is Recipient's responsibility +to acquire that license before distributing the Program. + +d) Each Contributor represents that to its knowledge it has sufficient +copyright rights in its Contribution, if any, to grant the copyright license +set forth in this Agreement. + +3. REQUIREMENTS + +A Contributor may choose to distribute the Program in object code form under +its own license agreement, provided that: + +a) it complies with the terms and conditions of this Agreement; and + +b) its license agreement: + +i) effectively disclaims on behalf of all Contributors all warranties and +conditions, express and implied, including warranties or conditions of title +and non-infringement, and implied warranties or conditions of merchantability +and fitness for a particular purpose; + +ii) effectively excludes on behalf of all Contributors all liability for +damages, including direct, indirect, special, incidental and consequential +damages, such as lost profits; + +iii) states that any provisions which differ from this Agreement are offered +by that Contributor alone and not by any other party; and + +iv) states that source code for the Program is available from such +Contributor, and informs licensees how to obtain it in a reasonable manner on +or through a medium customarily used for software exchange. + +When the Program is made available in source code form: + +a) it must be made available under this Agreement; and + +b) a copy of this Agreement must be included with each copy of the Program. + +Contributors may not remove or alter any copyright notices contained within +the Program. + +Each Contributor must identify itself as the originator of its Contribution, +if any, in a manner that reasonably allows subsequent Recipients to identify +the originator of the Contribution. + +4. COMMERCIAL DISTR