add blog, lisp solution and comments in code

8 files changed, 199 insertions, 51 deletions

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
index ed67045e6a..674b401cb4 100644
--- a/challenge-075/cheok-yin-fung/java/coinssum.class
+++ 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
index 23a408fe5a..99856867fe 100644
--- a/challenge-075/cheok-yin-fung/java/coinssum.java
+++ b/challenge-075/cheok-yin-fung/java/coinssum.java
@@ -5,7 +5,6 @@
 // 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;
@@ -29,7 +28,7 @@ public class coinssum {
         }
 
 
-
+// initialize the "ArrayList" for dynamic programming
         ArrayList<Vector>[] arr_for_dp = new ArrayList[total+1];
 
         int j = 0;
@@ -88,3 +87,4 @@ public class coinssum {
 //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/perl/ch-1.pl b/challenge-075/cheok-yin-fung/perl/ch-1.pl
index 53929b0a6e..ec5ed93822 100644
--- a/challenge-075/cheok-yin-fung/perl/ch-1.pl
+++ b/challenge-075/cheok-yin-fung/perl/ch-1.pl
@@ -5,55 +5,86 @@
 # 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
+# Usage: ch-1a.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++;
+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 $ans; 
+    return $tf_found;
 }
 
-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";
+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 "\n";
-    return scalar @out;
-}
 
-my $S;
-my @C;
+    #print the combinations of coins
+    for my $partition (@{$arr_for_dp[$total]}) {
+        print join " ", @{$partition};
+        print "\n";
+    }
 
-if ($ARGV[1]) {$S = shift @ARGV; @C = @ARGV;} else {$S = 3; @C = (1,2);}
+    print "\n";
+    #return answer
+    return scalar @{$arr_for_dp[$total]};
+}
 
-print "total number of ways: ", main($S, @C);
+print "total number of ways: ", coins_sum($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";
+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/pwc075ch-1.html b/challenge-075/cheok-yin-fung/perl/pwc075ch-1.html
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/challenge-075/cheok-yin-fung/perl/pwc075ch-1.html
diff --git a/challenge-075/cheok-yin-fung/python/ch-1.py b/challenge-075/cheok-yin-fung/python/ch-1.py
index b38387f019..ff0c56a241 100644
--- a/challenge-075/cheok-yin-fung/python/ch-1.py
+++ b/challenge-075/cheok-yin-fung/python/ch-1.py
@@ -1,13 +1,10 @@
 # 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
+# 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
@@ -17,8 +14,8 @@ def coins_sum(uinput):
     arr_for_dp = [ [] ]
 
     dp_range = list((range(1,total+1)))
-    print(dp_range)
 
+#initialize the array for dynamic programming
     j = 0
     for i in dp_range:
         if i == coins[j]:
@@ -39,6 +36,7 @@ def coins_sum(uinput):
                     if not(partition_p in arr_for_dp[i]):
                         arr_for_dp[i].append(partition_p.copy())
 
+    #return answer
     return arr_for_dp[total]
 
 
diff --git a/challenge-075/cheok-yin-fung/python/ch-2.py b/challenge-075/cheok-yin-fung/python/ch-2.py
index a13f885563..dcf7af2c54 100644
--- a/challenge-075/cheok-yin-fung/python/ch-2.py
+++ b/challenge-075/cheok-yin-fung/python/ch-2.py
@@ -10,8 +10,7 @@ def largest_rectangle_histogram(items):
 
     subtract1 = lambda n: n-1 if n > 0 else 0
 
-    temp = items
-    temp = temp + [0]  # put a zero at the end for ease
+    temp = items + [0]  # put a zero at the end for ease
 
     histogram = []
     pair = []