A* search

I took this class called Introduction to AI, and the professor gave me the assignment to write an A* heuristic program to find the shortest path between the cities. The shortest path heuristic was based on the Euclidean distance or alternatively the total number of links. The program needed to be shown on a graphical interface. I wrote this taking some time, going through all sorts of implementation issues. I assume my solution to be not optimal, but it works in a reasonable time. Below is the video describing one of the sample runs.

Sample locations input file

Sample Connections input  file

Main function

Node.java

Reader.java

Probabilistic Road-map method (PRM)

The probabilistic road-map approach is used in robotics to find a path from the present configuration to the robot's desired configuration. This is done by finding a path in the configuration space.

As shown above, the path from the source to the destination is plotted on the configuration space. I used the classical Dijkstra method to find the path. The sample input file and the main program are below.

Input

1 8

-7 20.5

-11 30.5

-18 16

-21.5 28

-7 25.5

-11 35.5

-18 21

-7 33

1 2 3 4

5 6 7 8

0 0

30 55

300 150 

76 91

The program code in Gist

Configuration Space

I took a class called Algorithms for Robotics in the school. The class was interesting, except that I messed up the finals. Anyway, the assignments included finding the configuration space of a 2D robotic arm, Simultaneous Localization & Mapping, etc. I thought of writing something about it here.

The configuration space of a robot allows it to calculate the possible motions it can take, given the locations of the obstacles.  The above picture represents the two angles of a 2D arm robot. Each goes from 0 to 360 degrees. The red shade indicates obstacles and the white space indicates the free space. The real-world coordinates are translated by the algorithm into the above representation to make things much easier. I wrote the program in Java. It was an interesting solution since I did not use any open-source libraries.

Sample input


3 11
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
3 2
3 3
4 3
1 2 6 5
3 4 8 7
9 10 11
3 0
2 2

Program link

Theme park

This problem appeared on the google code jam website. I took some time to write a solution.

Statement

Roller coasters are so much fun! It seems like everybody who visits the theme park wants to ride the roller coaster. Some people go alone; other people go in groups and don't want to board the roller coaster unless they can all go together. And everyone who rides the roller coaster wants to ride again. A ride costs 1 Euro per person; your job is to figure out how much money the roller coaster will make today.

The roller coaster can hold k people at once. People queue for it in groups. Groups board the roller coaster, one at a time, until there are no more groups left or there is no room for the next group; then the roller coaster goes, whether it's full or not. Once the ride is over, all of its passengers re-queue in the same order. The roller coaster will run R times in a day.

For example, suppose R=4, k=6, and there are four groups of people with sizes: 1, 4, 2, 1. The first time the roller coaster goes, the first two groups [1, 4] will ride, leaving an empty seat (the group of 2 won't fit, and the group of 1 can't go ahead of them). Then they'll go to the back of the queue, which now looks like 2, 1, 1, 4. The second time, the coaster will hold 4 people: [2, 1, 1]. Now the queue looks like 4, 2, 1, 1. The third time, it will hold 6 people: [4, 2]. Now the queue looks like [1, 1, 4, 2]. Finally, it will hold 6 people: [1, 1, 4]. The roller coaster has made a total of 21 Euros!

Input

The first line of the input gives the number of test cases, T. T test cases follow, with each test case consisting of two lines. The first line contains three space-separated integers: R, k, and N. The second line contains N space-separated integers gi, each of which is the size of a group that wants to ride. g0 is the size of the first group, g1 is the size of the second group, etc.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of Euros made by the roller coaster.

Limits

1 ≤ T ≤ 50.
gi ≤ k.
Small dataset

1 ≤ R ≤ 1000.
1 ≤ k ≤ 100.
1 ≤ N ≤ 10.
1 ≤ gi ≤ 10.
Large dataset

1 ≤ R ≤ 108.
1 ≤ k ≤ 109.
1 ≤ N ≤ 1000.
1 ≤ gi ≤ 107.

Sample

Input
3
4 6 4
1 4 2 1
100 10 1
1
5 5 10
2 4 2 3 4 2 1 2 1 3
Output
Case #1: 21
Case #2: 100
Case #3: 20

My Solution:

Snapper Chain

This problem appeared on google code jam website. I took some time to write a solution.

Statement

The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.
When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers -- making a clicking sound -- any Snapper receiving power at the time of the snap toggles between the ON and OFF states.

In hopes of destroying the universe by means of a singularity, I have purchased N Snapperdevices and chained them together by plugging the first one into a power socket, the second one into the first one, and so on. The light is plugged into the Nth Snapper.

Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on.

I keep doing this for hours. Will the light be on or off after I have snapped my fingers Ktimes? The light is on if and only if it's receiving power from the Snapper it's plugged into.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each one contains two integers, N and K.
Output
Limits
1 ≤ T ≤ 10,000.
Small dataset

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "ON" or "OFF", indicating the state of the light bulb.
1 ≤ N ≤ 10;
0 ≤ K ≤ 100;
1 ≤ N ≤ 30;
0 ≤ K ≤ 108;

Sample

Input
4
1 0
1 1
4 0
4 47
Output
Case #1: OFF
Case #2: ON
Case #3: OFF
Case #4: ON

My Solution

Price Finder

I just wanted to write something regarding my project work at the college. I always thought of creating something interesting. This idea came up randomly, though I can't recall how. It was to create a price finder website on the internet. Again it's formal writing!

In this age of online shopping customers often find the same product being sold at different prices on shopping websites. Customers usually want to buy the right product at minimum cost. It would be useful for them if they were to have a search engine that will give them the best website to buy from. We make use of web crawlers and screen scrapers to get the price of products on shopping websites and then store it in a database with indexing. We aim to develop a heuristic Search engine that would accept the name(s) of the product as input and return ideal website links as output.

Concept description

First I developed a web crawler module that would download the entire pages from shopping websites we need. As a prototype, I downloaded 5 major book shopping websites in India (books.rediff.com, flipkart.com,eshop.talash.com/books, gobookshoping.com, and nbcindia.com).

In the next module, I needed to create a user interface using JSP in which the user would enter the name of the product(s) he would like to purchase. The request is processed and finally, the desired results are displayed to the customer using a searcher and a price finder. The result would display website descriptions of those selling the requested product name. The user can then go to the link directly to purchase. 

A simple diagram demonstrating the concept

Design of web crawler module

The web crawler I wrote works by following hyperlinks on the shopping website, excluding external hyperlinks which point to other domains. The links are extracted from the HTML content of each page by using regular expressions and Jericho HTML parser. The process is repeated until all pages in the preferred shopping website are downloaded. 

The downloaded webpage is in HTML format. In the next step, we have to extract text from it. For that, I used an HTML parser library called Jericho. The downloaded pages are stored in a database along with address, text, and HTML content. I used the latest version of an open-source database called H2 for this purpose. Next, we have to index the text column in the database in order to make searching operations faster. For this, I used open-source Lucene text indexer which I found to be efficient. Finally, the name of the downloaded shopping website is written in a text file for later use by the searcher.

I was able to create a web crawler user interface using Java. It had options to specify the maximum number of pages to download with a progress bar indicating the status of the crawling process. Also, it had options to pause and resume the download. Many instances of this web crawler application can be initiated so that downloading websites simultaneously is possible to make use of the network bandwidth in an optimal way. It would run on any machine with a Java runtime environment installed.

Design of the user End module

The user end module is similar to the Google search page. It ran on an Apache Tomcat server. The user query is translated into a database search query by using a query parser.

Design of Query parser sub-module

If the quantity is specified in the query then it is saved and will be used to calculate the total price at a later stage. In the above example ‘wings of fire’ AND ‘Abdul Kalam' means look for pages that contain both the terms “wings of fire” and “Abdul Kalam”.

Design of Searcher sub-module

The job of the searcher module is to search for the parsed user query. Using multi-threading the translated user query is searched on each of the databases concurrently. 

Design of price finder sub-module

This module works inside the searcher module. The job of this module is to find the price of the product. Utilizing the result set of searcher it fetches those pages which contain the user query. For each of these pages, a carefully selected logic is used to get the price of the specified product. Finally, the product name, price of the product, and other details are cached for future queries.

The logic used to find the price

The assumption is that most shopping websites would display products in the below format.

           Name of the product…..some details……Price…reduction rates…Reduced price.

I made use of regular expressions to extract the price by looking for “product name” and then looking for “currency”.  

One example is shown below found at books.rediff.com

Everyday Eating For Babies And Children

Author: Judith Wills     Format:  Paperback      ISBN: 0007215274      Seller: Crossword      See more books by this author     Share this book with a friend Our Price Rs. 745 Get this book in 25 business days. Special offer: Free shipping on this book

List Price: Rs 499 Our Price: Rs. 349 Discount: Rs. 150

off

The user enters the name of a product or a list of products he wants to purchase. An additional option was provided to view the cached copy excluding images so that in case the original web server is down user can still see the content.