Self Challenge and Weekly Challenge (CY's Take on #074 Task 1)

board-game-challenge.jpg

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.

---

One week to the end of August!

Alan J. Perlis said, “A language that doesn’t affect the way you think about programming, is not worth knowing.

I would add a clause to it: unless it helps you earn your living...


Self Challenge

Making risky/improbable promises are usually looked down in Hong Kong, though some people do support the venturesome spirit (not quite for females, but – personal feelings). “Jump-in, jump-out” is not welcomed, as for my understanding to Hongkongers. (I actually stay on Internet more than in Hong Kong society.)

Anyway, here is Internet. (The Perl Community is still active on Internet, but almost no companies ask for coders in Perl in Hong Kong.) In “Public Parts – How Sharing in the Digital Age Improves the Way We Work and Live”, the author Jeff Jarvis has suggested that people forgive(shake off?) childish behaviors made by teenagers or young adults. I did have my facebook period and it was full of improbable promises (I did it on blogs.perl.org too actually, on learning OO in Perl 🤔) – in a word: foolish.

After some discussion with a data-scientist friend, I have made an improbable promise: to produce [Lisp,]* Python, Java and Perl solutions for tasks in PWC. Let’s see if||how_far I can do it next week!

Why Python and/or Java? Because so many people are using them and I should learn to read or study the relevant codes (linking with what is written at the beginning of this post). For Python, I found the following recipe: https://medium.com/@chirag__gupta/learn-python-in-10-minutes-tutorial-796b1f04f432 ; just the last part related to threading is alien to me. For Java, It will be very difficult for me to get the OO concepts at this stage, my expectation is just practicing and getting familiar with Java syntax with the smaller tasks among the Weekly Challenge tasks. □

(Why did I start to submit Lisp solutions? It could be explained as accidental events. First: I heard that S*CP is a great book on programming long time ago (here, means more than 10 years). Second: recently I found a Lisp book on my downloaded files and got some fun with it. I hope I can continue study for Lisp, learning cool stuff like lambda.)


Weekly Challenge

Hey, let’s back to this week’s PWC, especially Perl scripts submitted! I would like to polish on Task 1 only.

Solving the majority task before, I badly handle the task with the Boyer-Moore majority vote algorithm. It also reminds me an interesting post on Quora: What are some programming problems that look hard at a first glance but are actually easy? Solving the majority task with hashes is not hard, though.

Another optimized algorithm is divide-and-conquer. Given a list, divide it into left sublist and right sublist, get the majority element of the original list if:

  1. Case I: A and B, distinct, are the respectively majority elements in left sublist and right sublist; go for a linear search and verify which of them is the majority element of the list, or, none of the two are the majority element# of the list – in this case we conclude the list has no majority elements.
  2. Case II: A is the majority element in both left sublist and right sublist. Elementary addition concludes that A is the majority element of the list.
  3. Case III: A is the majority element of one of the sublists, another sublist has no majority element. Elementary addition concludes that a majority element of the list does not exist.
  4. Case IV: No majority elements on both sublists. A majority element does not exist for the list.

My script can be found here at the Weekly Challenge respository.□

#: "s" could be embarrassing here.


Stay alert and healthy! □

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