Moments on Perl or other Programming Issues

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.

Task 1 Coins Sum

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))) {
    arr_for_dp[i].add(partition_p);
}

Perl: (ch-1.pl)

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

answer:  450

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

[1]> (load "ch-1-test.lsp") 

;; Loading file ch-1-test.lsp ...

;; Loaded file ch-1-test.lsp

#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

answer:  416

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

answer:  41

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

answer:  3612

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

answer:  20151

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

answer:  7051

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

answer:  14

real	0m0.030s

user	0m0.022s

sys	0m0.009s

$ time python3 pwc075ch-1.py

answer:  14

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