Knight's tour

March 15, 2018

Introduction

It is very classical dynamic programming called Knight's tour. The problem statement is here on stackoverflow.com.

The most important thing is to know that we only need to count the number of phone numbers, but we do not need to know what numbers for each phone number. The second tip is to know that there are 10 numbers for each step at most.

Algorithm practice

Here is my C# algorithm.

My problem is that it takes me too long to come out the idea and write a solution. I need to make it fit into 20 minutes, 6 to 8 minutes to come out the idea, and I should be able to write the algorithm in less than 10 minutes.

Thinking process

We all know that most important is thinking process. Of course I had long thinking process this time. I drew something on paper, and I took time to think and play with the example.

What I like to do it to make some presentable notes here and document my thinking process. Good thinking process is the gold, the coding part is easy specially for dynamic programming algorithm.

1   2    3

4   5    6

7   8    9

    0

We can tell that 1 can reach 6 and 8. Please check next row and then next column. we denote that knights[1] = new int[]{6, 8}.
Same applies to each number in the first row, next row.

One thing I have to pay attention is number 6, there are 3 numbers to reach, row above, row below, column before, knights[6] = new int[]{0, 1, 7}.

Let us call it first play.

Next play is to work on a graph using those numbers as node, and then connections as edges. It is directed graph as well. Originally in my practice, my drawing is kind of messy. In the following, I try to simplify and make the drawing more readable.

For example, knights[1] = new int[]{6, 8}, I will draw like the following:


0   1    2    3    4   5     6    7    8    9

     ----------------------->

    ------------------------------->


And then we need to add knights[0] = new int[] { 4, 6},

0   1    2     3      4     5    6    7    8    9

------------------->

------------------------------>

We can use depth first search, but time complexity is too high using depth first search. We do not care the path detail. There are so many paths, all we care about the total number of paths.

Once I decide to use a table to store all intermediate result. I have ideas to solve the problem using polynomial time.

Suppose that we start from number 1, and then go over 4 steps and see how many results we can generate.


3              1       3    4     2
2    2   1       1            1
1    0   0   0  0  0 0  1 0  1   0
0    0   1   0  0  0 0  0 0  0   0
-------------------------------------------------
     0   1   2  3  4 5  6  7  8   9

Dynamic programming article

Feb. 14, 2018

Introduction

Chinese is my mother language. I like to see if I can learn dynamic programming quickly by reading some article in Chinese.

I started to review dynamic programming from the most popular blog in Chinese written in 2014. Here is the blog.

Study notes

One thing I like to do is to go over the blog word by word, and organize it better for me to read next time.

Here is one of articles I read and I saved the content to the gist.

10 steps to master dynamic programming (step II)

June 19, 2017


Plan to work on interviewbit.com dynamic programming tutorial. Here is the link of dynamic programming algorithms.

10 steps to master dynamic programming (step I)

June 9, 2017

Introduction

It takes a lot of practice to learn dynamic programming. As a Leetcode player, Julia learns very patiently to work on Leetcode 123 - buy and sell stock, even at most 2 transactions. Julia has to learn quickly to use dynamic programming to solve problem, and then build a recurrence formula like a mathematician. She will figure out how to do it.

First step to learn again is to play this rename game on stackexchange.com discussion post.

Dynamic Programming should be renamed

Discussion is here.

Dynamic programming

Julia's favorite verse:

Smart recursion plus memoization leading to a faster algorithm.
How to recognize that a problem may admit a smart recursion and come up with it? A common case is divide and conquer.

A

Any recurrence whatsoever

D

defining the subproblems
recursively solving the subproblems

F
frugal bottom-up recursion

I
Inductive Programming
Reverse Inductive Programming

L

Linear programming, integer programming, semidefine programming
Extract a recursive structure from the problem, and write down as a recurrence ( modeling)
"Solve the obtained recurrence in a bottom-up way"  (algorithms)

M

Multistage planning

Multiway-Divide and Memoized-Conquer, and Merge all subproblems

Memoiztion

O
Overlapping-divide-and-conquer

R
Reverse Inductive Programming
Recursive view
Recursive horizon

S
Splice-and-combine

To go with divide-and-conquer

Or overlapping-divide-and-conquer


Smart recursion, but not tables "table and fill"

T

Tabular/ tabulated recursion
Tabular call caching

Tables are sometime used.
Dynamic programming over trees (Maximum independent set), it uses a tree, or in some cases a tree of arrays,
or an array of trees, or in some cases a Cartesian product of trees.

Actionable Items

Google some keywords in the following list:

frugal bottom-up recursion

Tabular/ tabulated recursion

Maximum independent set

Overlapping-divide-and-conquer

Study the ICPC coach website: a Utah professor with great performance on Hackerrank.

Leetcode 123: Buy and sell stock III

June 8, 2017

Problem statement

It is hard level algorithm. And it can be solved using dynamic programming. It is challenging task to solve a dynamic programming algorithm.

Now it is 10:39 pm, Julia likes to choose a topic to do a short research, what you should do if the algorithm is too hard to solve? 30 minutes research.

10 steps to master dynamic programming

1. Watch a video to relax, I found one - google developer talked about competitive programming. Here is the link, 1 hour 44 minutes.

2. Read a math lecture note from brown university, lecture note is here. Read a mathematician web page and learn some research idea here.

3. Dynamic programming should be renamed. Discussion is here.

4. Read a median age article and talk about AWS - link is here.

5. Work on interviewbit.com dynamic programming problems, the link is here. (June 16, 2017)

Follow up 

June 9, 2017

Julia's C# practice is here.

June 12, 2017

Julia's talk about the algorithm design

It is a good ritual to talk about the design, make a story, structure the story the way easy to recall, and also very well structured highlighted with keywords using different colors. The true nature of dynamic programming reminds us spend more time to write a story, spend less time to write the code.

Here are the highlights of story to buy and sell stocks. One transaction, multiple choice of purchase time, how to find maximum value? how to introduce the recurrence formula?

First let us talk about buy and sell stocks algorithm here on Leetcode 123. As a recursive solution nature, we only need to discuss one transaction in the design. We need to consider when to purchase, when to sell.

One transaction leads us to think about the last transaction. The last time stamp index to sell or not sell the stock.

Assume that we sell at time stamp index, and we can purchase anytime before index, in other words, any j from 0 to index – 1. The overall profit can be expressed using  the profit based on j and then last transaction profit prices[index] – prices[j].

Let us talk about multiple choices, and what is the optimal value? Find the maximum values in all the options.

Next, let us introduce the recurrence formula. Define a profit function called profit(k, j), where k is the number of transactions and j is the time stamp. 


f[k, index] = max(f[k, index - 1], max(prices[index] - prices[j] + f[k - 1, j]) for any j in range of [0, index - 1])

Follow up 

I had a mock interview on January 28, 2018, and after the mock interview the peer shared with me how he learned the algorithm through $50.00 purchase of courses on algoexpert.io. I found this free lecture on the algorithm Leetcode 123: Buy and Sell stock III.

Short Palindrome - HackerRank - world codesprint #5

July 25, 2016

Problem statement

Julia spent 3+ hours to score 13 out of 40 points, she enjoyed the time to work on the problem.

 A few issues: wrong answer, time out, run time error.

 More than 3 submissions, failed to solve time out issue.

 1. C# solution

 2. Add memorization using Dictionary to save time, failed to solve issues.
C# solution 

 3. add one more memorization, failed to solve issues.
C# solution

 4. Review code and then add some comment, and analyse design issues:

C# solution

Review the design, try to find the flaws - a few ideas to improve timeout, no run-time error issue.

review code and then add comment for function countingPalindromes:

/*
	* use two loops
	*
	* get 0110 pairs
	* get 1001 paris
	*
	* Think about DP solution - dynamic programming - not working, too complicate
	*
	* brute force solution:
	* 0 - start char, end char, and then, count how many possibilities
	* Go through O(n*n) case, for any two 0 in pseudo string, check in-between
	*
	* For example:
	* 001010110
	*
	* The above case, there are 5 '0',
	* position of '0' is 0, 1, 3, 5, 8,
	* So, any two '0' combinations are 5*4/2*1 = 10
	*
	* A: 0, 1, in between, there is no chars, n/a
	* B: 0, 3, 2 chars in between - "01", count how many '1' in the substring, only 1.
	* C: 0, 5, 4 chars in between - "0101", two one inside, so how many combination
	* of 11, only 1 choice.
	* D: 0, 8, 7 chars in-between - "0101011", four one's in the substring, how many combination - 4*3/2 = 6 choices
	*/

Add comment for function getPseudoString(...)

/*
	* using 0 and 1 to construct the string
	* 1001
	* 0110
	*
	* There are 26 chars in alphabetic string, any two combination is 26*25/2*1 > 250
	* Instead, using 0 and 1 to stand for two distinct characters.
	* for example, abab
	* 0101
	* So, we can conclude one thing:
	* ababa
	* 01010
	* or
	* 10101
	* So, use memorization, 01010 and 10101 should be same key
	* See if this can solve time out issues - July 25, 2016
	*
	* reverse of string should be same key
	*/

It took Julia more than 3 hours to gain 13/40 point, but learning experience was so great, and she enjoyed the coding experience.

Starting from brute force solution, she made some progress to gain 13 points; go through optimal solution - DP, should be next step.
Statistics:

450 score 40/40

1600  score above 12/40
Total submission: 2180

Facts about HackerRank:
aiming brute force, 30% score.

Dynamic solution:

detail from editiorial notes.  

The idea of DP from the above website: string length is n

pattern to search

xyyx

xy ends position at i - iterate from 1 to n-1,

denote l[i]

yx starts at position i - iteration from i to n-1

denote r2[i]

yx starts at position >=i

denote r[i] = r2[i] + r2[i+1]+...+r2[n-1]

So, to get a solution:

   Iterate i from 1 to n-1
 
   sum of l[i] * r[i]

And one more thing,
          r[i] = r2[i] + r[i+1]

The idea Julia tried on July 24, 2016 -
suppose that T[i] is the short palindrome like "xyyx" at end of string i, how to construct T[i+1]?

Follow up after 8 months

C# code

Follow up 

8/25/2017
I go through the code, and evaluate the code. The fact is that the code is too complicate for a medium level algorithm. Based on the past code contest experience, the code should be very short and concise.

I will put some code review on my last practice, and then write a solution to help the dynamic programming algorithm practice and learning. Make it part of 10 step series.

I’ve tasted success and I’m hungry for more. I’ll prove I’ve got what it takes to win. #CreateYourMark pic.twitter.com/jansdjv9pG

— Lucas Pouille (@la_pouille) May 20, 2016