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.

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)

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

Leave a comment

About C.-Y. Fung

user-pic a beginner in programming; passionate in mathematics, distance running and gender issues; from Hong Kong. https://twitter.com/e7_87