Regular Expression Note in Ruby

What does regular expression do
Given a string, and a pattern, find if the string contains the pattern as a sub-string.

Ruby's syntax
/cat/ => matches string "cat"
/t a b/ => matches "hit a ball"
#matching
/cat/ =~ "cat and dog"

Changing Strings
"my name is saif".sub(/saif/, "Joseph")

gsub replaces all the matches
gsub! affects original string

Regex options
i => case insensitive
o => subsititue once
m => multiple line
x => allow space

Special characters
. + \ ^  * $  ? | ( ) { } [ ]

Anchors
^ : start of a line. /^abc/ => matches "abc def ghe"
$ : end of a line
\A : matches begining of a string
\z : matches end of a string
\Z: matches end of a string unless ends with \n
\b : word boundary
\B: non-word boundary

character class
/[aeiou]/ => matches a vowel character
/[0-9]/ => matches any digit between 0 through 9
/[^0-9]/ => matches anything other than a digit

Ruby option provide
/(?d)\w+/ => a is default character set support
/(?u)\w+/ => matches full unicode characters
/(?a)\w+/  => matches ascii characterset

Posix character class
[[:digit:]] => matches a digit
[[:^digit:]]] => anything except a digit
/\p{Alnum}/ => match a alpha numberic unicode character
period outside [] represents any character
/c.s/ => matches cos

Repetition
r* => zero or more occurrences of r
r+ => one or more
r? => zero or one
r{m,n} =>at least m, at most n
r{m,} => at least m
r{,n} => at most n
r{m} => exactly m

greedy repetition reg_exp+
lazy repettion reg_exp+?
possesive repettion reg_exp++


Alternation
'|' has very low precedence
/d|e/ => matches d or e

grouping
/red (ball|angry) sky/
$1 accesses the first group from outside of the regular expression, \1 from inside the regular expression.

named groups
/(?<first>w+)\k<first>/

lookahead (?=reg_ex)  negated version (?!re_ex)
str = "red, white, and blue"
str.scan(/[a-z]+(?=,)/) # => ["red", "white"]

look behind (?<=reg_exp) negated version (?<!re)

Controlling back tracking
inhibit backtracking: (?>reg_exp)
/((?>X+))(?!O)/ => matches XXXY but not XXO
possesive repetition can be used as well
/(X++)(?!O)/

Back reference to named groups
declaration: (?<name>reg_exp)
reference: \g<name>, \g can be used recursively
re =
/
  \A
    (?<brace_expr>
      {
         (
            [^{}]
           |
            \g<brace_expr>
         )*
      }
    )
/x

conditional group
declaration (?<name>reg_exp)
usage (?<name>...)

alternative in conditions
(?(group_id) true_pattern | false_pattern)

/(?:(red)|blue) ball and (?(1)blue|red) bucket/x  # blue ball and red bucket matches

named sub-routine
sentence = %r{
  (?<subject> cat | dog ) {0}
  (?<verb> eats | drinks ) {0}
 The \g<subject> \g<verb>
}

[Book Take Away] Farmer Boy

This book talks about an American Farmer Almanzo Wilder's childhood. I am very fond of the American way of life. I love the way the American people value freedom and above everything else. This book talks about many of American values. From this book I have learnt a quite a few things
a. Some people would put being free above everything else. That's why some people want to be a farmer. They won't like to be depended on other people. Even if that would cause them more works to do, they would have to depend on their weather and land and they might have to wake up a night to see if their cattle is freezing or not. Some people would not put their decisions to other people.
b. The way farmers break their colt and their oxen can be applied to day to day life. A farmer would be very careful about a young horse. They make sure that they are not startled when they are young. If you trouble a horse when it is young, it will be habituated for disobedient and will be a spoiled horse.
c. It is not good to put a huge amount of load to a Ox in the beginning. Because initially if they fails, they will always tend to give up.
d. We need to let choose people what they want to be in life or what they want to be. This is exactly what Almanzo Wilder's parents did.
e. We need to be frugal and not to waste money on things that we don't want. We cannot be lazy and waste time on unnecessary stuffs.
f. Like a good farmer we need to be prepared for future. 

[Philosophy] Walking Alone

I love to walk alone. This gives me a chance to reflect on a problem or think about something, on the least it lets my brain sometime to process some information. It becomes tempting sometimes to walk with someone else. I have found this, walking with someone else almost always makes me unhappy. Most of the time it is because I say mostly unnecessary things. It makes me sad later, I keep thinking why I have said those unnecessary things in the first place.

Next time when I am tempted to walk with someone, I need to remember these

0. I will almost be unhappier after the walk.
1. I will most likely say something that I will feel sorry inside me.
2. I would not get a chance for reflection.

I should walk alone whenever possible. When I am talking, I am not walking.

[Algorithms][DP] Thinking in DP 3

10. Maximum Sum Increasing Sub-sequence:
Problem: Given an array of numbers, a, find the sub sequence that holds the following properties

1. It is in increasing order
2. The sum is the maximum

Example: For {1, 101, 2, 3, 100, 4, 5}, the output would be 106 (1 + 2 + 3 + 100).

Recurrence: f(i) = max( f(j) + a[j] ), where, 0<= j < i and a[i] > a[j] 

Base case: f(0) = a[0]

Runtime: Number of sub-problems = O(n) 

Time to solve a sub-problem = O(n)

Total runtime = O(n ^ 2).

11. Largest Chain
Problem: Given n pairs find the maximum chain. 2 pairs (a, b) and (c,d) can form a chain if b < c.
Example: Given an array of pairs arr,  {(5, 24), (39, 60), (15, 28), (27, 40), (50, 90) }, then the longest chain that can be formed is of length 3, and the chain is {(5, 24), (27, 40), (50, 90)}.
Recurrence: f(i) = max( f(j) ) + 1, where 0 <= j < i; arr[j][1] < arr[i][0]
Base case: f(0) = 1
Runtime: Number of sub-problems = O(n)
Time to solve a sub-problem = O(n)
Total runtime = O(n ^ 2)

12. Longest Common Substring
Problem: Given 2 strings, find the longest substring.
Example: Given, ϵABCDE, ϵXBCDG, then longest common substring = BCD. All string starts with empty, ϵ.
Recurrence: 
                   {   if s1[i] == s2[j] then f(i-1, j-1) + 1
     f(i, j) =  {           
                   {   max( f(i-1, j), f(i, j-1) )
Base case: f(i, j) = 0
Runtime: Number of sub-problems = O(n ^ 2) as we have 2 indices i, j.
Time to solve a subproblem = O(1)
Total runtime = O(n ^ 2)

13. Catalan number
Problem: (n+1) th Catalan number, C_(n+1) = sum ( C_i * C_(n-i) )
Recurrence: See above
base case, C_0 = 1
Runtime: Number of sub-problems = O(n)
Time to solve a sub-problem = O(n)
Total runtime = O(n ^ 2)

14. Count Number of Ways to Reach a Given Score
Problem: The array pts gives the achievable point from any state of a game. Given a point n, find the number of ways those points can be reached.
Recurrence: f(i) = sum(f(i - pts[k])) for all 0 <= k < lenght (pts)
Runtime: Number of sub-problems = O(n)
Time to solve a problem = O(k)
Total Runtime = O(n * k)

[Story] Only the necessary things!

Oliver is a new driver. He has been trying to understand the basics of driving. Initially it seemed like a lot of rules, road signs and laws to deal with. When you are driving, you need to constantly look in front, look to the front at the left and right side of the road, using mirrors constantly check left and right of the car's back, using rear-view mirror check the back of the car. And every driving experience seemed to be a new experience. To him, all these aspects of driving seemed discrete and hard to relate.

Eventually he realized driving is mostly about doing the things that you absolutely need to do. For instance, driving faster than the speed limit is not necessary, if you want to change a lane and it is not safe to do so at the time then it is not necessary to change lane that moment of time, just take your time, keep going on, when it is safe, change lane. Also, it is not necessary to slam the break suddenly most of the time if you are paying attention.

Driving is about being conscious of the surrounding and do what is necessary. You need to know what is in front of you, what is far ahead, what is on your side and back.

You do not take action abruptly. You do not suddenly change lane or hit the break. If you want to change lane, you need to convey your intentions before hand by putting on turn signals so that other people on the road know what you are going to do. All other drivers will help you if you communicate properly and do not rush.

The intersections and lane changes are interesting parts. When you are on a intersection, this is the place where a road for two drivers overlaps. You need to be alert and let any car on the intersection go first. You need to clear the intersection as soon as you can safely. When you are changing lanes, you are attempting to get into other driver's drive way. Let them know your intention through signals, check blindspots to make absolutely sure that no car is in the place where you are trying to be. You need to speed up little bit while changing lane so that you do not interrupt the other driver's space.

At any given time, there are many people on the road with different state of mind. Some might be on rush, some might be new drivers like Oliver, some might be drunk or some might be having a medical condition. So it is very likely that something unexpected might happen. Some driver can cut in front him without proper signaling. Some pedestrian might be crossing the road dangerously, some driver can ignore the red signal or some driver can honk at him. It is good to accept the unexpected and act accordingly. Should something unexpected happens, he should not let go his cool, instead he should take it easy and accept these unexpectedness, take necessary steps and keep moving on without thinking about the past.


A few things driving teaches us

1. Know the rules of the road. We need to know what means what and should be aware of known incidents.
2. Safety first.
3. Know where you want to go and what you want to do.
4. Be mindful. Know what is in front, on sides and on back. 
5. Do not do anything if you absolutely have to do. For instance, you missed an Exit? Do not try to adjust your route right away and back up from there to exit. Instead keep moving on, take the next exit.
6. Do not take an action abruptly. Have a plan. Let others know what you are trying to do.
7. When sharing space with others, be extra careful (like when you are on an intersection or changing lanes).  
8. Expect the unexpected. Someone will always do something unexpected or stupid. Don't let stupid actions of others take your peace of mind. Take proper actions, keep moving on.

And surprisingly, the above are the basic teaching of Buddha!

[MATHEMATICS] Mendelbrot and Julia set

Background
When we define functions recursively, such as
f(t) = f(t-1) * f(t-1) + c
A few cases might arise, as we keep increasing number of iterations, t.
Converge: Eventually, f(t) might converge to a zero or non-zero number.
Diverge: f(t) might keep getting bigger and bigger.
Periodic: f(t) might oscillate among 2 or more values.
Chaos: f(t) might produce random values.

There are cases where a function behave might differently with the choice of base case and other constants in this case f(0) and c. For,
Example: f(t) = r * f(t - 1) * (1 - f(t - 1))
f(0) = 0.2, r = 1, f(t) converges to zero.
f(0) = 0.2, r = 2, f(t) converges to 0.52
f(0) = 0.2, r = 3, f(t) is a attenuating-oscillating function
f(0) = 0.2, r = 4 f(t) is a chaotic function

For a function, for a specific set of points in a closed boundary used as the choice for f(0) or c, the f(t) might converge or diverge fast or slowly.

Mendelbrot and Julia set
For Mendelbrot set, the function is defined as the following
f(t) = f(t-1) * f(t-1) + c
f(0) = 0 and c is chosen from numbers from complex number domain from the following rectangular boundary,
bottom-left = -2.25 -1.5i
top-right = 0.75 + 1.5i

Algorithm to generate the plot
We count number of iterations, t, for which magnitude(f(t)) reaches to 4. If f(t) converges, we say it took MAX_ITERATIONS to converge. We put computed iteration counts in a 2D array. Plotting the 2D array in 2D plane gives a visualization of the Mendelbrot set. Yellow regions depicts those points that converges so for them iterations count = MAX_ITERATIONS. Darker points say that they diverge very quickly.

f(0) = 0, c ranged from (-0.22 -0.7i to 0.75 -0.21i)

For Julia set, we fix c, and vary f(0) from a complex number boundary.

                              c = -0.35 + 0.65i and f(0) ranged from -2 to +2 in complex plane

c = -0.77 + 0.13i and f(0) ranged from -1 to +1 in complex plane

Reference:

0. Make your own Mendelbrot by Tariq Rashid

1. Github source code

[Algorithms][DP] Dynamic Programming Explained - 1

Dynamic programming systematically checks all possibility of a given problem.

To solve using dynamic programming, we need to come up with a way to recursively solve a problem. The recursion should be of format of DAG, a bigger sub problem should be depended on a smaller subproblem. Dynamic problem will not work if a smaller sub-problem depends on a bigger sub-problem.

Dynamic programming problem is a favorite choice of interviewers, at it tests understanding of recursion of an interviewee.

Steps to apply dynamic programming for a given problem
0. Check if the problem can be solved using recursion. Think if you have n items, can you solve the problem if you already know solution for n-1 th item. Consider each sub problem an optimal solution. If you know an optimal solution to all reachable lower state, how can you reach higher state with that knowledge.
1. If 0 holds, write the problem in terms of smaller problem. Observe how many variables you need. The number of variables determines the dimension of the array you will need to store solution.
2. Guesses is the number of steps your algorithm needs to combine small solutions to big solution.
3. From variables, determine how many sub problems will be there. Remember, recursive function calling is cheap O(1) time if dynamic programming is used. Guesses * number of sub problems will give the order of the algorithm.

Example:
problem: find fibonacci number

Using recursion:
fibonacci(i) = fibonacci(i-1) + fibonacci(i-2)

number variables is 1 (only i). Which means Number of sub problems = n;
Guesses = O(1) [fibonacci(i-1) + fibonacci(i-2) can be evaluated in O(1) time. Recursion is cheap for dp]

O(algorithm) = O(subproblem_count * guesses_at_each_subproblem) = O(n)

Another Example:
Rod cutting problem. An i lengthed rod can be cut in 2 spots. We need to find the maximum profit we can make out of it.

profit(i) = max(profit(j) + profit(i-j)) for all 0 < j < i-1

here # of variables = 1 => # subproblems = n
#guesses = O(n) [need to generate all points from 1 to i-1 for length i]

O(n * n) = O(n ^ 2)

Yet Another Example:
Knapsack problem
profit(i, capacity) = max(
                                         profit(i-1, capacity), //don't take i th element
                                         profit(i-1, capacity-w[i]) + val[i] //take ith element
                             )
we see 2 variables here. #subproblems = item_count * bag_capacity
#guesses = O(1)

O(algorithm) = O(item_count * bag_capacity)

this is a pseudo polynomial runtime. if bag_capacity is increases, we will need bigger array to store the intermediate results.