Longest Bitonic Subsequence

Problem Statement:
I had recently seen a problem statement which was asking to find the length of the longest bitonic subsequence in a given array of positive integers. A bitonic subsequence is a subsequence which first increases and then decreases. Here's what went inside my head while solving the problem:

Initial thoughts about the problem:
A subsequence can be longest if the smaller subsequences it is made of are the longest for their respective lengths. For the bitonic property to satisfy, we need to find the optimum value for longest increasing subsequence plus the longest decreasing subsequence. Therefore, this problem statement satisfies both the required properties of dynamic programming:

1. Overlapping subproblems.
2. Optimum substructure.

The solution:
So, the first target as part of finding a solution to the above problem statement is to find the length of the longest increasing subsequence (lis). Then, the length of the longest decreasing subsequence (lds). A combination of both of these should give me the solution of longest bitonic subsequence length. Now, we don't know how to combine lis and lds. So, I thought what if I calculate both the values for each of the indices in the given array i.e. lis from start to an index i, lds from index (i + 1) to the end and i ranges from 0 to the length of the given array. So, this gives me a picture of the lengths of both lis and lds for each of the indices in the given array. If we can store the sum of these values and find out the maximum among the stored values, then that is the required solution of the problem statement of finding the length of longest bitonic subsequence in a given array.

Understanding the code:
If you see the GitHub code (link in the references section below), there are majorly two methods lis() and lds() which calculates the longest increasing subsequence length and the longest decreasing subsequence length for a given range. The lis() is calculated always from the index 0 to an index i and the lds() is calculated from after the index i in the given array. Both of these operations are done for all of the indices and from within another method lbs() which keeps track of the sum of the values of lis and lds lengths. Finally, getMax() returns the maximum value stored in an array given the array and the number of elements in it.

Testcases:
A set of five testcases are given to test the algorithm from the main function itself. The outputs for each of them are added in the top comment section of the file.

References:
1. https://github.com/pyav/labs/blob/master/algorithms/dynamic%20programming/LongestBitonicSubsequence.java

Sudoku

Many of us would have solved Sudoku ranging across different levels. I got to see Sudoku problems for the very first time in a newspaper back in 2005 when I was in high school. I used to solve them regularly back then but became an infrequent Sudoku solver later and I haven't solved a Sudoku problem in past few years now. During my conversation with an old friend recently, he gave me the problem of solving a Sudoku solver program itself. Here is the set of steps that I worked on in order to come up with a solution:

Initial Setup

Initially we get a 2D matrix input where some values are pre-filled already (rest are set to 0). These values can range between 1 and the size of the matrix (number of rows or columns, since it is a square matrix). A Python program reads an input text file of testcases and constructs the string argument and sends it to the compiled Java code.

Row and Column checkers

This is for the validity of existence of a value in a particular grid which translates into (i, j) index of a 2D matrix. The row checker checks whether the value under consideration is already present in any of the columns of a particular row index i whereas the column checker checks all the rows of a column indexed at j. This is the code snippet to support these checks (click on the image for enlarged view):

Finding a grid to check for a value

This step is for finding a grid (i, j) where we put a value and proceed further. Here we first search for the value 0 and if found we take a value in range 1 through size of the matrix, verify its validity in that particular row and column as in the above section then put that value in the grid and move to another grid. For this to happen we need to iterate over all the grids hence a nested loop is needed. Since these operations like searching a grid having the value 0, validating a probable value to be put in that grid, looking for another subsequent grid(s), etc. keep happening repeatedly, hence we need to have them in one block and in a recursive method. Please check the method isSolutionPossible() in the GitHub reference link provided below for the relevant codes. We are taking the current state of the matrix as input to this method for further recursive calls as the next set of values need to be applied on the current and further set of corresponding matrix states.

Construction of the input matrix

The main() method takes the string args array as input, parses it and constructs the initial state of the matrix. It then initiates the recursive method call to check whether a solution is possible with the initial state of the matrix as input along with its size. If yes, then it prints the final state matrix which is a solution to the given Sudoku problem. Before returning the final state of the matrix, a final uniqueness check is done to counter the testcases of all-filled matrix already provided.

Resources:

1. Code repository:    https://github.com/pyav/Sudoku