Day 22/100 Fibonacci and Factorial Trailing Zero

Day 22/100 Fibonacci and Factorial Trailing Zero

Failure at Grade School Arithmetic

So, I was at conversation the other day, where the other person was touting the virtues of Python, and dissing C language. You know, the language I'm using to do 100 Days of Code challenge. Truthfully, I did encounter a few "Segmentation Fault" core dump error, but I simply took it in stride. What I didn't know, I soon find out. It's part of the learning process.

Why would anybody do it differently? Why would you blame the programming language when you're supposed to increase your own skill so that you no longer make mistakes, instead of expecting the computer to catch yours?

If you look at my programs, you'll see my tendency to be light on error checking routines. What can I say? I don't make that many mistakes. Sure I made some. Everybody does. The difference between me and other people is that I learn from my mistakes and not repeat them. I don't see that kind of commitment from your average coder. This is why I wonder if the oft claimed "Coding makes you smarter" is incorrectly attributed to survivor bias.

Pardon me for having a dim view of the situation. I have seen too many stupid people who don't know what they're doing, make bold claims that are obviously false. Let's not spread more misinformation than what is already out there.

The title above is being honest. The failure does not lie in coding, regardless of platform or programming language chosen. The failure is at grade school level of arithmetic. I'm talking about 5th grader arithmetic here! Add, subtract, multiply, and divide. It doesn't even involve any fraction! How hard can that be?

Very hard, it turns out. Let's take a look at fibonacci code I've written. I did it twice: First is my take on it. The second is what is commonly done by the community, assuming neither Dynamic Programming (memoization) nor Recursion is involved. This is LeetCode 509:

long long fib1(int n) {
  int i=1;
  long long m[2];
  if (n<1)  return 0;
  if (n>92) return -1; //oob
  for (m[0]=1,m[1]=1;--n;i=1-i) m[i]+=m[1-i];
  return m[i];
}

long long fib2(int n) {
  int i=0; long long a=0;
  long long b=1;long long c=1;
  if (n<1)  return 0;
  if (n>92) return -1; //oob
  for (a=0,b=1,c=1;--n;) {
    a=b; b=c; c=a+b;
  }
  return b;
}

As you can see, my version is more compact than what is usually done. It uses only 2 variables, stored as array, so that I can flip between them. Testing does take a while, but if you pride yourself as a software engineer, then you would want to do it that way! Although mathematicians can resort to recursive solution, software engineer cannot do that! For you to take pride in your coding skill as software engineer, the code has to be extremely tight, and no waste either running time (recursion) or memory (memoization). 

The second solution is actually acceptable. It's very commonly done by people who aren't mathematically sophisticated. It's kind of like FizzBuzz challenge. Sure, it's easily done, but is it optimum? Not really. So, the second solution is acceptable, but nothing to be proud of.

As far as recursion and memoization? In my very strong opinion, those are failures! Waste of cycles and bytes! Very unprofessional! I always say that my code is at amateur hobbyist level, but looking at some of these professional coding, I wonder if I'm not already better than most of them.

A second example is even more telling than the fibonacci problem. The problem is to count the number of trailing zeros in factorial. LeetCode 172. Now, we're talking deep into mathematical realm. Sure, leet coder act like it's an easy thing to figure out. But is it? If you can figure out the deep mathematical issues, then surely you can also figure out the most efficient way to compute it? 

Nope! That's a fail! As far as I'm concerned, this kind of question does not belong in the interview process. Fundamentally, either you ran into the problem already, and remember the solution, or alternatively, you haven't run into it previously, and will now have to compute large samples of factorials to try to determine some kind of patterns that you can recognize. Oh, do you know that in these kind of interviews you cannot use any kind of help including computers and browsers? That's right! You only have the white board to do it.

What that tells me is that the company who does these kind of things will fill up their ranks with people who memorize LeetCode problems, instead of the smart coder who can readily research the issue. What's that Einstein, Feynman, et al said? "Do not memorize things that can be looked up?" Exactly!

Let's see what the typical answer is involved. You can probably google this in just a few minutes:

int trail1(int n) {
  int c; int i;
  for (c=0,i=5;n/i>=1;i*=5) {
    c+=(n/i);
  }
  return c;
}

Looks nice and easy, doesn't it? But it's deceptively tricky. Can you even work out the problem even after looking at the code? I certainly cannot! I'm no mathematician. I need to see rows of factorials and count the zeros to get some kind of pattern recognition going. This question is not an easy question, despite the brevity of the solution.

So, am I a failure? Maybe as a mathematician. However, as a coder? Not only would I pass, those people who give the answer above are all failures! Remember, we're evaluating coding skills, here, not math skills. The only math skill you need is grade school level arithmetic! That's right! No more than arithmetic. Hence the failure is of at grade school level. Now tell me, what kind of highly skilled, highly experienced, highly paid, professional computer programmer would fail grade school math? Only impostors do.

You need to have proper foundation in your skills! This goes double if you want to be a professional! No short cuts! If you cannot do grade school arithmetic, I suggest taking up coding as a hobby, rather than being a professional.

Here is the proper solution to the question:

int trail2(int n) {
  int c=0;
  for (;n/=5;c+=n);
  return c;
}

One division, and one addition. That's it! 

Look, coding is hard. I understand that. What I don't understand is why would people fail at grade school arithmetic! The usual solution as shown above features 2 divisions and a multiply. How is that better? It's not better. It's not professional at all!

How many years ago did you first learn arithmetic? Are you still at that level? Sigh.

Sorry to be so negative about things, but I'm seeing way more incompetence going on lately than what it used to be. Unfortunately, it seems that people just don't care anymore. That's a dangerous attitude to have. In the worst case scenario, it will mean the whole destruction of the industry as we know it. Don't laugh. It happened before. Look up "Dot Com Meltdown" if you don't believe me. That's the equivalent of "Game Industry crash" or even "Great Depression" level of apocalyptic event. Let's not have another one, okay?

Sigh.

I keep telling people to learn fundamentals, but people just don't bother. They refuse to do so. Why would they? A convenient library is just a download away! Until one day, one of those library disappear and if you google "... brought down the internet", you will find some incredible stories that shouldn't happen, but that they happened!

Study your fundamentals!

Lookit dem Smileys...

int d8(int B) {
  int              O;
  return  (O=  (B  /=  5)
  )?  O+   d8  (B  ):  0;
}

One more thing: Python isn't English! That distinction belongs to Literary Programming as pioneered by Dr. Donald Knuth. Alternatively, you can pull up just about any Design Document. Are you a Rockstar computer programmer?

Day 21/100 Roman Numeral

Day 21/100 Roman Numeral

MMXX has been a bad year!

I'll just do a quick run today. Basically, I'm intrigued by the possibility of parsing text with text fragments, instead per character or per words. So, I decided to put out an array of text and the converted value. Since this is a quick experiment, and I want to have an actual program, I decided to do Roman numeral conversion. Leet Code 13

I don't have to do Roman numeral conversion program. I can do Morse Code, or Phonetic Alphabet, etc. But Roman numeral conversion is simple enough, so why not?

int roman(char *num) {
  int i; int n=0; int l;
  for (i=0;i<strlen(num);i++) num[i]=toupper(num[i]);
  while (strlen(num)) {
    for (i=0;i<MAXENTRY;i++) {
      l=strlen(Romc[i]);
      if (!strncmp(Romc[i],num,l)) {
        n+=Romv[i]; num+=l; break;
      }
    }
  }
  return n;
}

It took me about an hour to do this, simply because I forgot to Initialize the table! Oh, dear. Can we say C is a terrible language to work with? Not really. I mean, what kind of computer programmer is it, to forget to initialize the table? Also, what kind of computer language can help with that? Syntax error is easy. Semantic error, however, is something you just have to own it.

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAXDIGIT 5
#define MAXENTRY 13

char Romc[MAXENTRY][MAXDIGIT];
int  Roml[MAXENTRY];
int  Romv[MAXENTRY];

int roman(char *num) {
  int i; int n=0; int l;
  for (i=0;i<strlen(num);i++) num[i]=toupper(num[i]);
  while (strlen(num)) {
    for (i=0;i<MAXENTRY;i++) {
      l=strlen(Romc[i]);
      if (!strncmp(Romc[i],num,l)) {
        n+=Romv[i]; num+=l; break;
      }
    }
  }
  return n;
}

void Init() {
  strcpy(Romc[0],"CM"); Romv[0]=900;
  strcpy(Romc[1],"CD"); Romv[1]=400;
  strcpy(Romc[2],"XC"); Romv[2]=90;
  strcpy(Romc[3],"XL"); Romv[3]=40;
  strcpy(Romc[4],"IX"); Romv[4]=9;
  strcpy(Romc[5],"IV"); Romv[5]=4;
  strcpy(Romc[6],"M");  Romv[6]=1000;
  strcpy(Romc[7],"D");  Romv[7]=500;
  strcpy(Romc[8],"C");  Romv[8]=100;
  strcpy(Romc[9],"L");  Romv[9]=50;
  strcpy(Romc[10],"X"); Romv[10]=10;
  strcpy(Romc[11],"V"); Romv[11]=5;
  strcpy(Romc[12],"I"); Romv[12]=1;
}

int main (int argc, char *argv[] ) {
  int i;

  if   (argc<2) {
    puts("Usage: roman ROMAN\n");
    return 0;
  }
  Init();
  for (i=1;i<argc;i++) {
    printf("%6d %s\n",roman(argv[i]),argv[i]);
  }
  return 0;
}

One more thing: You probably notice that the logic used here isn't the same as the logic used everywhere else. That's because the goal isn't to convert Roman numerals per se, but as an exercise to parse partial text not separated by words. Those of you who depends on pre-existing libraries, do you even have one? In any language? Sometimes, you just have to buckle down and make your own library. There's no way around it if you want to work on the bleeding edge.

Day 20/100 Factor

Day 20/100 Factor

Primes and Factors

It's been 20 days so far, and I'm at a point where my momentum has been disrupted. This is because I'm at research stage where things are unknown. This week will probably feature the slowest progress as I am reorganizing my codes. Specifically, I'm doing this to create programs to use. I think that's the difference between my effort and other people's. They learn to code, I'm writing programs to use.

It's possible that I will take a week off next week as I am re-orienting myself. I still code everyday, just that I won't be showing off the programs I've written as they are too messy and raw.

Take today's program: It's Factor. There's actually a built-in program to do this. Have you seen the source code? It's rather messy! I'm certainly no mathematician. So, I did it the simple way. Even though I'm doing it the simplest way, it does the job quite fast most of the time. The internal program runs at 0.005s, while mine is at 0.027s. That's about 5 times difference, and that's quite normal. In other words, to achieve single digit multiple of performance, there's quite a bit you must do! That's fine by my book. Also remember that I'm not using Gnu C Compiler (GCC). I'm using Tiny C Compiler (TCC) because it compiles so fast.

Given all the disadvantages, I'm happy that the program performs at the speed that it is. Of course, if I'm factoring numbers greater than 32 bit, it can bog down quite a bit. Some of the larger numbers, such as those of 64 bit, may even take hours to do. However, the algorithm I use is very simple:

  printf("F1 %lld: ",n);
  for (i=1;i<=n;i++) {
    while ((n%i)==0) {
      printf("%lld ",i);
      n/=i; c++;
      if (i==1) i++;
    }
  }
  printf("\n");
  if (c==2) return 1;
  return 0;

  printf("F2 %lld: 1 ",n);
  for (i=n/2;n>1 && i>1;i--,c++) {
    if ((n%i)==0) {
      printf("%lld ",(n/i));
      n=i;
    }
  }
  printf("%lld\n",n);
  return (n/i);

As you can see, there are 2 versions of code. Both returns a condition if the number is prime, so you can check the number for prime. Like so:

    if (factor1(n)) puts("Prime");
    if (n==factor2(n)) puts("Prime");

And that makes all the difference. Trying to give that is what makes the code so challenging to write, especially since I'm approaching the problem from both direction: Increasing and Decreasing.

Most people, when given a problem, will solve it one way, but never bothered to solve it again another way. That's no way to learn! Always do it more than once. In fact, I habitually do it at least 3 times: The good way, the better way, and the best way. Adopting that philosophy yields the most efficient result in regard to cost/performance gain, and so I would encourage you to do it that way, too.

At the very least, try to approach the problem from opposite point of view. If you look left, look right! If you look up, look down! If you look forward, look backward! It's that easy! There's nothing stopping you from doing it, except yourself. 

The LeetCode challenge 254 expects you to output combinations as well, but when's the last time that kind of algorithm was used? Nothing that I can think of. Anyway, here is the completed factor program:

 
#include <stdio.h>
#include <stdlib.h>

int factor1(long long n) {
  long long i;
  long long c=0;

  printf("F1 %lld: ",n);

  for (i=1;i<=n;i++) {

    while ((n%i)==0) {

      printf("%lld ",i);

      n/=i; c++;

      if (i==1) i++;

    }

  }

  printf("\n");

  if (c==2) return 1;

  return 0;

}

int factor2(long long n) {
  long long i; long long c=0;
  printf("F2 %lld: 1 ",n);
  for (i=n/2;n>1 && i>1;i--,c++) {
    if ((n%i)==0) {
      printf("%lld ",(n/i));
      n=i;
    }
  }
  printf("%lld\n",n);
  return (n/i);
}

int main (int argc, char *argv[]) {
  int i,n;
  if (argc<2) { puts("factor [NUMBER] ..."); return 0; }

  for (i=1;i<argc;i++) {
    n=atoll(argv[i]);
    if (factor1(n)) puts("Prime");
    if (n==factor2(n)) puts("Prime");
  }
  return 0;
}

One more thing: In this case, I did another try another factoring algorithm involving recursion, but that didn't pan out, it being a fragile algorithm, so I didn't bother to show you. But it does take a few hours of my time as I try the algorithm, just so you know.

Day 19/100 FizzBuzz

Day 19/100 FizzBuzz

FizzBuzz Buzzineezz

Yeah, you know it's going to happen eventually. I Fizz the FizzBuzz Buzz. Lame, I know. But here it is...

FizzBuzz program basically prints out numbers from 1 to 100, except that if the number is evenly divisible by 3, it prints "Fizz" instead. If the number is evenly divisible by 5, it prints "Buzz" instead. And if the number is evenly divisible by 3 and 5, it prints "FizzBuzz" instead. This is LeetCode 412.

So, here is the first solution that comes to mind. This isn't a unique solution, by any means, just the one most readily comes to mind.

FB1

void FizzBuzz1() {
  int i;
  for (i=1;i<=100;i++) {
    if (!(i%3) && !(i%5)) printf("FizzBuzz\n");
    else if (!(i%3)) printf("Fizz\n");
    else if (!(i%5)) printf("Buzz\n");
    else printf("%d\n",i);
  }
}

The problem here is that the solution isn't exactly clever. It works, but that's about it. Another thing to worry about is that the program isn't really easily extended. How about if you want to add "Bazz" for numbers evenly divisible by 7? And add "Bang" for numbers evenly divisible by 9? You can see that hard coding the solution like that doesn't bring any prestige point to the programmer. As a side note, failing at the task will certainly bring shame to the programmer.

So, let's improve the solution. Thinking about it, the problem is that it has different states to the solution. Especially important is that you don't want to show the number if the answer is "Fizz", "Buzz", or both! That's a failure point, so be careful!

The standard professional engineering way to solve this is via states. Something like this:

FB2

void FizzBuzz2() {
  int i;
  int s=0;
  for (s=0,i=1;i<=100;s=0,i++) {
    if (!(i%3)) s+=1;
    if (!(i%5)) s+=2;
    switch (s) {
      case 0: printf("%d\n",i); break;
      case 1: printf("Fizz\n"); break;
      case 2: printf("Buzz\n"); break;
      case 3: printf("FizzBuzz\n"); break;
    }
  }
}

And that works. But it's somewhat big, over engineered program, isn't it? In fact, that is the professsional way to do things. I guess now you know why I'm firmly at the side of amateur hobbyist side. I no longer have any patience in overbearing bureaucratic structures. Well, if the program needs it, I don't mind. Usually, they don't need it, though. Let's simplify that monstrosity.

FB3

void FizzBuzz3() {
  int i;
  int s=0;
  for (i=1;i<=100;i++) {
    s=0;
    if (!(i%3)) { s=1; printf("Fizz"); }
    if (!(i%5)) { s=1; printf("Buzz"); }
    if (!s)     {      printf("%d",i); }
    printf("\n");
  }
}

So, in fact, we only need one state. Are we printing number? Or not? We don't need to get fancy! And that's a good solution, too, albeit less structured, and perhaps a little bit more difficult to read. Let's compact the program even more!

FB4

void FizzBuzz4() {
  int i;
  for (i=1;i<=100;i++) {
    printf("%d\r%s%s\n",i,
    (i%3)?"":"Fizz",
    (i%5)?"":"Buzz");
  }
}

It does look like it works and it's only one line, but there's a trick to it. The output depends on the fact that it uses '\r' carriage return character, which means that the number is always displayed, but hidden when FizzBuzz occur. Visually, it's the same thing, but if you check the output via program such as diff, then it will fail. Still, that's a neat hack that you can do to impress people!

FB5

void FizzBuzz5() {
  int i=0;
  while(100>i++){switch(p("%s%s",(i
  %3)?"":"Fizz",(i%5)?"":"Buzz")) {
  case 0:p("%d",i);default:p("\n");
}}}

FB6

void FizzBuzz6() {
  for(int i=0;100>i++;)
  switch(p("%s%s",(i%3)
  ?"": "Fizz",(i%5)?"":
  "Buzz")){case 0:p("%d"
  ,i);default :p("\n");
}}

Then again, there is impressive, and just plain old ridiculous! There's only a fine line between the two.

One more thing: If you're wondering what's p(), it's printf(). I simply define it in the beginning of the program.

Day 10/100 Happy Number

 Day 10/100 Happy Number

Happy Numbers are all alike

A happy number is a number that is having the sum of the squares of the digit to equals to 1. If it isn't 1, repeat until it does. Those numbers that does not reach 1, are unhappy numbers.

This is LeetCode 202, for those following LeetCode challenges. There are so many solutions. However, like most coding problems, there are different considerations regarding optimizations. Do you optimize for speed, or for memory?

This is a question that many programmers don't think about. Most of them simply put everything into hash, and be done with it. A little careful consideration will yield an analysis that basically tells you that the sequence of happy numbers will not exceed that of 999. In fact, on the leetcode official solution, that number was pegged at 243, due to the fact that the next number in sequence after 999 is 243.

That's nice. However, that is not good enough for me. Remember the high/low, mountain/valley problem? We only mark the top of the hill, or the bottom of the valley. In those cases, what are the numbers? Here is my first version of happy number program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXENTRY 1000
int Mark[MAXENTRY];
int happyLast;
int happyMax;
int happyMin;

int nextN(int M) {
  int N=0;
  while (M>0) {
    N+=(M%10)*(M%10);
    M/=10;
  }
  return N;
}

 

int IsHappy(int N) {
  if (N<1) return 0;
  while (1) {
    if (N<MAXENTRY) {
      if (N==1) return 1;
      if (Mark[N]) return 0;
      Mark[N]=1;
    }
    happyLast=N; N=nextN(N);
    if (happyLast>N && happyMin>N) happyMin=N;
    if (happyLast<N && happyMax<N) happyMax=N;
  }
}

 

int main (int argc, char *argv[] ) {
  int n,i;
  for (n=50000;n;n--) {
    for (i=0;i<MAXENTRY;i++) Mark[i]=0;
    happyMin=MAXENTRY; happyMax=0;
    if (IsHappy(n)) 
      printf("%d is happy. %d %d\n",n,happyMin,happyMax);
    else 
      printf("%d is unhappy. %d %d\n",n,happyMin,happyMax);
  }
  return 0;
}

If you notice, I track the minimum and maximum for each happy numbers. This is because I want to see for myself, what the range is for each numbers. You don't see that anywhere else. It's as if people just blindly copy solutions from each others. Speaking of which, here's the other solution, version 2. Diff is between version 1 and version 2:

19a20
> //  printf("%d\n",N);
28c29,36
<       if (Mark[N]) return 0;
---
>       if (N==100) return 1;
>       if (N==130) return 1;
>       if (N==2) return 0;
>       if (N==3) return 0;
>       if (N==4) return 0;
>       if (N==145) return 0;
>       if (N==162) return 0;
> //      if (Mark[N]) return 0;

As you can see, I no longer use the array to mark visited numbers. This is a great savings for memory. You also see different numbers for happy, such as 100 and 130, as well as for unhappy numbers.

By the way, the official solution shows that you only need to check number 4 for unhappy number. Somebody also pointed out that if the number is below 10, then only number 1 and 7 are happy. So that certainly saves some comparison. 

But is it faster? Let's see the timings.

Version 1: This version is the simple version, uses an array.

user 0m1.044s

Version 2: Skips the array. Uses the numbers as above.

user 0m0.390s

Version 3: Only checks number 1 and 4.

user 0m0.471s

Version 4: Removes checks for 3 and 162.

user 0m0.353s

As you can see, the simple version 1 takes the longest, and uses the most memory. Version 2, which takes account of actual minimum and maximum for each number, is not only memory efficient, but also much faster.

Version 3, which does only minimal checks, takes no memory and relatively fast, but is still slower than version 2.

Version 4, takes a look at the numbers, and removes the least important ones. There's only a solitary 3, and a smatterings 162. The program runs slightly faster without them.

Here is the last and most efficient version 4:

#include <stdio.h>

int nextN(int M) {
  int N=0;
  while (M>0) {
    N+=(M%10)*(M%10);
    M/=10;
  }
  return N;
}

int IsHappy(int N) {
  if (N<1) return 0;
  while (1) {
    if (N==1 || N==100 || N==130) return 1;
    if (N==2 || N==4   || N==145) return 0;
    N=nextN(N);
  }
}

int main (int argc, char *argv[] ) {
  int n,i;
  for (n=50000;n;n--) {
    if (IsHappy(n)) printf("%d is happy\n",n);
    else printf("%d is unhappy\n",n);
  }
  return 0;
}

One more thing:

That is not the only speed improvement possible. I can also do frequency analysis, looking at the most visited numbers, and check that. But that is an endeavor without end.  In case you're wondering, though: 4, 16, 20, 37, 42, 58, 89, 145 are frequently visited numbers, and those are the numbers in the cycle. 

Running time: user 0m0.290s

Day 9/100 Higher and Lower

 Day 9/100 Higher and Lower

Levels and Sequences

Last time, on Day 8, I explored LeetCode 845 and 2210. I'm continuing the exploration with LeetCode 300 and 315. I'm going to do 315 first, since that one is easy. All I have to do is basically take the value of each data in an array, and check whether the subsequent value is higher or lower from that initial value.

LeetCode 315 specifies only to count the number of lower values, but since it's so easy, I do it both for higher and lower values. Taking the diff from pnf.c (Day 7) and LeetCode 315:

LeetCode 315

29a30,35
> #define MAXENTRY 10000
> float DataV[MAXENTRY];
> int DataL[MAXENTRY];
> int DataH[MAXENTRY];
> //tstamp is num of entry
> 
100a107,123
> void Count() {
>   int i=0;
>   for (i=0;i<=tstamp;i++) {
>     if (i==tstamp) { DataV[i]=Adj; DataL[i]=DataH[i]=0; }
>     if (i<tstamp && DataV[i]>Adj) DataL[i]++;
>     if (i<tstamp && DataV[i]<Adj) DataH[i]++;
>   }
> }
> 
> void CountDisp() {
>   int i=0;
>   for (i=0;i<tstamp;i++) {
>     printf("Entry %3d value %f\t LowCount: %3d\tHiCount:%3d\n"
>            ,i,DataV[i],DataL[i],DataH[i]);
>   }
> }
> 
106a130,132
> 
>     Count();
> 
135a162,163
> 
>   CountDisp();

That's too easy! I count only 8 line significant difference from the original. Really, there's nothing to explain since it's self explanatory. Anyway, onto LeetCode 300. This time, take LeetCode 315 and patch this diff in:

LeetCode 300

111,112c111,112
<     if (i<tstamp && DataV[i]>Adj) DataL[i]++;
<     if (i<tstamp && DataV[i]<Adj) DataH[i]++;
---
>     if (i<tstamp && DataV[i]>Adj) { DataL[i]++; DataV[i]=Adj; }
> //    if (i<tstamp && DataV[i]<Adj) { DataH[i]++; DataV[i]=Adj; }
117c117
<   int i=0;
---
>   int i=0; int max=0;
119,120c119,121
<     printf("Entry %3d value %f\t LowCount: %3d\tHiCount:%3d\n"
<            ,i,DataV[i],DataL[i],DataH[i]);
---
>     printf("Entry %3d value %f\t LowCount: %3d \tHiCount: %3d\n",i,DataV[i],DataL[i],DataH[i]);
>     if (max<DataL[i]) max++;
> //  if (max<DataH[i]) max++;
121a123
>   printf("Longest sequence is: %d\n",max);

As far as the longest sequence is, I'm only counting one or the other. I could have counted both at once, but that requires an extra storage for DataV[]. The reason being is that although the algorithm is the same, for tracking sequence, the value of DataV[] is updated every time there is a count. And that's about the only significant difference between the two.

So, you choose: You can either count the low, the high, or put in an extra array variable to count both.

As you can see, leveraging existing program can do wonders for your development time. This is the concept behind "code reuse" although I suppose the term is more closely associated with either code library or objects (in OO paradigm), as opposed to hacking old program to do something new.

Experience speaking, sometimes the necessary change is rather drastic, and you need to change the program's core. In that case, it may be easier, faster, and better to just start a new program from scratch.

Happy coding!

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.

Pascal Triangle 3/100

 Pascal Triangle 3/100

Running out of screen space!

Day 3 of 100 Days of Code

So, Leetcode has this problem of creating Pascal triangle. And I've seen the solutions that people put up. It's vector this, list that, and I think doing it that way is overkill. What's with push-pop and all that jazz.

Personally, I think a single dimensional array suffice. After all, you're not computing beyond the last line, and that you can compute in either direction. Every solution I saw was from 0-N, whereas I do N-0, and save myself an extra array!

Computing the values is one thing. Displaying it is another, and I found out real quick that I don't have a big enough monitor to display more that 20 lines of values without losing the shape of the triangle. By the way, I redid the algorithm for displaying the triangle, so no more recursion being used from Day 1 program.

#include <stdio.h>
#include <stdlib.h> 

int PascalTri(int N) {
  int rows[100]; int i,j; 

  if (N<0 || N>20) return 1; //Out of bounds!
  rows[0]=1; for (i=99;i;i--) rows[i]=0;
  for (i=0;i<N;i++) {
    for (j=N-i-1;j;j--) printf("   ");
    for (j=0;j<=i;j++) printf(" %5d",rows[j]);
    puts("");
    for (j=i+1;j;j--) rows[j]+=rows[j-1];
  }
  return 0;
} 

int main (int argc, char *argv[] ) {
  int e=0;
  if   (argc<2) puts("Usage: pascaltri N\n");
  else e=PascalTri(atoi(argv[1]));
  if (e==1) puts("Error: Range is 0-20 inclusive.");
  return e;
}

One final note: Turns out that there is a way to mathematically compute the values so that I don't even need the array. Alas, I'm no mathematician.