For loops and recusion (Part 2)

Posted on by

Recursion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void print(List<int> t)
        {
            for (int i = 0; i < t.Count; i++)
            {
                Console.Write(t[i] + " ");
            }
        }

        static void addToList(List<List<int>> list, ref List<int> temp, int[] t, int j, int cDepth, int maxDepth)
        {
            for (int i = j; i < t.Length; i++)
            {
                temp.Add(t[i]);
                if (cDepth == maxDepth)
                {
                    list.Add(temp);
                    temp = new List<int>(temp);
                    temp.RemoveAt(temp.Count - 1);
                }
                if (cDepth + 1 <= maxDepth)
                {
                    addToList(list, ref temp, t, i + 1, cDepth + 1, maxDepth);
                    temp.RemoveAt(temp.Count - 1);
                }
            }
        }

        static void Main(string[] args)
        {
            List<List<int>> list = new List<List<int>>();
            List<int> temp = new List<int>(10);

            int[] t = { 1, 2, 3 };
            for (int i = 0; i < t.Length; i++)
                addToList(list, ref temp, t, 0, 0, i);

            foreach (List<int> e in list)
            {
                print(e);
                Console.WriteLine();
            }
        }
    }
}

Output:

1
2
3
1 2
1 3
2 3
1 2 3

Nested for loop

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void print(List<int> t)
        {
            for (int i = 0; i < t.Count; i++)
            {
                Console.Write(t[i] + " ");
            }
        }

        static void Main(string[] args)
        {
            int [] arr = {1,2,3};
            List<List<int>> list = new List<List<int>>();

            for (int i = 1; i < (1 << arr.Length); i++)
            {
                List<int> temp = new List<int>();
                for (int j = 0; j < arr.Length; j++)
                {
                    if ((i & (1 << j)) > 0)
                    {
                        temp.Add(arr[j]);
                    }
                }
                if (temp.Count > 0)
                    list.Add(temp);
            }

            foreach (List<int> e in list)
            {
                print(e);
                Console.WriteLine();
            }
        }
    }
}

Output:

1
2
1 2
3
1 3
2 3
1 2 3

Simple Forms using MVC in Spring (Java) with Ajax

Posted on by

1) Create a new “Dynamic Web Project” in Eclipse. Name it “SimpleProject”.
Next, obtain the following jar files

hibernate-validator-4.3.0.Final.jar
jboss-logging-3.1.2.GA.jar
jstl-1.2.jar
spring-beans-3.2.0.M2.jar
spring-context-3.2.0.M2.jar
spring-core-3.2.0.M2.jar
spring-expression-3.2.0.M2.jar
spring-web-3.2.0.M2.jar
spring-webmvc-3.2.0.M2.jar
standard-1.1.2.jar
validation-api-1.0.0.GA.jar
jackson-core-asl-1.7.1.jar

Optional: Use maven to get the jar files. Put the following pom.xml in the same directory as your project

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">

	<modelVersion>4.0.0</modelVersion>
	<groupId>com.mycompany.app</groupId>
	<artifactId>my-module</artifactId>
	<version>1</version>

	<dependencies>
		<dependency>
			<groupId>org.codehaus.jackson</groupId>
			<artifactId>jackson-mapper-asl</artifactId>
			<version>1.7.1</version>
		</dependency>
		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-core</artifactId>
			<version>3.1.2.RELEASE</version>
		</dependency>
		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-beans</artifactId>
			<version>3.1.2.RELEASE</version>
		</dependency>
		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-webmvc</artifactId>
			<version>3.1.2.RELEASE</version>
		</dependency>
		<dependency>
			<groupId>jstl</groupId>
			<artifactId>jstl</artifactId>
			<version>1.2</version>
		</dependency>
		<dependency>
			<groupId>org.hibernate</groupId>
			<artifactId>hibernate-validator</artifactId>
			<version>4.3.0.Final</version>
		</dependency>
	</dependencies>
	<build>
		<defaultGoal>compile</defaultGoal>
		<plugins>
			<plugin>
				<groupId>org.apache.maven.plugins</groupId>
				<artifactId>maven-dependency-plugin</artifactId>
				<version>2.5.1</version>
				<executions>
					<execution>
						<id>copy1</id>
						<phase>compile</phase>
						<goals>
							<goal>copy-dependencies</goal>
						</goals>
						<configuration>
							<outputDirectory>.\WebContent\WEB-INF\lib</outputDirectory>
							<!-- other configurations here -->
						</configuration>
					</execution>
				</executions>
			</plugin>
		</plugins>
	</build>
</project>

2) Create a database class

package com.simplesearch.database;

import java.util.HashMap;
import java.util.Map;

public class SearchDB {
	Map <Integer, String>category;
	
	public Map<Integer, String> getCategory() {
		return category;
	}

	public void setCategory(Map<Integer, String> category) {
		this.category = category;
	}

	public SearchDB()
	{
		category = new HashMap<Integer, String>();
		category.put(10, "Computers");
		category.put(11, "TV");
		category.put(12, "Tablet");
	}
}

3) Create the model class

package com.simplesearch.model;

import javax.validation.constraints.NotNull;
import javax.validation.constraints.Pattern;
import javax.validation.constraints.Size;

import org.hibernate.validator.constraints.Range;

public class SearchModel {
	@NotNull(message="Search cannot be null.")
	@Size(min=1, message="Search cannot be empty.")
	@Pattern(regexp="^[a-z]*$", message="Must contain letters only.")
	String searchTerm;
	
	@Range(min=10, max=12, message="Please select a category.")
	@NotNull(message="Invalid category.")
	int category;
	public String getSearchTerm() {
		return searchTerm;
	}
	public void setSearchTerm(String searchTerm) {
		this.searchTerm = searchTerm;
	}
	public int getCategory() {
		return category;
	}
	public void setCategory(int category) {
		this.category = category;
	}
}

4) Create the controller class

package com.simplesearch.controller;

import java.util.*;

import javax.servlet.http.HttpServletRequest;
import javax.validation.ConstraintViolation;
import javax.validation.Validator;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.web.bind.annotation.ModelAttribute;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.ResponseBody;

import com.simplesearch.database.SearchDB;
import com.simplesearch.model.SearchModel;

@Controller
@RequestMapping(value="/search")
public class SimpleSearchController {
	Validator validator;
	SearchDB db;
	
	public SimpleSearchController()
	{
		db = new SearchDB();
	}
	
	@Autowired
	public SimpleSearchController(Validator validator)
	{
		this.validator = validator;
		db = new SearchDB();
	}
	
	@RequestMapping(method=RequestMethod.GET)
	public String getCreateSearch(Model model)
	{
		model.addAttribute("SearchModel", new SearchModel());
		return "search/index";
	}
	
	@RequestMapping(method=RequestMethod.POST)
	public @ResponseBody Map<String, String> create(@RequestBody SearchModel search)
	{
		Map<String, String> s = new HashMap<String, String>();
		Set<ConstraintViolation<SearchModel>> failures = validator.validate(search);

		if (!failures.isEmpty()) {
			for (ConstraintViolation<SearchModel> constraintViolation : failures) {
				s.put(constraintViolation.getPropertyPath().toString(), constraintViolation.getMessage());
			}
		}

		return s;
	}
	
	@RequestMapping(value="searchResults", method=RequestMethod.GET)
	public String getResult(Model m, HttpServletRequest request)
	{
		SearchModel s = new SearchModel();
		Map<java.lang.String,java.lang.String[]> rMap = request.getParameterMap();
		String []category = rMap.get("category");
		String []searchTerm = rMap.get("searchTerm");
		if(category != null)
		{
			try
			{
				int cat = Integer.parseInt(category[0]);
				s.setCategory(cat);
			}catch(Exception e)
			{
				
			}
		}
		if(searchTerm != null)
		{
			s.setSearchTerm(searchTerm[0]);
		}
		
		Set<ConstraintViolation<SearchModel>> failures = validator.validate(s);
		if (!failures.isEmpty()) {
			m.addAttribute("errorMessages", "Invalid input");
		}
		else
		{
			m.addAttribute("categories", db.getCategory());
			m.addAttribute("searchModel", s);
		}
		
		return "search/searchResults";
	}
	
	@ModelAttribute("category")
	protected Map<Integer, String> categoryList(HttpServletRequest request) throws Exception {
		return db.getCategory();
	}
}

5) Create the views
Create folder “views” under WEB-INF then create folder “search” under “views”
Create index.jsp

<%@ page language="java" contentType="text/html; charset=ISO-8859-1"
    pageEncoding="ISO-8859-1"%>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<%@ taglib uri="http://java.sun.com/jsp/jstl/core" prefix="c" %>
<%@ taglib uri="http://java.sun.com/jsp/jstl/fmt" prefix="fmt" %>
<%@ taglib prefix="form" uri="http://www.springframework.org/tags/form" %>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Search</title>

<script type="text/javascript" src="<c:url value="resources/jquery-1.8.2.min.js" />"></script>

<script type="text/javascript">
$.fn.serializeObject = function()
{
   var o = {};
   var a = this.serializeArray();
   $.each(a, function() {
       if (o[this.name]) {
           if (!o[this.name].push) {
               o[this.name] = [o[this.name]];
           }
           o[this.name].push(this.value || '');
       } else {
           o[this.name] = this.value || '';
       }
   });
   return o;
};

$(document).ready(function() {
	$("#SearchModel").submit(function() {
		$("#category_error").hide();
		$("#searchTerm_error").hide();
		var search = JSON.stringify($('form').serializeObject());
		$.ajax({
			'type':'POST',
			'url':'',
			'contentType': 'application/json',
			'data': search,
			'dataType': 'json',
			'success': function(data) {
				if(data.category != null)
				{
					$("#category_error").show();
					$("#category_error").html(data.category);
				}
				if(data.searchTerm != null)
				{
					$("#searchTerm_error").show();
					$("#searchTerm_error").html(data.searchTerm);
				}
				
				if(data.category == null && data.searchTerm == null)
				{
					window.location.replace("search/searchResults?" + $('form').serialize());
				}
			}
		});
		return false;
	});
});
</script>
</head>
<body>
	<form:form modelAttribute="SearchModel" action="search" method="post">
		Category: 
		<form:select path="category">
			<form:option value="0">--Select--</form:option>
			<form:options items="${category}" />
		</form:select>
		<div id="category_error" style="display:none"></div>
		<br>
		<form:label	id="searchTermLabel" for="searchTerm" path="searchTerm" cssErrorClass="error">Search: </form:label>
		<form:input path="searchTerm" /><form:errors path="searchTerm" />
		<div id="searchTerm_error" style="display:none"></div>
		<br>
		<p>
			<input id="create" type="submit" value="Create" />
		</p>
	</form:form>

</body>
</html>

Create searchResults.jsp

<%@page import="org.apache.jasper.tagplugins.jstl.core.ForEach"%>
<%@ page language="java" contentType="text/html; charset=ISO-8859-1"
    pageEncoding="ISO-8859-1"%>

<%@ taglib uri="http://java.sun.com/jsp/jstl/core" prefix="c" %>
<%@ taglib uri="http://java.sun.com/jsp/jstl/fmt" prefix="fmt" %>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Search</title>
</head>
<body>
	${errorMessages}

	<c:if test="${searchModel != null}">
		You searched for ${searchModel.searchTerm} in category: ${categories[searchModel.category]}
	</c:if>
</body>
</html>

Create welcome.jsp in the “views” folder

<%@ page language="java" contentType="text/html; charset=ISO-8859-1"
    pageEncoding="ISO-8859-1"%>
<%@ taglib uri="http://java.sun.com/jsp/jstl/core" prefix="c" %>

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Insert title here</title>
</head>
<body>
<c:redirect url="search" />
</body>
</html>

6) Create “resources” folder in WebContent folder (same level as WEB-INF). Put jquery js file in resources folder
7) Create the context configuration in WEB-INF folder
servlet-context.xml

<?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:mvc="http://www.springframework.org/schema/mvc"
    xmlns:context="http://www.springframework.org/schema/context"
    xsi:schemaLocation="
        http://www.springframework.org/schema/mvc http://www.springframework.org/schema/mvc/spring-mvc-3.0.xsd
        http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans-3.0.xsd
        http://www.springframework.org/schema/context http://www.springframework.org/schema/context/spring-context-3.0.xsd">
 
    <!-- DispatcherServlet Context: defines this servlet's request-processing infrastructure -->
 
    <!-- Scans within the base package of the application for @Components to configure as beans -->
    <!-- @Controller, @Service, @Configuration, etc. -->
    <context:component-scan base-package="com.simplesearch" />
 
    <!-- Enables the Spring MVC @Controller programming model -->
    <mvc:annotation-driven />
    <mvc:view-controller path="/" view-name="welcome"  />
 	<bean class="org.springframework.web.servlet.view.InternalResourceViewResolver">
		<property name="prefix" value="/WEB-INF/views/"/>
		<property name="suffix" value=".jsp"/>
	</bean>
	
    <mvc:resources mapping="/resources/**" location="/resources/" />
</beans>

Note: Make sure to replace “com.simplesearch” with your package.
Optional: If this configuration is not present, you will need to provide the full path in the get request.

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

For example:
Without the configuration

	@RequestMapping(method=RequestMethod.GET)
	public String getCreateSearch(Model model)
	{
		model.addAttribute("SearchModel", new SearchModel());
		return "/WEB-INF/views/search/index.jsp";
	}

With the configuration

	@RequestMapping(method=RequestMethod.GET)
	public String getCreateSearch(Model model)
	{
		model.addAttribute("SearchModel", new SearchModel());
		return "search/index";
	}

8) Create/Modify the web.xml (in WEB-INF)

<?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_3_0.xsd" id="WebApp_ID" version="3.0">
  <display-name>SimpleSearch</display-name>
    <servlet>
        <servlet-name>appServlet</servlet-name>
        <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
        <init-param>
            <param-name>contextConfigLocation</param-name>
            <param-value>/WEB-INF/servlet-context.xml</param-value>
        </init-param>
        <load-on-startup>1</load-on-startup>
    </servlet>       
 
    <servlet-mapping>
        <servlet-name>appServlet</servlet-name>
        <url-pattern>/</url-pattern>
    </servlet-mapping>
</web-app>

Note: Make sure “/WEB-INF/servlet-context.xml” points to your spring configuration

Finally,
go to http://localhost:8080/SimpleProject in your browser.

For loops and recursion

Posted on by

Example 1
Nested for loop

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static int depth = 4;
        static void funcFor()
        {
            for (int i = 0; i < depth; i++)
            {
                for (int j = 0; j < depth; j++)
                {
                    for (int k = 0; k < depth; k++)
                    {
                        for (int l = 0; l < depth; l++)
                        {
                            Console.WriteLine(i + " " + j + " " + k + " " + l);
                        }
                    }
                }
            }
        }

        static void Main(string[] args)
        {
            funcFor();
        }
    }
}

Output:

0 0 0
0 0 1
0 0 2
0 0 3
0 1 1
0 1 2
0 1 3
0 2 2
0 2 3
0 3 3
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

Same functionality but with recursion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static int[] arr1 = { 1, 2, 3 };
        
        static void print(int[] a)
        {
            for (int i = 0; i < a.Length; i++)
                Console.Write(a[i] + " ");
            Console.WriteLine();
        }

        static void funcR(int j, int depth, int maxDepth, int maxLength)
        {
            for (int i = j; i <= maxLength; i++)
            {
                arr1[depth] = i;
                if (depth == maxDepth)
                    print(arr1);
                if (depth + 1 <= maxDepth)
                    funcR(i, depth + 1, maxDepth, maxLength);
            }
        }

        static void Main(string[] args)
        {
            funcR(0, 0, arr1.Length - 1, arr1.Length);
        }
    }
}

Kruskal’s algorithm

Posted on by

Solution to problem 107 @ Project Euler. Implemented using Kruskal’s algorithm.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace problem107
{
    class Program
    {
        class Vertex
        {
            public Vertex(int index)
            {
                this.index = index;
            }
            public int index;

            public override bool Equals(object obj)
            {
                return index == ((Vertex)obj).index;
            }
            public override int GetHashCode()
            {
                return index;
            }

            public override string ToString()
            {
                return index.ToString();
            }
        }

        class Edge
        {
            public Edge(int weight, Vertex v1, Vertex v2)
            {
                this.weight = weight;
                this.v1 = v1;
                this.v2 = v2;
            }
            public int weight;
            public Vertex v1;
            public Vertex v2;

            public override bool Equals(object obj)
            {
                Edge e2 = (Edge)obj;
                return (this.v1.Equals(e2.v1) && this.v2.Equals(e2.v2))||
                    (this.v2.Equals(e2.v1) && this.v1.Equals(e2.v2));
            }

            public override int GetHashCode()
            {
                return weight;
            }

            public override string ToString()
            {
                return "" + v1.index + "-" + v2.index;
            }

            public static int compareByWeight(Edge e1, Edge e2)
            {
                if (e1.weight < e2.weight)
                    return -1;
                else if (e1.weight > e2.weight)
                    return 1;
                else
                    return 0;
            }
        }

        class Tree
        {
            public List<Vertex> vertices = new List<Vertex>();
            public List<Edge> edges = new List<Edge>();
            public static Tree Merge(Tree t1, Tree t2, Edge e)
            {
                Tree newTree = new Tree();
                newTree.vertices.AddRange(t1.vertices);
                newTree.vertices.AddRange(t2.vertices);
                newTree.edges.AddRange(t1.edges);
                newTree.edges.AddRange(t2.edges);
                newTree.edges.Add(e);
                return newTree;
            }
        }

        class Forest
        {
            public List<Tree> trees = new List<Tree>(); 
        }

        static List<Vertex> createVertices(int n)
        {
            List<Vertex> v = new List<Vertex>();
            for (int i = 0; i < n; i++)
            {
                v.Add(new Vertex(i));
            }
            return v;
        }

        //http://en.wikipedia.org/wiki/Kruskal%27s_algorithm#Description
        static void solve()
        {
            string[] lines = System.IO.File.ReadAllLines(@"network.txt");
            //create a forest
            Forest F = new Forest();

            //create a list of vertices
            List<Vertex> vertices = createVertices(lines.Length);

            //each vertex is a tree in a forest
            foreach (Vertex v in vertices)
            {
                Tree t1 = new Tree();
                t1.vertices.Add(v);
                F.trees.Add(t1);
            }

            //create a list of all edges
            List<Edge> S = new List<Edge>();

            for (int i = 0; i < lines.Length; i++)
            {
                //find vertex to one end
                Vertex v1 = vertices.Find(x => x.index == i);

                string[] e = lines[i].Split(',');
                for (int j = 0; j < e.Length; j++)
                {
                    if (e[j] != "-")
                    {
                        //find vertex to the other end
                        Vertex v2 = vertices.Find(x => x.index == j);

                        //create the edge
                        Edge edge = new Edge(Convert.ToInt32(e[j]), v1, v2);

                        //try to find the edge in the list
                        Edge temp = S.Find(x => x.Equals(edge));

                        //if not found, add the add to the list
                        if (temp == null)
                            S.Add(edge);
                    }
                }
            }

            //sort them by weight. smallest weight first
            S.Sort(Edge.compareByWeight);

            int sumBeforeMininized = S.Sum(x => x.weight);

            int count = 0;
            while (S.Count > 0)
            {
                //get the first edge from the list
                Edge e = S[count];
                //remove the edge
                S.Remove(e);

                //find the trees that contains the vertices in edge e
                Tree t1 = F.trees.Find(x => x.vertices.Find(y => y.Equals(e.v1)) != null);
                Tree t2 = F.trees.Find(x => x.vertices.Find(y => y.Equals(e.v2)) != null);

                //if the 2 trees found are the same, ignore
                if (t1 == t2)
                    continue;

                //Merge the two tress together by creating a new tree
                //then adding all the vertices and edges including
                //edge e
                Tree tFinal = Tree.Merge(t1, t2, e);

                //remove the 2 trees from the forest and add the new merged tree
                F.trees.Remove(t1);
                F.trees.Remove(t2);
                F.trees.Add(tFinal);
            }

            int sumAfterMininized = F.trees[0].edges.Sum(x => x.weight);
            Console.WriteLine(sumBeforeMininized - sumAfterMininized);
        }

        static void Main(string[] args)
        {
            solve();
        }
    }
}

Simple Forms using MVC in Spring (Java)

Posted on by

1) Create a new “Dynamic Web Project” in Eclipse. Name it “SimpleProject”.
Next, obtain the following jar files

hibernate-validator-4.3.0.Final.jar
jboss-logging-3.1.2.GA.jar
jstl-1.2.jar
spring-beans-3.2.0.M2.jar
spring-context-3.2.0.M2.jar
spring-core-3.2.0.M2.jar
spring-expression-3.2.0.M2.jar
spring-web-3.2.0.M2.jar
spring-webmvc-3.2.0.M2.jar
standard-1.1.2.jar
validation-api-1.0.0.GA.jar

Optional: Use maven to get the jar files. Put the following pom.xml in the same directory as your project

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">

	<modelVersion>4.0.0</modelVersion>
	<groupId>com.mycompany.app</groupId>
	<artifactId>my-module</artifactId>
	<version>1</version>

	<dependencies>
		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-core</artifactId>
			<version>3.1.2.RELEASE</version>
		</dependency>
		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-beans</artifactId>
			<version>3.1.2.RELEASE</version>
		</dependency>
		<dependency>
			<groupId>org.springframework</groupId>
			<artifactId>spring-webmvc</artifactId>
			<version>3.1.2.RELEASE</version>
		</dependency>
		<dependency>
			<groupId>jstl</groupId>
			<artifactId>jstl</artifactId>
			<version>1.2</version>
		</dependency>
		<dependency>
			<groupId>org.hibernate</groupId>
			<artifactId>hibernate-validator</artifactId>
			<version>4.3.0.Final</version>
		</dependency>
	</dependencies>
	<build>
		<defaultGoal>compile</defaultGoal>
		<plugins>
			<plugin>
				<groupId>org.apache.maven.plugins</groupId>
				<artifactId>maven-dependency-plugin</artifactId>
				<version>2.5.1</version>
				<executions>
					<execution>
						<id>copy1</id>
						<phase>compile</phase>
						<goals>
							<goal>copy-dependencies</goal>
						</goals>
						<configuration>
							<outputDirectory>.\WebContent\WEB-INF\lib</outputDirectory>
							<!-- other configurations here -->
						</configuration>
					</execution>
				</executions>
			</plugin>
		</plugins>
	</build>
</project>

2) Create a database class

package com.simplesearch.database;

import java.util.HashMap;
import java.util.Map;

public class SearchDB {
	Map <Integer, String>category;
	
	public Map<Integer, String> getCategory() {
		return category;
	}

	public void setCategory(Map<Integer, String> category) {
		this.category = category;
	}

	public SearchDB()
	{
		category = new HashMap<Integer, String>();
		category.put(10, "Computers");
		category.put(11, "TV");
		category.put(12, "Tablet");
	}
}

3) Create the model class

package com.simplesearch.model;

import javax.validation.constraints.Pattern;
import javax.validation.constraints.Size;

import org.hibernate.validator.constraints.Range;

public class SearchModel {
	@Size(min = 1, message="Search cannot be empty.")
	@Pattern(regexp="^[a-z]+$", message="Must contain letters only.")
	String searchTerm;
	
	@Range(min=10, max=12, message="Please select a category.")
	int category;
	public String getSearchTerm() {
		return searchTerm;
	}
	public void setSearchTerm(String searchTerm) {
		this.searchTerm = searchTerm;
	}
	public int getCategory() {
		return category;
	}
	public void setCategory(int category) {
		this.category = category;
	}
}

4) Create the controller class

package com.simplesearch.controller;

import java.io.IOException;
import java.util.Map;
import java.util.Set;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import javax.validation.ConstraintViolation;
import javax.validation.Validator;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.web.bind.annotation.ModelAttribute;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;

import com.simplesearch.database.SearchDB;
import com.simplesearch.model.SearchModel;

@Controller
@RequestMapping(value="/search")
public class SimpleSearchController {
	Validator validator;
	SearchDB db;
	
	public SimpleSearchController()
	{
		db = new SearchDB();
	}
	@Autowired
	public SimpleSearchController(Validator validator)
	{
		this.validator = validator;
		db = new SearchDB();
	}
	
	@RequestMapping(method=RequestMethod.GET)
	public String getCreateSearch(Model model)
	{
		model.addAttribute("SearchModel", new SearchModel());
		return "search/index";
	}
	
	@RequestMapping(method=RequestMethod.POST)
	public void create(SearchModel search, HttpServletResponse response)
	{
		Set<ConstraintViolation<SearchModel>> failures = validator.validate(search);

		try {
			if (!failures.isEmpty()) {
				response.getWriter().print("Search failed. Reason(s): ");
				response.getWriter().println();
				for (ConstraintViolation<SearchModel> constraintViolation : failures) {
					response.getWriter().println(constraintViolation.getMessage());
				}
			}
			else
			{
				response.getWriter().println("You searched for: " + search.getSearchTerm() + 
						" in category " + db.getCategory().get(search.getCategory()));
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		
	}
	
	@ModelAttribute("category")
	protected Map<Integer, String> categoryList(HttpServletRequest request) throws Exception {
		return db.getCategory();
	}
}

5) Create the views
Create folder “views” under WEB-INF then create folder “search” under “views”
Create index.jsp

<%@ page language="java" contentType="text/html; charset=ISO-8859-1"
    pageEncoding="ISO-8859-1"%>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<%@ taglib uri="http://java.sun.com/jsp/jstl/core" prefix="c" %>
<%@ taglib uri="http://java.sun.com/jsp/jstl/fmt" prefix="fmt" %>
<%@ taglib prefix="form" uri="http://www.springframework.org/tags/form" %>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Search</title>
</head>
<body>
	<form:form modelAttribute="SearchModel" action="search" method="post">
		Category: 
		<form:select path="category">
			<form:option value="0">--Select--</form:option>
			<form:options items="${category}" />
		</form:select>
		<br>
		<br>
		<form:label	id="searchTermLabel" for="searchTerm" path="searchTerm" cssErrorClass="error">Search: </form:label>
		<form:input path="searchTerm" /><form:errors path="searchTerm" />
		<br>
		<p>
			<input id="create" type="submit" value="Create" />
		</p>
	</form:form>

</body>
</html>

6) Create the context configuration in WEB-INF folder
servlet-context.xml

<?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:mvc="http://www.springframework.org/schema/mvc"
    xmlns:context="http://www.springframework.org/schema/context"
    xsi:schemaLocation="
        http://www.springframework.org/schema/mvc http://www.springframework.org/schema/mvc/spring-mvc-3.0.xsd
        http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans-3.0.xsd
        http://www.springframework.org/schema/context http://www.springframework.org/schema/context/spring-context-3.0.xsd">
 
    <!-- DispatcherServlet Context: defines this servlet's request-processing infrastructure -->
 
    <!-- Scans within the base package of the application for @Components to configure as beans -->
    <!-- @Controller, @Service, @Configuration, etc. -->
    <context:component-scan base-package="com.simplesearch" />
 
    <!-- Enables the Spring MVC @Controller programming model -->
    <mvc:annotation-driven />
 
 	<bean class="org.springframework.web.servlet.view.InternalResourceViewResolver">
		<property name="prefix" value="/WEB-INF/views/"/>
		<property name="suffix" value=".jsp"/>
	</bean>
</beans>

Note: Make sure to replace “com.simplesearch” with your package.
Optional: If this configuration is not present, you will need to provide the full path in the get request.

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

For example:
Without the configuration

	@RequestMapping(method=RequestMethod.GET)
	public String getCreateSearch(Model model)
	{
		model.addAttribute("SearchModel", new SearchModel());
		return "/WEB-INF/views/search/index.jsp";
	}

With the configuration

	@RequestMapping(method=RequestMethod.GET)
	public String getCreateSearch(Model model)
	{
		model.addAttribute("SearchModel", new SearchModel());
		return "search/index";
	}

7) Create/Modify the web.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_3_0.xsd" id="WebApp_ID" version="3.0">
  <display-name>SimpleSearch</display-name>
    <servlet>
        <servlet-name>appServlet</servlet-name>
        <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
        <init-param>
            <param-name>contextConfigLocation</param-name>
            <param-value>/WEB-INF/servlet-context.xml</param-value>
        </init-param>
        <load-on-startup>1</load-on-startup>
    </servlet>       
 
    <servlet-mapping>
        <servlet-name>appServlet</servlet-name>
        <url-pattern>/</url-pattern>
    </servlet-mapping>
</web-app>

Note: Make sure “/WEB-INF/servlet-context.xml” points to your spring configuration
8) Run on Tomcat. The address should be “http://localhost:8080/SimpleProject/search&#8221;

Simple Forms using MVC in ASP.net

Posted on by

1) Create a new “ASP.NET MVC 3 Web Application” in Visual Studio Web Developer.

2) Create a simple database class (used for retrieving data)
Optional: Create a folder for the database class

SearchDB.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace MvcApplication2
{
    public class Category
    {
        public Category(int id, string name)
        {
            this.id = id;
            this.name = name;
        }
        public int id { get; set; }
        public string name { get; set; }
    }

    public class SearchDB
    {
        public SearchDB()
        {
            List<Category> l = new List<Category>();
            Category s1 = new Category(10, "Computers");
            l.Add(s1);
            s1 = new Category(11, "TV");
            l.Add(s1);
            s1 = new Category(12, "Tablets");
            l.Add(s1);

            categories = l;
        }

        public List<Category> categories { get; set; }
    }
}

3) Create the model
Make sure to create the class in the “Models” folder

SearchModel.cs

using System;
using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;
using System.Linq;
using System.Web;

namespace MvcApplication2.Models
{
    public class category
    {
        public int id { get; set; }
        public string name { get; set; }
    }

    public class SearchModel
    {
        [Required(ErrorMessage = "Cannot be empty")]
        [Display(Name = "Search")]
        [RegularExpression("^[a-z]+$", ErrorMessage="Lowercase letters only")]
        public string searchTerm { get; set; }

        [Display(Name = "Category")]
        public int CategoryDDL { get; set; }
    }
}

4) Create controller
Make sure to create class in the “Controller” folder

SearchController.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Mvc;
using MvcApplication2.Models;

namespace MvcApplication2.Controllers
{
    public class SearchController : Controller
    {
        SearchDB db = new SearchDB();
        //
        // GET: /Search/

        public ActionResult Index()
        {
            ViewBag.CategoryDDL = new SelectList(db.categories, "id", "name");
            return View();
        }

        [HttpPost]
        public ActionResult Index(SearchModel search)
        {
            if (ModelState.IsValid)
            {
                return RedirectToAction("SearchResults", search);
            }

            return View(search);
        }

        public ActionResult SearchResults(SearchModel search)
        {
            if (ModelState.IsValid == false)
            {
                return Content("Invalid Input!");
            }

            ViewBag.CategoryName = db.categories.Find(m => m.id == search.CategoryDDL).name;
            return View(search);
        }
    }
}

5) Create View
Make sure to create a new folder “Search” in “Views” folder
Index.cshtml

@model MvcApplication2.Models.SearchModel

@{
    ViewBag.Title = "ViewPage1";
}

<script src="@Url.Content("~/Scripts/jquery.validate.min.js")" type="text/javascript"></script>
<script src="@Url.Content("~/Scripts/jquery.validate.unobtrusive.min.js")" type="text/javascript"></script>

@ViewBag.Message
@using (Html.BeginForm())
{
    @Html.LabelFor(m => m.CategoryDDL)
    @Html.DropDownList("CategoryDDL")
    <br />
    <br />
                                  
    @Html.LabelFor(m => m.searchTerm)
    @Html.TextBoxFor(m => m.searchTerm)
    <br />
    @Html.ValidationMessageFor(m => m.searchTerm)
    <p>
        <input type="submit" value="Search" />
    </p>                            
}

SearchResults.cshtml

@model MvcApplication2.Models.SearchModel

<!DOCTYPE html>

<html>
<head>
    <title>Search Results</title>
</head>
<body>
    <div>
       You have searched for @Model.searchTerm in category @ViewBag.CategoryName
        <br />
        @Html.ActionLink("Back to Search", "Index")
    </div>
</body>
</html>

http://localhost:(port)/search

Dijkstra’s algorithm

Posted on by

Solution to Problem 83 on Project Euler. Solution implemented using Dijkstra’s shortest path algorithm.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace problem83
{
    class Node
    {
        public Node(int value, int x, int y)
        {
            this.value = value;
            this.x = x;
            this.y = y;
        }
        public int value;
        public int x;
        public int y;

        public override string ToString()
        {
            return value + " " + x + " " + y;
        }
    }

    class Program
    {
        static int size = 80;
        static public Node[,] grid = new Node[size, size];
        static public List<Node> ListOfNodes = new List<Node>();
        static void generateGrid()
        {
            string[] lines = System.IO.File.ReadAllLines(@"matrix.txt");
            size = lines.Length;
            grid = new Node[size, size];
            for (int i = 0; i < lines.Length; i++)
            {
                string[] s = lines[i].Split(',');
                for (int j = 0; j < s.Length; j++)
                {
                    grid[j, i] = new Node(Convert.ToInt32(s[j]), j, i);
                    ListOfNodes.Add(grid[j, i]);
                }
            }
        }

        static Node findSmallestDistance(Hashtable dist, List<Node> Q)
        {
            int distance = int.MaxValue;
            Node node = null;

            foreach (Node n in Q)
            {
                if ((int)dist[n] < distance)
                {
                    distance = (int)dist[n];
                    node = n;
                }
            }
            return node;
        }

        static Node[] findNeighbor(Node n)
        {
            List<Node> neighbor = new List<Node>();
            int x = n.x;
            int y = n.y;
            if (x + 1 < size)
                neighbor.Add(grid[x + 1, y]);
            if (x - 1 >= 0)
                neighbor.Add(grid[x - 1, y]);
            if (y + 1 < size)
                neighbor.Add(grid[x, y + 1]);
            if (y - 1 >= 0)
                neighbor.Add(grid[x, y - 1]);

            return neighbor.ToArray<Node>();
        }

        static void Dijkstra()
        {
            //hashtable to store the sum (or distance)
            Hashtable dist = new Hashtable();
            //List to store all the nodes
            List<Node> Q = new List<Node>();

            for (int y = 0; y < size; y++)
            {
                for (int x = 0; x < size; x++)
                {
                    Node n = grid[x, y];
                    //set node as key and value to infinity (or int max)
                    //because all sum (or distance) is infinity
                    dist[n] = int.MaxValue;
                    //add node to list
                    Q.Add(n);
                }
            }

            //set the first sum to the first value in the grid
            dist[grid[0, 0]] = grid[0, 0].value;

            while (Q.Count > 0)
            {
                //find the node with the smallest sum (or shortest distance)
                Node u = findSmallestDistance(dist, Q);
                //remove it from the list Q
                Q.Remove(u);

                //if the smallest sum (or distance) is infinity
                //then no need to continue
                if ((int)dist[u] == int.MaxValue)
                    break;

                //locate the neighbors in the grid
                Node[] neighbors = findNeighbor(u);
                foreach (Node v in neighbors)
                {
                    //add the neighbor's value to the sum (or distance) of current node. 
                    int alt = (int)dist[u] + v.value;
                    //if the value is smaller, replace that value
                    if (alt < (int)dist[v])
                    {
                        dist[v] = alt;
                    }
                }
            }

            Console.WriteLine(dist[grid[size - 1, size - 1]]);
        }

        static void solve()
        {
            generateGrid();
            Dijkstra();
        }
        static void Main(string[] args)
        {
            solve();
        }
    }
}

Using AsParallel for parallel processing

Posted on by 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            BigInteger[] factorialArray = new BigInteger[100000];
            for (int i = 0; i < 100000; i++)
                factorialArray[i] = i + 1;
            var y = factorialArray.AsParallel().Aggregate((factorial, i) => factorial * i);


            //632382 ^ 518061
            //make sure to run on a quad-core computer or else it will take very long
            BigInteger[] exponent = new BigInteger[518061];
            for (int i = 0; i < 518061; i++)
                exponent[i] = 632382;
            var g = exponent.AsParallel().Aggregate((product, i) => product * i);
        }
    }
}

Postfix Calculator in C#

Posted on by 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace calculator
{
    public enum OperatorType { MULTIPLY, DIVIDE, ADD, SUBTRACT, EXPONENTIAL, OPAREN, CPAREN };
    public interface Element
    {
    }

    public class NumberElement : Element
    {
        double number;
        public Double getNumber()
        {
            return number;
        }

        public NumberElement(String number)
        {
            this.number = Double.Parse(number);
        }

        public override String ToString()
        {
            return ((int)number).ToString();
        }
    }

    public class OperatorElement : Element
    {
        public OperatorType type;
        char c;
        public OperatorElement(char op)
        {
            c = op;
            if (op == '+')
                type = OperatorType.ADD;
            else if (op == '-')
                type = OperatorType.SUBTRACT;
            else if (op == '*')
                type = OperatorType.MULTIPLY;
            else if (op == '/')
                type = OperatorType.DIVIDE;
            else if (op == '^')
                type = OperatorType.EXPONENTIAL;
            else if (op == '(')
                type = OperatorType.OPAREN;
            else if (op == ')')
                type = OperatorType.CPAREN;
        }

        public override String ToString()
        {
            return c.ToString();
        }
    }

    public class Parser
    {
        List<Element> e = new List<Element>();
        public List<Element> Parse(String s)
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.Length; i++)
            {
                char c = s[i];
                if (Char.IsDigit(c))
                    sb.Append(c);
                if (i + 1 < s.Length)
                {
                    char d = s[i + 1];
                    if (Char.IsDigit(d) == false && sb.Length > 0)
                    {
                        e.Add(new NumberElement(sb.ToString()));
                        //clears stringbuilder
                        sb.Remove(0, sb.Length);
                    }
                }

                if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
                        || c == '(' || c == ')')
                    e.Add(new OperatorElement(c));
            }
            if (sb.Length > 0)
                e.Add(new NumberElement(sb.ToString()));

            return e;
        }
    }


    public class InfixToPostfix
    {
        List<Element> converted = new List<Element>();
        int Precedence(OperatorElement c)
        {
            if (c.type == OperatorType.EXPONENTIAL)
                return 2;
            else if (c.type == OperatorType.MULTIPLY || c.type == OperatorType.DIVIDE)
                return 3;
            else if (c.type == OperatorType.ADD || c.type == OperatorType.SUBTRACT)
                return 4;
            else
                return Int32.MaxValue;
        }

        public void ProcessOperators(Stack<Element> st, Element element, Element top)
        {
            while (st.Count > 0 && Precedence((OperatorElement)element) >= Precedence((OperatorElement)top))
            {
                Element p = st.Pop();
                if (((OperatorElement)p).type == OperatorType.OPAREN)
                    break;
                converted.Add(p);
                if (st.Count > 0)
                    top = st.First();
            }
        }
        public List<Element> ConvertFromInfixToPostFix(List<Element> e)
        {
            List<Element> stack1 = new List<Element>(e);
            Stack<Element> st = new Stack<Element>();
            for (int i = 0; i < stack1.Count; i++)
            {
                Element element = stack1[i];
                if (element.GetType().Equals(typeof(OperatorElement)))
                {
                    if (st.Count == 0 ||
                            ((OperatorElement)element).type == OperatorType.OPAREN)
                        st.Push(element);
                    else
                    {
                        Element top = st.First();
                        if (((OperatorElement)element).type == OperatorType.CPAREN)
                            ProcessOperators(st, element, top);
                        else if (Precedence((OperatorElement)element) < Precedence((OperatorElement)top))
                            st.Push(element);
                        else
                        {
                            ProcessOperators(st, element, top);
                            st.Push(element);
                        }
                    }
                }
                else
                    converted.Add(element);
            }

            //pop all operators in stack
            while (st.Count > 0)
            {
                Element b1 = st.Pop();
                converted.Add(b1);
            }

            return converted;
        }

        public override String ToString()
        {
            StringBuilder s = new StringBuilder();
            for (int j = 0; j < converted.Count; j++)
                s.Append(converted[j].ToString() + " ");
            return s.ToString();
        }
    }

    public class PostFixEvaluator
    {
        Stack<Element> stack = new Stack<Element>();

        NumberElement calculate(NumberElement left, NumberElement right, OperatorElement op)
        {
            Double temp = Double.MaxValue;
            if (op.type == OperatorType.ADD)
                temp = left.getNumber() + right.getNumber();
            else if (op.type == OperatorType.SUBTRACT)
                temp = left.getNumber() - right.getNumber();
            else if (op.type == OperatorType.MULTIPLY)
                temp = left.getNumber() * right.getNumber();
            else if (op.type == OperatorType.DIVIDE)
                temp = left.getNumber() / right.getNumber();
            else if (op.type == OperatorType.EXPONENTIAL)
                temp = Math.Pow(left.getNumber(), right.getNumber());

            return new NumberElement(temp.ToString());
        }
        public Double Evaluate(List<Element> e)
        {
            List<Element> v = new List<Element>(e);
            for (int i = 0; i < v.Count; i++)
            {
                Element element = v[i];
                if (element.GetType().Equals(typeof(NumberElement)))
                    stack.Push(element);
                if (element.GetType().Equals(typeof(OperatorElement)))
                {
                    NumberElement right = (NumberElement)stack.Pop();
                    NumberElement left = (NumberElement)stack.Pop();
                    NumberElement result = calculate(left, right, (OperatorElement)element);
                    stack.Push(result);
                }
            }
            return ((NumberElement)stack.Pop()).getNumber();
        }
    }

    class Program
    {
        public double Calculate(String s)
        {
            Parser p = new Parser();
            List<Element> e = p.Parse(s);
            InfixToPostfix i = new InfixToPostfix();
            e = i.ConvertFromInfixToPostFix(e);

            PostFixEvaluator pfe = new PostFixEvaluator();
            return pfe.Evaluate(e);
        }

        static void Main(string[] args)
        {
            Program c = new Program();
	        double d = c.Calculate("4+6+9*8-(5*6+9)^2");
            Console.WriteLine(d);
        }
    }
}

Finding duplicates using Linq

Posted on by 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[] { 3, 3, 3, 4, 5, 6, 6, 7, 9,9,9,9,9 };

            var p = from n in arr 
                    group n by n into g where g.Count() > 1
                    select new {num = g.Key, count = g.Count()};
            foreach (var y in p)
            {
                Console.WriteLine(y.num + " " + y.count);
            }
        }
    }
}