Algorithm – N Kings

N Kings

You have to place the N kings in on N squared chess board so that no two kings are in same row and column and do not attack each other.

About input, first line of the input is number of testcases T. Then every next 2 lines are for the testcase. In the first line N is the size of chess board and K is the number of Kings already in place starting from first row. Next line has K numbers. Each “number”(pos) in position i is in the row i and column “number” in which king is already placed. 0 <= K <= N. 0 <= pos[i] <= N-1

About output: Output will be the number of possible ways kings can be placed modulus 1000000007.

Input:
2
3 0

4 1
2

Output:
0
1

 

Algorithm

Solved the problem recursively by setting up board and checking every column for each row if the current position is valid. You can see the solution as Depth First Search as we traverse up till the leaf first(solution). The algorithm uses Constraint Programming by default as the first row after the already placed pieces will always have minimum constraint that is will have less possible positions to start with.

 

Code

You can see the code here. Its in python(2.6.2).

Spidey: Python Web Crawler

I created a web crawler using python and its modules. It follows certain conditions like it reads robots.txt before crawling a page. If the robots.txt allows the page to be crawled the spidey crawls it. It dives in recursively. But there are certain limitations I have set. It do not go beyond 20 pages, as it is just a prototype. It cannot be detect traps, where it will go infinitely.

Spidey is a very basic crawler which works just fine with websites at least on the websites I have tested. I have tested it with http://python.org/ and http://stackoverflow.com/ and it did pretty well.

The modules I have used for the purpose are urllib2, re, BeautifulSoup, robotparser.

Here is the code if you want to test/use it.

Socket Programming: Handling multiclients

Referring to previous post, we will continue with same code. In this post we will try to handle multiple clients. You can read rest of the post on my personal website, here is the link.

Multiple clients means that multiple client programs can connect to server program. For this we will use threads. Threads are nothing but process and runs only the part that is required (we decide what is going to run) to be run.

There will be a minor change in both server and client programs.

Required: Python 2.6+

Using:

server.py

#!/usr/bin/python

# Import all from module socket
from socket import *
#Importing all from thread
from thread import *

# Defining server address and port
host = ''  #'localhost' or '127.0.0.1' or '' are all same
port = 52000 #Use port > 1024, below it all are reserved

#Creating socket object
sock = socket()
#Binding socket to a address. bind() takes tuple of host and port.
sock.bind((host, port))
#Listening at the address
sock.listen(5) #5 denotes the number of clients can queue

def clientthread(conn):
#infinite loop so that function do not terminate and thread do not end.
     while True:
#Sending message to connected client
         conn.send('Hi! I am server\n') #send only takes string
#Receiving from client
         data = conn.recv(1024) # 1024 stands for bytes of data to be received
         print data

while True:
#Accepting incoming connections
    conn, addr = sock.accept()
#Creating new thread. Calling clientthread function for this function and passing conn as argument.
    start_new_thread(clientthread,(conn,)) #start new thread takes 1st argument as a function name to be run, second is the tuple of arguments to the function.

conn.close()
sock.close()

Use the same client.py code for client from previous post.

#!usr/bin/python
from socket import *

host = 'localhost' # '127.0.0.1' can also be used
port = 52000

sock = socket()
#Connecting to socket
sock.connect((host, port)) #Connect takes tuple of host and port

#Infinite loop to keep client running.
while True:
    data = sock.recv(1024)
    print data
    sock.send('HI! I am client.')

sock.close()

Understanding :

Highlighted code is the changes done in the previous code we had.

What we have done in server.py is we took the communicating part inside the infinite while loop of function clientthread and using it in thread on line 32.

In client.py we took the communicating part inside the infinite while loop.

Everything else is explained in comments.

Note:

• Programs will not terminate by themselves because they will never come out of loop. So certainly you will receive error that socket is already in use.
• start_new_thread() takes 3 arguments. 3rd argument is kwargs which is of no use right now.
• 2nd argument of start_new_thread has to be a tuple. Tuples are fixed length array in python.
• Module threading can also be used for threading.
• start_new() is identical to start_new_thread().
• 5 in sock.listen(5) in server.py is of no use as every client will interact with server. May be it  will be required when server can not handle more process.

My personal website is up and all new blog posts will only be available on https://neerajkhandelwal.com.

Socket Programing: Python

We will be understanding the basics of socket programming using Python.You may be thinking why socket programming? Well, its because if you need to send data over a network you need to know about socket. The HTTP websites runs on port 80. Each website has a IP adress. So when you request for a website actually your browser is trying to get data from someipaddress:80. 80 is default port that browser uses, otherwise specified. You might have used Apache. What it does it creates server(we call apache server) and binds it to 127.0.0.1 and port 80. 127.0.0.1 is called  loopback address as it tells the browser to look in the consumer’s computer only instead of searching web.

Lets start, first of all socket is a connection point like your phone. You connect to some socket (someone on other side of phone) and send and receive message or data (chat). 

Requires: Python 2.6 + Using: Lets try to create a server first.

#!/usr/bin/python

# Import all from module socket
from socket import *

# Defining server address and port
host = ''  #'localhost' or '127.0.0.1' or '' are all same
port = 52000 #Use port > 1024, below it all are reserved

#Creating socket object
sock = socket()
#Binding socket to a address. bind() takes tuple of host and port.
sock.bind((host, port))
#Listening at the address
sock.listen(5) #5 denotes the number of clients can queue

#Accepting incoming connections
conn, addr = sock.accept()

#Sending message to connected client
conn.send('Hi! I am server') #send only takes string
#Receiving from client
data = conn.recv(1024) # 1024 stands for bytes of data to be received
print data

#Closing connections
conn.close()
sock.close()

Now a client.

#!usr/bin/python
from socket import *

host = 'localhost' # '127.0.0.1' can also be used
port = 52000

sock = socket()
#Connecting to socket
sock.connect((host, port)) #connect takes tuple of host and port

data = sock.recv(1024)
print data
sock.send('HI! I am client.')

sock.close()

Understanding:

Everything is explained in comments.

Note:

• The program above is waiting for type of programming. Look at the send and recv part in both programming, if server is sending something client must always know when server will send and vice versa or it should wait for that. Of course if you don’t want to drop anything you are sending.
• # is used for comments except the first line it is for telling where python program is. Use path to python.exe on Windows.
• Always use sock.close() to close the socket otherwise socket is in use error will be thrown by python. You may also see it if the program terminates in between.
• 5 in sock.listen is of no use right now as the server.py will terminate as soon as it is done with first client.
• sock.recv() waits till it does not receive something.
• print data will not work with python 3.0+. Use print(data).

There will be more on it. Till if you want to read more about it, see here.