Sudoku Solver

I had seen a hard problem on Leetcode regarding Sudoku Solver a few days back and had been thinking of a solution since then. I have solved Sudoku previously and thought of converting the manual approach to a programmatic way of solving it. Here is the final solution which got accepted by Leetcode.

The idea is to keep finding a grid to put a number in, try putting numbers between 1 through 9 into it and check for validity of the board with each number. If the board is valid after putting in a number, try another grid. If the board fails the validity check for all the numbers from 1 through 9, put back the initial dot ('.') onto that grid and return to previous state of the grid i.e. Backtrack. At this previous state, try another number on the previous grid. Keep doing this until you get a solution. The Leetcode problem above asks to assume that there exists a solution.

POST call forbidden (403) in Spring Boot application

If you are getting status code 403 (forbidden) error for a POST call in Spring Boot application and if you are fine with disabling CSRF (cross site request forgery), you can disable CSRF to continue your POST call.

Here is the code snippet to do this:

@EnableWebSecurity

public class WebSecurityConfig extends WebSecurityConfigurerAdapter {

    @Override

    protected void configure(HttpSecurity http) throws Exception {

        http.csrf().disable();

    }

}

References:

1. https://github.com/pyav/restful-web-services/blob/main/src/main/java/com/pyav/rest/webservices/restfulwebservices/WebSecurityConfig.java

Issue resolution in maven project for Spring Boot application in Eclipse

Writing this post to record the steps to resolve the following issue in maven project while running it in Eclipse for a Spring boot application:

Non-resolvable parent POM: Could not transfer artifact org.springframework.boot:spring-boot-starter-parent:pom:1.5.3.RELEASE from/to central (http://repo.maven.apache.org/maven2)

Steps to resolve which worked for me:

1. Update project:  Right click on the project -> Maven -> Update Maven Project (opens a pop-up window)
2. Check the project in the "Available Maven Codebases" list.
3. Check "Force Update of Snapshots/Releases".
4. Click "OK".
5. Build the project: Right click on the project -> Build Project.
6. Run the application: Right click on the application code -> Run as -> Java application

Thanks for reading.

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

Ubuntu 18.04 (Bionic Beaver) upgrade failure and recovery

I got Ubuntu's upgrade notification and I started upgrading my installation. For some reason I had to abort the upgrade and shut down the system which led to the corruption of entire installation. Hence, I was not able to boot the installation normally and here are the steps which I had followed to recover the system:

1. Pressing shift button when the system started led to see the boot menu and I had selected one of 
    the old recovery images.
2. sudo dpkg --configure -a
    - installed the package maintainer's version.
3. Upgraded the system from updates gui.
4. There were lots of images so I had to purge the ones which were not required:
    - sudo apt-get purge "linux-image-version_of_the_image_to_remove" (w/o quotes)
    - sudo update-grub2
5. sudo reboot
    - Pressed shift button to show the boot menu -> went to advanced options.
    - The new image and its recovery were listed. This is because of purging the old images as above.

zlib import error in python3

I have been getting import zlib error in python3. So, after a little search on the internet, I found and did the following which had a different lib error but it resolved the error for zlib and zipfile import which I was getting earlier:

cd Python-3.6.4
make clean
sudo apt-get install zlib1g-dev
./configure
make
make test
sudo make install

And now the import zlib/ zipfile worked. 

Free memory allocated in a Binary Search Tree

A lot of times I have seen codes which are not written keeping memory in mind. A great example is dynamically allocating memory for data structure demonstration on many coding websites. Though they are not meant to demonstrate efficient use of memory, it doesn't take much effort to write codes which actually free the memory. For example, if you have a look on this code, which finds the inorder predecessor and successor of a key in a Binary Search Tree, you see that the call to 'free_all()' frees the memory allocated to demonstrate the actual problem at hand. The function has just two lines of recursive calls along with free() and an exit criteria, hence it doesn't take much effort to write such functions.

A valgrind analysis of the code without the call to 'free_all()' throws the following:

gcc -Wall inorder_successor_predecessor.c && valgrind --leak-check=yes ./a.out
.
.
20 30 40 50 60 70 80
The BST is created, enter the key for inorder successor and inorder predecessor: 30
The predecessor is: 20
The successor is: 40
.
.
84 (12 direct, 72 indirect) bytes in 1 blocks are definitely lost in loss record 7 of 7
.
.
LEAK SUMMARY:
   definitely lost: 12 bytes in 1 blocks
   indirectly lost: 72 bytes in 6 blocks
     possibly lost: 0 bytes in 0 blocks
   still reachable: 0 bytes in 0 blocks
        suppressed: 0 bytes in 0 blocks

For counts of detected and suppressed errors, rerun with: -v
ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)


Whereas, a valgrind analysis of the code with the call to 'free_all()' throws the following:

HEAP SUMMARY:
    in use at exit: 0 bytes in 0 blocks
  total heap usage: 9 allocs, 9 frees, 108 bytes allocated

All heap blocks were freed -- no leaks are possible

For counts of detected and suppressed errors, rerun with: -v
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)


Therefore, sometimes few lines can actually save a lot of memory.

Two different times, two different places

December 23, 2015: The day came when I was supposed to leave Bangalore and start my journey to Goa to meet my college friends who were coming there. I had finished my work and started for the bus station where my bus was scheduled to leave from. Though I was little late due to heavy traffic, yet I reached the station before the bus had left. I was traveling alone this time and started a conversation with the guy sitting near to me on the window seat and got to know that he was pursuing MBA. He gave lots of information to me regarding MBA and its future prospects.The bus stopped at a place and we had dinner after which we started again and the bus reached Goa an hour late in the morning. 

My friend Abhilash was at the bus stand to receive me. A couple of friends arrived in the evening and by then I had moved to a GTDC hotel near Vasco-da-Gama railway station. I had visited Goa to meet high school friends in July, 2015 when heavy rain welcomed me. Whereas last time we hopped on the beaches and visited forts, this time we spent more time on one or two beaches, ate near the beaches and visited Churches. My friend Jishnu drove the car. 

When I look back a week, I feel that Goa seemed to be different this time. It may be that I saw it with different eyes. Eyes which had seen it once, eyes which felt happy seeing friends but somewhere or the other it felt loneliness. I don't know what it was but when I reached about 100 metres above the sea level while parasailing, everything seemed to have stopped, still as if it never moved. I saw the sky, the distant water, other boats and there was no ground below my feet. That was the moment when I felt as if I am not even a pebble beside the sea. That was the time when I had the flashback of one of my friends who had told me about the thrill in paragliding. I felt the same and returned with lots of memories. 

There were two other friends who shared room with me. One of them was Amit, whom I saw after about five years. All of us shared lots of memories of college. We also visited Dona Paula, where we got an awesome panoramic view in the moonlight. The rays on the water surface seemed to have created a path in the water, a path which lead to somewhere unknown. 

At last, the day came when we had to return. I had spent four days in Goa but still I wanted to stay back with my friends. I knew that it was not possible and we had to separate one after another. I boarded on the bus to Bangalore on 27th. And thus ended my journey to Goa with lots of happiness but with heavy heart. 

Difference between two numbers in a system with limited operation

One of my friends, Ravi, asked me a question today and he said that it was asked to him by one of his interviewers some time back. Here is the problem statement:

You are designing a new computing system in which following four operations are possible as of now:

(1) Assignment of a variable to another : x = y.

(2) Assignment of zero to a variable : x = 0.

(3) Increment a variable : x++.

(4) Looping in a way which takes a number (variable) as argument and loops for that number (variable) even if you change that variable's value inside the loop. You can't break out of the loop.

How to calculate difference of two numbers "x - y" in the above system?

After spending some time in thinking about the solution, here is what I came up with:

There is one more information given to us. The system is new and designed by us. Hence, we know the architecture of the system and hence the highest positive value possible in that system after which a variable becomes zero if incremented by 1. 

Now, we can assign the highest possible value for that architecture, say 65535 for 16-bit as we are allowed to assign a value to a variable. Then we can increment it twice to get the output as 1. We see that if we add 2 to the highest value we get 1, in a similar fashion, we can add 'n' to the variable having highest value to get 'n-1'. So, we see that in the first iteration, we start with 'n' and get 'n-1'. We can then start with 'n-1' and we will get 'n-2' and so on. We will get 'n-y' after 'y' iteration. Here we can take "x = n". 

Hence we will get "x - y" with the set of operation defined in the problem statement above and one more additional information about the highest number possible in the system.