Merge pull request #2166 from E7-87-83/master

Cheok-Yin's submission for Challenge #075

11 files changed, 595 insertions, 0 deletions

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
new 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
new 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
@@ -0,0 +1,54 @@
+# Python3
+# Perl Weekly Challenge #075 Task 1 Coins Sum, Python script
+# 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.
+
+def coins_sum(uinput):
+    userinput = uinput
+    total = userinput.pop(0)
+    coins = userinput
+    dp_range = []
+    arr_for_dp = [ [] ]
+
+    dp_range = list((range(1,total+1)))
+
+#initialize the array for dynamic programming
+    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 = 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(partition_p.copy())
+
+    #return answer
+    return arr_for_dp[total]
+
+
+if __name__ == "__main__":
+    urinput = [];
+    target = int(input("Enter the sum: \n"))
+    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:
+        print(item)
+    print("answer: ", len(ans))
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..dcf7af2c54
--- /dev/null
+++ b/challenge-075/cheok-yin-fung/python/ch-2.py
@@ -0,0 +1,77 @@
+# 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
+
+def largest_rectangle_histogram(items):
+    max_item = max(items)
+
+    subtract1 = lambda n: n-1 if n > 0 else 0
+
+    temp = items + [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=' ')        
+        print()
+    print('  ', end='')
+    print("_ " * length)
+    print('  ', end='')
+    for i in range(length):
+        print(str(items[i]), end=' ')
+    print()
+
+
+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/
+#https://coderwall.com/p/q_rd1q/emulate-do-while-loop-in-python
+#https://coderwall.com/p/uhskuq/reverse-array-in-python