Solution: The RailRoad Problem

Here is the solution for the RailRoad problem described in the previous post (If you want to solve the problem on yourself, skip this and go to the next post directly).

import java.util.*;

public class RailRoads {
static int counter = 0;

public static void main(String[] args) {
RailRoads rr = new RailRoads();
int n = 11;
int[] a = new int[n];
List<Integer> track = new ArrayList<Integer>();

rr.begin(a, track);
System.out.println(“Total count:” + counter);
}

public void begin(int[] a, List<Integer> track) {
boolean inseq = false;
for (int i = a.length – 1; i >= 0; i–) {
if (a[i] == 0) {
inseq = true;
a[i] = 1;
intermediate(a, track);
} else if (inseq)
break;
}
}

public void intermediate(int[] a, List<Integer> track) {
boolean inseq = false;
//copy before to track correctly
List<Integer> track2 = new ArrayList<Integer>(track);
int[] a2 = new int[a.length];
copy(a, a2);

for (int i = 0; i < a.length; i++) {
if (a[i] == 1) {
a2[i] = 2;
track2.add(a.length – i);
finalstep(a2, track2);

}
else if(inseq)
break;
}
}

public void finalstep(int[] a, List<Integer> track) {
boolean found = true;
for (int i = 0; i < a.length; i++) {
if (a[i] != 2)
found = false;
}
if (found) {
System.out.print(“Train seq:”);
for (Integer i: track) {
System.out.print(i + ” “);
}
System.out.println();
counter++;
} else {
List<Integer> track2 = new ArrayList<Integer>(track);
int[] a2 = new int[a.length];
copy(a, a2);
begin(a2, track2);
}
}

public static void copy(int[] from, int[] to) {
for (int i = 0; i < from.length; i++) {
to[i] = from[i];
}
}
}

(Any suggestions over the implementation are welcome…)

The RailRoads problem

Here is another interesting problem that I am trying to solve currently:

There are three railroad tracks: INPUT, OUTPUT, and INTERMEDIATE. The INPUT railroad has N (1 <= N
<= 11) engines numbered 1 to N where the engine numbered 1 can move to INTERMEDIARY first
followed by engine numbered 2 and so on. The last engine that moved into INTERMEDIARY from INPUT
can move into OUTPUT, then the second last and so on. No engine from INPUT can move into OUTPUT
without going through INTERMEDIATE and no engine from OUTPUT can move elsewhere. Also, engines
from INTERMEDIATE can only be moved to OUTPUT. Write a program to generate all possible
sequences of the N engines in the OUTPUT railroad. The sequences should be in ascending order. (Use
of a series of nested for loops to generate permutations will be penalized).
For example:
Input:
4
Output:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
3 2 1 4
3 2 4 1
3 4 2 1
4 3 2 1

(Solution to follow in the next post….)

The Maximal Subsequence Sum Problem

In this post, I’ll touch upon three different algorithms that solve the Maximal Subsequence problem with different complexity levels. One of them doesn’t work if the sum is negative, but is efficient. This is one of the most interesting problems in the Computer Science domain. Here is the question:

Given a sequence of numbers, find the maximum sum of all possible sub-sequences

E.g.:  1. Input: 1, 2, 2, 1, -5, 3, 1  Output: 6 (1,2,2,1)

2. Input: 1, 2, -5, 4  Output: 4

3. Input: 1, 2, 3, 3, -6, 4 Output: 9

Algorithm 1:

Naive algorithm that solves the problem in O(n^2) time complexity. Straight forward logic.

/**
* The O(n*n) algorithm for the Maxumum sub sequence sum problem.
*
* @author Phanikumar Bhamidipati
*/
public class MaxSum3 {
public static void main(String args[]) {
MaxSum3 ms = new MaxSum3();
//int[] a = {1, 2, 3, 3, -6, 5};
//int[] a = {1, 3, 3, -10, 3, 1, 1, 1};
int[] a = {-5, -2, -2 };
int maxsum = ms.getMaxSum(a);
System.out.println(“Maximum Subsequence sum:” + maxsum);
}

public int getMaxSum(int a[]) {
int maxSum = Integer.MIN_VALUE;
for(int i=0;i<a.length;i++) {
int thisSum = a[i];
for(int j=i+1;j<a.length;j++) {
if(thisSum > maxSum) {
maxSum = thisSum;
}
thisSum += a[j];
}
}

return maxSum;
}

}

Algorithm 2:

If we are okay with returning zero if the sum is actually negative, we get an efficient, linear time algorithm. Logic simply ignores if the sum goes less than zero.

/**
* Code that finds Maximum Subsequence Sum of a given array
* in O(N) complexity.
* @author Phanikumar Bhamidipati
*/

public class MaxSum {
public static void main(String args[]) {
MaxSum ms = new MaxSum();
int[] a = {1, 2, 3, 3, -6, 5};
int maxsum = ms.getMaxSum(a);
System.out.println(“Maximum Subsequence sum:” + maxsum);
}

public int getMaxSum(int[] a)
{
int maxSum = 0;
int thisSum = 0;

for(int i=0; i<a.length;i++) {
thisSum += a[i];

if(thisSum < 0)
thisSum = 0;
else if(thisSum > maxSum)
maxSum = thisSum;
}

return maxSum;
}
}

Algorithm 3:

Little more complex, but solves all cases. Uses Divide & Conquer methodology. Solves the problem in O(N logN + N) time complexity. Works for negative subsequence sums also.

public class MaxSum2{
public static void main(String args[]) {
MaxSum2 ms = new MaxSum2();
int[] a = {-5, 1, -2, -2 };
int[] b = {1, 2, -5, 4};
int maxsum = ms.getMaxSum(0, a.length-1, a);
System.out.println(“Maximum Subsequence sum:” + maxsum);
}

public int getMaxSum(int i, int j, int[] a)
{
if(i==j)
{
return a[i];
}

int center = (i+j)/2;

int leftsum = getMaxSum(i, center, a);
int rightsum = getMaxSum(center+1, j, a);

int leftbordermaxsum = Integer.MIN_VALUE;
int rightbordermaxsum = Integer.MIN_VALUE;
if(center < a.length)
{
int leftbordersum = a[center];
leftbordermaxsum =a[center];
for(int p=center-1;p>=i;p–) {
leftbordersum += a[p];
if(leftbordersum > leftbordermaxsum)
leftbordermaxsum = leftbordersum;
}
}

if(center+1 < a.length)
{
int rightbordersum = a[center+1];
rightbordermaxsum = a[center+1];
for(int p=center+2;p<=j;p++) {
rightbordersum += a[p];
if(rightbordersum > rightbordermaxsum)
rightbordermaxsum = rightbordersum;
}
}

return Math.max(leftsum, Math.max(rightsum, leftbordermaxsum + rightbordermaxsum));
}
}

The interesting this is about the third problem, how the left and right subsequences are divided and how the ‘border sum’ is calculated. Note that the left border sum is calculated from center to left, and the right border sum is calculated from center to right. This algorithm works for negative sums also, with certain initializations to Integer’s smallest possible value etc.

Mediator design pattern

I am specially mentioning this pattern out of all the well known 23, because I kept encountering scenarios that benefit from this pattern. Let me describe a scenario in very simple terms.
Say there are 3 types of vehicles – Motorbike, Car, and a special type of car for the handicapped. 3 types of parking – one for each. Motorbikes and cars can only park in their designated parking, while the handicapped cars can park either in their own parking or the regular car parking. All vehicles must pay for the parking through a swiping machine if they are able to park their vehicles. Design an implementation for this.

Mediator pattern suits best for this type of design, in my opinion. Here is the sample code:

interface Vehicle
{
	public boolean park();
}

class Motorbike implements Vehicle
{
	ParkingMediator m;
	public boolean park() {
		return m.park(this);
	}

	public boolean parkMe(Parking p)
	{
		if(! p instanceof BikeParking)
			return false;
		//..proceed with parking...
	}
}
class Car implements Vehicle
{
	ParkingMediator m;
	public boolean park() {
		return m.park(this);
	}

	public boolean parkMe(Parking p)
	{
		if(! p instanceof CarParking)
			return false;
		//..proceed with parking...
	}
}
//special featured car
class AccessibleCar extends Car implements Vehicle
{
	ParkingMediator m;
	public boolean park() {
		return m.park(this);
	}

	public boolean parkMe(Parking p)
	{
		if(super.parkMe(p))
			return true;
		else {
			if(! p instanceof AccessibleCarParking)
				return false;
			//..proceed with parking...
		}
	}
}

interface Parking {}
class BikeParking implements Parking {}
class CarParking implements Parking {}
//Any accessible car is a car, but any accessible car parking is NOT
//a car parking because normal cars can't be parked in it...
class AccessibleCarParking implements Parking {}

class CardSwipeMachine {}

class ParkingMediator {
	Parking p;
	CardSwipeMachine csm;

	public boolean park(Motorbike m)
	{
		return m.parkMe(p)?csm.swipe(m):false;
	}
	public boolean park(Car c)
	{
		return c.parkMe(p)?csm.swipe(c):false;
	}
	public boolean park(AccessibleCar ac)
	{
		return ac.parkMe(p)?csm.swipe(ac):false;
	}
}

P.S.:  1. The problem mentioned is picked from another site.

2. Refer Wikipedia for another detailed example.

Generation of permutations

Here is a code that generates all possible permutations for a given character sequence:

public class Permutations {
	static int count = 0;
	public static void main(String args[]) {
		String a = "abcde";
		p(a.toCharArray());
	}
	public static void p(char[] a) {
		for(int i=0;i<a.length;i++) {
			char[] b = new char[a.length];
			b[0] = a[i];
			f(a, b, 0);
		}
		System.out.println("Total Permutations:" + count);
	}
	public static void f(char[] a, char[] b, int idx)
	{
		if(idx == a.length-1) {
			print(b);
			return;
		}
		for(int i=0;i<a.length;i++) {
			if(!exists(a[i], b, idx)) {
				char[] c = new char[b.length];
				copy(b, c);
				c[idx+1] = a[i];
				f(a, c, idx+1);
			}
		}
	}
	public static void copy(char[] from, char[] to)
	{
		for(int i=0;i<from.length;i++){
			to[i] = from[i];
		}
	}
	public static boolean exists(char c, char[] a, int idx) {
		for(int i=0;i<=idx;i++) {
			if(c == a[i])
				return true;
		}
		return false;
	}
	public static void print(char[] c) {
		count++;
		System.out.print("Perm:");
		for(int i=0;i<c.length;i++) {
			System.out.print(c[i]);
		}
		System.out.println();
	}
}

RESTClient & FireBug: Must add-ons for Web 2.0 Developers

Here I’d like to mention about the two FireFox add-ons that I found extremely useful:

1. RESTClient

This  is an awesome tool for RESTful services development! My testing time has gone down at least 5 times after moving to this. Earlier, I used to depend on a sloppy, IE specific Javascript to send XMLHttp requests. This tool exactly requires what you need to test – the URL, body and headers..

And ya, it does support cookies.. If an app depends on cookies to be sent along with REST requests for authentication/authorization, login to the app in one tab so that the cookies are established, and then open the add-on to send requests..

I really thank the creators for the add on!

2. FireBug

This is another awesome debugger tool for Javascript, without which JS programming would’ve been a nightmare. This is a well known add-on and an IE variant is also available. You can observe the HTML structure , put breakpoints, watch variables and many more!

The interesting feature I observed is logging in the FireBug console. Just say console.print(<whatever variable or values you need>), the output will be printed without altering the event sequence. An alert would mess up your event sequence and sometime you may not  be able to progress further. Being a pure server side programmer and getting used to “log file analysis”, this brings me a breeze of relief when I have to work on JS..

More details on FireBug here.

Two interesting problems

Following are the two interesting problem solving questions I stumbled upon recently:

1. Given a function say f() that returns a random integer between 1 and 5, find another function that returns a random integer between 1 and 7 using f().
2. Given two character arrays a[] and b[] containing [a-z|A-Z|0-9] write an algorithm that returns array with characters in both the arrays (intersection). Give a linear complex (O(n)) solution.

The solutions are simple but important to know.

Words for the day – 10

1. Annals – choronological record, reports of a work or a social body. E.g.: 50 years ago, a golden chapter was inscribed in the annals of history (A Govt of India ad on Panchayat Raj foundation celebrations)
2. Incisive – Sharp, having ability to distinguish fine distinctions, acute. E.g: Michell Johnson and Bret lee jolted England with their incisive bowling.
3. Rendition – A performance of a music or composition. E.g.: A traditional rendition as a tribute to Mahatma Gandhi.
4. Innate – Inborn, congenital, natural
5. Perilous – dangerous, precarious. E.g.: The company’s attempts seem to be perilous with potential anti trust law violations.
6. Bevy – Flock, gathering. E.g.: A bevy of young women surrounded him.
7. Fend off – Prevent the occurrence, avoid, obviate, ward off, avert
8. Ilk – like (Noun), kind of. E.g.: I can’t tolerate people of his ilk.
9. Conjecture – Surmise, A message/hypothesis formed by speculating.
10. Juggernaut – A massive inexorable force that seem to crush everything in its way, Jagannath (!)
11. Promulgate – formally announce, proclaim, publish. E.g.: Certain Englishmen wrongly promulgated that the Hindu devotees were lunatic fanatics to throw themselves under the wheels of chariot of Lord Krishna to attain salvation.  The term ‘juggernaut’ is coined from this notion.
12. Circa – approximately, around. E.g.: The church was built around 1840.
13. Wilderness – A state of disfavor, a bewildering profusion. E.g.: He led the party back from the wilderness. (OR) The duties of citizens are lost sight of in the wilderness of interests of individuals and groups.
14. Flummox – Puzzle, Be a mystery, bewilder, perplex, baffle
15. Embryonic – Of an organism prior to birth or hatching, an early stage of development. E.g.: In the embryonic stage of the egg.

Words for the day – 9

1. Admonish – warn, caution, counsel, take to task. E.g.: Ban Ki-moon admonished the UN countries about the adverse effects of global warming.
2. Brazen – unrestrained by convention or propriety, audacious, insolent. E.g.: Brazen arrogance of Jagan supporting MLAs.
3. Imminent – about to occur, close in time, impending
4. Devise – come up with, invent
5. Jostle – make your way by pushing, shove. E.g.: Polanski’s supporters are jostling for a place to support him.
6. Ludicrous – laughable, idiotic, ridiculous, absurd, preposterous. E.g.: Polanski’s supporters came up with a ludicrous term.
7. Pejorative – expressing disapproval, dyslogistic. E.g.: We might need to devise a less pejorative term for such an action.
8. Infraction – a crime lesser than a felony (like murder or arson). E.g.: Was he convicted of a minor infraction?
9. Jacuzzi – a large underwater bathtub with underwater jets that massage the body. E.g.: He got her into a jacuzzi and persuaded to take a sedative.
10. Sodomy – Intercourse through anus committed by a man (to a man or woman).
11. Extradition – Surrender of a convicted person by one state or country to another. E.g.: Even though he fled to France long time back, he is facing charges of extradition still now.
12. Revel – Unrestrained merrymaking, celebrate noisily, enjoy. E.g.: Jovetic revels Fiorentina by beating Liverpool.
13. Balk – Refuse to comply, pause or hold back due to uncertainty, hesitate
14. Gambit – ploy, opening remark intended to secure advantage for the speaker, a manoeuvre in a game or conversation. E.g.: Such actions by the developed countries will open up a gambit.
15. Sequestration – act of sequestering, isolation, Seizing property that belongs to someone else, requisition. E.g.: Sequestration of the carbon is a must in all coal-fired plants.

Words for the day – 8

1. Vetted – inspected, examined carefully
2. Clunker (Amer) – An old, unusable car, someone who is unsuccessful. E.g.: Cash for clunkers scheme by Obama has seen good response.
3. testy – easily irritable, cranky, peevish, scratchy
4. couture – high fashion designing and dress making
5. creole – natural language, mother tongue
6. bickering – Argue over petty things, quarrel, fuss, quibble, squabble, tiff
7. flabbergast – amaze, boggle down. E.g.: The owner was flabbergasted on knowing about the meat eating, beer guzzling ram!
8. Critter – regional term for creature (domestic animals)
9. devour – eat greedily, destroy completely. E.g.: The fire devoured the house.
10. jitter – motion, small wave-like movements. E.g.: The critter is giving  jitters in the town.
11. Transgression – Act or wrong doing, violation of a law or principle, evildoing
12. Impulsive – out of natural instincts, without forethought, whimsical, capricious, impetuous
13. Aver – Allege, to declare or affirm that something is true, report, say, assert, avow, swan
14. Sophomore – a 2nd year undergraduate (N or Adj). E.g.: His sophomore year, The sophomore class.
15. Deluge – Flood, soak, overwhelming with number, inundate, swamp, torrent. E.g.: A deluge of flowers.