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:


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.


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


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.


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.


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.


I have gradually developed a format for my submissions.

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

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, 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 : (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 .

Let’s see .
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, 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

input: approx 15900 integers
real	0m0.069s
user	0m0.049s
sys	0m0.020s
real	0m0.064s
user	0m0.044s
sys	0m0.019s

real	0m0.075s
user	0m0.062s
sys	0m0.013s
real	0m0.066s
user	0m0.053s
sys	 0m0.012s

real 0m0.078s
user 0m0.064s
sys 0m0.014s
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.