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

### 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 S_{30}, instead of S_{1000}), 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 S_{N} from S_{N-2} instead of S_{N-1}. For the S_{30}, I forcefully generated it from S_{26}, 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:

- missed the two edge cases;
- generated 11 elements instead of 10 elements;
- 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; - 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 statementuse strict;

Usage: ch-x [parameters]

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 , min _{1} ,0 , min_{2}, min_{2}, 0, min_{3}, 0
, min_{4}, ..., 0, min_{last} ]` where

`min`>

_{i}`min`for

_{j}`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

I just love reading your blog, keep it up.