## Time Challenge (CY's Take on PWC#075 Task 1)

If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email).

Thanks for the volunteers, there are code Reviews on Perl/Raku; in addition, on each Monday, you can read the RECAP linking others' solutions and blogs; I often learn something from both RECAP and Perl Review.

Do tell me, if I am wrong or you strongly oppose my statements!

---

While the weekly challenge is fighting towards new record of number of submissions, I am starting my own programming adventure. Congratulations to CY Fung, she knows how to code in Python and Java now. I am going to submit guest solutions in these two languages for the coming challenges.

In mathematics, the integer partition is not easy. The partition function does not have a direct closed form. It grows fast -- p(4) = 5 (in the setting of the task, \$S = 4, \$C = (1,2,3,4), \$ANS = 5), p(20) = 627 (as before... \$S = 20, \$C = [1..20], \$ANS = 627). See the English Wikipedia page for details.

I decided to see if the combinatorics libaries on CPAN have the partition function or maybe some related functions. Integer::Partition is found. The latest update date is in 2013. I did not check the ZS1 and ZS2 algorithms but immediately put the function to be used.

My ch-1a.pl firstly grasp the integer partitions of \$S, then check for each partition if the members of that partition are all among the members of coins.

Is there a way to KO the task without CPAN libraries? Yes. The task can be treated as a dynamic programming problem. We can calculuate all the ways of coin paying for starting from 1 to \$S-1, and the ways of paying for \$S is Σ ways(\$S-\$a_coin_value). Naturally we store these information in an array.

OH NO NO. Σ ways(\$S-\$a_coin_value) double-counting or triple-counting or quadruple-counting ... We can avoid the repetition by checking if the combination of coin paying is already counted.

I have written solutions in Python, Java, Perl and Lisp with the same algorithms, except the process for checking if two lists are the same and then checking if a list is inside the list of partitions:

Python:
if not(partition_p in arr_for_dp[i]):
arr_for_dp[i].append(partition_p.copy())

Java:
if ((!arr_for_dp[i].contains(partition_p))) {
}

Perl: (ch-1.pl)

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;
}

...

if (!contain([@temp], \$arr_for_dp[\$i])) {

push @{\$arr_for_dp[\$i]}, [@temp] ;

}

...

Lisp:

```(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) ))
)

......  ((((( ...
(if (NOTANY (lambda (x) (same-combination newpartition x))
(aref vec-for-dp i) )
(push newpartition (aref vec-for-dp i))))))))```

##### Language Differences

In Java, arr_for_dp is an ArrayList of vectors. (Thanks to C++ experience before, I learn to build codes in Java quickly.)

In Python, an array of lists of sorted list come in handy. In my Python code, for paying \$5, with coins valued \$1, \$2 and \$4, I have arr_for_dp as:

[
[],
[[1]], [[2], [1, 1]],
[[1, 2], [1, 1, 1]],
[[4], [1, 1, 2], [1, 1, 1, 1], [2, 2]],
[[1, 4], [1, 1, 1, 2], [1, 1, 1, 1, 1], [1, 2, 2]]
]

* Line breaks added by CY Fung; also line breaks for the below cases

In Perl, since it is said that Perl does not have arrays of arrays in a strict sense, one has to use an array of references of arrays; using Data::Dumper, we see @arr_for_dp in my Perl code for the same task parameters:

\$VAR1 = 1;
\$VAR2 = [[1]];
\$VAR3 = [[2],[1,1]];
\$VAR4 = [[1,2],[1,1,1]];
\$VAR5 = [[4],[1,1,2],[1,1,1,1],[2,2]];
\$VAR6 = [[1,4],[1,1,1,2],[1,1,1,1,1],[1,2,2]];

In the list processing language, Lisp, we have the following structure vec-for-dp:

#(
NIL
((1))
((1 1) (2))
((2 1) (1 1 1))
((2 2) (1 1 1 1) (2 1 1) (4))
((4 1) (2 1 1 1) (1 1 1 1 1) (2 2 1))
)

##### Performance

As mentioned above, there is the ch-1a.pl using the integer partition module and ch-1.pl using dynamic programming. How are their performance? I did a few simple tests:

```Test Case I: \$S = 50, @C = (1,2,5,10,20)
\$ time perl ch-1.pl 50 1 2 5 10 20
total number of ways: 450

real	0m7.887s
user	0m7.875s
sys	0m0.008s

\$ time perl ch-1a.pl 50 1 2 5 10 20
total number of ways: 450

real	0m1.441s
user	0m1.440s
sys	0m0.000s

Test Case II: \$S = 49, @C = (1,2,5,10,20)
\$ time perl ch-1.pl 49 1 2 5 10 20
total number of ways: 416

real	0m6.964s
user	0m6.932s
sys	0m0.016s

\$ time perl ch-1a.pl 49 1 2 5 10 20
total number of ways: 416

real	0m1.865s
user	0m1.861s
sys	0m0.001s

Test Case III: \$S = 20, @C = (1,2,5,10,20)
\$ time perl ch-1.pl 20 1 2 5 10 20
total number of ways: 41

real	0m0.042s
user	0m0.042s
sys	0m0.000s

\$ time perl ch-1a.pl 20 1 2 5 10 20
total number of ways: 41

real	0m0.019s
user	0m0.015s
sys	0m0.004s```

ch-1a.pl seems faster.

Let's compare(compete?) among languages also (I omit ch-1a.pl, which is using different approach):

```Test Case I: \$S = 50, @C = (1,2,5,10,20)
\$ time java coinssum
450

real	0m0.377s
user	0m0.943s
sys	0m0.057s

\$ time python3 ch-1.py

real	0m0.096s
user	0m0.087s
sys	0m0.008s

\$ ... #config for clisp
... #some ASCII art from CLISP
Welcome to GNU CLISP 2.49.60+ (2017-06-25)
... #some messages from CLISP
#P"/home/e78783/ch-1-test.lsp"
[2]> ; which is a version without printing the combinations
[3]> (compile 'coins-sum)
... #some messages from CLISP
[4]> (time (coins-sum (list 50 1 2 5 10 20)))
450
Real time: 15.42992 sec.
Run time: 15.403774 sec.
Space: 289025776 Bytes
GC: 266, GC time: 0.460318 sec.

Test Case II: \$S = 49, @C = (1,2,5,10,20)
\$ time java coinssum
416

real	0m0.351s
user	0m0.822s
sys	0m0.037s

\$ time python3 ch-1.py

real	0m0.096s
user	0m0.082s
sys	0m0.013s

\$ ...clisp
416
Real time: 13.077948 sec.
Run time: 13.057861 sec.
Space: 244747848 Bytes
GC: 237, GC time: 0.400488 sec.

Test Case III: \$S = 20, @C = (1,2,5,10,20)
\$ time java coinssum
41
real	0m0.105s
user	0m0.149s
sys	0m0.015s

\$ time python3 ch-1.py

real	0m0.037s
user	0m0.021s
sys	0m0.011s

\$ ...clisp
41
Real time: 0.048842 sec.
Run time: 0.048742 sec.
Space: 664376 Bytes
```

It seems that my Python3 code ch-1.py performs faster than my Perl code ch-1.pl sometimes... This surprises me a bit, but it could be due to the efficiency of the contain subroutine, I suspect.

For the pride of Perl, let's go for some more tests between Python and Perl. Some larger test datas. And "Perl team" decides to use ch-1a.pl as the representative. The last one uses a set of irregular test data.

```Test Case IV: \$S = 80, @C = (1, 2, 5, 10, 15, 20)
time perl ch-1a.pl 80 1 2 5 10 15 20
total number of ways: 3612

real	2m37.021s
user	2m36.619s
sys	0m0.088s

\$ time python3 ch-1.py

real	0m3.075s
user	0m3.022s
sys	0m0.020s

Test Case V: \$S = 80, @C = (1, 2, 4, 5, 10, 15, 20, 30, 50)
\$ time python3 ch-1.py

real	1m1.464s
user	1m1.118s
sys	0m0.096s

\$ time perl ch-1a.pl 80 1 2 4 5 10 15 20 30 50
total number of ways: 20151

real	2m46.592s
user	2m46.015s
sys	0m0.176s

Test Case VI: \$S = 50, @C = (1, 2, 4, 5, 10, 11, 13, 15, 16, 17, 20, 23, 30, 37, 41, 50)

\$ time python3 pwc075ch-1.py

real	0m5.672s
user	0m5.607s
sys	0m0.032s

\$ time perl ch-1a.pl 50 1 2 4 5 10 11 13 15 16 17 20 23 30 37 41 50
total number of ways: 7051

real	0m2.965s
user	0m2.958s
sys	0m0.004s```

```\$ time perl ch-1.pl 50 1 2 4 5 10 11 13 15 16 17 20 23 30 37 41 50
^Z
[1]+  Stopped                 perl ch-1.pl 50 1 2 4 5 10 11 13 15 16 17 20 23 30 37 41 50

real	3m19.583s
user	0m0.000s
sys	0m0.000s
```

OK, ch-1a.pl wins some pride of Perl at Test Case VI, which some more "prime-valued coins" besides \$2 and \$5 are allowed in the city.

Let's have a short obstacle race for the languages and scripts as the end of this section: (the scripting languages join the challenge multiple times)

```Test Case VII: \$S = 7, @C = (1, 2, 3, 4, 5, 7)

\$ time python3 pwc075ch-1.py

real	0m0.030s
user	0m0.022s
sys	0m0.009s

\$ time python3 pwc075ch-1.py

real	0m0.024s
user	0m0.016s
sys	0m0.008s

\$ time perl ch-1a.pl 7 1 2 3 4 5 7
total number of ways: 14

real	0m0.012s
user	0m0.008s
sys	0m0.004s

\$ time perl ch-1.pl 7 1 2 3 4 5 7
total number of ways: 14

real	0m0.018s
user	0m0.014s
sys	0m0.003s

\$ time perl ch-1.pl 7 1 2 3 4 5 7
total number of ways: 14

real	0m0.020s
user	0m0.016s
sys	0m0.004s

\$ time java coinssum
14

real	0m0.080s
user	0m0.080s
sys	0m0.029s

\$ clisp
... #some conversation with CLISP
> (time (coins-sum
(list 7 1 2 3 4 5 7))
)
((4 3) (5 2) (3 2 2) (3 2 1 1) (4 1 1 1) (2 1 1 1 1 1) (1 1 1 1 1 1 1)
(3 1 1 1 1) (2 2 1 1 1) (5 1 1) (2 2 2 1) (4 2 1) (3 3 1) (7))14
Real time: 0.003331 sec.
Run time: 0.003248 sec.
Space: 65704 Bytes
```

...Lisp becomes the champion on this short obstacle race!

To end this blogpost, if I am really going to handle a coin-paying condition by my own scripts, I am going to use ch-1a.pl . This blogpost runs long, therefore I should to write a new blogpost for Task 2, my coding experience with the new languages (Java & Python) (I am very happy that I can pick up the basics of them within a week) and some more discussion. Before blogging, see if I can write a Lisp solution for Task 2 by Monday.□

link for codes: ch-1.pl, ch-1a.pl, ch-1.py, coinssum.java, ch-1.lsp

#### P.S. 1:

The following messages appear while my laptop compiles the Java codes.

```Note: coinssum.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
Note: coinssum.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.```

#### P.S. 2:

Just read laurent_r's blogpost, with consideration on algorithms, his script runs significantly faster than my ch-1a.pl