ACM Apply on Google App Engine

Was working on http://acmapply.appspot.com/ (Google App Engine). Will be coming up with the tutorial to the site soon.

Filling a bounded region, Turbo C

A program to fill a bounded region to be implemented in Turbo C, as a practical of Computer Graphics. As input, a point inside the bounded region is given. 


Implementation:
Starting from the given point apply dfs to the points at n,s,e and w.  As the base conditions check whether the color at the given pixel is equal to the boundary. If it is, return. Also even if it is equal to the fill color, return. Sadly I had to program in Turbo C, yes our college still uses that compiler. Here 4 is the fill color.


Function:
// x and y coordinates of point inside
// getmaxcolor() is the color of boundary
// fill the pixel with color 4


dfs(int x, int y) { 
  if (getpixel(x,y)==getmaxcolor() || getpixel(x,y)==4)
      return; 
  putpixel(x,y,4); 
  dfs(x-1,y);
  dfs(x+1,y);
  dfs(x,y-1);
  dfs(x,y+1); 
}



Floodfill implementation using dfs (stack)
Image Source: Wikipedia 


The output is pretty interesting when you use a delay function with it.    

929 - Number Maze Uva Online Judge

Tried the problem in Java, completed it. But in Java it is too slow that is why unable to submit it. Solved it using BFS with PriorityQueue.

929 - Number Maze

Time limit

Java

3.000

0.144

8 hours ago

Programming in 61 minutes

Check out this great link by Dhruv Matani http://dhruvbird.com/61.html

PriorityQueue Implementation

While learning Dijkstra's I have come across this class PriorityQueue.

class PriorityQueue

It basically keeps the elemts sorted accordingly. The head of the queue is the least element to the specified ordering. Implementation note: this implementation provides O(log(n)) time for the insertion methods (offer, poll, remove() and add) methods; linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

How will the sorting be done?

This is either naturally specified or otherwise, that depends on the arguments of the constructor. Like if the class Integer is specified then the comparison will be done using the compareTo method of the comparable interface. This is when we do 

PriorityQueue temp = new PriorityQueue();

For adding and removal the methods which are available are : add() and poll() (removes the element from the head of the Queue)

Program

public static void main(String[] args) {

PriorityQueue temp = new PriorityQueue();

temp.add(4); temp.add(2); temp.add(3); temp.add(7); temp.add(1);

while (!temp.isEmpty()) {

System.out.println(temp.poll());

}

}

Output

1

2

3

4

7

This being the case when we use a class which has already implemented the Comparable Interface. 

Now suppose that we have user defined objects to be stored in the PriorityQueue, then for the sorting to be done the user defined class will implement the interface Comparable and override the compareTo(Object c) method.

import java.util.PriorityQueue;

class Node implements Comparable{

public int a,b,c;

public void setA(int a) {

this.a = a;

}

public void setB(int b) {

this.b = b;

}

public void setC(int c) {

this.c = c;

}

public int compareTo(Node o) {

return new Integer(this.c).compareTo(o.c);

};

}

public class PQExample {

public static void main(String[] args) {

Node n = new Node();

n.setA(1);

n.setC(4);

Node n2 = new Node();

n2.setA(2);

n2.setC(6);

Node n3 = new Node();

n3.setA(3);

n3.setC(1);

PriorityQueue temp = new PriorityQueue();

temp.add(n); temp.add(n2);temp.add(n3);

while (!temp.isEmpty()) {

System.out.println(temp.poll().a);

}

}

}

Output

3

1

2

I learnt these concepts from Pratik Tandel (pt1989) ,  http://problemclassifier.appspot.com/

Setting up Eclipse for C++ in Windows

Help -> Software Updates


Add a new site
http://download.eclipse.org/tools/cdt/releases/helios


Then follow the normal instructions.


I don't know why even I am adding this as a blog post.

Java Program to print all links in the specified URL

import java.net.*;
import java.util.StringTokenizer;
import java.io.*;

public class ReadURL 
{
    public static void main(String[] args) throws Exception 
    {
    URL yahoo = new URL("http://aintmeekcoder.blogspot.com");
    BufferedReader in = new BufferedReader(new InputStreamReader(yahoo.openStream()));
    String inputLine;
    int loc;
    while ((inputLine = in.readLine()) != null)
        {
            if ((loc=inputLine.indexOf("
            {
                for (int i=loc+9; inputLine.charAt(i)!='>'; i++)
                {
                    System.out.print(inputLine.charAt(i));
                }
                System.out.println();
            }
        }
    in.close();
    }
}

352 Seasonal War Uva Online Judge

Problem: http://uva.onlinejudge.org/external/3/352.html
My Approach:

• Traverse all elements starting from 0,0
• Check whether the element is one
• If it is the applydfs
• applydfs
• if it is one, mark it as 0
• apply the same to all its unvisited neighbours
• if zero, return
• count the no. of times dfs is applied
• this will count the number of connected components
• And thus we have our answer

784 Maze Exploration Uva Online Judge

Points to remember before submitting:


1. Consider any line starting with '_' as seperator between the inputs.
2. Print the seperator also along with the grid.
3. The walls of the grid can be represented using any alphabet (any character as a matter of fact)

Codechef Programming Google Calendar

Introducing the Codechef Programming Calendar, Add it to your Google Calendars.

Codechef Programming Calendar

Programming Abstraction Notes: Lecture 4

Notes of Programming Abstractions( Stanford Engineering Everywhere) see.stanford.edu

ifstream for Input Stream for a File. Also remember that ifstream in


in.open("oldfile.txt");
This takes as Parameter old string that means quotations. Which means that
string s = "oldfile.txt";
in.open(s) will give us an error

To fix this problem use s.c_str() function instead of s as the parameter, This
converts it into the old string

Some Discussions about Object Oriented Programming. The Next Big Thing.

Scanner Class was discussed. In Visual C++ while creating a new object there is

no need for the new operator.

What are Container Classes?

CS106B Vector class has a built in Better Array

Bounds Checking
Add, Insert, remove
Memory Managemet, knows its size

Vector Class as a template. Vector decribes what it is storing using a place holder. Example:
template ElemType>

class Vector {
public:
addObject ( ElemType value);
}

How to check if an integer is a power of 2 ?

 

Source: http://www.codechef.com/wiki/tutorial-bitwise-operations

Explanation:

The Integer which is the power of two will always have the leftmost bit 1 and the remaining bits as 0. Let this number be x.

And the number (x-1) will never have the leftmost bit as 1. So x & (x-1) will always give 0 if the number is power of 2.

So to check whether the number is power of two, check x & (x-1) , if the answer is 0 then the number is infact power of 2.

JSP Servlets, Tomcat v6 and MySql

Installing the Server, Tomcat

1. Install Java. Make sure you have Java 5 or 6 installed.
2. Unzip Tomcat. Unzip tomcat-6.0.28-preconfigured.zip.
3. Download Eclipse. Install the Java EE version of Eclipse. If you have JDK 1.6.0_21 or later, you must fix the Eclipse permgen space error.
4. Tell Eclipse about Tomcat. Start Eclipse and go to the Workbench. Click on Servers tab at bottom. R-click, New, Server, Apache, Tomcat v6.0, navigate to Tomcat installation folder (e.g.,C:\apache-tomcat-6.0.28), OK.
5. Test the server. Test Tomcat within Eclipse. Details here.
6. Adjust Eclipse preferences. Suppress unnecessary warnings about serialized classes. Window, Preferences, Java, Compiler, Errors/Warnings, change "Serializable class without ..." to "Ignore". Many other personal preferences re font size, indentation style, etc.

Installing MySql Community Server (Database)

• Use the following link http://dev.mysql.com/downloads/mysql/ to download MySql Community Server
• MySQL will be installed as a service which will start up with Windows. It is recommended you accept most of the defaults although I did check in the "Include Bin Directory in Windows Path" checkbox (which allows Windows to find executables from the command line if you choose to run it that way occasionally) and you should add a password when given the opportunity. You should configure your firewall to accept the port(usually port 3306).
• Download the Java MySql Connector dev.mysql.com/downloads/connector/j/5.1.html
• Download and unzip the file linked above. Copy the mysql-connector-java-5.1.6-bin.jar to the WEB-INF/lib
• Download the proper Graphic User Interface for your MySql: dev.mysql.com/downloads/gui-tools/5.0.html

Java Code to Create your Database, Make sure you replace username and password with the proper values:

import java.io.*;
import java.sql.*;

public class CreateDatabase{
  public static void main(String[] args) {
    System.out.println("Database creation example!");
    Connection con = null;
    try{
      Class.forName("com.mysql.jdbc.Driver");
      con = DriverManager.getConnection
("jdbc:mysql://localhost:3306/","root","HashMap");
      try{
        Statement st = con.createStatement();
        BufferedReader bf = new BufferedReader
(new InputStreamReader(System.in));
        System.out.println("Enter Database name:");
        String database = bf.readLine();
        st.executeUpdate("CREATE DATABASE "+database);
        System.out.println("1 row(s) affected");
      }
      catch (SQLException s){
        System.out.println("SQL statement is not executed!");
      }
    }
    catch (Exception e){
      e.printStackTrace();
    }
  }
}

Java Code to connect to the database you just created.

import java.sql.*;

public class MysqlConnect{
  public static void main(String[] args) {
    System.out.println("MySQL Connect Example.");
    Connection conn = null;
    String url = "jdbc:mysql://localhost:3306/";
    String dbName = "Replace with YOUR SCHEMA NAME";
    String driver = "com.mysql.jdbc.Driver";
    String userName = "root"; 
    String password = "root";
    try {
      Class.forName(driver).newInstance();
      conn = DriverManager.getConnection(url+dbName,userName,password);
      System.out.println("Connected to the database");
      conn.close();
      System.out.println("Disconnected from database");
    } catch (Exception e) {
      e.printStackTrace();
    }
  }
}

Installing Microsoft Visual Studio 2005 on Windows 7

 

Install Microsoft Visual Studio 2005 and then install the following updates:

Service Pack 1

http://www.microsoft.com/downloads/details.aspx?familyid=bb4a75ab-e2d4-4c96-b39d-37baf6b5b1dc&displaylang=en

Service Pack 1 Update

http://www.microsoft.com/downloads/details.aspx?FamilyID=90e2942d-3ad1-4873-a2ee-4acc0aace5b6&displaylang=en

String.matches()

public boolean matches(String regex)

Tells whether or not this string matches the given regular expression.

Using String.split() instead of String Tokenizer

 

StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.

Design and Analysis of Algorithms

Resources:

MIT OCW : http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/index.htm

Princeton : http://www.cs.princeton.edu/~wayne/cs423/lectures.html

<c:out = “” /> tag problem

While using the JSTL a very common problem faced is that

<c:out value="${now}"/> tags are not interpreted as they are supposed to be.

After going through the forums, I changed my xml version from 2.5 to 2.4 and all the tags started working correctly.

Earlier XML:

<?xml version="1.0" encoding="utf-8"?>
<web-app xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xmlns="http://java.sun.com/xml/ns/javaee"
xmlns:web="http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd"
xsi:schemaLocation="http://java.sun.com/xml/ns/javaee
http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd" version="2.5">

After Making the Changes:

<?xml version="1.0" encoding="utf-8"?>
<web-app xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xmlns="http://java.sun.com/xml/ns/javaee"
xmlns:web="http://java.sun.com/xml/ns/javaee/web-app_2_4.xsd"
xsi:schemaLocation="http://java.sun.com/xml/ns/javaee
http://java.sun.com/xml/ns/javaee/web-app_2_4.xsd" version="2.4">

 

References: http://forum.springsource.org/archive/index.php/t-21093.html

Local Datastore Dashboard for Google App Engine

 

While the server is running… Here is the URL

http://localhost:8888/_ah/admin/datastore

Using the JSP Standard Tag Library (JSTL) in Spring Framework

We need jar files namely jstl.jar and standard.jar that are there in the Spring Framework, these files are to be copied to ‘/war/WEB-INF/lib' directory.

Also we have to copy this file from the Spring distribution ('spring-framework-2.5/dist/resources/spring-form.tld') to the 'springapp/war/WEB-INF/tld' directory that we also need to create. Next we must also add a <taglib/> entry to the 'web.xml' file.

  <jsp-config>
    <taglib>
      <taglib-uri>/spring</taglib-uri>
      <taglib-location>/WEB-INF/tld/spring-form.tld</taglib-location>
    </taglib>
  </jsp-config>

Using Spring Framework and Google App Engine for a Web Application.

Step by Step Procedure for the Hello World Application:

• Install the Google Plugin
• Create a new Web application and untick GWT (Google Web Toolkit)
• Download the latest Spring Release
• Add the Jars to the folder WEB-INF/lib

The following JAR files should be present in the folder:

Make the Following Changes to the web.xml file

<?xml version="1.0" encoding="utf-8"?>

<web-app xmlns="http://java.sun.com/xml/ns/javaee" version="2.5">
    <servlet>
        <servlet-name>dispatcher</servlet-name>
        <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
        <load-on-startup>1</load-on-startup>
    </servlet>

    <servlet-mapping>
        <servlet-name>dispatcher</servlet-name>
        <url-pattern>/a/*</url-pattern>
    </servlet-mapping>
</web-app>

Create a file dispatcher-servler.xml in the WEB-INF Directory

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:p="http://www.springframework.org/schema/p"
 xmlns:context="http://www.springframework.org/schema/context"
 xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd
 http://www.springframework.org/schema/context http://www.springframework.org/schema/context/spring-context.xsd">

 <context:component-scan base-package="ipathshala.controllers" />

 <bean id="viewResolver"
 class="org.springframework.web.servlet.view.InternalResourceViewResolver"
 p:prefix="/WEB-INF/views/" p:suffix=".jsp" >
 <property name="viewClass" value="org.springframework.web.servlet.view.JstlView" />
 </bean>

</beans>

HelloController.java

package ipathshala.controllers;

import javax.servlet.http.HttpServletRequest;

import org.springframework.stereotype.Controller;
import org.springframework.ui.ModelMap;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;

import com.google.appengine.api.users.UserService;
import com.google.appengine.api.users.UserServiceFactory;

@Controller
@RequestMapping("/hello")
public class HelloController {

    private UserService userService = UserServiceFactory.getUserService();

    @RequestMapping(method = RequestMethod.GET)
    public String hello(HttpServletRequest request, ModelMap model)
    {
        String url = request.getRequestURI();
        String message;

        if(request.getUserPrincipal() != null)
        {
            message = new StringBuilder()
            .append("Hello, ")
            .append(request.getUserPrincipal().getName())
            .append("! You can <a href=\"")
            .append(userService.createLogoutURL(url))
            .append("\">Sign Out</a>.").toString();
        }else{
            message = new StringBuilder()
            .append("Please ")
            .append("<a href=\"")
            .append(userService.createLoginURL(url))
            .append("\">Sign In</a>.").toString();
        }

        model.addAttribute("message", message);

        return "hello/hello";
    }

}

This line above @RequestMapping("/hello") maps all the requests /a/hello to this controller after being examined by the DispatcherServlet.

Create a Folder views under WEB-INF and two Sub folders hello and common.

hello/hello.jsp

<%@ page contentType="text/html;charset=UTF-8" language="java" %>
<%@ page isELIgnored="false" %>
<%@ include file="/WEB-INF/views/common/includes.jsp" %>
<p>${message}</p>

common/includes.jsp

<%@ page session="false"%>
<%@ taglib prefix="c" uri="http://java.sun.com/jsp/jstl/core" %>
<%@ taglib prefix="fmt" uri="http://java.sun.com/jsp/jstl/fmt" %>

You should now be able to click “Debug” and run the application by visiting “localhost:8888/a/hello”.

References:

• Adent Lord’s Spring 3.0 GAE article: http://www.ardentlord.com/apps/blog/show/829881-spring-3-0-on-google-app-engine
  
• GAE Documentation: http://code.google.com/appengine/docs/java/gettingstarted/
  
• Spring 3.0 Documentation: http://static.springsource.org/spring/docs/3.0.x/spring-framework-reference/html/
  
• Spring MVC 2.5 Tutorial: http://static.springsource.org/docs/Spring-MVC-step-by-step/

 

Session Management using Google User on Google App Engine

Code to be inserted in every JSP Page


HttpSession s = request.getSession();
if (s.getAttribute("logged")==null){
s.setAttribute("from",request.getRequestURI());
response.sendRedirect("/login");
}
else {
s.setAttribute("from",request.getRequestURI());
%>Logout<%
//UserService userSer = (UserService)s.getAttribute("userSer");
}

Login.java


public class Login extends HttpServlet {
    public void doGet(HttpServletRequest request, HttpServletResponse response)
            throws IOException {
     UserService userSer=UserServiceFactory.getUserService();
     User u=userSer.getCurrentUser();
     HttpSession s=request.getSession();
     String from=(String)s.getAttribute("from");
     s.setAttribute("logged","yes");
     s.setAttribute("userSer", userSer);
     response.sendRedirect(userSer.createLoginURL(from));
    
    }
}

Logout.java


public class Logout extends HttpServlet {
    public void doGet(HttpServletRequest request, HttpServletResponse response)
            throws IOException {
    
     HttpSession s = request.getSession();
     String from=(String)s.getAttribute("from");
     UserService us=(UserService)s.getAttribute("userSer");
     s.invalidate();
     response.sendRedirect(us.createLogoutURL("/index.html"));
    
    }
}

Java Best Practices

A good article on Java Best Practices

http://java.sun.com/developer/technicalArticles/javaserverpages/servlets_jsp/

Edit Form Example using php

$query = mysql_query("SELECT * FROM table") or die(mysql_error());

while ($row = mysql_fetch_assoc($query))
{
eco ''; eco 'TV'; eco 'Video'; eco 'Car'; eco 'House'; eco '';
}

Read eco as echo

Source: http://www.webmasterworld.com/forum88/9773.htm

File Upload on Google App Engine using struts2 � A daily technical diary

File Upload on Google App Engine using struts2 � A daily technical diary

http://whyjava.wordpress.com/2009/10/04/file-upload-on-google-app-engine-using-struts2/

Google App Engine and Apache Struts

These are the few links to be referred when you want to use Jakarta Struts on Google App Engine.

http://code.google.com/p/struts2-gae/

http://royjin.wordpress.com/2010/05/25/create-google-app-engine-struts-java-application/

A better and Efficient Date input Calendar

The previous blog post about Input Date Calendar mentioned a link to the project hosting of a date input calendar but it seems like that its not good enough. So I found this another link, This one is more efficient and better and easy to use.

http://www.dynamicdrive.com/dynamicindex7/jasoncalendar.htm

Deleting All entries in the Google Datastore locally

The Google Server (App Engine), simulates the development server on the local machine using a file called as local_db.bin in the WEB-INF/appengine-generated/ directory. (It is not uploaded with your application.)


http://code.google.com/intl/fr/appengine/docs/java/tools/devserver.html#Using_the_Datastore

To delete all entries, stop the server, delete this file and then Start the server again.

Searching the Student Objects stored in the Datastore by their Name

Persistents of Student objects are stored in the datastore. One of their properties is their name. The following is the Java Servlet that searches the objects by their name which match the token and returns them to the JSP Page.




import java.io.IOException;
import java.util.ArrayList;
import java.util.List;


import javax.jdo.PersistenceManager;
import javax.servlet.RequestDispatcher;
import javax.servlet.ServletException;
import javax.servlet.http.*;




@SuppressWarnings("serial")
public class NameSearch extends HttpServlet {
public void doPost(HttpServletRequest req, HttpServletResponse resp)
throws IOException {

String token = req.getParameter("search");
PersistenceManager pm=PMF.get().getPersistenceManager();
String query= "select from " + Student.class.getName();
List students= (List) pm.newQuery(query).execute();
ArrayList results = new ArrayList();
for (Student a:students)
{
// Checking whether token appears in the name whether lower or upper
if (a!=null && token!=null)
if(a.getName().toLowerCase().indexOf(token.toLowerCase()) != -1)
{
// Adding the reference to the object into the ArrayList
System.out.println(a.getName());
results.add(a);
}
}
req.setAttribute("result", results);
//Sending the results data via RequestDispatcher to your JSP Page.
                RequestDispatcher r=req.getRequestDispatcher("SearchAS.jsp");
try 
{
r.forward(req, resp);
} catch (ServletException e) 
{
e.printStackTrace();
}



}
}

Converting String to a date object

When date is input in a form, at the server end it is received as a String, so numerous times it happens that the Date String has to be converted into the Date Object. Here is the code:

01.package org.kodejava.example.java.util;

02. 

03.import java.text.DateFormat;

04.import java.text.SimpleDateFormat;

05.import java.text.ParseException;

06.import java.util.Date;

07. 

08.public class StringToDate

09.{

10.public static void main(String[] args)

11.{

12.DateFormat df = new SimpleDateFormat("dd/MM/yyyy");

13. 

14.try

15.{

16.Date today = df.parse("20/12/2005");           

17.System.out.println("Today = " + df.format(today));

18.} catch (ParseException e)

19.{

20.e.printStackTrace();

21.}

22.}

23.}