Day 8/100 Mountains, Hills, and Valleys

 Day 8/100 Mountains, Hills, and Valleys

Aren't they all the same?

Today is a special bonus where I'm tackling LeetCode challenge special. What's so special about it? I'm tackling 2 challenges at once! Well, not really. Just one after another. Technically, I can do both at once, though, just so you know.

LeetCode 845

The first challenge is Leet Code 845. This is a special challenge because I was unable to understand the problem properly. Specifically, regarding the nature of a mountain. What should you do if there's plateaus? The example only show a completely flat data, but in the real significant data set, there's no plateau! Everything either goes up or goes down. 

Obviously, that's not real world. It also makes solving the problem much easier. Specifically, you don't have to keep the state of ascending and descending when encountering the flat level of the mountain. This becomes a problem when real world data have flat inputs. 

The exercise, then, becomes pointless. Here I am spending a significant amount coding, solving the problem, and the resulting program does not apply in the real world! What kind of pointless exercise is that? Do they really ask these kind of questions in job interviews? Really? What's the point of wasting people's time?

The unfortunate thing is that no one really got the right answer, at least after cursory inspection of the solutions. This includes the official solution, which is Two Pointer algorithm. I notice 3 while() functions in the official solution. Isn't that over complicating thing?

Last time, I have shown you the Point and Figure chart. Well, now is as good time as any to take advantage of that. Here's the solution as diff from that program:

29a30,32
> int lmtn=0;
> int mtnx=0;
> 
119c122,127
<     if (dir<0 && slot>lslot) { showScan(1); dir=1; }
---
>     if (dir<0 && slot>lslot) {
>        showScan(1); dir=1;
>        if (Debug) printf("(%d)",(tstamp-lmtn));
>        if (mtnx<(tstamp-lmtn)) mtnx=tstamp-lmtn;
>        lmtn=tstamp;
>     }
135a144
>   printf("\nMax Mountain Range: %d\n",mtnx);

That's not difficult at all! Do you notice anything special? There are only 2 variables involved: Max Mountain value (mtnx) and Last Max Mountain value (lmtn). That's O(1) space characteristics. There is also nothing complicated about the loops. I simply use the same looping as the original. So that's O(N) Time. 

Nothing to it! Can you recognize the algorithm used? 

Let's go back to Day 6 of the challenge where I did a word count program. The algorithm there is basically: "We're in a space, we're not in a space,..." repeated until end of input. That's a simple, easy to use algorithm. And that's basically what I did. "We're ascending (calculate mtnx), we're descending,..." repeated over and over. And that takes care of things nicely. Bonus: You can do the same for descending to calculate valleys.

And that's it! Remember how I said that Word Count program is a significant program? Well, that's because the pattern is very common, and this problem proves it! Not even the solution of official Leet Code answer realized that this problem is as simple and clear as the word count problem! 

LeetCode 2210

The next challenge I'm doing is the Leet Code 2210: Count Hills and Valleys in an Array. There is no official solution at the time of this writing. However, that does not stop me at all. Remember how the last solution is as easy as Word Count? Well, this one is like that.

29a30,32
> int hills=0;
> int valls=0;
> 
118,119c121,122
<     if (dir>0 && slot<lslot) { showScan(1); dir=-1; }
<     if (dir<0 && slot>lslot) { showScan(1); dir=1; }
---
>     if (dir>0 && slot<lslot) {showScan(1);dir=-1;hills++; }
>     if (dir<0 && slot>lslot) { showScan(1);dir=1;valls++; }
135a139,140
>   printf("Hills:\t%d\n",hills);
>   printf("Valleys:\t%d\n",valls);

The difference is that instead of calculating the period between climbs, we simply noted the direction of travel, and increment the counter every time there is a change of direction. Same data, same algorithm as Leet Code 845.

Looking over the solutions, it seems that a lot of people are able to catch on the algorithm. Yet, it is the same class of problems. What makes the previous problem so hard to get right?

I can't think of any reason. Then again, I guess this is why some people think that computer programming is hard and takes years to master. They simply didn't think things through.

I think my progress went significantly faster when I decided that people are stupid. This means that computer programs are simplistic at its core. Certainly, there are complicated programs, but the numbers are much, much less than you think! In fact, they're pretty rare.

Therefore, my advice to you is to not give up. If you run into a complicated program, step back and think about it. What is it that the program is trying to do? And what would be the nearest program that does the same thing? Who knows? Maybe you can simply modify preexisting program to do it.

Problem? What problem? There is no problem.