2020-06-26

All the world's a stage

All the world’s a stage,
And all the men and women merely players;
They have their exits and their entrances,
And one man in his time plays many parts,
His acts being seven ages. At first, the infant,
Mewling and puking in the nurse’s arms.
Then the whining schoolboy, with his satchel
And shining morning face, creeping like snail
Unwillingly to school. And then the lover,
Sighing like furnace, with a woeful ballad
Made to his mistress’ eyebrow. Then a soldier,
Full of strange oaths and bearded like the pard,
Jealous in honour, sudden and quick in quarrel,
Seeking the bubble reputation
Even in the cannon’s mouth. And then the justice,
In fair round belly with good capon lined,
With eyes severe and beard of formal cut,
Full of wise saws and modern instances;
And so he plays his part. The sixth age shifts
Into the lean and slippered pantaloon,
With spectacles on nose and pouch on side;
His youthful hose, well saved, a world too wide
For his shrunk shank, and his big manly voice,
Turning again toward childish treble, pipes
And whistles in his sound. Last scene of all,
That ends this strange eventful history,
Is second childishness and mere oblivion,
Sans teeth, sans eyes, sans taste, sans everything.

“All the world’s a stage” is the phrase that begins a monologue from William Shakespeare’s pastoral comedy As You Like It, spoken by the melancholy Jaques in Act II Scene VII Line 139. The speech compares the world to a stage and life to a play and catalogues the seven stages of a man’s life, sometimes referred to as the seven ages of man.

2020-06-25

王阳明诗十二首

王守仁

你未看此花时，此花与汝心同归于寂。
你来看此花时，则此花颜色一时明白起来，便知此花不在你的心外。
Before you see the flower, both you and the flower are in a state of isolation. When you see the flower its color and shape become clearer to you — which means that knowledge of the flower cannot exist apart from mind.

答人问道

饥来吃饭倦来眠，只此修行玄更玄。
说与世人浑不信，却从身外觅神仙。

中秋

去年中秋阴复晴，今年中秋阴复阴。
百年好景不多遇，况乃白发相侵寻。
吾心自有光明月，千古团圆永无缺。
山河大地拥情辉，赏心何必中秋节。

王门四句教

无善无恶心之体，有善有恶意之动。
知善知恶是良知，为善去恶是格物。

赠阳伯

阳伯即伯阳，伯阳竟安在？
大道即人心，万古未尝改。
长生在求仁，金丹非外待。
谬矣三十年，于今吾始悔。

书汪进之太极岩

始信心非明镜台，须知明镜亦尘埃。
人人有个圆圈在，莫向蒲团坐死灰。

溪水

年华若流水，一去无回停。
悠悠百年内，吾道终何成！

咏良知四首示诸生

个个人心有仲尼，自将闻见苦遮迷。
而今指与真头面，只是良知更莫疑。

问君何事日憧憧？烦恼场中错用功。
莫道圣门无口诀，良知两字是参同。

人人自有定盘针，万化根源总在心。
却笑从前颠倒见，枝枝叶叶外头寻。

无声无臭独知时，此是乾坤万有基。
抛却自家无尽藏，沿门持钵效贫儿。

示诸生

尔身各各自天真，不问求人更问人。
但致良知成德业，谩从故纸费精神。
乾坤是易原非尽，心性何形得有尘？
莫道先生学禅语，此言端的为君陈。

啾啾吟

智者不惑仁不忧，君胡戚戚眉双愁？
信步行来皆坦道，凭天判下非人谋。

2020-06-24

贈衛八處士 - Meeting With an Old Friend

贈衛八處士

杜甫

人生不相見，動如參與商。今夕複何夕，共此燈燭光！
少壯能幾時，鬓發各已蒼！訪舊半爲鬼，驚呼熱中腸。
焉知二十載，重上君子堂。昔別君未婚，兒女忽成行。
怡然敬父執，問我來何方？問答乃未已，驅兒羅酒漿。
夜雨剪春韭，新炊間黃粱。主稱會面難，壹舉累十觞。
十觞亦不醉，感子故意長。明日隔山嶽，世事兩茫茫。

Show English translation

2020-06-19

Stray Birds

by Rabindranath Tagore

6
IF you shed tears when you miss the sun, you also miss the stars.

18
WHAT you are you do not see, what you see is your shadow.

20
I CANNOT choose the best.
The best chooses me.

22
THAT I exist is a perpetual surprise which is life.

24
REST belongs to the work as the eyelids to the eyes.

25
MAN is a born child, his power is the power of growth.

40
DO not blame your food because you have no appetite.

48
The stars are not afraid to appear like fireflies.

51
YOUR idol is shattered in the dust to prove that God’s dust is greater than your idol.

52
MAN does not reveal himself in his history, he struggles up through it.

56
LIFE is given to us, we earn it by giving it.

65
TINY grass, your steps are small, but you possess the earth under your tread.

75
WE read the world wrong and say that it deceives us.

79
MAN barricades against himself.

82
LET life be beautiful like summer flowers and death like autumn leaves.

84
IN death the many becomes one; in life the one becomes many.
Religion will be one when God is dead.

90
IN darkness the One appears as uniform; in the light the One appears as manifold.

99
DEATH’S stamp gives value to the coin of life; making it possible to buy with life what is truly precious.

117
THE grass-blade is worth of the great world where it grows.

130
IF you shut your door to all errors truth will be shut out.

134
THE roots below the earth claim no rewards for making the branches fruitful.

139
TIME is the wealth of change, but the clock in its parody makes it mere change and no wealth.

149
THE world has opened its heart of light in the morning.
Come out, my heart, with thy love to meet it.

167
THE world has kissed my soul with its pain, asking for its return in songs.

176
THE water in a vessel is sparkling; the water in the sea is dark.
The small truth has words that are clear; the great truth has great silence.

193
A MIND all logic is like a knife all blade.
It makes the hand bleed that uses it.

203
THE day, with the noise of this little earth, drowns the silence of all worlds.

204
THE song feels the infinite in the air, the picture in the earth, the poem in the air and the earth;
For its words have meaning that walks and music that soars.

206
LET me not put myself wrongly to my world and set it against me.

211
GOD’s right hand is gentle, but terrible is his left hand.

217
THE service of the fruit is precious, the service of the flower is sweet, but let my service be the service of the leaves in its shade of humble devotion.

222
THE world does not leak because death is not a crack.

225
THE fountain of death makes the still water of life play.

231
SET bird’s wings with gold and it will never again soar in the sky.

242
THIS life is the crossing of a sea, where we meet in the same narrow ship.
In death we reach the shore and go to our different worlds.

248
MAN is worse than an animal when he is an animal.

252
AROUND the sunny island of Life swells day and night death’s limitless song of the sea.

268
DEATH belongs to life as birth does. The walk is in the raising of the foot as in the laying of it down.

279
WE live in this world when we love it.

282
I SHALL die again and again to know that life is inexhaustible.

284
LOVE is life in its fulness like the cup with its wine.

300
GOD waits for man to regain his childhood in wisdom.

307
LET me not shame thee, Father, who displayest thy glory in thy children.

313
WE shall know some day that death can never rob us of that which our soul has gained, for her gains are one with herself.

316
LET me live truly, my Lord, so that death to me become true.

323
I HAVE suffered and despaired and known death and I am glad that I am in this great world.

Stray Birds By Rabindranath Tagore

2020-06-14

HackerRank - Regex - Assertions

Positive Lookahead

regex_1(?=regex_2)

The positive lookahead (?=) asserts regex_1 to be immediately followed by regex_2. The lookahead is excluded from the match. It does not return matches of regex_2. The lookahead only asserts whether a match is possible or not.

For Example

c(?=o)

is matched with chocolate

Task

gooooo!

o(?=oo)

Negative Lookahead

regex_1(?!regex_2)

The negative lookahead (?!) asserts regex_1 not to be immediately followed by regex_2. Lookahead is excluded from the match (do not consume matches of regex_2), but only assert whether a match is possible or not.

For Example

c(?!o)

is matched with chocolate

Task

If S =goooo, then regex should match goooo. Because the first g is not follwed by g and the last o is not followed by o.

gooooo

1	(\S)(?!\1)

Positive Lookbehind

(?<=regex_2)regex_1

The positive lookbehind (?<=) asserts regex_1 to be immediately preceded by regex_2. Lookbehind is excluded from the match (do not consume matches of regex_2), but only assert whether a match is possible or not.

For Example

1	(?<=[a-z])[aeiou]

is matched with helo

Task

123Go!

1	(?<=[13579])\d

Negative Lookbehind

(?<!regex_2)regex_1

The negative lookbehind (?<!) asserts regex_1 not to be immediately preceded by regex_2. Lookbehind is excluded from the match (do not consume matches of regex_2), but only assert whether a match is possible or not.

For Example

1	(?<![a-z])[aeiou]

is matched with helo

Task

1o1s

1	(?<![aeiuoAEIOU]).

Resources

Regex - Subdomains - Assertions

2020-06-09

LeetCode - Algorithms - 793. Preimage Size of Factorial Zeroes Function

Problem

793. Preimage Size of Factorial Zeroes Function

Relevant problem

An easy problem as 172. Factorial Trailing Zeroes and its solutions: https://hezhigang.github.io/2020/06/06/LeetCode-Algorithms-factorial-trailing-zeroes/

Java

Binary Search strategy

Binary search, also known as half-interval search, logarithmic search, or binary chop, is a general algorithm for linearly ordered data structure, and There are numerous variations of binary search.

Let $ f(x) $ be the number of zeroes at the end of $x!$. We can observe that $ f(x) $ rise when $ x \equiv 0 \hspace{2mm} (mod \hspace{1mm} 5) $,
and $ f(5k)=f(5k+1)=f(5k+2)=f(5k+3)=f(5k+4) $.
$ f(x)=\lfloor \frac{x}{5} \rfloor + \lfloor \frac{x}{25} \rfloor + \cdots + \lfloor \frac{x}{5^n} \rfloor $ where $ \lfloor \frac{x}{5^n} \rfloor \geq 1 $
This geometric sequence with common ratio $ r = \frac{1}{5} $ has a limit that can be computed from the finite sum formula $ \sum_{k=1}^{\infty} \frac{x}{5^k} = \lim_{n \to \infty}\sum_{k=1}^{n} \frac{x}{5^k} = \frac{\frac{x}{5}}{1-\frac{1}{5}} = \frac{x}{4} $, so, there is a inequality that $ \frac{x}{5} < f(x) < \frac{x}{4} $, which gives a small upper and lower bound for binary search algorithm.

class Solution {
    public int preimageSizeFZF(int K) {
        int count = 0;
        long r = search_rank(K);
        count = r==-1?0:5;
        return count;
    }
    
    private long search_rank(long K) {
        long lo = 4*K;
        long hi = 5*K;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long y = f(mid);
            if (K < y)
                hi = mid - 1;
            else if (K > y)
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }

    private long f(long x) {
        long count = 0;
        for (long i = 5; i <= x; i *= 5)
            count += x / i;
        return count;
    }
}

Submission Detail

44 / 44 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Preimage Size of Factorial Zeroes Function.
Memory Usage: 35.6 MB, less than 100.00% of Java online submissions for Preimage Size of Factorial Zeroes Function.

Complexity Analysis

Time Complexity

$ O(NlogN) $ where N is the input integer such that $ f(x)=N $

Space Complexity

$ O(1) $ as there is no extra space other than local varibles.

2020-06-07

HackerRank - Regex - Backreferences

Matching Same Text Again & Again

\group_number

This tool (\1 references the first capturing group) matches the same text as previously matched by the capturing group.

For Example

(\d)\1

It can match 00, 11, 22, 33, 44, 55, 66, 77, 88 or 99.

Task

ab #1?AZa$ab #1?AZa$

1	^([a-z])(\w)(\s)(\W)(\d)(\D)([A-Z])([a-zA-Z])([aeiouAEIOU])(\S)\1\2\3\4\5\6\7\8\9\10$

Backreferences To Failed Groups

Backreference to a capturing group that match nothing is different from backreference to a capturing group that did not participate in the match at all.

Capturing group that match nothing

(b?)o\1

is matched with o

Here, b? is optional and matches nothing.
Thus, (b?) is successfully matched and capture nothing.
o is matched with o and \1 successfully matches the nothing captured by the group.

Capturing group that didn’t participate in the match at all

(b)?o\1

is not matching o

In most regex flavors (excluding JavaScript), (b)?o\1 fails to match o.

Here, (b) fails to match at all. Since, the whole group is optional the regex engine does proceed to match o.
The regex engine now arrives at \1 which references a group that did not participate in the match attempt at all.
Thus, the backreference fails to match at all.

Task

12-34-56-78

12345678

1

1	^\d{2}(-?)\d{2}\1\d{2}\1\d{2}$

2

1	^\d{2}(-?)(\d{2}\1){2}\d{2}$

Branch Reset Groups

NOTE - Branch reset group is supported by Perl, PHP, Delphi and R.

(?|regex)

A branch reset group consists of alternations and capturing groups. (?|(regex1)|(regex2))
Alternatives in branch reset group share same capturing group.

1	(?\|(Haa)\|(Hee)\|(bye)\|(k))\1

is mathched with HaaHaa and kk

Task

12-34-56-78

12:34:56:78

12---34---56---78

12.34.56.78

1	/^\d{2}(?\|(-)\|(:)\|(---)\|(\.)\|){1}(\d{2}\1){2}\d{2}$/

Forward References

NOTE - Forward reference is supported by JGsoft, .NET, Java, Perl, PCRE, PHP, Delphi and Ruby regex flavors.

Forward reference creates a back reference to a regex that would appear later.
Forward references are only useful if they’re inside a repeated group.
Then there may arise a case in which the regex engine evaluates the backreference after the group has been matched already.

1	(\2amigo\|(go!))+

is matched with go!go!amigo

Task

tactactic

tactactictactic

1	^(\2tic\|(tac))+$

Resources

Regex - Subdomains - Backreferences

2020-06-06

LeetCode - Algorithms - 172. Factorial Trailing Zeroes

Problem

172. Factorial Trailing Zeroes

Java

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        for (long i = 5; i <= n; i *= 5)
            count += n / i;
        return count;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 0 ms, faster than 100.00% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 36.6 MB, less than 31.99% of Java online submissions for Factorial Trailing Zeroes.

my solution

Accepted until 4th submission.

class Solution {
    public int trailingZeroes(int n) {
        if (n == 0)
            return 0;
        Double d = Math.floor((Math.log(n)) / (Math.log(5)));
        int m = d.intValue();
        int x = 0;
        for (int i = 1; i <= m; i++) {
            x += n / Math.pow(5, i);
        }
        return x;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 1 ms, faster than 20.14% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 36.6 MB, less than 39.00% of Java online submissions for Factorial Trailing Zeroes.

my solution - 2

class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int m = logarithm(n,5);
        int x = 0;
        for (int i = 1; i <= m; i++) {
            x += n / Math.pow(5, i);
        }
        return x;
    }
    
    private int logarithm(int n, int r) {
        return (n > r - 1) ? 1 + logarithm(n / r, r) : 0;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 1 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 38.6 MB, less than 5.16% of Java online submissions for Factorial Trailing Zeroes.

my solution - 3

class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        long x = 0;
        long p = 5;
        while (n >= p) {
            x += n / p;
            p *= 5;
        }
        Long l = new Long(x);
        return l.intValue();
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 1 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 36 MB, less than 94.80% of Java online submissions for Factorial Trailing Zeroes.

my solution - 4

class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int x = 0;
        for (long p = 5; n >= p; ) {
            x += n / p;
            p *= 5;
        }
        return x;
    }
}

Submission Detail

502 / 502 test cases passed.
Runtime: 2 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
Memory Usage: 38.1 MB, less than 10.66% of Java online submissions for Factorial Trailing Zeroes.

2020-06-05

LeetCode - Algorithms - 169. Majority Element

There are many solutions to an easy problem.

Problem

169. Majority Element

Java

sorting

import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        final int len = nums.length;
        Arrays.sort(nums);
        return nums[len >> 1];
    }
}

Submission Detail

46 / 46 test cases passed.
Runtime: 1 ms, faster than 99.67% of Java online submissions for Majority Element.
Memory Usage: 42.9 MB, less than 72.59% of Java online submissions for Majority Element.

brute force

class Solution {
    public int majorityElement(int[] nums) {
        int half = nums.length >> 1;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i : nums) {
            Integer k = new Integer(i);
            if (map.containsKey(k)) {
                map.put(k, map.get(k)+1);
            }
            else {
                map.put(k, 1);
            }
        }
        int major = nums[0];
        for(Map.Entry<Integer, Integer> e : map.entrySet()) {
            if (e.getValue()>half) {
                major = e.getKey();
                break;
            }
        }
        return major;        
    }
}

Submission Detail

46 / 46 test cases passed.
Your runtime beats 37.72 % of java submissions.
Your memory usage beats 14.52 % of java submissions.

Boyer-Moore Voting Algorithm

class Solution {
    public int majorityElement(int[] nums) {
        int count=0;
        int candidate = nums[0];
        for(int num : nums) {
            if (count==0)
                candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;        
    }
}

Submission Detail

46 / 46 test cases passed.
Runtime: 1 ms, faster than 99.67% of Java online submissions for Majority Element.
Memory Usage: 42.2 MB, less than 99.93% of Java online submissions for Majority Element.

2020-06-01

The Rainbow

by Christina Rossetti

Boats sail on the rivers,
And ships sail on the seas;
But clouds that sail across the sky
Are prettier than these.

There are bridges on the rivers,
As pretty as you please;
But the bow that bridges heaven,
And overtops the trees,
And builds a road from earth to sky,
Is prettier far than these.

贈衛八處士

Meeting With an Old Friend

Positive Lookahead

For Example

Task

Negative Lookahead

For Example

Task

Positive Lookbehind

For Example

Task

Negative Lookbehind

For Example

Task

Resources

Problem

Relevant problem

Java

Binary Search strategy

Submission Detail

Complexity Analysis

Time Complexity

Space Complexity

Matching Same Text Again & Again

For Example

Task

Backreferences To Failed Groups

Capturing group that match nothing

Capturing group that didn’t participate in the match at all

Task

1

2

Branch Reset Groups

Task

Forward References

Task

Resources

Problem

Java

solution of geeksforgeeks © Count trailing zeroes in factorial of a number

Submission Detail

my solution

Submission Detail

my solution - 2

Submission Detail

my solution - 3

Submission Detail

my solution - 4

Submission Detail

Problem

Java

sorting

Submission Detail

brute force

Submission Detail

Boyer-Moore Voting Algorithm

Submission Detail