Data Structures in Java/C++

Reconstruct a binary tree given its Inorder and Preorder traversals in Java

2011-12-13T07:59:00.000-08:00

This is one of the interesting problems that I encountered recently. Given two sequences one being an in-order traversed sequence and other being a pre-ordered traversed sequence, a binary tree has to be reconstructed out of it.

This is theoretically possible. This problem can be cracked if we form a common pattern between these two traversed values. In a pre-order traversal, the root element will always be the first element. This element when searched in an in-order traversal will have all elements to the left on the left side of the array and all elements to the right on the right side of the array.

Applying this solution recursively will give the binary tree for us. I have included a Swing UI so as to visualize the output easily.

Example,
Pre Order Sequence = A B D E C F G H I
In Order Sequence = D B E A F C H G I

I tweaked a bit from this source for UI.

package dsa.btree;

import javax.swing.JFrame;

public class PreOrderInOrderReconstructor {
 public static void main(String[] args) {
  PreOrderInOrderReconstructor pir = new PreOrderInOrderReconstructor();
  String[] preOrderSequence = { "A", "B", "D", "E", "C", "F", "G", "H", "I" };
  String[] inOrderSequence = { "D", "B", "E", "A", "F", "C", "H", "G", "I" };
  Node root = pir.reConstruct(preOrderSequence, 0,
    preOrderSequence.length - 1, inOrderSequence, 0,
    inOrderSequence.length - 1);
  JFrame f = new JFrame("BinaryTree");
  f.getContentPane().add(new BinaryTreeView(root));
  f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  f.setBounds(50, 50, 400, 400);
  f.setVisible(true);
 }

 private Node reConstruct(String[] preOrderSequence, int pMin, int pMax,
   String[] inOrderSequence, int iMin, int iMax) {
  if ((pMax - pMin) < 0) {
   return null;
  }
  if ((pMax - pMin) == 0) {
   return new Node(preOrderSequence[pMin]);
  }
  Node n = new Node(preOrderSequence[pMin]);
  int inorderPos = findInOrderPos(inOrderSequence,
    preOrderSequence[pMin], iMin, iMax);
  int leftBias = inorderPos - iMin;
  n.addLeft(reConstruct(preOrderSequence, pMin + 1, pMin + leftBias,
    inOrderSequence, iMin, iMin + leftBias - 1));
  n.addRight(reConstruct(preOrderSequence, pMin + leftBias + 1, pMax,
    inOrderSequence, iMin + leftBias + 1, iMax));
  return n;
 }

 private int findInOrderPos(String[] inOrderSequence, String string,
   int minIndex, int maxIndex) {
  for (int i = minIndex; i < maxIndex; i++) {
   if (inOrderSequence[i].equals(string)) {
    return i;
   }
  }
  return -1;
 }
}

The Node structure

package dsa.btree;

/**
 * A class representing one node of the tree.
 */
public class Node {
 private String content = null;
 private Node left = null;
 private Node right = null;
 
 public Node(String c) {
  this.content = c;
 }
 
 public String getContent() { return content; }
 
 public Node getLeft() { return left; }
 
 public Node setLeft(String content) {
  left = new Node(content);
  return left;
 }
 
 public Node getRight() { return right; }
 
 public void addRight(Node reConstruct) {
  this.right = reConstruct;
 }

 public void addLeft(Node reConstruct) {
  this.left = reConstruct;
 }
}

The code for UI

package dsa.btree;

import java.awt.Dimension;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.util.HashMap;
import javax.swing.JPanel;

public class BinaryTreeView extends JPanel {
 
 private static final long serialVersionUID = 1L;
 private Node root = null;
 private HashMap<Node, Rectangle> nodeLocations = null;
 private HashMap<Node, Dimension> subtreeSizes = null;
 private boolean dirty = true;
 private int parent2child = 20, child2child = 30;
 
 private Dimension empty = new Dimension(0, 0);
 private FontMetrics fm = null;
 
 public BinaryTreeView(Node root) {
  this.root = root;
  nodeLocations = new HashMap<Node, Rectangle>();
  subtreeSizes = new HashMap<Node, Dimension>();
 }
 
 private void calculateLocations() {
  nodeLocations.clear();
  subtreeSizes.clear();
  if (root != null) {
   calculateSubtreeSize(root);
   calculateLocation(root, Integer.MAX_VALUE, Integer.MAX_VALUE, 0);
  }
 }
 
 private Dimension calculateSubtreeSize(Node n) {
  if (n == null) return new Dimension(0, 0);
  Dimension ld = calculateSubtreeSize(n.getLeft());
  Dimension rd = calculateSubtreeSize(n.getRight());
  int h = fm.getHeight() + parent2child + Math.max(ld.height, rd.height);
  int w = ld.width + child2child + rd.width;
  Dimension d = new Dimension(w, h);
  subtreeSizes.put(n, d);
  return d;
 }
 
 private void calculateLocation(Node n, int left, int right, int top) {
  if (n == null) return;
  Dimension ld = (Dimension) subtreeSizes.get(n.getLeft());
  if (ld == null) ld = empty;
  Dimension rd = (Dimension) subtreeSizes.get(n.getRight());
  if (rd == null) rd = empty;
  int center = 0;
  if (right != Integer.MAX_VALUE)
   center = right - rd.width - child2child/2;
  else if (left != Integer.MAX_VALUE)
   center = left + ld.width + child2child/2;
  int width = fm.stringWidth(n.getContent().toString());
  Rectangle r = new Rectangle(center - width/2 - 3, top, width + 6, fm.getHeight());
  nodeLocations.put(n, r);
  calculateLocation(n.getLeft(), Integer.MAX_VALUE, center - child2child/2, top + fm.getHeight() + parent2child);
  calculateLocation(n.getRight(), center + child2child/2, Integer.MAX_VALUE, top + fm.getHeight() + parent2child);
 }
 
 private void drawTree(Graphics2D g, Node n, int px, int py, int yoffs) {
  if (n == null) return;
  Rectangle r = (Rectangle) nodeLocations.get(n);
  g.draw(r);
  g.drawString(n.getContent().toString(), r.x + 3, r.y + yoffs);
  if (px != Integer.MAX_VALUE)
   g.drawLine(px, py, r.x + r.width/2, r.y);
  drawTree(g, n.getLeft(), r.x + r.width/2, r.y + r.height, yoffs);
  drawTree(g, n.getRight(), r.x + r.width/2, r.y + r.height, yoffs);
 }
 
 public void paint(Graphics g) {
  super.paint(g);
  fm = g.getFontMetrics();
  if (dirty) {
   calculateLocations();
   dirty = false;
  }
  Graphics2D g2d = (Graphics2D) g;
  g2d.translate(getWidth() / 2, parent2child);
  drawTree(g2d, root, Integer.MAX_VALUE, Integer.MAX_VALUE, fm.getLeading() + fm.getAscent());
  fm = null;
 }
 
}

Hope you learnt something today along with me.

Cheers!
Braga

Given a sorted array, find k in least possible time in Java

2011-11-27T04:36:00.000-08:00

Given a sorted array and a value k, write a program to find whether that number is present in that array or not.

The first solution that comes to the mind for this problem is to traverse through the entire array and find whether it is having the value k and return true or false. This takes O(n) running time. But then, we are presented with a hint that the input array is sorted (lets assume in ascending order). This problem can be attacked by doing a divide and rule analysis.

This can be done recursively. See whether k is inbetween the last and first element in the array. If it is, then divide the array into two and repeat the same. If its not, simply return false. Yes, its as simple as that. Following is the java code for the same.

package dsa.arrays;

public class SortedFindK {
 
 public static void main(String[] args) {
  SortedFindK ssfm = new SortedFindK();
  ssfm.findKOfArray(null, 7);
  ssfm.findKOfArray(new int[]{1,4,6,7,45,78,88}, 45);
  ssfm.findKOfArray(new int[]{1,2,3,4,5,6,8,9,14}, 99);
  ssfm.findKOfArray(new int[]{-1,0,1,2,3,4,5}, 2);
  ssfm.findKOfArray(new int[]{1,2,3,4,5}, 5);
  ssfm.findKOfArray(new int[]{}, 3);
  ssfm.findKOfArray(new int[]{1}, 9);
 }
  
 public void findKOfArray(int[] csArray, int k){
  if(csArray == null || csArray.length == 0) { 
   System.out.print("\nHave some dignity. Send a valid array with at least 1 element");
   return;
  }
  int length = csArray.length;
  System.out.print("\n"+findKRecursively(csArray, 0 , length-1, k));
 }
 
 public boolean findKRecursively (int[] arr, int start, int end, int k){
  if(arr[start]==k || arr[end]==k){
   return true;
  }
  if(k > arr[start] && k < arr[end]){
   if(k <= arr[end/2]){
    return findKRecursively(arr, start, end/2, k);
   }else{
    return findKRecursively(arr, end/2 + 1, end, k);
   }
  }else{
   return false;
  }
 }
 
}
/*
Have some dignity. Send a valid array with at least 1 element
true
false
true
true
Have some dignity. Send a valid array with at least 1 element
false
*/

Leave some comments if you have anything to say.

Cheers!
Braga

Find middle element in a circularly sorted array

2011-11-26T04:51:00.000-08:00

Given a circularly sorted array, find its middle element in best possible time.

A circularly sorted array is an array that is obtained by shifting an array k times. For example, the following is a circularly sorted array,

[5, 6, 7, 8, 9, 1, 2, 3, 4]

If you sort this array and find the middle element it will be 5. But then, sorting is a painful operation which will take O(nlogn) timing. So it is out of the equation right away. If you closely observe this problem, it is enough to find the shifting index, the place where the sorting varies. For example, the shifting index in the above example is 5. Once that is found, then it is a matter of applying the bias over the length.

This program can be attacked in a recursive manner. Take the first and last elements in the array and compare them. If they are sorted, then the last element is greater than the first element. If this condition is not met, we will have to divide this array into two halves and try applying the same logic. If you do this, at some point you will arrive at a situation where you are left with only two elements or lesser. The end value is the shift index. Once the shift index is found, it is easy to find the middle element(s) for odd and even cases. Java code is below.

package dsa.arrays;

public class ShiftedSortedFindMiddle {
 
 public static void main(String[] args) {
  ShiftedSortedFindMiddle ssfm = new ShiftedSortedFindMiddle();
  ssfm.findMiddleOfArray(null);
  ssfm.findMiddleOfArray(new int[]{15,16,1,3,6,7});
  ssfm.findMiddleOfArray(new int[]{2,3,1});
  ssfm.findMiddleOfArray(new int[]{6,7,8,1,2,3,4,5});
  ssfm.findMiddleOfArray(new int[]{1,2,3,4,5});
  ssfm.findMiddleOfArray(new int[]{});
  ssfm.findMiddleOfArray(new int[]{1});
 }
  
 public void findMiddleOfArray(int[] csArray){
  if(csArray == null || csArray.length == 0) { 
   System.out.print("\nAre you Nuts? Send a valid array with at least one element you moron");
   return;
  }
  int length = csArray.length;
  int switchIndex = recursiveFind(csArray, 0 , length-1);
  System.out.print("\nMiddle Element(s) : " + csArray[(length/2 + switchIndex)%length]);
  if (length%2 == 0){
   System.out.print(" and " + csArray[(-1 + (length/2) + switchIndex)%length]);
  }
 }
 
 public int recursiveFind (int[] arr, int start, int end){
  if(end-start == 1){
   return end;
  }
  if(arr[start] > arr[end]){
   if(arr[start] > arr[end/2]){
    return recursiveFind(arr, start, end/2);
   }else if(arr[start/2] > arr[end]){
    return recursiveFind(arr, end/2 + 1, end);
   }else{
    return end;
   }
  }
  return start;
 }
 
}
/*
Are you Nuts? Send a valid array with at least one element you moron
Middle Element(s) : 7 and 6
Middle Element(s) : 2
Middle Element(s) : 5 and 4
Are you Nuts? Send a valid array with at least one element you moron
Middle Element(s) : 1
*/

Leave comments if something is unclear.

Cheers!
Braga

Queue using Stack in Java

2011-11-24T08:52:00.000-08:00

A Queue can constructed with its underlying data structure being a stack. Typically, we will need two Stacks one for enqueue and the other for dequeue.

During every enqueue() operation over a queue, we will keep pushing value to a first stack, lets say stack1.

During every dequeue() operation, we will have to simply pop an element from stack2 if stack2 is not empty. If stack2 is empty, we will need to pop all elements from stack1 one by one and push it to stack2. And then pop an element from stack2.

Take for example, I am inserting elements from 1 to 6 to a queue. This is how the following queue and the corresponding stack will look like,

Then trying a dequeue() operation will try to immediately pop values from stack 2.

So, it will pop all values from stack1 and push them to stack2 as follows,

Now the dequeue() operation shall be performed with ease since stack2 is not empty.

Finally, more enqueue will add or keep pushing values to the stack.

Following is the Java code. Note, I have not comprehensively covered the entire methods in a Queue, but this should be well more than enough.

package dsa.stack;

import java.util.Stack;

/**
 * An implementation of Queue using two Stacks
 * @author Braga
 */

public class QueueStack<T>{
 private Stack<T> firstStack;
 private Stack<T> secondStack;
 
 public QueueStack(){
  firstStack = new Stack<T>();
  secondStack = new Stack<T>();
 }

 public QueueStack<T> enQueue(T item) {
  firstStack.push(item);
  return this;
 }

 public T deQueue() {
  if(!secondStack.isEmpty()){
   return secondStack.pop();
  }else if(!firstStack.isEmpty()){
   while(!firstStack.isEmpty()){
    secondStack.push(firstStack.pop());
   }
   return secondStack.pop();
  }
  return null;
 }

 public int size() {
  return firstStack.size() + secondStack.size();
 }
 
 public boolean isEmpty(){
  if (size() == 0) {
   return true;
  }
  return false;
 }

}

And a test class for this with output

package dsa.stack;

public class TestQueue {
 public static void main(String[] args) {
  QueueStack<Integer> queueUsingStack = new QueueStack<Integer>();
  queueUsingStack.enQueue(1).enQueue(2).enQueue(3).enQueue(4).enQueue(5).enQueue(6);
  System.out.println("Queue current size is : "+queueUsingStack.size());
  System.out.println(queueUsingStack.deQueue());
  System.out.println(queueUsingStack.deQueue());
  System.out.println(queueUsingStack.deQueue());
  System.out.println(queueUsingStack.deQueue());
  queueUsingStack.enQueue(10).enQueue(11).enQueue(12);
  System.out.println(queueUsingStack.deQueue());
  System.out.println(queueUsingStack.deQueue());
  System.out.println(queueUsingStack.deQueue());
  System.out.println(queueUsingStack.deQueue());
 }
}
/*
Queue current size is : 6
1
2
3
4
5
6
10
11
*/

Cheers!
Braga

Program to check whether a tree is a BST

2011-11-18T03:28:00.000-08:00

Write a program to check whether a given tree is a binary search tree.

We all know that a binary search tree follows the rule : for any given node with value N, all the values in the left of that node is lesser than N and all the values in the right of that node will be greater than or equal to N. For example,

This is a tricky question. We may try to immediately run through all the nodes checking only the immediate left and right nodes and coming to a conclusion that it is a binary search tree. But this program may not work for this scenario.

The simplest solution to this problem is to do an inorder traversal through the entire tree and find whether it is sorted or not. Typically we can do that by pushing into any array. Even better is to calculate the minimum value at each step. Program is as follows. Please leave some comments if something is confusing. I will get back immediately.

package dsa.tree;

public class Tree {
 Node root;

 public static void main(String args[]) {
  Tree anyTree = new Tree();
  anyTree.root = new Node(3);
  anyTree.root.left = new Node(2);
  anyTree.root.right = new Node(5);
  anyTree.root.left.left = new Node(1);
  anyTree.root.left.right = new Node(4);
  
  
  if(anyTree.isBst(anyTree.root)){
   System.out.println("Is BST");
  }else{
   System.out.println("Is Not bst");
  }
 }

 private int MINVALUE = -1;
 
 public boolean isBst(Node node) {
  if(node.left!=null){
   if(!isBst(node.left)) return false;
  }
  if(node.data > MINVALUE){
   MINVALUE = node.data;
  }else{
   return false;
  }
  if(node.right!=null){
   if(!isBst(node.right)) return false;
  }
  return true;
 }
 
}

Cheers!
Braga

Windows, Linux and OSX

2011-08-31T12:08:00.000-07:00

Windows is the most used Operating System from an end user point of view. Next is Mac and the last ofcourse is linux. But this is not the case for a developer. Most of the development forums I've found online for the past so many years have given me results that has dealt fairly equal with these three major operating systems.

So, I would suggest to get your hands dirty with all these, if you have not already. If you have a Windows machine at work, buy a Macbook at home, install Linux (best is Ubuntu) on your desktop. Yes, this involves some cost, but trust me, its definitely worth it and you can see yourself well ahead of the curve as a developer.

For me, I use Linux at work and Mac at home. I hardly use windows these days but I have used it for a good 10+ years!!

Cheers,
Braga

Blocks in Ruby

2011-08-14T14:15:00.000-07:00

Blocks are one of the coolest things to have when you are coming from a language like C++ or Java. Say you are writing a function and you want to have some functionality within it which should be handled totally by the caller. Well, blocks come for the rescue.

Say I have a method like this.

def test_method

  #Something you do at the start

  #I want to do something that the caller intends to do

  #Something you do at the end

end

There is a sweet keyword in Ruby to replace the second line of the test_method called yield.

def test_method

  puts "start"

  yield

  puts "end"

end

And you can now make a call like,

test_method {puts "From block"}

Would output,
start
From block
end

Nothing great if you already are a ruby nerd. But for Java blokes, blocks are something to think for.

Cheers!
Braga

Conway's Game of Life in Java!!

2011-08-09T14:25:00.000-07:00

I recently met with Conway's Game of Life problem given as a programming assignment by one of the famous MNCs to clear level 1 in interview process. It was so mouth watering that I want to develop an UI for it and publish it in my blog. Spent 3 hours and came up with this.

Quick gist about the game from wikipedia

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

Any live cell with fewer than two live neighbours dies, as if caused by under-population.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overcrowding.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

Following is the screenshot and an applet for the same. The Code is free to share and distribute. Visit my github link for this game for the bleeding edge copy.

Cheers!!
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 7

2011-07-03T08:53:00.000-07:00

«Previous
1
2
3
4
5
6
7
Next »

The first posting's output and this may vary since that was developed with XCode 3 and this one with XCode 4. There are slight differences between both of them, but that we don't want to know. You can download XCode 4 for $5 from Apple's website.

I wanted to keep this final section very light. Hence going to show only the output here. :)

Click here to download the entire source code for this project. It is free to develop and distribute. Hope you guys learnt something.

Cheers!!
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 6

2011-07-03T08:42:00.000-07:00

This is our last part of the tutorial. We have done whatever that needs to be done with respect to the UI. All that is left is the coding part. In the last post, you would have seen that we had a couple of methods defined called as updateResult() and range(). These are supposed to be private methods. But then, I don't want to overload the readers with that concept yet, hence I have not set the access modifier for them. They will come in handy in our implementation part.

The implementation part involves responding to the actions that are sent from the UI. Lets take a look at the implementation of the height slider and go line by line.

- (IBAction)heightSlider:(id)sender {
    UISlider *hSlider = (UISlider*) sender;
 int hVal = (int)hSlider.value;
 NSString *hLabel = [[NSString alloc]initWithFormat:@"%i", hVal];
 height.text = hLabel;
 [self updateResults];
 [hLabel release];
}

The first line is nothing but a copy of the method declaration. The return type of the this method is an IBAction. The argument that it takes is the sender's object. If you had known Java, 'id' is a data type similar to Object. It is the sender's object. Since we have attached this method with the Slider, this would be the Slider itself.

On the fist line inside the method, we are typecasting the sender to the UISlider since we know for sure that the sender is an instance of UISlider. We then get its value, asssign it to a NSString variable followed by assigning it to the height text. Since we have allocated the NSString we should release it. You could notice there is a tiny little call to updateResults. It is nothing but updating the BMI and the Result at the bottom. Its implemenation is,

- (void)updateResults{
    float h = [height.text floatValue];
 float w = [weight.text floatValue];
 float bmiVal = w / ((h/100)*(h/100));
 NSString *bmiResult = [[NSString alloc]initWithFormat:@"%.1f", bmiVal];
 bmi.text = bmiResult;
 result.text = [self range:bmiVal];
 [bmiResult release];
}

- (NSString *) range:(float)bmiVal{
    NSString *theRange;
 
 if(bmiVal < 16.5){
  theRange = @"Severly Underweight";
 }else if (bmiVal<18.5) {
  theRange = @"Underweight";
 }else if (bmiVal<25) {
  theRange = @"Normal";
 }else if (bmiVal<30) {
  theRange = @"Overweight";
 }else if (bmiVal<35) {
  theRange = @"Obese";
 }else {
  theRange = @"Severly Obese";
 }
 return theRange;
}

The above code is self explanatory and straightforward to read. We also need to add a similar slider method for weight as we did for height.

- (IBAction)weightSlider:(id)sender {
    UISlider *wSlider = (UISlider*) sender;
 int wVal = (int)wSlider.value;
 NSString *wLabel = [[NSString alloc]initWithFormat:@"%i", wVal];
 weight.text = wLabel;
 [self updateResults];
 [wLabel release];
}

Whoof thats a lotta coding. Lets see the final output in the final part of this tutorial!

Cheers!
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 5

2011-07-03T08:29:00.000-07:00

In the past section we saw how to design the view and set the basic things up. Now, its time to do some coding. Before that, to check whether everything are Ok, press the ⌘ + B button to build your project. It may prompt you to save the project. If it does, click the Save button. The build should succeed at this point. If it fails, then go and check the logs or tell me the error in the comments section, I would surely help you out!

Now, back to business. We need to dynamically update the values in the UI. To attach this with the code, we have a binding object defined called as IBOutlet. Using this object, we would be able to set stuff in the code and see it change in the UI. Looks magic. To start binding the UI components and the code. Click on the Editor icon the right top side to see both the Interface Builder and the Interface file side by side.

Select your component on the UI - the height label. Hold down the control key and draw a line from the component to the Interface definition, you should be seeing a line coming up automatically for it to be inserted as shown below.

Lets name that IBOutlet variable to be height. Do the same for weight, bmi and the result labels. So, we are done with defining our binding variables namely the IBOutlet. Now whatever change you do for these outlets will now be reflected in the UI. We have one more thing left from the hooking up perspective - the Sliders. We need to assign an action when we slide the height and weight sliders. It is pretty simple. Select the height slider, choose the properties from the side and click on the Value changed option and drag it to the interface code. All you should be naming here is the method name which would be height slider. Note, you do not need to press Control key as we did for the Outlets.

You would need to add a couple of more methods in your interface file. The final code would look something like the following

#import <UIKit/UIKit.h>

@interface helloXcodeViewController : UIViewController {
    
    IBOutlet UILabel *height;
    IBOutlet UILabel *weight;
    IBOutlet UILabel *bmi;
    IBOutlet UILabel *result;
}
- (IBAction)heightSlider:(id)sender;
- (IBAction)weightSlider:(id)sender;
- (void)updateResults;
- (NSString *) range:(float)bmiVal;
@end

Cheers!
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 4

2011-07-03T07:55:00.000-07:00

Welcome to the part4 of the BMI Calculator iPhone application tutorial. We saw in the last section on how to set components on the UI. I had said that there was a small thing mentioned about the slider.

Before I tell more about it. Lets strategize how our application should behave. You slide two things in your application namely the heights and weights, the user will be seeing his body mass index calculated and will be given the result on whether he is normal or underweight or obese etc. We will be needing to determine the upper and lower bounds of the heights and weights. I have taken the height range as 120-210 cm and the weight range as 30-130 kg.

Whenever you click on any component, it corresponding property should be appearing at the right hand panel. Go ahead and click on the height slider. Set the minimum and maximum values of the slider as we discussed before.

You would also need to set the initial value. Since it needs to be in the center, set the height as 165 (average of 120 and 210). Same you would need to do by selecting the weight slider. 30-130 as lower upper bounds with 80 as the current value.

Thats it we are done designing our wonderful UI for the iPhone Application. We have some UI-Code hookup and some coding left before we declare our application is complete which we will be doing in the coming posts.

Cheers!
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 3

2011-07-03T07:44:00.000-07:00

Fellas,

Welcome to the part 3 of the tutorial. You could be thinking, "what the hell did I learn in Part 2?" Well. Lets take one baby step at a time. The second part of the tutorial's project name read "Body Mass Index Calculator". But then I had to change it to helloworldXcode, the name would not mind much, but whatever you choose, choose it wiser.

On the left hand top side of the you should be able to see your project. Expand it and you should be seeing your interface file (.h), Implementation file (.m) and the UI file (.xib). Clicking on any of these will bring up the corresponding code or UI on the main panel.

Go ahead and select the .xib ViewController file. You should now see an empty Canvas appearing on the center of the editor where you can drag and drop stuff. For our body mass index we need few UILabels that are going to be static and few UILabels that are going to change dynamically on the user action.
For dragging and dropping components on to the View you should select the Object from the drop down on the right hand side bottom corner as shown below.

We also will need a couple of slider for selecting the height and weight. Already sounds cool eh? Here is a screenshot on what stuff you should be dragging and dropping on the center of the editor.

After dropping the elements which includes totally 9 labels and two sliders you should be aligning them like shown in the following screenshot. The placement of the labels depends totally on your imagination and creativity, but lets make it professional looking so that our application should sell at least a million times in the App store. That was a joke :)

You could notice that changing the names of the labels are very simple. Just double click on it and start typing as shown in the above screenshot. With this your basic set up of the view is complete, we just have a few more things left regarding the slider functionality, but we will cover it in the next section.

Cheers,
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 2

2011-07-03T07:30:00.000-07:00

Welcome to the second part of the BMI Calculator Application for iPhone tutorial. I assume that you have XCode installed in your mac or Mac under VMWare. Launch XCode and select a new View based project.

Click on Next. Fill up the basic details and move on.

Once you have selected where to save your project, you should see something like this. Note: We are using Xcode 4 to develop this application, the view may vary from the previous version of Xcodes.

Thats it in this part of the tutorial. Lets start using the Interface builder and do some coding in the coming posts.

Cheers,
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 1

2011-07-02T12:49:00.000-07:00

«Previous
1
2
3
4
5
6
7
Next »

After an extensive learning on Objective C and covering the basics of iPhone development, I wanted to get my hands dirty with a working application. Following the concept of Minimal Marketable Subset, I thought I would develop a very primitive Body Mass Index calculator. Ok, into business

Our Final BMI Calculator Application is going to look like this.

Prerequisities

Since this is a very narrow development environment (yes you cannot develop this with windows), I would want to give a brief on what you will need, both hardware and software. First of all, you would need a Macbook or a Macbook Pro. A basic Macbook would do. Its based on how far you go. If you are very serious into iPhone development, then I would recommend you get a Macbook Pro. On the software side, you would need the XCode development suite. You can get it from Apple's website, it is free to download. It asks you to create an Apple Id. Go to youtube or google, you should find tons of resources there.

If you want to create clean iPhone Applications, you should have a very strong C Programming Background. And it would be nice if you are familiar with Object Oriented Concepts. You would need to learn Objective C basics and then the basics of iPhone development. Believe me, those links are simply too good. You can learn them both in just a day if you are freak like me.

Armed up with these basics, we can dive into the tutorial right away from the next post.

Cheers,
Braga

Minimal Markatable Subset

2011-07-02T12:19:00.000-07:00

It has been a long time since my last technical post. Yes, 6 months!! I wanted to write something on iPhone Application development. But before doing that, I want to tell you guys on something that I learnt during my two day training on clearing the Certified Scrum Master.
During this training, I heard this term called "Minimal Marketable Subset". After hearing to what it meant, my view as a developer changed drastically. Basically, I want my code to be perfect. Whenever I develop something, I want it to be highly user interactive, highly easier and the highly optimized. But know what, that is one of the huge mistakes I have done so far. Because of this attitude, I can never be satisfied and declare my product/project as completed. I felt that was the right way to think till I heard of "Minimal Marketable Subset". It is the minimum thing that is needed to get something up and running. You can develop in increments as the application develops. That is the basis of any Agile practice and I have started to adopt it to my programming practice.
To put in simple terms, "do what you can with what you have and do it quick"

15 game in Flash Actionscript3

2010-12-21T01:08:00.000-08:00

Having implemented the 15-game in Java, I thought I would attempt the same with Flash + AS3. And the same was done swiftly and I have presented the output and the code here. This is the same as the applet version, you will have to use your arrow keys to play.

package{
 //----
 //IMPORT
 //
 import flash.display.*;
 import flash.events.*;
 import flash.text.*;
 import flash.ui.Keyboard;
 import flash.media.Sound;
 import flash.system.System;

 //Class creation
 public class Main extends MovieClip {
  
  private var SIZE:int;
  private var panelSize:int = 400;
  private var panelArray:Array = new Array(SIZE, SIZE);
  
  private var parentStage:Stage;
  private var baseClip:MovieClip;
  
  private var music:Sound = new BubbleSound();
  
  public function Main(stage, bClip, difficulty):void {
   SIZE = difficulty;
   parentStage = stage;
   baseClip = bClip;
   stage.addEventListener(KeyboardEvent.KEY_DOWN, keyPressed);
   layout_in_grid();
   
   for(var i:int=0;i<SIZE*100;i++){//RANDOMIZE MOVES
    handleKeyPress(Math.floor(Math.random()*4) + 37);
   }
  }
  
  private function layout_in_grid():void{
   addChild(getGamePanel(SIZE));
  }
  
  private function keyPressed(e:KeyboardEvent):void{
   handleKeyPress(e.keyCode);
   music.play();
   if(areThingsInPlace()){
    baseClip.gotoAndStop(3,"Scene 1");
    stage.removeEventListener(KeyboardEvent.KEY_DOWN, keyPressed);
    this.parent.removeChild(this);
    var victory:Sound = new VictorySound();
    victory.play();
    return;
   }
  }
  
  private function handleKeyPress(keyCode:int):void{
   var emptyIndex:int = findEmptyIndex();
   var x:int = emptyIndex/SIZE;
   var y:int = emptyIndex%SIZE;
    
   switch (keyCode) {
    case Keyboard.LEFT://LEFT KEY
     if(y==SIZE-1) return;
     doSwap(x,y,x,y+1);
     break;
    case Keyboard.UP://UP KEY
     if(x==SIZE-1) return;
     doSwap(x,y,x+1,y);
     break;
    case Keyboard.RIGHT://RIGHT KEY
     if(y==0) return;
     doSwap(x,y,x,y-1);
     break;
    case Keyboard.DOWN://DOWN KEY
     if(x==0) return;
     doSwap(x,y,x-1,y);
     break;
   }
  }
  
  private function findEmptyIndex():int {
   for(var i:int=0;i<SIZE;i++){
    for (var j:int=0;j<SIZE;j++){
     if(panelArray[i][j].num_txt.text == '0'){
      return i*SIZE + j;
     }
    }
   }
   return 0;
  }
  
  private function doSwap(x:int, y:int, x1:int, y1:int):void{
   var temp:int;
   temp = panelArray[x][y].num_txt;
   panelArray[x][y].num_txt.text = panelArray[x1][y1].num_txt.text;
   panelArray[x1][y1].num_txt.text = temp;
   
   if(panelArray[x][y].num_txt.text == '0'){
    panelArray[x][y].alpha = 0;
    panelArray[x1][y1].alpha = 1;
   }else{
    panelArray[x][y].alpha = 1;
    panelArray[x1][y1].alpha = 0;
   }
    
  }
  
  private function getGamePanel(difficulty:int):MovieClip {
   var gridLayout:GridLayout = new GridLayout(SIZE, panelSize);
    
   var componentsList:Array = getRandomizedList(difficulty);
   var index:int = 0;
   for(var i:int=0;i<difficulty;i++){
    panelArray[i] = new Array(difficulty);
    for(var j:int=0;j<difficulty;j++){
     panelArray[i][j] = componentsList[index++];
     gridLayout.add(panelArray[i][j]);
    }
   }
   gridLayout.x = (parentStage.stageWidth / 2) - (gridLayout.width / 2);
     gridLayout.y = (parentStage.stageHeight / 2) - (gridLayout.height / 2);

   return gridLayout;
  }
  
  private function areThingsInPlace():Boolean{
   for(var i:int=0;i<SIZE*SIZE-1;i++){
    if(Number(panelArray[Math.floor(i/SIZE)][i%SIZE].num_txt.text) != (i+1)){
     return false;
    }
   }
   return true;
  }
  
  private function getRandomizedList(difficulty:int):Array  {
   var componentSet:Array = new Array(SIZE*SIZE);
   for(var i:int=0;i<difficulty*difficulty-1;i++){
    var square:SquareClip = new SquareClip();
    square.num_txt.text = (i+1).toString(10);
    componentSet[i] = square;
   }
   var emptyClip:SquareClip = new SquareClip();
   emptyClip.num_txt.text = (0).toString(10);
   componentSet[i] = emptyClip;
   return componentSet;
  }
 }
}

The Layout grid file which I wrote on my own to simulate an exact Grid Layout similar to the one in Java.

package{
 //----
 //IMPORT
 //
 import flash.display.*;
 import flash.events.*;
 import flash.text.*;
 
 //Class creation
 public class GridLayout extends MovieClip{
  
  private var _size:int;
  private var _size_of_grid:int;
  private var _gap:int;
  private var _itemCount:int;
  private var _totalFilled:int;
  
  public function GridLayout(size, size_of_grid):void {
   _size = size;
   _size_of_grid = size_of_grid;
   _totalFilled = 0;
  }
  
  public function add(object):int{
   if(_totalFilled == (_size*_size )){
       trace("GRID IS FULL");
     return 0;  
   }
   object.x = ( (_totalFilled % _size) ) * (_size_of_grid/_size)  ;
   object.y =  Math.floor(_totalFilled / _size) * (_size_of_grid/_size) ;
   _totalFilled++;
   addChild(object);
   return 1;
  }
  
 }
}

Cheers!!
Braga

Print % using printf in C

2010-12-20T15:56:00.000-08:00

Problem:

How can you print % using the printf function? (Remember % is used as a format specifier!!!)
Very Simple, following cases are examples

#include <stdio.h>

int main()
{
    printf("\%\n"); // warning: unknown conversion type character 0xa in format - but prints
    printf("%%\n"); // correct statement
    printf("%\n");  // warning: unknown conversion type character 0xa in format
}

Cheers!!
Jack

Find Output for this C Program

2010-12-20T15:49:00.000-08:00

Problem:

What would be the output of the following C program? (Is it a valid C program?)

#include <stdio.h>
int main()
{
    int i=43;
    printf("%d\n",printf("%d",printf("%d",i)));
    return 0;
}

Explanation:

This will produce output “4321”. The return type of printf is “int” which is the number of characters written to stdout.

printf("%d\n",printf("%d",printf("%d",i)));
printf("%d\n",printf("%d",printf("%d",43))); => 43
printf("%d\n",printf("%d",2)); => 2
printf("%d\n",1); => 1

Cheers!!
Jack

C - %n format specifier in printf

2010-12-20T15:44:00.000-08:00

Well, what does the format specifier %n of printf function do?

Explanation:
Print nothing, but write number of characters successfully written so far into an integer pointer parameter.

Example:

#include <stdio.h>

int main()
{
    int val;
    printf("print the number of characters so far %n doesnt matter what you write here\n", &val);
    printf("val = %d\n", val);
    return 0;
}

Output:
blah blah
val = 38

Cheers!
Jack

C program to determine endian'ess

2010-12-20T05:52:00.000-08:00

We shall see a small C program to determine whether a machine's type is little-endian or big-endian.

Definition:

BigEndian means that the higher order byte of the number is stored in memory at the lowest address, and the lower order byte at the highest address. The big end comes first.

eg: OAOBOCOD will be stored as OA(a) OB(a+1) OC(a+2) OD(a+3)

LittleEndian means that the lower order byte of the number is stored in memory at the lowest address, and the higher order byte is stored at the highest address i.e., the little
end comes first.

eg: OAOBOCOD will be stored as OD(a) OC(a+1) OB(a+2) OA(a+3)

Program:

#include <iostream>

using namespace std;

int main()
{
   int num = 1;
   if(*(char *)&num == 1)
      printf("Little-Endian\n");
   else // will be NULL
      printf("Big-Endian\n");

   return 0;
}

Cheers!!
Jack

Addition without using the + operator in C

2010-12-20T05:39:00.000-08:00

Write a C function which does the addition of two integers without using the '+' operator. You can use only the bitwise operators.(Remember the good old method of implementing the full-adder circuit using the OR and XOR gates....)

Now, for the code implemented in C.

#include<stdio.h>
int main()
{
    int a = 12, b = 25;
    while (b)
    {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    printf("%d\n",a);
}

Cheers!
Jack

CAT Brain Teaser

2010-12-20T05:32:00.000-08:00

Well, this can be considered off-topic. A brain teaser in CAT. Only 2% students were able to solve this in the CAT Exam. They should have been really sick :) Enough build up, lets see what the problem is.

Given,

5+3+2 = 151022
9+2+4 = 183652
8+6+3 = 482466
5+4+5 = 202541

Then, 7+2+5 = ???

Solution:

5+3+2 = (5*3)(5*2)(5*3 + 5*2 - 3)
9+2+4 = (9*2)(9*4)(9*2 + 9*4 - 2)
8+6+3 = (8*6)(8*3)(8*6 + 8*3 - 6)
5+4+5 = (5*4)(5*5)(5*4 + 5*5 - 4)

Hence,

7+2+5 = (7*2)(7*5)(7*2 + 7*5 - 2) = 143547

Cheers!!
Jack

"Offsetof" Macros in C : What it is and why it is

2010-12-16T18:49:00.000-08:00

Problem:

The following is the offset macros which is used many a times. Lets figure out what is it trying to do and what is the advantage of using it.

#define offsetof(a,b) ((int)(&(((a*)(0))->b)))

Explanation:

offsetof tells you where in the memory allocation of the structure you will find a particular member.

Consider the example,

/* offsetof example */
#include <stdio.h>
#include <stddef.h>

struct mystruct
{
    char singlechar;
    char arraymember[10];
    char anotherchar;
};

int main ()
{
    printf ("offsetof(mystruct,singlechar) is %d\n",offsetof(mystruct,singlechar));
    printf ("offsetof(mystruct,arraymember) is %d\n",offsetof(mystruct,arraymember));
    printf ("offsetof(mystruct,anotherchar) is %d\n",offsetof(mystruct,anotherchar));

    return 0;
}

The structure defined takes up 12 bytes:

* byte 0: singlechar
* byte 1: arraymember[0]
* byte 2: arraymember[1]
* byte 3: arraymember[2]
* ...
* byte 10: arraymember[9]
* byte 11: anotherchar

The output will be:

offsetof(mystruct,singlechar) is 0
offsetof(mystruct,arraymember) is 1
offsetof(mystruct,anotherchar) is 11

If you allocate an object of type, and get a byte* to the start of the structure, you can use offsetof to find out where each member is. If you use that pointer offset, and convert it back to the correct type, it will give you a pointer to the member.

int main()
{
    mystruct s;
    s.anotherchar = 5;
    char* pBeginningOfS = (char*)(void*)(&s);
    char* pAnotherChar = pBeginningOfS + offsetof(mystruct, anotherchar);
    *pAnotherChar = 17;
    printf("anotherchar is %d", s.anotherchar);
    return 0;
}

The output will be:

anotherchar is 17

The reason you can't assume that each member will be a specific offset from the beginning of the struct is complicated, and compiler dependent. If you must do something like this (which is really low-level stuff which you should avoid unless you have to), then use a macro like offsetof, rather than trying to manually specify the offset yourself.

Hope you learnt something.

Cheers!!
Jack

How to find angle between hour and minute hands in an analog clock?

2010-12-16T07:17:00.000-08:00

Given a simple clock, we have to find the angle between the hour and minute hands. Since this is a deliberate question, we should obviously be ignoring the thickness of the hands in the clock.

We need to understand the following things before we arrive at our solution.

The hour hand moves at the rate of 0.5 degrees per minute.
The minute hand moves at the rate of 6 degrees per minute.

The reason for the above statements are obvious if you think a layer deep. Now, for the code (works both for C++ and Java)

double angle(int h, int m)
{
     double hangle = 0.5D * (h*60 + m);
     double mangle = 6*m;
     angle = abs(hangle – mangle);
     angle = min(angle, 360-angle);
     return angle;
}

Cheers!!
Jack.

What is the difference between memcpy and memmove?

2010-12-16T07:09:00.000-08:00

Answer:

With memcpy, the destination cannot overlap the source at all. With memmove copying takes place as if an intermediate buffer was used, allowing the destination and source to overlap. This means that memmove might be very slightly slower than memcpy, as it cannot make the same assumptions.

void * memcpy  ( void * destination, const void * source, size_t num );
void * memmove ( void * destination, const void * source, size_t num );

Cheers!!
Jack

Linked List : Given a pointer to any node, delete the node pointed by the pointer

2010-12-16T06:45:00.000-08:00

Given a linked list like this,

Given a pointer to any node, delete the node pointed by the pointer. Note: no head pointer is given.

Solution:

Assume a pointer to p3, lets call it to 'p'. Since only pointer to current node is provided, there is no way to delete the current node from the list. But instead of deleting the current node, we can just move the next node data to current node and delete the next node. The algorithm can be explained simply as,

p->data = p->next->data;
t = p->next;
p->next = p->next->next;
delete t;

Cheers!!
Jack

C program to find fibonacci series using only one variable !!!

2010-12-15T15:14:00.000-08:00

Problem:
Generating Fibonacci series using only one variable.

There are many ways to achieve this. I have given three ways to do this in the following methods.

Method #1:
We can have a simple function to do this.

F(n) = [(x^n) – ((1 – x)^n)]/ sqrt(5);
Where x = (1 + sqrt(5))/2 = 1.6180339887

Method #2:
The following recursive function would do the job.

int fib(n)
{
     return (n>2) ? n : fib(n-1)+fib(n-2);
}

Method #3:
The following one works great as well!

#include <stdio.h>
#include <stdlib.h>

int main (void)
{
     unsigned long i = 1;
     printf ("0\n");
     while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) {
          printf ("%d\n", i & 0xffff);    
          i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff));
     }
     return 0;
}

Cheers!!
Jack

Interview Puzzle - Equal heads

2010-10-14T05:25:00.000-07:00

Puzzle:

There are 50 coins on the table out of which 43 are tail-face up and 7 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 50 coins in two sets (not necessarily equal) such that both have equal number of coins with heads face up.

Solution:

Divide the 50 coins into two sets - once set with 43 coins and the other set with 7 coins. Thus, the first set will contain 'x' heads and '43-x' tails and the second set will contain '7-x' heads and 'x' tails. The possibilities can be tabulated as shown in the left table.

Now, flip the coins in the second set, so that both will contain 'x' heads. The result after flipping can be seen on the right table. You can see that both sets have equal number of heads whatever be the distribution.

Cheers!!
Jack

Print a Matrix in diagonal zig zag order

2010-10-07T09:52:00.000-07:00

Problem:
Given a square matrix, write a program to print the items in zig zag diagonal order.

Following is an example,

So the output expected for the above example is,

1 -> 2 -> 6 -> 3 -> 7 -> 11 -> 4 -> 8 -> 12 -> 16 -> 5 -> 9 -> 13 -> 17 -> 21 -> 10 -> 14 -> 18 -> 22 -> 15 -> 19 -> 23 -> 20 -> 24 -> 25

Solution:

This program is a bit tricky and is very hard to solve immediately when asked in an interview. People who try to attack problems involving matrices always think they need at least two loops to arrive at the solution. But the surprise here is the problem can be solved in just a single loop with a very simple logic. I have provided the solution in C++ below, you may also try to solve the same in the language of your choice!!

#include <iostream>
using namespace std;

#define MAX 5

int main(){
    int a[MAX][MAX] = 
        {{ 1, 2, 3, 4, 5},
         { 6, 7, 8, 9,10},
         {11,12,13,14,15},
         {16,17,18,19,20},
         {21,22,23,24,25}};
    int i=0,j=0;
    while(i<MAX){
         cout << a[i][j] << " -> ";
         if(i==MAX-1){
             i = j+1; j = MAX-1;
         }
         else if(j==0){
             j = i+1; i = 0;
         }
         else{
             i++; j--;
         }
    }
    cout << endl;
     
    return 0;
}

Cheers!!
Jack

A Free game in Java

2010-09-25T10:41:00.000-07:00

I wanted to play this game so badly as I use to be very good at it. I was not knowing the proper keyword to find it online. So, what the heck, I went ahead and created one! The front end used was Swing.
The objective of this game is to arrange from numbers 1 through 24 (or depending on the size) in proper order and you have one square free. You can move to that empty sqaure by pressing either of the four arrow keys UP/DOWN/LEFT/RIGHT. All the puzzles formed will have a solution. You can use this code anywhere you want.

If you have Java installed in your browser, you should be able to see the Applet. Just click anywhere inside the applet and start playing using the arrow keys! Have fun!

Screenshot	Applet

package boxgame;

import java.awt.*;
import java.awt.event.KeyEvent;
import java.util.ArrayList;
import java.util.List;

import javax.swing.*;

public class BoxPuzzle extends JFrame{
    private static final long serialVersionUID = 1L;
    
    private static final int SIZE = 5;
    JPanel[][] panelArray = new JPanel[SIZE][SIZE];
    private boolean dialogShown = false;
    
    public BoxPuzzle(){
        this.setTitle(SIZE*SIZE-1+" square puzzle");
        this.add(getGamePanel(SIZE));
        this.setSize(SIZE*75, SIZE*75);
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        this.setLocationRelativeTo(null);
        for(int i=0;i<SIZE*100;i++)//RANDOMIZE MOVES
            handleKeyPress((int)(Math.random()*4) + 37);
        processKeys();
        this.setVisible(true);
    }
    
    private void processKeys(){
        KeyboardFocusManager.getCurrentKeyboardFocusManager().addKeyEventDispatcher( 
            new KeyEventDispatcher()  {  
                public boolean dispatchKeyEvent(KeyEvent e){
                    if(e.getID() == KeyEvent.KEY_PRESSED){
                        handleKeyPress(e.getKeyCode());
                        if(areThingsInPlace() && !dialogShown){
                            dialogShown = true;
                            JOptionPane.showMessageDialog(null,"Congratulations!!! YOU WIN!!");
                            System.exit(1);
                        }
                    }
                    return false;
                }  
        });
    }
    
    private void handleKeyPress(int keyCode) {
        int emptyIndex = findEmptyIndex();
        int x = emptyIndex/SIZE;
        int y = emptyIndex%SIZE;
        
        switch (keyCode) {
        case 37://LEFT KEY
            if(y==SIZE-1) return;
            doSwap(x,y,x,y+1);
            break;
        case 38://UP KEY
            if(x==SIZE-1) return;
            doSwap(x,y,x+1,y);
            break;
        case 39://RIGHT KEY
            if(y==0) return;
            doSwap(x,y,x,y-1);
            break;
        case 40://DOWN KEY
            if(x==0) return;
            doSwap(x,y,x-1,y);
            break;
        }
    }
    
    private void doSwap(int x,int y,int x1,int y1){
        Component temp1,temp2;
        temp1 = panelArray[x][y].getComponent(0);
        temp2 = panelArray[x1][y1].getComponent(0);
        panelArray[x][y].remove(0);
        panelArray[x1][y1].remove(0);
        panelArray[x1][y1].add(temp1);
        panelArray[x][y].add(temp2);
        temp2.requestFocus();
        this.repaint();
    }

    private int findEmptyIndex() {
        for(int i=0;i<SIZE;i++)
            for (int j=0;j<SIZE;j++)
                if(!(panelArray[i][j].getComponent(0) instanceof JButton))
                    return i*SIZE + j;
        return 0;
    }

    private boolean areThingsInPlace(){
        for(int i=0;i<SIZE*SIZE-1;i++){
            String name = (panelArray[i/SIZE][i%SIZE].getComponent(0)).getName();
            if(name!=null && !(name.equals(""+i)))
                return false;
        }
        return true;
    }
    
    public static void main(String args[]){
        new BoxPuzzle();
    }

    private JPanel getGamePanel(int difficulty) {
        JPanel pnlGame = new JPanel();
        GridLayout matrixLayout = new GridLayout(difficulty, difficulty);
        pnlGame.setLayout(matrixLayout);
        
        List<JComponent> componentsList = getRandomizedList(difficulty);
        int index = 0;
        for(int i=0;i<difficulty;i++){
            panelArray[i] = new JPanel[difficulty];
            for(int j=0;j<difficulty;j++){
                panelArray[i][j] = new JPanel();
                panelArray[i][j].setLayout(new GridLayout(1,1));
                panelArray[i][j].add(componentsList.get(index++));
                pnlGame.add(panelArray[i][j]);
            }
        }
        return pnlGame;
    }

    private List<JComponent> getRandomizedList(int difficulty) {
        List<JComponent> componentSet = new ArrayList<JComponent>();
        for(int i=0;i<difficulty*difficulty-1;i++){
            JButton button = new JButton(""+(i+1));
            button.setName(""+i);
            componentSet.add(button);
        }
        componentSet.add(new JPanel());
        return componentSet;
    }
}

Cheers,
Bragaadeesh.

Trie data structure - In C++

2010-09-10T16:03:00.000-07:00

«Previous
1
2
3
4
5
6
7
Next »

Having had a comprehensive coverage of the TRIE data structure in Java, me and my roommate thought it would achieve completion if we have the same implemented in C++. Don't get carried away by the length of the code. Its as simple and easy as the equivalent one in Java. You may go through the comprehensive tutorial here. Trust me, it takes only 10 minutes!!.

Please feel free to ask any questions if you face difficulties in understanding any part of the resource. I would respond to you immediately.

/*
    ASSUMPTIONS:
        All characters are case insensitive
    ENHANCEMENTS:
        Auto correction of word
        Display all words in postorder

    SAMPLE DATA: - ALGO, ALL, ALSO, ASSOC, TREE, TRIE

                                +--> [G] ---+--> [O]
                                |
                    +--> [L] ---+--> [L]
                    |           |
        +--> [A] ---+           +--> [S] ---+--> [O]
        |           |
        |           +--> [S] ---+--> [S] ---+--> [O] ---+--> [C]
[\0] ---+
        |                       +--> [E] ---+--> [E]
        |                       |
        +--> [T] ---+--> [R] ---+
                                |
                                +--> [I] ---+--> [E]

*/

#include <iostream>
#include <cctype>

using namespace std;

class trie
{
    private:
        struct node
        {
            char  character;       // character of the node
            bool  eow;             // indicates a complete word
            int   prefixes;        // indicates how many words have the prefix
            node* edge[26];        // references to all possible sons
        }*root;                        // trie root node

        void preorder_display(node *); // preorder display
        void truncate_node(node *);    // Deletes node and sub-nodes
        void delete_node(node *);      // Deletes node if prefixes is 1

    public:
        trie();                        // constructor
        ~trie();                       // destructor

        void insert_word(char *);      // to insert a word
        void delete_word(char *);      // to delete a word
        bool search_word(char *);      // to search a word

        void display();                // display complete trie
};

trie::trie()
{
    root = new node();
    root->character = '\0';
    root->prefixes = 0;
    root->eow = false;
    for(int i=0;i<26;i++)
    {
        root->edge[i] = NULL;
    }
}

trie::~trie()
{
    truncate_node(root);
}

void trie::truncate_node(node* n)
{
    for(int i=0;i<26;i++)
    {
        if(n->edge[i] != NULL)
        {
            truncate_node(n->edge[i]);
        }
    }
    delete n;
}

void trie::insert_word(char* s)
{
    node *t = root;
    while(*s != '\0')
    {
        int c = toupper(*s) - 'A';
        if(t->edge[c] == NULL)
        {
            node* n = new node();
            n->character = *s;
            n->eow = false;
            n->prefixes = 1;
            for(int i=0;i<26;i++)
            {
                n->edge[i] = NULL;
            }
            t->edge[c] = n;
            t = n;
        }
        else
        {
            t = t->edge[c];
            t->prefixes++;
        }
        *s++;
    }
    t->eow = true;
}

bool trie::search_word(char* s)
{
    node *t = root;
    while(*s != '\0')
    {
        int c = toupper(*s) - 'A';
        if(t->edge[c] == NULL)
        {
            return false;
        }
        else
        {
            t = t->edge[c];
        }
        *s++;
    }
    if(t->eow == true)
        return true;
    else
        return false;
}

void trie::delete_word(char* s)
{
    node* t = root;
    while(*s != '\0')
    {
        int c = toupper(*s) - 'A';
        if(t->edge[c] == NULL)
        {
            return;
        }
        else if(t->edge[c]->prefixes == 1)
        {
            truncate_node(t->edge[c]);
            t->edge[c] = NULL;
            return;
        }
        else
        {
            t = t->edge[c];
        }
        *s++;
    }
}

void trie::display()
{
    preorder_display(root);
}

void trie::preorder_display(node* t)
{
    if(t == NULL)
        return;

    cout << "iterating :: " << t->character << " :: " << t->eow << " :: " << t->prefixes << endl;

    for(int i=0;i<26;i++)
    {
        if(t->edge[i] != NULL)
            preorder_display(t->edge[i]);
    }
}

Demonstration of trie operations

int main()
{
    trie mytrie;
    char *s[] = {"tree","trie","algo","assoc","all","also","ass"};
    for(int i=0;i<sizeof(s)/sizeof(*s);i++)
    {
        mytrie.insert_word(s[i]);
    }

    mytrie.display();

    if(mytrie.search_word("all") == true) cout << "all exist" << endl;
    else cout << "all do not exist" << endl;

    mytrie.delete_word("all");

    if(mytrie.search_word("all") == true) cout << "all exist" << endl;
    else cout << "all do not exist" << endl;

    mytrie.display();
}

Cheers!!
Jack.

Efficient way to calculate prime numbers

2010-09-09T02:56:00.000-07:00

In several puzzles/coding competitions we may need to check for prime numbers and this is required to be done in considerable time to save precious run time. The traditional approach is,

bool is_prime(int x)
{
  if(x <= 1)
    return false;
  for(int i = 2; i < x; i++)
    if(x%i == 0)
      return false;
  return true;
}

This will however will loop through all elements below x to see if a factor exists. Example, for finding if 13 is prime, we check if its divisible by 2,3,4,....12. This can be optimized to loop through only half the elements since the highest factor is going to be num/2 as,

bool is_prime(int x)
{
  if(x <= 1)
    return false;
  for(int i = 2; i <= x/2; i++)
    if(x%i == 0)
      return false;
  return true;
}

But by analysis you can see that for a number say 100, the factors are (1*100),(2*50),(4*25),(5*20),(10*10),(20*5),(25*4),(50*2),(100*1). For finding out if 100 is prime or not we just need to check if 100 is divisible by any number not greater than 10 i.e., it is sufficient to check from 2 to 10. The reason being if its divisible by 4, its also divisible by 25.

Hence the best approach to check if a number is prime or not will be

bool is_prime(int x)
{
  if(x <= 1)
    return false;
  int s = (int) sqrt(x);
  for(int i = 2; i <= s; i++)
    if(x%i == 0)
      return false;
  return true;
}

Final prime number program in Ruby (bonus)

def is_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end

This approach will check for factors in very minimized number of loops.

Cheers!!
Bragaadeesh

Stack Implementation in C++ through an array

2010-09-08T12:14:00.000-07:00

Stack is one of the important data structures that every computer programmer should be aware of. It follows the simple LIFO (Last In First Out) principle. Implementation of stack can be done in many ways. One of the simplest way is using Arrays. Here an array is initialized to a maximum value first, lets call it capacity. As and when we push elements onto the array, its size will get increased. When the size reaches the capacity, we should ideally double the array size. But in the code given below I am not doing that.

#include <iostream>
        using namespace std;
        #define STACKSIZE 10
        class stack
        {
                private:
                        int arr[STACKSIZE+1];
                        int tos;
                public:
                        stack();
                        void push(int x);
                        int  pop();
                        bool is_empty();
                        bool is_full();
                        int  size();
                        void display();
        };

        stack::stack()
        {
                tos = 0;
        }

        void stack::push(int x)
        {
                if(!is_full())
                        arr[tos++] = x;
                else
                        cout << "Stack is full, Can not push " << x << endl;
        }

        int stack::pop()
        {
                if(!is_empty())
                        return arr[--tos];
                else
                        cout << "Stack is empty, cannot pop" << endl;
                return -1;
        }

        bool stack::is_empty()
        {
                if(tos == 0)
                        return true;
                else
                        return false;
        }

        bool stack::is_full()
        {
                if(tos == STACKSIZE)
                        return true;
                else
                        return false;
        }

        int stack::size()
        {
                return tos;
        }

        void stack::display()
        {
                if(tos == 0)
                {
                        cout << "No elements to display" << endl;
                        return;
                }
                for(int i=0;i
                        cout << arr[i] << " ";
                cout << endl;
        }

        int main()
        {
                stack mystack;
                cout << mystack.size() << endl;
                mystack.push(1);
                if(mystack.is_full())
                        cout << "stack is full" << endl;
                mystack.pop();
                if(mystack.is_empty())
                        cout << "stack is empty" << endl;
        }

Cheers!!
Bragaadeesh.

Motivation

2010-09-08T12:05:00.000-07:00

In his book, 7 Habits of Highly Effective People, Stephen Covey tells the story of a woodcutter who took a new job for a timber merchant. The woodcutter was determined to do his best, so when the employer presented him with an axe he went straight to work. The first day the woodcutter brought 18 trees to the boss. “Congratulations,” the boss said. “Keep it up!” With this motivational encouragement the cutter went out the next day with even more determination. However, at the end of the day he could only bring back 15 trees. The third day he worked harder still, yet try as he might only 10 trees could be felled. So it went; each succeeding day yielded fewer trees. “I must be losing my strength,” the woodcutter thought. He decided to approach his boss to apologize for his unexplained deteriorating output. “When was the last time you sharpened your axe?” the boss asked. The woodcutter stared dumbfounded. “Sharpen my axe! I had no time to sharpen my axe. I have been too busy trying to cut trees!”

It is possible to be too busy to maintain your effectiveness. Whatever your personal situation, this might be the right time to ask yourself if it is time to “sharpen your axe.”

Cheers!!
Bragaadeesh.

Project Euler : Considering natural numbers of the form, ab, finding the maximum digital sum.

2010-08-28T11:35:00.000-07:00

Problem 56

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?

Solution (in Ruby)

Nothing much to discuss about the solution, I've implemented it directly as given in the problem statement.

max = []
1.upto(99) { |x| 1.upto(99){|y| max << (x**y).to_s.split(//).inject(0){|b,i| b+=i.to_i}} }
puts "The maximum sum is #{max.max}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Evaluate the sum of all amicable pairs under 10000.

2010-08-27T12:19:00.000-07:00

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.

Solution (in Ruby)

For this problem, it is vital to write an efficient method to find the sum of divisors of a number. The divisor finding logic is same as the one stated in Problem 12. Rest is an as-is implementation of the problem statement.

def divisors_sum(n)
  return 1 if n==1
  sum = 0
  1.upto(Math.sqrt(n)) {|x| sum+= (x + n/x) if n%x == 0}
  sum-=Math.sqrt(n).to_i if (Math.sqrt(n) - Math.sqrt(n).to_i) == 0
  return sum-=n
end
sum = 0
1.upto(9999) do |n|
  b = divisors_sum(n)
  a = divisors_sum(b)
  sum+=n if(a!=b && a==n)
end
puts "The sum of all amicable pairs under 10000 is #{sum}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many letters would be needed to write all the numbers in words from 1 to 1000?

2010-08-27T05:55:00.000-07:00

Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Solution (in Ruby)

We will have to first try to come out with the unique words that are present in the numbers. We start with the ones which are one, two upto nine. Then the elevens starting from eleven to nineteen. Then the tens, twenties upto nineties. We should also define a hundred and thousand. After that the logic is directly readable from the ruby code given below.

ONES = ["zero","one","two","three","four","five","six","seven","eight","nine"]
ELEVENS = ["eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]
TEN,AND = ["ten","and"]
TENS = ["twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"]
HUNDRED, THOUSAND = ["hundred","thousand"]

def nums_upto_99(n)
  return ONES[n] if n < 10
  return TEN if n==10
  return "#{ELEVENS[n-11]}" if n < 20
  return TENS[n/10-2] if n%10==0 && n< 100
  "#{TENS[n/10-2]} #{ONES[n%10]}"
end

def nums_upto_1000(n)
  return nums_upto_99(n) if n<100
  return "#{ONES[1]} #{THOUSAND}" if n==1000
  return "#{ONES[n/100]} #{HUNDRED}" if n%100 == 0
  "#{ONES[n/100]} #{HUNDRED} #{AND} #{nums_upto_99(n%100)}"
end
count = 0
1.upto(1000){|n| count+=nums_upto_1000(n).gsub(/ /,'').size}
puts "The total characters are #{count}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Discover all the fractions with an unorthodox cancelling method.

2010-08-26T14:23:00.000-07:00

Problem 33

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Solution (in Ruby)

This problem unlike the other problems does not ask us to go to millions and trillions and the scope is such that this can be solved in the least running time. All this problem demands careful inspection of the problem statement itself. Its clear we need to iterate through numbers from 1 to 99. For the outer loop (numerator), its enough we run from 12 since its the first double digit number which does not end with a 0 or their digits being equal. We run upto 97 since the numerator cannot be greater than equal to denominator since the fraction should be less than 1
Same is the case for the inner loop. We should always continue to the next iteration if the last number of either numerator or denominator is 0, or if both digits or equal or if the numerator is greater than or equal to denominator. Rest of the solution is just a language specific implementation of finding whether the two different fractions are indeed equal.

n_s, d_s = [1,1]
12.upto(97) do |n|
  13.upto(98) do |d|
    next if n/10 == n%10 || d/10 == d%10 || n%10 ==0 || d%10 ==0 || n>=d
    a,b = [n.to_s.split(//), d.to_s.split(//)]
    if (a&b).size == 1 && (a-(a&b))[0].to_f / (b-(a&b))[0].to_f == n.to_f/d.to_f
      n_s*=(a-(a&b))[0].to_i
      d_s*=(b-(a&b))[0].to_i
    end
  end
end
puts "The product in its lowest common terms is #{d_s/n_s}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : What is the value of the first triangle number to have over five hundred divisors?

2010-08-26T13:45:00.000-07:00

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

Solution (in Ruby)

The main aspect about this solution is finding an efficient way to calculate the number of divisors. Lets take a simple example. The number 6 has 4 divisors namely 1,2,3,6. For this number its enough we run upto the Square root of 6 which is integer floored value to be 2. 1 is divisible by 6 by 6 times, so 1 and 6 are divisors. 2 is divisble by 6 3 times, so 2 and 3 are divisors. So totally we have 4 divisors.
There is one more point to be noted here. For a square number such as 16, if we apply this formula, we will end up getting 6 divisors --> 1, 2, 4, 4, 8, 16. You may see we may calculate 4 twice. But it occurs only once for a square number. This special case is handled in the solution given below. The rest is an as-is implementation of the problem statement.

def divisors_count(n)
  return 1 if n==1
  count = 0
  1.upto(Math.sqrt(n)) do |x|
    if n%x == 0
      count+=1 unless n.to_f/x == x
      count+=1
    end
  end
  count
end

INFINITY = 1.0/0.0
1.upto(INFINITY) do |n|
  if divisors_count(n*(n+1)/2) > 500
    puts "The first triangle number to have over 500 divisors is #{n*(n+1)/2}"
    break
  end
end

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : How many Lychrel numbers are there below ten-thousand?

2010-08-26T07:02:00.000-07:00

Problem 55

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

Solution (in Ruby)

This problem had a higher difficulty rating in project euler problems. But it was one of the straightforward ones that I solved it with Ruby. Nothing to say about the solution, its an as-is implementation of the problem statement.

def is_lynchrel(n)
  50.times do
    n += n.to_s.reverse.to_i
    return false if n.to_s == n.to_s.reverse
  end
  true
end
count = 0
1.upto(9999) do |n|
  count +=1 if is_lynchrel(n)
end
puts "Lynchrel numbers below 10000 is #{count}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Concealed Square

2010-08-26T03:58:00.000-07:00

Problem 206

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

Solution (in Ruby)

Before we look at the optimal solution, lets look at what brute force has to offer us. There are nine slots in the number which leaves us to iterate on 1000000000 times (1 trillion times). This is simply not doable, it will take years to run through this loop. So brute force is out of the equation. We need to find a digit or two to reduce the loop count.

So its wiser to look at some of the property of square numbers. Square number ending with zero, has to have the previous digit also 0, which leaves us with only 8 slots now. One more property is that the square root for this particular number has to start with 1. The reason is in finding the square root, we need pair numbers from the back and need to find the square root of the first hanging digit/pair. In this case its 1. Square root 1 is 1 and its enough to inspect only one digit. This leaves us 1 more slot less in our problem. And one final property is the ending digit. Here its 9. Only numbers that end with 3 and 7 produces 9. This leaves our permutation reduce by one more digit (since its enough for us to step 10 times every time in the loop). We need to find the lower bound of the number which is 10203040506070809. The square root of this number is 101010101. We shall end with either 3 or 7. And start with the maximum digit in that sequence which is 199999999. Thats it!! Now we've shortened the problem to be solved within seconds!!

(101010107..199999999).step(10) do |n|
  if ((n*n).to_s.gsub /(.)./,'\1') == "123456789" || (((n-4)*(n-4)).to_s.gsub /(.)./,'\1') == "123456789"
    puts "The unique positive number is #{n*10}"
    break
  end
end

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many circular primes are there below one million?

2010-08-25T13:51:00.000-07:00

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?

Solution (in Ruby)

The solution to this problem invovles one performance enhancement in finding the prime numbers. If you want to check whether the same number is prime more than once in your program, it is highly important to have a look on the running time. That is why I am using an array to store the number as the index itself. This would make sure that the number given is found to be prime or not in O(1) time. Rest of the solution did what the problem statement demands

def find_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end
large = []
1.upto(1000000) { |each_num| large[each_num] = true if find_prime(each_num) }
count = 0
1.upto(1000000) do |num|
  str = num.to_s
  all = (0...str.length).collect { |i| large[((str * 2)[i, str.length]).to_i] ? true : false }
  count+=1 if all.inject(0){|b,i| b&&=i}
end
puts "The count of such primes is #{count}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

2010-08-25T12:00:00.000-07:00

Problem 36

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Solution (in Ruby)

The solution is one the simplest and straightforward when implemented in Ruby.

sum = 0
1.upto(1000000) do |num|
  sum+=num if num.to_s == num.to_s.reverse && num.to_s(base=2) == num.to_s(base=2).reverse
end
puts "Sum is #{sum}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many triangle words does the list of common English words contain?

2010-08-25T11:45:00.000-07:00

Problem 42

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.
Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Solution (in Ruby)

The main place where we need to attack this problem involves in finding the roots of the quadratic equation. We know the roots of the quadratic equation

If you apply this equation to the simple formula to find the triangle numbers, we will find out that a = 1 and b = 1 and c will be twice the triangle number. There will be two roots possible, one will be positive and other will be negative. It is enough to find the positive root. If that root is a whole number, then that will be a proper triangle number.

names = File.new("/words.txt","r").gets.split(/,/)
count = 0
names.each do |n|
  value = n.gsub!(/^"(.*?)"$/,'\1').split(//).inject(0){|b,i| b+i[0]-64}
  positive_root = (-1+Math.sqrt(1+8*value))/2
  count+=1 if positive_root == positive_root.ceil
end
puts "The total number of words is #{count}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Using an efficient algorithm find the maximal sum in the triangle?

2010-08-23T13:08:00.000-07:00

Problem 67

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

Solution (in Ruby)

To attack this problem, we should think in the reverse order as exploring all the possible routes would take 20 billion years to solve this problem!! We should start at the bottom but before level. For each number in that level, replace with the sum of that number and the maximum of the below two numbers. Do this for each level and bingo! we will arrive at the solution. So easy now isnt it? :) Thats 'after' you know it. Ruby code is presented below. There is another problem (Problem 18) (the minor input version) which also is the same one like the one above.

input = ''

f = File.new("/triangle.txt","r")
while (line = f.gets)
  input += line
end

class Row
  attr_accessor :index, :data
end

index = 0
triangle =  input.lines.map{|each_line| r = Row.new; r.index = index; r.data=[]; index+=1; sub_index = 0
  each_line.split.map{|n| r.data[sub_index] = n.to_i; sub_index+=1}; r}

(triangle.size - 2).downto(0) do |n|
  0.upto(triangle[n].data.size-1) do |sub_index|
    triangle[n].data[sub_index] += [ triangle[n+1].data[sub_index+1] , triangle[n+1].data[sub_index] ].max
  end
end

puts "The maximum value is #{triangle[0].data}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find a quadratic formula that produces the maximum number of primes for consecutive values of n.

2010-08-23T04:09:00.000-07:00

Problem 27

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.
Using computers, the incredible formula n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.
Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

Solution (in Ruby)

Normally we would want to run through 1000 numbers in the outer loop and 1000 numbers in the inner loop to attack this problem. But we can significantly reduce that by just running 168 x 168 times by calculating the number of primes below 1000 first. This would reduce our running time. The rest of the solution is an as-is implementation of the problem statement.

def is_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end

max_primes = []; a_s = []; b_s = []
INFINITY = 1.0/0.0

primes_upto_1000 = []
1.upto(999) do |each_num|
  primes_upto_1000 << each_num if is_prime(each_num)
end

primes_upto_1000.each do |a|
  primes_upto_1000.each do |b|
    each_prime = 0
    0.upto(INFINITY) do |n|
      break unless is_prime(n**2 - a*n + b)
      each_prime+=1 
    end
    max_primes<<< -a ; b_s << b
  end
end

puts "Product of a and b is #{a_s[max_primes.index(max_primes.max)] * b_s[max_primes.index(max_primes.max)]}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : What is the total of all the name scores in the file of first names?

2010-08-23T03:31:00.000-07:00

Problem 22

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 53 = 49714.
What is the total of all the name scores in the file?

Solution (in Ruby)

All we had to do is read the file convert all the values into an array and sort it. Then for each word we need to apply the rule as stated in the problem. If you could look at the code inside the loop, i would be ripping the starting and trailing quotes '"' and then converting them to index numbers. ie A for 1, B for 2 upto Z for 26. Rest is self explanatory.

names = File.new("/names.txt","r").gets.split(/,/).sort
sum = 0
index = 1
names.each do |n|
  sum += n.gsub!(/^"(.*?)"$/,'\1').split(//).inject(0){|b,i| b+i[0]-64} * index
  index+=1
end
puts "The total of all the name scores is #{sum}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : How many Sundays fell on the first of the month during the twentieth century?

2010-08-23T02:05:00.000-07:00

Problem 19

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Solution (in Ruby)

This particular solution does not involve any hard calculations, just run through the dates starting from the first sunday step by 7 days and check if the sunday lies on the first day of the month.

require 'date'
d1, d2, total_sundays = [Date::civil(1901, 1, 1), Date::civil(2000, 12, 31), 0]
d1 +=1 while (d1.wday != 0)
d1.step(d2, 7){|date| total_sundays+=1 if date.day == 1}
puts "Total number of Sundays : #{total_sundays}"

Hover here to see the solution

Project Euler : Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order.

2010-08-22T13:39:00.000-07:00

Problem 52

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Solution(in Ruby)

The solution to this problem is simple and straight forward as shown below. Just convert the problem statement into code with tweaks here and there, we should arrive at the solution smoothly. Do not get scared by the catch statement, its just to break nested loops. Moreover, it is enough to inspect numbers that start with 1. The obvious reason being numbers that begin with 2 get more digits when multiplied by 6 which would defeat our purpose.

INFINITY = 1.0 / 0.0
catch (:done) do
  1.upto(INFINITY) do |i|
    ((10**i)...(2*10**i)).each do |x|
      y = x.to_s.split(//)
      if ( y - (x*2).to_s.split(//) ).size == 0 && y.size == (x*2).to_s.split(//).size &&
         ( y - (x*3).to_s.split(//) ).size == 0 && y.size == (x*3).to_s.split(//).size &&
         ( y - (x*4).to_s.split(//) ).size == 0 && y.size == (x*4).to_s.split(//).size &&
         ( y - (x*5).to_s.split(//) ).size == 0 && y.size == (x*5).to_s.split(//).size &&
         ( y - (x*6).to_s.split(//) ).size == 0 && y.size == (x*6).to_s.split(//).size
        puts "The minimum unique number is #{x}"
        throw :done
      end
    end
  end
end

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the minimal path sum from the left column to the right column.

2010-08-22T13:15:00.000-07:00

Problem 82
The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

131	673	234	103	18
201	96	342	965	150
630	803	746	422	111
537	699	497	121	956
805	732	524	37	331

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.

Solution(in Ruby)

This problem has to be attacked in the reverse order ie starting from the right to left. Lets take the last but before column. For each cell in that column, find the minimum possible sum for that cell. To find the minimum possible sum, you will have to find all the 'L' paths explored, their sum has be calculated and stored and the minimum sum has to be stored in that cell. After traversing that entire column, replace that particular column value with the minimal sum. Repeat this process for the immediate left column until you exhaust all the columns reaching the left most column. The minimal value of the leftmost column is the minimal sum which is exactly what we look for.

require 'matrix'

input = ''
file = File.new("/matrix.txt","r")
while (line = file.gets) 
  input += line
end

class Cell
  attr_accessor :min_sum, :value
end

x = Matrix.rows(input.lines.map{|each_line| each_line.split(/,/).map{
      |n|
      c = Cell.new
      c.min_sum = c.value = n.to_i
      c
    }})

MAX = x.row_size

(MAX-2).downto(0) do |column|
  0.upto(MAX-1) do |row|
    val_array = []
    aggregate = x[row,column].value
    val_array << aggregate + x[row,column+1].value
    (row+1).upto(MAX-1) do |down_traverse|
      aggregate += x[down_traverse,column].value
      val_array << aggregate + x[down_traverse,column+1].value
    end
    aggregate = x[row,column].value
    (row-1).downto(0) do |up_traverse|
      aggregate += x[up_traverse,column].value
      val_array << aggregate + x[up_traverse,column+1].value
    end
    x[row,column].min_sum = val_array.min
  end
  0.upto(MAX-1) do |each_row|
    x[each_row,column].value = x[each_row,column].min_sum
  end
end
val_array = []
0.upto(MAX-1) do |val|
  val_array << x[val,0].value
end

puts "The minimum sum is #{val_array.min}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Find the longest sequence using a starting number under one million.

2010-08-21T13:13:00.000-07:00

Problem 14

The following iterative sequence is defined for the set of positive integers:

n --> n/2 (n is even)
n --> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 --> 40 --> 20 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Solution (in Ruby)

In order to solve this problem, we first need to find a pattern by attacking in the reverse order. If you could see if the number gotten is a power of two, it will diminish all the way upto 1. So its wiser to store their frequency (power of 2 numbers) first in the array. The next interesting property is that if you find the chain count for a number you do not want to find that again. Combining these two properties, we can very well get a linear solution for the input count of 1 million solving the problem within seconds.

MAX_NUM = 1000000
n = Array.new(MAX_NUM)
n[0] = 0
n[1] = 1
counter = 1
index = 1
while (counter < MAX_NUM)
  n[counter] = index
  index+=1
  counter*=2
end
(MAX_NUM-1).downto(2) do |num|
  if n[num]
    next
  end
  rolling = num
  sequence = 0
  while !n[rolling]
    if rolling % 2 == 0
      rolling = rolling/2
    else
      rolling = 3*rolling + 1
    end
    sequence+=1
  end
  n[num] = sequence + n[rolling]
end
puts "The maximum chained number is #{n.index(n.max)}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Calculate the sum of all the primes below two million.

2010-08-21T05:35:00.000-07:00

Problem 10
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

Solution(in Ruby)
The solution to this problem involves the tricky implementation of prime number functionality. Rest is just a matter of programming.

def is_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end
sum = 0
2.upto(2000000) do |num|
  x+=num if is_prime(num)
end
puts "Sum is #{sum}"

Hover here to see the solution

Cheers!
Bragaadeesh

Project Euler : Find the greatest product of five consecutive digits in the 1000-digit number.

2010-08-21T05:21:00.000-07:00

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution (in Ruby)

The solution to this problem can be solved by just naked eyes. Anyway, I have presented the code in Ruby.

num = '73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450'
f = ''
num.lines{|x| f += x.chop}
y = f.split(//)
arr = []
0.upto(995) do |index|
  arr << y[index].to_i * y[index+1].to_i * y[index+2].to_i * y[index+3].to_i * y[index+4].to_i
end
puts arr.max

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Find the largest palindrome made from the product of two 3-digit numbers.

2010-08-21T04:42:00.000-07:00

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.
Find the largest palindrome made from the product of two 3-digit numbers.

Solution (in Ruby)

The solution to this problem is pretty straight forward. All we had to do is run from 101 to 999 and multiply all the combination and push them into an array and find the maximum value.

arr = []
101.upto(999) do |i|
  101.upto(999) do |j|
    prod = i*j
    arr << prod if prod.to_s == prod.to_s.reverse
  end
end
puts "The largest palindromic number is #{arr.max}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Finding maximum prime factor

2010-08-21T03:44:00.000-07:00

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Solution (in Ruby)

The solution to this problem is simple. But the main problem here is to construct a rock solid method that returns whether a given number is prime or not. A prime number is a number which divisible by itself and 1 only. Example of prime numbers are 2,3,11,4999. The following is the ruby code to find whether or not a number is prime or not. You may see that I have used a square root of the number as the upper bound, the simple reason being, there cannot be a number greater than the square root of that number being prime (you can get it if you think deep)

def is_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end

Now that we have written a method that returns whether or not a number is prime, the rest of the problem is fairly simple. Again, we have to use the square root property. It is enough if we run the prime number validation from the square root of the number. We will have to traverse all the way to 2 for this. The first occurring prime factor is ofcourse the solution to our problem.

Math.sqrt(600851475143).to_i.downto(2) do |n|
  if is_prime(n) && 600851475143%n ==0
    puts "Maximum prime factor for this number is #{n}"
    break
  end
end

Hover here to see the solution.

Cheers!!
Bragaadeesh.

Project Euler : Finding maximum product in a matrix

2010-08-21T02:36:00.000-07:00

Problem 11

In the 20 x 20 grid below, four numbers along a diagonal line have been marked in red.

02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 x 63 x 78 x 14 = 1788696.
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 x 20 grid?

Solution (In Ruby)

The solution to this particular problem is simple and by simple naked eye viewing we can get what we want. But then, if the numbers are almost in the same range and if the matrix size is more then it will become real difficult to identify the maximum number. The following ruby code will find the maximum number. All we are doing here is finding the product of the numbers in the fashion we are supposed to. There is no trick shortcut here. We 'will' have to traverse the entire matrix for finding the product.

require 'matrix'
input =
 '08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
  49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
  81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
  52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
  22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
  24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
  32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
  67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
  24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
  21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
  78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
  16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
  86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
  19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
  04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
  88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
  04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
  20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
  20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
  01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'

x =  Matrix.rows(input.lines.map{|line| line.split.map{|n| n.to_i}})
val = []
0.upto(19) do |r|
  0.upto(19) do |c|
    val << x[r,c] * x[r,c+1] * x[r,c+2] * x[r,c+3] if c<=16
    val << x[r,c] * x[r+1,c] * x[r+2,c] * x[r+3,c] if r<=16
    val << x[r,c] * x[r+1,c+1] * x[r+2, c+2] * x[r+3, c+3] if c<=16 && r<=16
    val << x[r,c] * x[r+1,c-1] * x[r+2, c-2] * x[r+3, c-3] if c>=3 && r<=16
  end
end
puts puts "Maximum product is #{val.max}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000).

2010-08-20T14:44:00.000-07:00

Problem 48

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.
Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

Solution (In Ruby)

The solution to this problem becomes simple if we just directly implement with the brute force technique. It just costs two lines in Ruby and the source code is given below.

sum = (1..1000).to_a.inject(0) {|b,i| b+= i**i}.to_s
puts sum.to_s[(sum.size-10)..(sum.size)]

Hover here to see the solution.

Cheers!!
Bragaadeesh

Project Euler : Find the sum of the digits in the number 100!

2010-08-20T13:58:00.000-07:00

Problem 20
n! means n x (n -1) x ... x 3 x 2 x 1
Find the sum of the digits in the number 100!

Solution (In Ruby)

All we have to do for the above problem is to write a factorial method. Get the value of 100! and split it into characters and simply add them. Source code is given below.

def fact(n)
  return 1 if n == 0
  n * fact(n-1)
end
puts "Result is #{fact(100).to_s.split(//).inject(0){|b,i| b+i.to_i}}"

Hover here to see the result

Cheers!!
Bragaadeesh

Project Euler : What is the sum of both diagonals in a 1001 by 1001 spiral?

2010-08-20T13:29:00.000-07:00

Problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

22 23 24 25
 7  8  9 10
 6  1  2 11
 5  4  3 12
16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

The solution (in ruby)

The problem initially looks complex and makes us want to use matrices. For a small input such as the one given, it will be easier to solve. But when the size of the matrix increases, it is almost impossible to do a proper traversal and find the edge values. This problem can be attacked easily if we are able to decipher the pattern. If you could notice the given matrix carefully, you may find that at each square corners, we have a square number on the right top corner, leave the first value (1), we can sum it later.

For the first level, the corner value is 9 = 3²
For the second level, corner value is 25 = 5²

This keeps going. Our job is to find a forumla at each covering square. The forumla that I arrived at each level in terms of n is [4 * (n² - (n-1)*3/2)]. If you apply the above formula for level 3 we will get 24, for level 5, its 76. If you add these two you will get 100. Now add that with 1, you will get the desired answer as 101. Finding that formula is left to the reader as an excercise (it can be found using finite differences)
Now the source code in ruby,

result = 1
(3..1001).step(2) do |n|
  val += (n*n - 3 * (n-1)/2)*4
end
puts "Result is #{result}"

HOVER HERE TO SEE THE ANSWER

Cheers!!
Bragaadeesh.

Project Euler : Find the sum of all the numbers that can be written as the sum of 5th powers of their digits.

2010-08-20T12:34:00.000-07:00

Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

The Solution (in Ruby)

This problem is a bit tricky and can be solved with a trial and error method. Best way to attack this problem is to first arrive at a solution for the 4th power as given in the problem, convince ourselves that the solution that we have coded is correct. Then run the same for 5th powers. Of course the upper bound is a mystery, but who cares you have trial and error to know the answer.

final_result = 0
2.upto(200000) do |x|
  sum = x.to_s.split(//).inject(0){|b,i| b+i.to_i**5}
  final_result += sum if sum == x
end
puts "The magic sum is #{final_result}"

HOVER HERE TO SEE THE SOLUTION!!

Cheers!!
Bragaadeesh

Google CodeJam 2010 : "Rope Intranet" Problem with solution

2010-08-08T13:13:00.000-07:00

Problem

A company is located in two very tall buildings. The company intranet connecting the buildings consists of many wires, each connecting a window on the first building to a window on the second building.
You are looking at those buildings from the side, so that one of the buildings is to the left and one is to the right. The windows on the left building are seen as points on its right wall, and the windows on the right building are seen as points on its left wall. Wires are straight segments connecting a window on the left building to a window on the right building.

You've noticed that no two wires share an endpoint (in other words, there's at most one wire going out of each window). However, from your viewpoint, some of the wires intersect midway. You've also noticed that exactly two wires meet at each intersection point.
On the above picture, the intersection points are the black circles, while the windows are the white circles.
How many intersection points do you see?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing an integer N, denoting the number of wires you see.
The next N lines each describe one wire with two integers A_i and B_i. These describe the windows that this wire connects: A_i is the height of the window on the left building, and B_iis the height of the window on the right building.

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 intersection points you see.

Limits

1 ≤ T ≤ 15.
1 ≤ A_i ≤ 10⁴.
1 ≤ B_i ≤ 10⁴.
Within each test case, all A_i are different.
Within each test case, all B_i are different.
No three wires intersect at the same point.

Small dataset

1 ≤ N ≤ 2.

Large dataset

1 ≤ N ≤ 1000.

Sample

Input	Output
`2 3 1 10 5 5 7 7 2 1 1 2 2`	`Case #1: 2 Case #2: 0`

Solution

This is one of the simpler problems that I was able to solve in the Codejam round. Following is the source code.

private long solve(int[] a, int[] b) {
  
  PointMesh p = new PointMesh();
  
  for(int i=0;i<a.length;i++){
   p.add(a[i], b[i]);
  }
  
  return p.intersects;
 }

 class PointMesh{
  long intersects;
  List<Line2D> lineList = new ArrayList<Line2D>();
  Line2D line1 = new Line2D.Double();
  Line2D r = new Line2D.Double();  
  
  void add(int a,int b){
   Point2D p1 = new Point2D.Double(0, a);
   Point2D p2 = new Point2D.Double(10, b);
   Line2D newLine = new Line2D.Double(p1,p2);
   
   for(Line2D eachLine:lineList){
    if(eachLine.intersectsLine(newLine))
     intersects++;
   lineList.add(newLine);
  }
 }

Complete source code : here
Practice inputs : here

Cheers!!
Bragaadeesh.

Google CodeJam 2010 : "File Fix-it" Problem with solution

2010-07-24T15:20:00.000-07:00

Problem

On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.
A directory is uniquely identified by its name and its parent directory (the directory it is directly contained in). This is usually encoded in a path, which consists of several parts each preceded by a forward slash ('/'). The final part is the name of the directory, and everything else gives the path of its parent directory. For example, consider the path:

/home/gcj/finals

This refers to the directory with name "finals" in the directory described by "/home/gcj", which in turn refers to the directory with name "gcj" in the directory described by the path "/home". In this path, there is only one part, which means it refers to the directory with the name "home" in the root directory.
To create a directory, you can use the mkdir command. You specify a path, and thenmkdir will create the directory described by that path, but only if the parent directory already exists. For example, if you wanted to create the "/home/gcj/finals" and "/home/gcj/quals" directories from scratch, you would need four commands:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.
The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to list it explicitly.)
The next M lines each give the path of one directory that you want to create.
Each of the paths in the input is formatted as in the problem statement above. Specifically, a path consists of one or more lower-case alpha-numeric strings (i.e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty.

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 mkdir you need.

Limits

1 ≤ T ≤ 100.
No path will have more than 100 characters in it.
No path will appear twice in the list of directories already on your computer, or in the list of directories you wish to create. A path may appear once in both lists however. (See example case #2 below).
If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.
The input file will be no longer than 100,000 bytes in total.

Small dataset

0 ≤ N ≤ 10.
1 ≤ M ≤ 10.

Large dataset

0 ≤ N ≤ 100.
1 ≤ M ≤ 100.

Sample

Input	Output
`3 0 2 /home/gcj/finals /home/gcj/quals 2 1 /chicken /chicken/egg /chicken 1 3 /a /a/b /a/c /b/b`

Solution

To attack this problem we can use the famous TRIE data structure. We have already seen enough about this data structure in steps and this becomes so handy in this particular problem.
A TRIE data structure simply stores the data that becomes easy for retrieval. But lets not bother about the retrieval part in this particular problem. We will simply increase our counter whenever we add a new folder to the existing directory structure. The place where we optimize this problem involves in its running time. Whenever we see a new directory structure, we simply pass through it in the length times instead which is linear in time jargons. The solution is given below.

private int solve(String[] already, String[] fresh) {
  Trie trieDSA = new Trie();
  
  for(int i=0;i<already.length;i++){
   trieDSA.insert(already[i],false);
  }
  
  for(int i=0;i<fresh.length;i++){
   trieDSA.insert(fresh[i], true);
  }
  
  return trieDSA.counter;
 }

So clean, isnt it? The TRIE and the Node classes are given below. Remember, please go through my TRIE data structure introduction for few minutes, its definitely a knowledgeable one! Trust me :)

class Node {
 String currentPath;
 boolean marker; 
 Collection<Node> child;
 
 public Node(String path){
  child = new HashSet<Node>();
  marker = false;
  currentPath = path;
 }
 
 public Node subNode(String path){
  if(child!=null){
   for(Node eachChild:child){
    if(eachChild.currentPath.equals(path)){
     return eachChild;
    }
   }
  }
  return null;
 }
}

class Trie{
 private Node root;
 
 public int counter = 0;

 public Trie(){
  root = new Node("");
 }

 public void insert(String pathArray, boolean shouldTrack){
  Node current = root; 
  
  String[] paths = pathArray.substring(1).split("\\/");
  
  if(paths.length==0){
   //DO NOTHING
   current.marker=true;
  }
   
   
  for(int i=0;i<paths.length;i++){
   Node child = current.subNode(paths[i]);
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(paths[i]));
    current = current.subNode(paths[i]);
    if(shouldTrack){
     counter++;
    }
   }
   // Set marker to indicate end of the word
   if(i==paths.length-1)
    current.marker = true;
  } 
 }
}

Complete source code : here
Sample Input : here

Cheers!!
Bragaadeesh.

Hello World in Ruby

2010-06-06T03:14:00.000-07:00

After getting a decent knowledge of what Ruby is and the useful resources that are available, lets get into action by creating our first hello world program.

Ruby and Ruby on Rails development becomes amazingly easy using Netbeans IDE where you can perform almost all the tasks in one single IDE. Download and install the Netbeans-Ruby version. You should be having JDK installed in your box, thats pretty much the pre-requisite for Netbeans to install.

Once your installation is done, launch Netbeans go to File --> New Project. A new project wizard should come up. Select Ruby Application, click Next and click Finish. Thats it!!!! You dont even have to type a Hello World. The new project template does it for you! So sweet isnt it? Now, click on the big green Run button and the console should print out Hello World without a hitch.

Way to go!! We shall try out some simple programs in the coming posts.

Cheers!
Bragaadeesh.

Useful books on Ruby and Ruby on Rails

2010-06-04T11:44:00.000-07:00

Before we jump into the real discussion on Ruby and Ruby on Rails, I felt it will be nicer if I could provide some of the very good books available out there. Programming Ruby 1.9 is the starter pack that everyone who is willing to work on Ruby has to go through.

Agile Web Development using Rails 3rd Edition
Programming Ruby 1.9
Head First Rails

Cheers!
Bragaadeesh.

Lets Ruby!

2010-05-29T05:36:00.000-07:00

I have been working mostly in Java for the past 4 years and my new work demands me to learn Ruby. So I've started looking into it for the past week and thought I would share my learning process so that it would be useful for someone out there. And thats the objective of this series of posts for someone having a Java background and wanting to learn Ruby.

Lets get into business. I am really excited to see the way Ruby language syntax is and I am eager to learn this mouth-watering scripting language of coolest nature. During my initial analysis, I learnt that Ruby is,

Implemented in many other high level languages such as C, Java, .Net etc.,
Is relatively slower.
Ruby is a high level language made of a high level language.
Not suitable for large applications.
Completely open source and is in a budding state.
Has a framework called Rails which is good for Agile development
Community out there is getting better day by day and finding help immediately should not be a problem as time goes by.
Has significant changes between releases which many developers wont welcome right away.
Running time cannot be easily estimated since the language has several underlying implementation in several languages. But there are various profilers available to test them.
Books are always outdated by the time when you finish them.

Now that the premise being established on what Ruby is, we shall learn it and have a comparison/understanding on how it relates to Java.

Cheers,

Bragaadeesh.

How to exploit Google docs

2010-05-28T13:13:00.000-07:00

Now that google has removed the restriction on its documents, it is time for us to start exploiting it.

No need to upload your pictures in some free image webhosting websites where you wont be having the 100% surity of whether it might come up all time or you'l see a "bandwidth exceeded" message. Upload it to your own google account and with some tweak, we can link it directly in the webpage. You can do the same with Picasa, but you will have to create an album every time and it becomes kind of annoying to maintain it.

Same goes with the flash presentations as well. No need to host it to any unreliable free websites. Upload it to your own google document. Plus if you want any referring files you can very well upload it to Google Docs. Yes, there is a limit on the size per account but still 7+ GB will become handy for small and medium bloggers.

Ok, the steps are very very simple.

1. Login to http://docs.google.com. Sign in with your google id and password.

2. Click on upload from the left top and select "any" file type you want only restriction is it cannot exceed 100 MB. Do not forget to uncheck "Convert documents, presentations, and spreadsheets to the corresponding Google Docs formats" if you feel you dont want Google mess up your documents.

3. After you upload the file, select the file and click on Share and select "Get the link to share". You should be getting a link in a text bar as shown below

4. To append the file in your page all you got to do is add this to the url &export=open&type=.swf

This way you can directly embed your flash or jpg or png directly in your pages (the type=.xxx will vary depending on the file you've uploaded). If you want to give a direct download link append this command at the end &export=download&confirm=no_antivirus

The last one &confirm=no_antivirus can be given to files of .exe and .zip extensions.

Hope this helped. A sample flash file embedded from google doc can be found here.

Cheers!!
Bragaadeesh.

Print Matrix in a circular path (Interview question)

2010-05-11T14:31:00.000-07:00

Hi friends,

This is one of the interview questions I faced recently and thought I would share it.

Question:
Given a matrix print all its value in a circular fashion like shown in the image below.

Solution:
To attack this problem we definitely want to have a left-right, top-bottom, right-left and bottom-top spans. For attaining this, we obviously want to have 4 loops. The C++ code is given below.

//============================================================================
// Name        : circular_matrix_read.cpp
// Author      : c++
// Description : output given matrix elements circularly
//============================================================================

#include <iostream>
using namespace std;

#define HEIGHT 6
#define WIDTH  3

int main()
{
 //int array[HEIGHT][WIDTH] = {{1,2,3,4,5},{16,17,18,19,6},{15,24,25,20,7},{14,23,22,21,8},{13,12,11,10,9}};
 //int array[HEIGHT][WIDTH] = {{1,2,3,4,5,6},{14,15,16,17,18,7},{13,12,11,10,9,8}};
 int array[HEIGHT][WIDTH] = {{1,2,3},{14,15,4},{13,16,5},{12,17,6},{11,18,7},{10,9,8}};
 int maxh = HEIGHT-1, maxw = WIDTH-1;
 int minh = 0, minw = 0;
 while(1)
 {
  if(minh > maxh || minw > maxw)
   break;

  //top-left to top-right
  for(int i=minh,j=minw;j<=maxw;j++)
   cout << array[i][j] << endl;
  minh++;

  if(minh > maxh || minw > maxw)
   break;

  //top-right to bottom-right
  for(int i=minh,j=maxw;i<=maxh;i++)
   cout << array[i][j] << endl;
  maxw--;

  if(minh > maxh || minw > maxw)
   break;

  //bottom-right to bottom-left
  for(int i=maxh,j=maxw;j>=minw;j--)
   cout << array[i][j] << endl;
  maxh--;

  if(minh > maxh || minw > maxw)
   break;

  //bottom-left to top-left
  for(int i=maxh,j=minw;i>=minh;i--)
   cout << array[i][j] << endl;
  minw++;
 }
 return 0;
}
//1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Cheers!
Bragaadeesh.

Google CodeJam 2010 : Theme Park with Solution

2010-05-09T14:24:00.000-07:00

Guys,

This is one of the three problems asked in the 2010 Edition of Google Codejam Qualification Round. The question is quite interesting and simple to solve and I did solve. But the problem here is the running time. If not a proper strategy is followed, then the running time of the algorithm will be more and eventually you cannot submit the answer in time for large data set. Lets look at the problem.

Problem

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 g_i, each of which is the size of a group that wants to ride. g₀ is the size of the first group, g₁ 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.
g_i ≤ k.

Small dataset

1 ≤ R ≤ 1000.
1 ≤ k ≤ 100.
1 ≤ N ≤ 10.
1 ≤ g_i ≤ 10.

Large dataset

1 ≤ R ≤ 10⁸.
1 ≤ k ≤ 10⁹.
1 ≤ N ≤ 1000.
1 ≤ g_i ≤ 10⁷.

Sample

Input	Output
`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`	`Case #1: 21 Case #2: 100 Case #3: 20`

Solution

The solution for this problem may look simple and if we follow the problem as is, its pretty straight-forward. So, here is the solution that I initially arrived at,

private int solve(int R, int k, int[] groups){
  
  int moneyMade = 0;
  LinkedList<Integer> groupsQueue = new LinkedList<Integer>();
  
  for(int i=0;i<groups.length;i++){
   groupsQueue.add(groups[i]);
  }
  
  while(R>0){
   //calculate the people that can fit in
   int eachSum = 0;
   int i;
   for(i=0;i<groups.length;i++){
    eachSum+=groupsQueue.get(i);
    if(eachSum>k){
     eachSum-=groupsQueue.get(i);
     break;
    }
   }
   moneyMade+=eachSum;
   //alterQueue
   for(int j=0;j<i;j++){
    groupsQueue.add(groupsQueue.poll());
   }
   R--;
  }
  
  return moneyMade;
 }

If you look at the above solution, I have followed the problem by the word. But turned out this cannot take the large data input set simply because of the amount of time it takes to run. The mole in the above solution is that I calculate the eachSum everytime for all R iterations. The large dataset is having R upto 10^8 and Group to be 10^7. So the runtime in worst case will be 10^16 which even the fastest computers invented these days struggle to solve in small time.

So, I had to attack my problem in a different manner. All Google CodeJam problems dont have any space criterion, so its wise to make use of it. So, what would be ideal here is to precalculate the sum and extent for each group before hand. This would take a max of 10^3 * 10^3 = 10^6 iterations. The results are stored in a separate array for faster recovery.

Then iterate through the entire R once and finish the problem in constant time. The matured code is given below.

private long solve(long R, long k, long[] groups){
  int len = groups.length;
  long[] sums = new long[len];
  int[] span = new int[len];
  //irrespective of R, calculate and keep the extent and sum in separate arrays
  for(int x=0;x<len;x++){//Maximum 1000 runs
   int sum = 0; int extent=0;
   for(int y=x;;y++){
    if(sum+groups[y%len]>k || len==extent){
     break;
    }
    extent++;
    sum+=groups[y%len];
   }
   sums[x] = sum;
   span[x] = extent;
  }
  long totalSum = 0;
  int i = 0;
  for(int r=0;r<R;r++){
   totalSum += sums[i];
   i+=span[i];
   i=i%len;
  }
  return totalSum;
 }

Files you may need.
1. Input file - Small dataset
2. Input file - Large dataset
3. Output file - Small dataset
4. Output file - Large dataset
5. Complete Source code in Java

Cheers!,
Bragaadeesh.

Google CodeJam : Alien Language Problem with Solution

2010-05-04T10:06:00.000-07:00

This is the problem asked in 2009 Google Codejam's qualification round. Lets get into business straightaway.

Problem

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.

Input

The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.

Output

For each test case, output

Case #X: K

where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.

Limits

Small dataset

1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10

Large dataset

1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500

Sample

Input

3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc

Output
Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

The solution for this problem is relatively simple compared to the other codejam problems that we are going to solve in the future. The solution is implemented in Perl language. It uses the regex pattern matching method.

#!/usr/local/bin/perl

use strict;
use warnings;

print "Enter file name :: ";
my $infile = <STDIN>;

open(INP,"<$infile") or die "can not open file for reading";

my $line_num = 0;
my $num_of_words = 0;
my $num_of_testcases = 0;
my @words_array;
my @testcases_array;

while(<INP>)
{
 if($line_num == 0)
 {
  my @tmp = split(/\s/,$_);
  $num_of_words = $tmp[1];
  $num_of_testcases = $tmp[2];
 }
 elsif($line_num >= 1 and $line_num < ($num_of_words + 1))
 {
  s/[\s\t\n]//;
  $words_array[$line_num - 1] = $_;
 }
 elsif($line_num >= ($num_of_words + 1) && $line_num < ($num_of_words + $num_of_testcases + 1))
 {
  s/[\s\t\n]//;
  s/\(/[/g;
  s/\)/]/g;
  $testcases_array[$line_num - 1 - $num_of_words] = $_;
 }
 $line_num++;
}

my $words_passed = 0;
my $testcase_num = 1;
foreach my $pattern (@testcases_array)
{
 foreach my $word (@words_array)
 {
  if($word =~ m/$pattern/)
  {
   $words_passed++;
  }
 }
 print "Case #$testcase_num: $words_passed\n";
 $words_passed = 0;
 $testcase_num++;
}

close(INP);

Input file of large dataset : Download
Output file of large dataset : Download

Cheers!
Bragaadeesh

Find three numbers in an array which forms a maximum product (for signed integers)

2010-05-03T11:57:00.000-07:00

This is a problem that we had already seen. But it gives more kick if the input has negative elements and zero!!!

Question:
Given an array of integers (signed integers), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].

int[] MaxProduct(int[] input, int size)

The solution involves in finding three maximum and two minimum numbers. If the minimum numbers are negatives and if their product is greater than the two maximum number's product, then they have to considered for maximum product. Handling all these scenarios with comprehensive test cases, please find the code below for the problem implemented in C++

//============================================================================
// Name        : three_largest_elems.cpp
// Author      : Prabhu Jayaraman
// Version     : v2
// Copyright   : open
// Description : To find three signed numbers in an array with max product
//========================================================a====================

#include <iostream>
using namespace std;

#define MAX 10

int* MaxProduct(const int input[], const int size)
{
 int* output = new int[3];
 int negative = 0;
 for(int i = 0; i < 3; i++)
 {
  output[i] = -999999;
 }
 int min[2] = {0,0};

 for(int i=0;i<size;i++)
 {
  // find two smallest negative numbers
  if(input[i] <= 0)
  {
   if(input[i] < min[0])
   {
    min[1] = min[0];
    min[0] = input[i];
   }
   else if(input[i] < min[1])
   {
    min[1] = input[i];
   }
   negative++;
  }

  // find three largest positive numbers
  if(input[i] > output[0])
  {
   output[2] = output[1];
   output[1] = output[0];
   output[0] = input[i];
  }
  else if(input[i] > output[1])
  {
   output[2] = output[1];
   output[1] = input[i];
  }
  else if(input[i] > output[2])
  {
   output[2] = input[i];
  }
 }

 if(size != negative)
 {
  if((min[0] * min[1]) > (output[0] * output[1]) || (min[0] * min[1]) > (output[1] * output[2]))
  {
   output[1] = min[0];
   output[2] = min[1];
  }
 }

 return output;
}

int main()
{
 const int input[MAX] = {-6,-1,-2,-33,-4,-15,-7,-28,-9,-10};
 int* result = 0;
 result = MaxProduct(input,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result[i] << endl;
 }

 const int input1[MAX] = {0,-1,-2,-33,4,15,-7,-28,-9,-10};
 int* result1 = 0;
 result1 = MaxProduct(input1,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result1[i] << endl;
 }

 const int input2[MAX] = {0,-1,-2,-33,-4,-15,-7,-28,-9,-10};
 int* result2 = 0;
 result2 = MaxProduct(input2,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result2[i] << endl;
 }

 const int input3[MAX] = {6,1,2,33,4,15,7,28,9,10};
 int* result3 = 0;
 result3 = MaxProduct(input3,MAX);

 for(int i = 0; i < 3; i++)
 {
  cout << (i+1) << "# element : " << result3[i] << endl;
 }

 return 0;
}

Cheers!
Bragaadeesh.

Given a sorted array find the pair that forms the sum in O(n) time

2010-05-03T10:43:00.000-07:00

This problem is quite frequently asked and we had already seen a solution in O(n) time but using a hash table here. However in this posting we shall see how to attack this problem when the input data is sorted.

For example for the input,

[-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24] and the sum bein 0, the matching pair is -12 and 12

The solution for this problem relies upon the knowledge of the input data : sorted. We will be having two pointers, one from the start of the Array called as min and the other from the end of the array called as max. We always calculate the sum with the values present in the minimum and maximum indexes. If the sum is greater than what is needed, we will be decrementing the max pointer and for the other case, we will be incrementing the min pointer. This happens till min exceeds max.

Following the solution in C++

//============================================================================
// Name        : array_find_sum.cpp
// Author      : Prabhu Jayaraman
// Version     : v1
// Copyright   : Free
// Description : Find elements in the array that equals to given sum
//============================================================================

#include <iostream>
using namespace std;

#define MAX 15

int main()
{
 int array[MAX] = {-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24};
 const int find_sum = 0;
 int max_index = MAX - 1;
 int min_index = 0;
 while(min_index < max_index)
 {
  if(array[min_index] + array[max_index-min_index] == find_sum)
  {
   cout << array[min_index] << " & " << array[max_index-min_index] << " Matched" << endl;
   return 0;
  }
  if(array[min_index]+array[max_index-min_index] < find_sum)
  {
   min_index++;
   max_index++;
  }
  if(array[min_index]+array[max_index-min_index] > find_sum)
  {
   max_index--;
  }
 }
 cout << "NO MATCH" << endl;
 return 0;
}
//-12 & 12 matched

Cheers!
Bragaadeesh

Compact a given array coding problem

2010-05-03T10:00:00.000-07:00

This problem may look very simple and indeed it is because the solution can be arrived at very easily. But to arrive at a clean and an efficient may take sometime. This question is asked to test the cleanliness and simplicity in providing solutions. Enough hype, here is the question.

Given an array of random numbers and -1 placed in-between, compact that array ie., all the -1s are to be removed and the final output should be the last valid index with the fresh array. For example.

You should not swap the values just the last valid index along with the array is enough to decipher the not -1 values.

The solution to this problem is seemingly simple and the same has been implemented in Java below.

public class CompactArray {
 public static void main(String[] args) {
  CompactArray c = new CompactArray();
  int[] sampleArray = {-1,5,3,-1,3,5,2,1,-1,6};
  System.out.print(" Input : ");printArray(sampleArray, sampleArray.length);
  int validIndex = c.compact(sampleArray);
  System.out.print("Output : ");printArray(sampleArray, validIndex);
 }
 
 private int compact(int[] arr){
  int k = 0;
  for(int i=0;i<arr.length;i++){
   if(arr[i]!=-1)
    arr[k++] = arr[i];
  }
  return k;
 }
 
 private static void printArray(int[] sampleArray, int validIndex) {
  for(int i=0;i<validIndex;i++){
   System.out.print(sampleArray[i]+" ");
  }
  System.out.println();
 }
}
/*
Input : -1 5 3 -1 3 5 2 1 -1 6 
Output : 5 3 3 5 2 1 6 
*/

Cheers!
Bragaadeesh.

Find three numbers in an array which forms a maximum product

2010-04-28T12:04:00.000-07:00

This problem again is asked as a coding question in one of the top companies. I have provided the solution for this in C++.

Question:
Given an array of integers (unsigned integers > 0), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].
int[] MaxProduct(int[] input, int size)

Solution:
The program expects both the solutions, one in O(n) time and the other one in O(nlogn). To achieve O(nlogn), sort the entire set by using quick sort or merge sort and take the top three values.
I have provided the code for the O(n) case. It does a single scan on the entire set of elements once and finds the largest three numbers with the logic as shown below.

//============================================================================
// Name        : three_largest_elems.cpp
// Author      : Prabhu Jayaraman (My honorable room mate, college mate, work colleague)
// Version     : v1
// Copyright   : open
// Description : To find three largest numbers in an array in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main()
{
 int a[10] = {1,2,33,4,15,6,7,28,9,10};
 int largest_1 = 0, largest_2 = 0, largest_3 = 0;

 for(int i=0;i<10;i++)
 {
  if(a[i] > largest_3 && a[i] < largest_2)
  {
   largest_3 = a[i];
  }
  else if(a[i] > largest_2 && a[i] < largest_1)
  {
   largest_3 = largest_2;
   largest_2 = a[i];
  }
  else if(a[i] > largest_1)
  {
   largest_3 = largest_2;
   largest_2 = largest_1;
   largest_1 = a[i];
  }
 }
 cout << "largest :" << largest_1 << endl;
 cout << "2nd largest :" << largest_2 << endl;
 cout << "3rd largest :" << largest_3 << endl;
 return 0;
}

Cheers!!
Bragaadeesh

Find the last person seated around in a circle program/puzzle

2010-04-28T10:48:00.000-07:00

This is a programming question asked at one of the class companies. Following is the question

“n” people are seated around in a circle. At each step, the “m”th person is eliminated from the circle. The next iteration continues from the person next to the eliminated person. In the end, there will be only one person remaining. Given “n” and “m”, write a program to find out the person who will be remaining at the end.
int FindWinner(int n, int m)

Me and my roommate both implemented a solution for the above problem one in Java and the other in C++ respectively. Please see the code and the ouput for the above problem below.

Implementation in Java

package brainteasers;

public class FindWinner {
 public static void main(String[] args) {
  FindWinner finder = new FindWinner();
  char winner = finder.findWinner(10,3);
  System.out.println("\nAnd the winner is "+(char)(winner-32)+"!!");
 }
 
 private char findWinner(int n, int m){
  char[] people = getPeople(n);
  boolean[] eliminated = new boolean[n];
  //always start from 1st person
  int remainingGuys = n;
  int current = 0;
  
  while(remainingGuys>1){
   int inkiPinki=0;
   
   while( eliminated[current] || ++inkiPinki != m )
       current = (current+1) % n;
   
   eliminated[current] = true;
   printStatus( eliminated, people );
   remainingGuys--;
   
   while(eliminated[(current+1)%n]){
    current++;
   }
   
   current = (current+1)%n;
  }
  
  System.out.println();
  return people[current];
 }

 private void printStatus(boolean[] eliminated, char[] people) {
  System.out.println();
  for(int i=0;i<eliminated.length;i++){
   char output;
   if(eliminated[i]){
    output = people[i];
   }else{
    output = (char)(people[i] - 32);
   }
   System.out.print(output+" ");
  }
 }

 private char[] getPeople(int n) {
  char[] people = new char[n];
  System.out.println("Participants are...");
  for(int i=0;i<n;i++){
   people[i] = (char)(i+97);
   System.out.print((char)(people[i]-32)+" ");
  }
  System.out.println();
  return people;
 }
}
/*
Participants are...
A B C D E F G H I J 

A B c D E F G H I J 
A B c D E f G H I J 
A B c D E f G H i J 
A b c D E f G H i J 
A b c D E f g H i J 
a b c D E f g H i J 
a b c D E f g h i J 
a b c D e f g h i J 
a b c D e f g h i j 

And the winner is D!!
*/

Implementation in C++

//============================================================================
// Name        : puzzle.cpp
// Author      : Prabhu Jayaraman
// Version     : 0.1
// Copyright   : Free
// Description : Find Last man stand
//============================================================================

#include <iostream>
using namespace std;

int FindWinner(int n, int m)
{
 int a[n];
 for(int i=0;i<n;i++)
 {
  a[i] = 1;
 }
 int e = 0;
 int c = 0;
 for(int i=0;;i++)
 {
  if(e == (n-1))
   break;
  if(a[i%n] == 1)
   c++;
  if(c == m)
  {
   a[i%n] = 0;
   e++;
   c = 0;
  }
 }
 for(int i=0;i<n;i++)
 {
  if(a[i] == 1)
   return i+1;
 }
 return -1;
}

int main()
{
 int x = FindWinner(20,19);
 cout << x << endl;
 return 0;
}

Cheers,
Bragaadeesh

TRIE data structure Part 6 : A Sample UI

2010-04-10T04:57:00.000-07:00

Lets have a look at a sample application in Swing. We load the TRIE data structure using a dictionary word list. And using the application we can perform a search. This application is a very much prototypical just to check the insert() and search() operations.

Input file : words.txt

Sample Application

There are two possible outcomes to our search criteria, one true and another false. The following is the dialog shown when a word "article" is entered.

And when a word something like "dasdsa" is entered the following dialog is shown.

The Java code for the Trie Loader,

package dsa.tries;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class TrieLoader {
 
 public static Trie trieDSA;

 public static void main(String[] args) {
  TrieLoader trieLoader = new TrieLoader();
  trieLoader.load();
  new TrieTestFrame();
 }
 
 public void load(){
  trieDSA = new Trie();
  BufferedReader br = null;
  try {
   br = new BufferedReader(new FileReader(new File("src/properties/words.txt")));
   String eachLine = null;
   while((eachLine=br.readLine())!=null){
    trieDSA.insert(eachLine);
   }
  } catch (Exception e) {
   e.printStackTrace();
  } finally{
   if(br!=null){
    try {
     br.close();
    } catch (IOException e) {
     e.printStackTrace();
    }
   }
  }
 }
}

The TrieTestFrame,

package dsa.tries;

import java.awt.Dimension;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JTextField;

public class TrieTestFrame extends JFrame {

 private static final long serialVersionUID = 1L;
 
 private JPanel basePanel = new JPanel();
 private JTextField textField = new JTextField(20);
 private JButton button = new JButton("Check");

 public TrieTestFrame(){
  designUI();
 }
 
 private void designUI(){
  this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  this.setTitle("TRIE Test");
  
  button.addActionListener(new ActionListener() {
   @Override
   public void actionPerformed(ActionEvent e) {
    if(TrieLoader.trieDSA.search(textField.getText())){
     JOptionPane.showMessageDialog(basePanel, "The word you entered exist!!");
    }else{
     JOptionPane.showMessageDialog(basePanel, "The word you entered does not exist!!","Error",JOptionPane.ERROR_MESSAGE);
    }
   }
  });
  
  basePanel.add(textField);
  basePanel.add(button);
  
  add(basePanel);
  
  this.setSize(400,100);
  
  Toolkit tk = Toolkit.getDefaultToolkit();
     Dimension screenSize = tk.getScreenSize();
     int screenHeight = screenSize.height;
     int screenWidth = screenSize.width;
     setLocation(screenWidth / 2 - 200, screenHeight / 2 - 50);
  
  this.setVisible(true);
 }
}

For the Node and Trie class please click here.

Cheers,
Bragaadeesh.

TRIE data structure Part 5 : Complexity Analysis

2010-04-10T04:17:00.000-07:00

Now that we've seen the basic operations on how to work with a TRIE, we shall now see the space and time complexities in order to get a real feel of how good a TRIE data structure is. Lets take the two important operations INSERT and SEARCH to measure the complexity.

INSERT operation first. Lets always take into account the worst case timing first and later convince ourselves of the practical timings. For every Node in the TRIE we had something called as Collection where the Collection can be either a Set or a List. If we choose Set, the order of whatever operation we perform over that will be in O(1) time, whereas if we use a LinkedList the number of comparisons at worst will be 26 (the number of alphabets). So for moving from one node to another, there will be at least 26 comparisons will be required at each step.

Having these in mind, for inserting a word of length 'k' we need (k * 26) comparisons. By Applying the Big O notation it becomes O(k) which will be again O(1). Thus insert operations are performed in constant time irrespective of the length of the input string (this might look lik an understatement, but if we make the length of the input string a worst case maximum, this sentence holds true).

Same holds true for the search operation as well. The search operation exactly performs the way the insert does and its order is O(k*26) = O(1).

TRIE data structure Part 4 : The SEARCH Algorithm

2010-04-10T03:00:00.000-07:00

In the previous section we saw how to insert string into TRIE. In this section, we shall see how to perform a search in the TRIE when a string or key is passed.

Consider the following TRIE as usual.

The search alogirthm involves the following steps

For each character in the string, see if there is a child node with that character as the content.
If that character does not exist, return false
If that character exist, repeat step 1.
Do the above steps until the end of string is reached.
When end of string is reached and if the marker of the current Node is set to true, return true, else return false.

Using the above algorithm, lets perform a search for the key "do".

See whether "d" is present in the current node's children. Yes its present, so set the current node to child node which is having character "d".
See whether "o" is present in the current node's children. Yes its present, so set the current node to child node which is having character "o".
Since "o" is the end of the word, see whether marker is set to true or false. Marker is set to false which means that "do" is not registered as a word in the TRIE. So, return false.

Using the same algorithm, lets perform a search for the key "ball"

See whether "b" is present in the current node's children. Yes its present, so set the current node to child node which is having character "b".
See whether "a" is present in the current node's children. Yes its present, so set the current node to child node which is having character "a".
See whether "l" is present in the current node's children. Yes its present, so set the current node to child node which is having character "l".
See whether "l" is present in the current node's children. Yes its present, so set the current node to child node which is having character "l".
Since "l" is the end of the word, see whether marker is set to true or false. Marker is set to true which means that "ball" is registered as a word in the TRIE. So, return true

public boolean search(String s){
  Node current = root;
  while(current != null){
   for(int i=0;i<s.length();i++){    
    if(current.subNode(s.charAt(i)) == null)
     return false;
    else
     current = current.subNode(s.charAt(i));
   }
   /* 
    * This means that a string exists, but make sure its
    * a word by checking its 'marker' flag
    */
   if (current.marker == true)
    return true;
   else
    return false;
  }
  return false; 
 }

The above java code does the search operation in the TRIE data structure. We shall look more into the running time and efficiency of TRIE in the next part.

Cheers,
Bragaadeesh.

TRIE data structure Part 3 : The INSERT Algorithm

2010-04-02T14:36:00.000-07:00

In this section we shall see how the insert() method on the TRIE data structure works. We shall take a specific case and analyze it with pictorial representation.

Before we begin, assume we already have an existing TRIE as shown below.

Lets see the steps on how to insert a word "bate". Any insertion would ideally be following the below algorithm.

If the input string length is zero, then set the marker for the root node to be true.
If the input string length is greater than zero, repeat steps 3 and 4 for each character
If the character is present in the child node of the current node, set the current node point to the child node.
If the character is not present in the child node, then insert a new node and set the current node to that newly inserted node.
Set the marker flag to true when the end character is reached.

Now if you go through the already written code for this, you can have a better understanding by comparing it with the above algorithm.

public void insert(String s){
  Node current = root; 
  if(s.length()==0) //For an empty character
   current.marker=true;
  for(int i=0;i<s.length();i++){
   Node child = current.subNode(s.charAt(i));
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(s.charAt(i)));
    current = current.subNode(s.charAt(i));
   }
   // Set marker to indicate end of the word
   if(i==s.length()-1)
    current.marker = true;
  } 
 }

Now lets see how the word "bate" is getting inserted. Since the word "bate" is having length greater than zero, we can start inspecting each word.

See whether "b" is present in the current node's children (which is root). Yes its present, so set the current node to the child node which is having the character "b".
See whether "a" is present in the current node's children. Yes its present, so set the current node to the child node which is having the character "a".
See whether "t" is present in the current node's children. Yes its present, so set the current node to the child node which is having the character "t".
See whether "e" is present in the current node's children. No, its not present, so create a new node with character set to "e". Since "e" is the end of the word, set the marker flag to true.

The above picture shows how the word "bate" is inserted into the existing TRIE data structure. This example clearly shows how the insertion in a TRIE happens.
We shall take a look on the Search operation in the next part.

Cheers,
Bragaadeesh.

TRIE data structure Part 2 : Node and TRIE class in Java

2010-04-02T13:37:00.000-07:00

In the first part of the TRIE ADT, we saw the basics of the TRIE data structure. In this section, lets get our hands dirty by directly looking at the TRIE data structure implemented in Java.

We already saw the Node structure of the TRIE ADT had a content (char), a marker (boolean) and collection of child nodes (Collection of Node). It now has one more method called as subNode(char). This method takes a character as argument would return the child node of that character type should that be present.

package dsa.tries;

import java.util.Collection;
import java.util.LinkedList;

/**
 * @author Braga
 */
public class Node {
 char content;
 boolean marker; 
 Collection<Node> child;
 
 public Node(char c){
  child = new LinkedList<Node>();
  marker = false;
  content = c;
 }
 
 public Node subNode(char c){
  if(child!=null){
   for(Node eachChild:child){
    if(eachChild.content == c){
     return eachChild;
    }
   }
  }
  return null;
 }
}

Now that we've defined our Node, lets go ahead and look at the code for the TRIE class. Fortunately, the TRIE datastructure is insanely simple to implement since it has two major methods insert() and search(). Lets look at the elementary implementation of both these methods.

package dsa.tries;

public class Trie{
 private Node root;

 public Trie(){
  root = new Node(' '); 
 }

 public void insert(String s){
  Node current = root; 
  if(s.length()==0) //For an empty character
   current.marker=true;
  for(int i=0;i<s.length();i++){
   Node child = current.subNode(s.charAt(i));
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(s.charAt(i)));
    current = current.subNode(s.charAt(i));
   }
   // Set marker to indicate end of the word
   if(i==s.length()-1)
    current.marker = true;
  } 
 }

 public boolean search(String s){
  Node current = root;
  while(current != null){
   for(int i=0;i<s.length();i++){    
    if(current.subNode(s.charAt(i)) == null)
     return false;
    else
     current = current.subNode(s.charAt(i));
   }
   /* 
    * This means that a string exists, but make sure its
    * a word by checking its 'marker' flag
    */
   if (current.marker == true)
    return true;
   else
    return false;
  }
  return false; 
 }
}

We shall look into the detailed working of the insert() and search() methods in separate posts, but I will tell you the gist of both those methods here. The insert() methods adds a new words to the already existing TRIE data structure. The search() method would return true or false based on whether the search string we specified exist or not.

Take a quick look at the java code above because we are going to use this in the posts that follow.

Cheers,
Bragaadeesh.

TRIE data structure Part 1: The TRIE ADT in Java

2010-04-02T06:09:00.000-07:00

«Previous
1
2
3
4
5
6
7
Next »

TRIE is an interesting data-structure used mainly for manipulating with Words in a language. This word is got from the word retrieve. TRIE (pronounced as 'try') has a wide variety of applications in

Spell checking
Data compression
Computational biology
Routing table for IP addresses
Storing/Querying XML documents etc.,

We shall see how to construct a basic TRIE data structure in Java.

The main abstract methods of the TRIE ADT are,

public void insert(String s);
public boolean search(String s);

In this data-structure, each node holds a character instead of a String. Each node has something called as 'marker' to mark the end of a word. And each node has a Collection of child nodes. This Collection can be either a Set or a List based on the speed vs space criterion.

The basic element - Node of a TRIE data structure looks like this,

char content;
boolean marker;
Collection<Node> child;

A TRIE tree would typically look like the following

The above TRIE is constructed by inserting the words ball, bat, doll, dork, do, dorm, send, sense. The markers are denoted on the Node using a red star(*). We shall look into more about the TRIE data structure in depth in the next post.

Reverse a Singly Linked List Recursively in Java

2010-03-06T02:33:00.000-08:00

We have already seen how to reverse a singly linked list with illustrative pictures. Now lets see how we can do it recursively. In the previous problem we did it iteratively, now we shall do it recursively.
To attack any problem in a recursive approach, we need to be very clear about the end/boundary conditions. For a linked list, reverse of a null list or reverse of list of size 1 is going to be the same.
Reverse of a linked list of size x will be the reverse of the 'next' element followed by first.
A picture means a thousand words. So, here is what happens internally.

Now for the comprehensive Java code (reference for SinglyLinkedList implementation can be found here)

package dsa.linkedlist;

public class ReverseLinkedListRecursively {
 
 public static void main(String args[]){
  ReverseLinkedListRecursively reverser = new ReverseLinkedListRecursively();
  SinglyLinkedList<Integer> originalList = reverser.getLabRatList(10);
  System.out.println("Original List : "+originalList.toString());
  originalList.start = reverser.reverse(originalList.start);
  System.out.println("Reversed List : "+originalList.toString());
 }
 
 public Node<Integer> reverse(Node<Integer> list)
 {
     if (list == null || list.next==null) return list;
     Node<Integer> nextItem = list.next;
     list.next = null;
     Node<Integer> reverseRest = reverse(nextItem);
     nextItem.next = list;
     return reverseRest;
 }

 
 private SinglyLinkedList<Integer> getLabRatList(int count){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=0;i<count;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
}
/*
 * SAMPLE OUTPUT
 * Original List : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
 * Reversed List : 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
 */

Cheers,
Bragaadeesh.

Find all possible palindromes in a String in Java C++

2010-02-22T03:47:00.000-08:00

This is not the regular palindrome finder. Given a string, we should be able to print all the possible palindromes. Let me quickly give a brief example.
For the following text : abccbab
All the possible palindromes are,
bab
abccba
bccb
cc
If you could see there are two possible outcomes in palindrome, one is odd and other is even. My initial solution was very worse. What I actually did was did a permutation/combination of all the possible texts and send it to a palindrome() method. It will run in the worst possible time.
However, there is even a simpler solution available. First do a parse for odd occurring palindromes followed by even palindromes.
For odd palindromes run through each character from the text. For each character, see if there the pre and post occuring characters are equal, if they are equal print them and do the same for the next levels. In the following example shown below, assume you are at 'y' and see the previous and next characters are equal. If they are see further more until the palindrome functionality ceases. Print all of them whilst this time.

Thats it. Do the same for all the characters. Since there is no meaning in doing this for first and last characters, we can very well omit them.
Similar logic holds for even sized palindromes. Here we wont be holding the center character. Rest of the logic remains the same. The java code follows,

package dsa.stringmanipulation;

/**
 * Program to print all palindromes in a string
 * @author Bragaadeesh
 */
public class FindAllPalindromes {
 public static void main(String[] args){
  FindAllPalindromes finder = new FindAllPalindromes();
  finder.printAllPalindromes("abcddcbaABCDEDCBA");
 }
 
 public void printAllPalindromes(String inputText){
  if(inputText==null){
   System.out.println("Input cannot be null!");
   return;
  }
  if(inputText.length()<=2){
   System.out.println("Minimum three characters should be present");
  }
  //ODD Occuring Palindromes
  int len = inputText.length();
  for(int i=1;i<len-1;i++){
   for(int j=i-1,k=i+1;j>=0&&k<len;j--,k++){
    if(inputText.charAt(j) == inputText.charAt(k)){
     System.out.println(inputText.subSequence(j,k+1));
    }else{
     break;
    }
   }
  }
  //EVEN Occuring Palindromes
  for(int i=1;i<len-1;i++){
   for(int j=i,k=i+1;j>=0&&k<len;j--,k++){
    if(inputText.charAt(j) == inputText.charAt(k)){
     System.out.println(inputText.subSequence(j,k+1));
    }else{
     break;
    }
   }
  }

 }
}
/*
Sample Output:
DED
CDEDC
BCDEDCB
ABCDEDCBA
dd
cddc
bcddcb
abcddcba
*/

The code in C++

#include <iostream>
using namespace std;

void printAllPalindromes(char*);

char* subSequence(char*,int,int);

int main() {
 char *s = "abcddcbaABCDEDCBA";
 printAllPalindromes(s);
 return 0;
}

char* subSequence(char* mainSequence, int from, int to){
 char * tgt = new char[to-from+1];
 for(int i=0;i<(to-from);i++){
  tgt[i] = mainSequence[i+from];
 }
 tgt[to-from] = '\0';
 return tgt;
}

void printAllPalindromes(char* inputText) {
 if(!inputText) {
  printf("Input cannot be null!");
  return;
 }
 if(strlen(inputText)<=2) {
  printf("Minimum three characters should be present\n");
 }
 //ODD Occuring Palindromes
 int len = strlen(inputText);
 for(int i=1;i<len-1;i++) {
  for(int j=i-1,k=i+1;j>=0&&k<len;j--,k++) {
   if(inputText[j] == inputText[k]) {
    char* subSeq = subSequence(inputText,j,k+1);
    cout<<subSeq<<endl;
    delete subSeq;
   } else {
    break;
   }
  }
 }
 //EVEN Occuring Palindromes
 for(int i=1;i<len-1;i++) {
  for(int j=i,k=i+1;j>=0&&k<len;j--,k++) {
   if(inputText[j] == inputText[k]) {
    char* subSeq = subSequence(inputText,j,k+1);
    cout<<subSeq<<endl;
    delete subSeq;
   } else {
    break;
   }
  }
 }

}
/*
 Sample Output:
 DED
 CDEDC
 BCDEDCB
 ABCDEDCBA
 dd
 cddc
 bcddcb
 abcddcba
 */

Cheers,
Bragaadeesh.

Stack using Linked Lists in Java

2010-02-21T02:03:00.000-08:00

Stack is a data structure that follows the simple FILO (First In, Last out) or LIFO (Last In, First Out) rule. Imagine a real world stack where you arrange Notebooks one over the other. The first notebook you insert will be at the bottom and that will come only at last. The implementation of stack can be done in many ways. We are going to see how to make use of a Singly Linked List to the use.
We can implement stack using a Linked List in the below shown ways. One is to have the END node on top and other is to have the START node at the top. If we recollect the singly linked list data structure, insertAtFirst() is an operation which can be done in O(1) time and insertAtLast() will take O(n) time (because we need to traverse till the last node). So, we can make use of the second method to use stack using linkedlists.

The three methods that stands out for a stack are pop(), push() and peek().
push() - push elements into a stack. We will use the insertAtFirst() method of LinkedList. Throws StackOverflowException when the stack is full.
pop() - remove and returns the top element from a stack. We will use the removeAtFirst() method of LinkedList. Throws StackEmptyException when the stack is empty.
peek() - return the top element from the stack without removing it. We will use the getFirst() method of LinkedList. Throws StackEmptyException when the stack is empty.

The java code for this looks very simpler. We will make use of the existing SinglyLinkedList class that we have used before.

package dsa.stack;

import dsa.linkedlist.SinglyLinkedList;

public class Stack<E> extends SinglyLinkedList<E>{
 
 public static final int MAX_STACK_SIZE = 100;
 
 public E pop() throws StackEmptyException{
  if(this.size()==0){
   throw new StackEmptyException();
  }
  return this.removeAtFirst();
 }
 
 public E peek() throws StackEmptyException{
  if(this.size()==0){
   throw new StackEmptyException();
  }
  return this.getFirst().data;
 }
 
 public void push(E data) throws StackOverflowException{
  if(this.size()>MAX_STACK_SIZE){
   throw new StackOverflowException();
  }
  this.insertAtFirst(data);
 }
 
 public static void main(String args[]){
  Stack<Integer> stack = new Stack<Integer>();
  try{
   System.out.println("Pushing 1, 2, 3, 4, 5");
   stack.push(1);
   stack.push(2);
   stack.push(3);
   stack.push(4);
   stack.push(5);
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Peek once : "+stack.peek());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
  }catch(StackEmptyException e){
   System.out.println(e.getMessage());
  }catch(StackOverflowException e){ 
   System.out.println(e.getMessage());
  }
 }
}
/*
SAMPLE OUTPUT:
Pushing 1, 2, 3, 4, 5
Pop once  : 5
Peek once : 4
Pop once  : 4
Pop once  : 3
Pop once  : 2
Pop once  : 1
Stack is empty!
*/

package dsa.stack;

public class StackEmptyException extends Exception{
 public StackEmptyException(){
  super("Stack is empty!");
 }
}

package dsa.stack;

public class StackOverflowException extends Exception{
 public StackOverflowException(){
  super("Stack Overflown");
 }
}

Cheers,
Bragaadeesh.