Should one study programming by doing hard problem? As one learns programming, how useful it is to spend time to solve hard problems? Like, I saw a problem solving site where one task is for example to find a regular expression for decimal numbers divisible by 9 or do regular expression for a particular problem that is as small as possible (in sense of number of characters in the expression). Is there worth of spending time to try those kind of problems or should one always try to solve problems as easily as possible?
It is probably a mistake to always do one or the other. If you are learning a hard task (becoming a competent programmer), it isn't helpful if you mix in another hard task as well (hard problems). Initially, it is good to write programs for problems that you already understand well, so that you can focus on the creation. A program has both form and content. If you work on very hard problems exclusively, it is possible that you will wind up just hacking a solution together without any elegance. 

But if you never solve hard problems it won't become clear to you why advanced programming structures and paradigms are needed. 

My advice would be to start out your programming education with fairly easy problems - that you can get your mind around easily. But mix in a harder problem or two as you go. Then when you become more proficient with the forms, move to harder problems and occasional very hard ones. 

You are stretching your brain in two dimensions here. Eventually you want it to be very flexible. But you can stretch more in one dimension than the other at a time. If your problems are so difficult that you get frustrated then you may not make much progress on any dimension. 

And, of course, problems that seem hard to a novice programmer, may not seem very hard to a pro. You learn a lot of tricks-of-the-trade as you go along. 

Also the problem that you mentioned doesn't result in a very big program. It is a bit tricky, of course, but very small as programs go. You want to reach a place where you can intelligently create very large programs.