How and What to do in Programming (CY's Take on PWC#075 Task 2) [Edited]

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

---

Continued from the discussion of Task 1.

Task 2 Largest Rectangle Histogram

I am not a narcissist; though some of my actions are narcissistic traits, it does not imply that there is yet another narcissist; I am motivating myself for a better self.

Back to the task. This look like a task testing our overall commanding of the language (especially when the bonus is also considered), not an algorithm-oriented task.

At the first sight, looking for the largest rectangle seems uneasy. My order of coding has been: Perl code, Python code, Java code (3 at a time because I got a day-off on Tuesday) and (after a few days) Lisp code. The following is my note during coding the Perl of the task, informally:

Reverse:
0 7 (0, 0, 0, 0, 1, 0)
1 6 (0, 0, 0, 0, 2, 0)
2 5 (0, 0, 0, 1, 3, 1)
3 4 (0, 0, 0, 2, 4, 2)
4 3 (1, 0, 1, 3, 5, 3)
5 2 (2, 1, 2, 4, 6, 4)
6 1 (3, 2, 3, 5, 7, 5)

read line 7: [4];
    length [4] * (line_num) = 7
read line 5: [3..5]
    length [3..5] * (line_num) = 15
read line 3: [0], [2..5]
    length [0] * (line_num) = 3
    length [2..5] * (line_num) = 12
read line 2: [0..5]
    length [0..5] * (line_num) = 12 

The bonus "try to print the histogram as shown in the example" stated in the task statements looks like a hint to me more than a bonus. :)

Therefore I make a subtract1 subroutine for the task:.

sub subtract1 {
    return map { $_ != 0 ? $_-1 : 0 } @_;
}
In the Lisp version
(defun subtract1 (A)
(mapcar #'(lambda (term) (if (zerop term) (quote 0) (- term 1)  )  ) 
     A )))
In the Python version
subtract1 = lambda n: n-1 if n > 0 else 0

# ...
for i in range(max_item):
    histogram.append(temp)
    temp = list(map(subtract1, temp))

Then it is about finding the sets of consecutive non-zero entries on a row, list has been used directly only in Lisp
(defun generate-pos-in-line (line) 
  (setf pos-in-line nil)
  (setf temp nil)
  (loop for i from 0 to (- (length ARR) 1) do
     (if (zerop (nth i line)) 
         (progn (setf temp (reverse temp)) 
         (if (not (not temp)) 
             (push temp pos-in-line)) 
             (setf temp nil) ) 
         (push i temp))
  )
  (if (not (not temp)) (push temp pos-in-line) ()) ;# 
  pos-in-line
)

# (By the way, I understand the following joke now: https://docs.raku.org/language/faq#Is_Raku_Lisp?)

In Perl, I use hash:

# some codes for looking for the head "$h" and the tail "$t"
# , which record the position of the consecutive non-zero block...
if ( defined($h) && defined($t) && (!exists $areas{"$h,$t"}) ) { $areas{"$h,$t"} = ($t-$h+1)*($MAX_-$i); }

In Python, I use a pair of indices into a list

if not([h,t] in pair):
    areas.append( (t-h+1)*(max_item-i) )
    pair.append([h,t])

In Java, since I am a novice and nobody guides me, conservatively, I use 3 for-loops to approach the existence of rectangles.

Notes on experience coding in Python

Like many beginners of a new programming language, I made use of search engine. However, some code implementations are for Python2, not Python3 ! I did not notice the difference until I directly "copy and paste" some lines online. Then I typed python ch-2.py into terminal, and it produces error message. Then I learnt that I should use python3 ch-2.py. And then, a new list of errors... A lot of time was spent on investigation  the 'map' object is not subscriptable error. Oh, now I understand more the debate on Perl 5 and Perl 7 now.

Thanks to my data-scientist friend who has coded Python for years, she made a list of comments on my draft script, for example, the style of __main__, and Input/Output. ch-2.py inconveniently asks user input the parameter with line breaks but ch-1.py allows user input parameters just with space separated. I did not change the way of input in ch-2.py in order to record the difference here.

inside ch-1.py:

if __name__ == "__main__":
    urinput = [];
    target = int(input("Enter the sum: \n"))
    set_of_coins = [int(x) for x in input("Enter the value of coins with spaces seperated:\n").split()]
    urinput = [target] + set_of_coins;

inside ch-2.py:

if __name__ == "__main__":
    length = int(input("Enter number of items of the histogram: \n"))
    print("Enter items of the histogram with line breaks")
    items = []
    for i in range(length):
        items.append(int(input()))

Many people said that Python is beginner-friendly, while I cannot agree after my first experience dealing with Python this week. Anyway, my first programming language has been Pascal. (The farthest distance I went with Pascal was a text-interface Sudoku program in Windows in 2007, or a medal in HKOI 2008).Then I am not a beginner in coding, so at here I safely dismissed a discussion "what is the best programming language for beginners" for other programming beginners (beginning programmers?) at this moment when I am tired and selfish.

Notes on experience coding in Java

Java programs perform faster than I thought.

Notes on experience coding in Lisp

As some people(for example the author of Higher-Order Perl) said, Perl and Lisp share many features. I will keep learning Common Lisp.

This time I made the codes messy and made the debugging process time-consuming.

Notes on what to learn further

Which is more important, learning data structures and algorithms, or learning new programming paradigms?

This week I spent most time on coding new languages and did not optimize my ch-1.pl. Is it a time management dilemma?


link for codes: ch-2.pl, ch-2.py, histogram.java, ch-2.lsp

Anyway, lists of stuff I would like to also learn more

  • exception handling inside codes
  • git commands from computer terminal
  • more Java, Lisp, Perl and Python

Best Wishes. □


PS:

One step to the optimized code, for Task 2! If I had taken time to check my output of rectangles, I could achieve the O(n) solution as well.  See the explanation on GeeksForGeeks.org  .

Let's comfort myself now: anyway I have learnt of more about the built-in data structures of Python, Java and Lisp through my imperfect algorithm implementations.

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