CY's take Perl Weekly Challenge on #055

This is a part of Perl Weekly Challenge(PWC) #055 and the followings are related to my solution.

Do tell me if I am wrong or you strongly oppose my statements!

named.jpg

Oh.

Mohammad and some other experienced perl coders are very generous and encouraging towards my road of learning Perl, (e.g. last time Laurent's comment; I thank him inside code and again here) (and with pride, last week I located on the 45th of the PWC team member chart), but my foundation is not good enough. From now on until the summer passes, I may try only the easier task of the two tasks in each week's challenge. And I will blog about it if the coding is completed before Saturday. Technical documentation is also an important skill of coders. (As I am in GMT+8.00 Timezone, I have an early morning to work on more, but sometimes I have to go to work, and sometimes these several hours do not help much because I am the type of "I should not resign, I should not resign"... and code until the deadline is really close.) (And this blog runs over 8am on Monday in the timezone.) I want more idiomatic Perl codes also.

----
Task #2.
(Interesting stuff first... kinda principles of me.)

Originally I think of some algorithms with swapping and induction, likewise, if we want wave array of 1 to 6, we may consider the wave arrays of 2,3,4,5 first, then have five arrays:
5 3 4 2
5 2 4 3
4 3 5 2
4 2 5 3
3 2 5 4
Then we unshift 6 and 1 into the arrays:
6 1 /5 3 4 2
6 1 /5 2 4 3
6 1 /4 3 5 2
6 1 /4 2 5 3
6 1 /3 2 5 4

Then we may swap the 6 with 5, swap the 1 with 2. ...

However, it needs not to code that we can foresee the swapping doesn't work efficiently with inputs with non-unique entries. ( Actually my submitted code hasn't solved the problem of duplication completely, it just alleviates the situation a bit.)

My submitted approach is using combinations. What in my mind was the famous balls-and-urns in the twelvefold way in combinatorics. Therefore the metaphor is used throughout the main part of my codes.


Task #1.

It has some tricky corner cases/corner condition to consider. Likewise, for 11111111111111, we cannot do nothing. Therefore we have to flip at least one of the ones and it reduces the sum of 1's in the binary string. Oh god.


Transformations.

My both attempts use certain kind of transformations (and reverse transformation, conceptually similar to what I did in PWC#053 Task #1). For task #1, through the transformation, I get an O( (log N)*(log N) ) solution.

For task #2, I modify every input as a "canonical" form: sorted; the smallest must be 1, and the terms are the consecutive integer or equal to the previous terms. Then I use -1 internally represented unfilled positions(, and 0 for some special positions). For the larger integers, roughly speaking, most of them occupy the "even" positions (index started at 0), I put them through the Algorithm::Combinatorics qw/combinations/ .


My attempts can be found in

https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-055/cheok-yin-fung/perl .



To thank Mohammad for the encouragement and hosting the PWC, (already planned to recommend this CPAN module last time, but my task #2 last time failed to get the extra credit) I will recommend the syntax highlighter maintaining by Mohammad:

Syntax::Highlight::Engine::Kate::Perl .

(Every Monday I await for the new challenge. If I am at work, I will impatiently check my smartphone many times to see the latest challenge as early as possible. Thanks to Ryan, I also look forward to the code reviews to learn and improve Perl programming skills.)
Cheers. Continue to code and learn in the new week!
(Keep hygiene and healthy lifestyle during the pandemic also.)

1 Comment

I simply love reading your blog. I liked the flow and consistency. Great work. Keep it up.

Leave a comment

About C.-Y. Fung

user-pic I blog about Perl or other programming issues as a beginner.