CY's Recent Submission for PWC(068-073) [edited]

Skipped blogging on Perl Weekly Challenge(PWC) for a few weeks! Let's review what I learnt from PWC#068 to PWC#072 first:

PWC#068

Inexperienced in object-oriented, (after a few hours violent trial and error, ) I finally gave up the task #2 reordering a singly linked list.

For the task #1 zero matrix (task statement here), I handled it innocently. By the way, I read the review by Mr Crain and deeply recommend others read Myoungjin Jeon's solution.

PWC#069

Task #1 - Strobogrammatic Number

I use the combinatorics library on CPAN. However, a poorly designed code performs poorly in the face of combinatorial explosion, in comparison with other PWC members' scripts. If I had considered symmetry, as the Perl Reviewer Mr Crain stated, the code would be more effective.

There is a mistake on my code: I treat all single digits as strobogrammatic. Forgetting what happened around during that week...

After finishing my codes, usually I will look on others' blogposts and see if there are any gems of Perl idioms, optimization or algorithms. (For the first of these three things, usually I cannot understand; still a novice! Learning Perl or Beginning Perl is consulted, in particular of anything with references.)

Task #2 - 0/1 String

Before the update (asking for S30, instead of S1000), I thought it had been a task challenging BIG integers or LONG strings handling... .

Back to the task. I have "jumped a step" by generating SN from SN-2 instead of SN-1. For the S30, I forcefully generated it from S26, which is the largest S i can be properly generated by the core of my code (and computer memory).

PWC#070

Task #1 - Character Swapping

Got familiarity with substr.

Task #2 - Gray Code Sequence

I learnt about Gray code in my first semester in university, in a combinatorics class I did poorly. (I did poorly in every class that semester, including linear algebra and multivariable calculus.) Anyway, the Gray code looks easier now.

Bravely (Boldly?), as a novice in programming, I submitted a script in Lisp! I haven't got time to study Perl Best Practices but I have jumped to learn a new language... while I haven't figured out or got resources on best practices of Lisp.

PWC#071

Task #1 - Peak Element

I must warn myself to read instructions and examples carefully. I:

  1. missed the two edge cases;
  2. generated 11 elements instead of 10 elements;
  3. had almostly missed the uniqueness requirement for the elements, but after causally reading laurent_r's blog in the morning(GMT+8), I rushed to add a few lines;
  4. thought it had been fixed it up? But I forgot to declare a hash, so the submitted code was actually refused to run under use strict.

I wrote a Lisp script for this task. Lots of setf was used, after 10 days, I think the code will be more readable and maintainable using some defun.

Task #2 - Trim Linked List

Singly linked list again! OO. OO. OO. Is it necessary to make a class of nodes and linked list? I "consulted" Rosetta Code and learnt to implement linked lists by nested hashes.

PWC#072

Task #1 - Trailing Zeroes

Most members output a complete and grammarically correct English sentence, as in the example. Again, I forgot the formatting.

For personal record: I wrote a Lisp script for PWC tasks again.

Task #2 - Lines Range

Just digged out the Learning Perl.

Sidenote

I have gradually developed a format for my submissions.

Firstly, put the task statement with the habitual or necessary heading statements (

#!/usr/...
task statement
Usage: ch-x [parameters]
use strict;
use warnings;
).

Secondly, I put the example test case as default values and allow people deal with my codes from command-line arguments. (

if ($ARGV[0] and $ARGV[1]) { $S = shift @ARGV; @A = @ARGV; } else { $S = 3; @A = (1, 5, 0, 2, 9, 3, 7, 6, 4, 8); } )

This may help when I try to look for or review my codes written.

PWC#073 (submission deadline: the coming Monday GMT+8 0759)

"Write test cases first!" I would try to follow this "software engineering" rule of thumb## (especially for scripting language?).

Task #1 - Min Sliding Window

I have learnt to use is_deeply this time.

Just thinking the optimization if we know the minimum values are rare and both $S and the list are large. See if I can write a script suitable for the above condition and show its complexity# within this weekend.


Task #2 - Smallest Neighbour

No need to be very observant, we can see there are some patterns of the output like [0 , min1 ,0 , min2, min2, 0, min3, 0 , min4, ..., 0, minlast ] where mini > minj for i < j. In words: a weakly descending sequence with some zeroes interpolated.

Time to learn Lisp and see if I have time and knowledge to write a Lisp script as part of guest submissions for PWC.

(Again...) Wish you all stay healthy mentally and physically! □


My codes can be found on the E7-87-83 GitHub repository. You may appreciate others' codes on the official GitHub repository Knowledge base of PWC.

Do tell me , if you have oppositions!

#: I am very lazy on writing proofs. However, I took all required courses in math (not all with flying colours) in university but forgot to declare double major in Physics and Math, thus I graduated with a BSc in Physics only. Sometimes I would have resentments towards this life episode; sometimes I comfort myself by telling that I am neither good at writing rigorous proofs nor linear algebra computations, thus the certificate might avoid some embarrassment.

##: See Testing Is the Engineering Rigor of Software Development, by Neal Ford, in 97 Things Every Programmer Should Know. I think I read the importance of (unit) testing elsewhere also.



 Addendum (on 16th Aug):

(here >> means "much greater than")


By ch-1.pl, the number of traversals: (N-S+1)*S = NS - S^2 + S

If N >> S and S is relatively small, efficiency of the algorithm = O(N)

If N and S are about the same magnitude, efficiency of the algorithm = O(N) .

What if N >> S >> 1 ?

Let λ = S/N, while 0 < λ < 1 .
Since we assume N >> S, λ = S/N << 1 ,

The number of traversals of ch-1.pl : (N-λN+1)*λN = λN^2 - λ^2 N^2 + λN = O(λN^2)
The algorithm is good only if λ is approximately equal to 1/N ; however,
λ = S/N; if λ is roughly equal to 1/N, S = 1 . The case "window size = 1" is not a meaningful input.
We can say: when N >> S >> 1, we always have O(N^2) if we complete the task by ch-1.pl .


Let’s see ch-1a.pl .
Improvements for N >> S >> 1 AND "local minimums" are rare:

How many extra variable(s) is/are needed? (space complexity) ; at least there should be two variables: one records the position of the current "local minimum", another records the value of the current "local minimum".

Let γN be the number of "local minimums" (while 0 < γ << 1) (we should also assume λ < γ) :
Without loss of necessary analysis, we skip the details on beginning and ending,
Under the algorithm of ch-1a.pl, the number of changes of “local minimums” should be γN.


Are there any improvements for N >> S >> 1 AND "local minimums" are frequently changed?
Its time complexity should be O(λN^2) as well. Not a significant improvement.


Verification of the effectiveness of ch-1a.pl

input: approx 15900 integers
S=20

ch-1.pl
real	0m0.069s
user	0m0.049s
sys	0m0.020s


ch-1a.pl
real	0m0.064s
user	0m0.044s
sys	0m0.019s

S=30

ch-1.pl
real	0m0.075s
user	0m0.062s
sys	0m0.013s

ch-1a.pl
real	0m0.066s
user	0m0.053s
sys	 0m0.012s


S=100

ch-1.pl
real 0m0.078s
user 0m0.064s
sys 0m0.014s

ch-1a.pl
real 0m0.052s
user 0m0.031s
sys 0m0.015s

1 Comment

I just love reading your blog, keep it up.

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