Columnar Transposition technique using TMS 320C 5402

Although this is totally not related to Java or data structures for which this blog is intended to, I thought I would post this here anyway. This is my project work that I did during college. This implements Columnar Transposition technique of encryption using TMS 320C 5402 which is Digital Signal Processor. Full project report for this can be found here (you may require to sign in using your Google Account). License would be free to distribute and use anywhere.

ABSTRACT

Aim:

            To implement the columnar transposition technique, a famous encryption technique on the input message using TMSC5402.

Columnar Transposition technique:

           

            Here the message or plain text is encrypted into a decrypted message using the random arrangement of the plain text. The arrangement of the resulting cipher text although seems random to the hacker (unauthorized intermediate person trying to read the message), it is in certain order and that order is been decided by a key. The key is simply numbers from 1 to ‘k’, where ‘k’ is the key size. The numbers are in some random order, mostly decided by the user or the sender. A simple example is shown below.

Plain text                     :           ABSTRACT

Let the key ‘k’ be 7, 3, 2, 8, 1, 5, 4, 6

1	2	3	4	5	6	7	8
A	B	S	T	R	A	C	T

Then the encrypted cipher text is (according to our key)

Cipher text                  :           CSBTARTA

            This is the simplest form. As we can see the decryption can be done using the secret key that we have used for the encryption.

7	3	2	8	1	5	4	6
C	S	B	T	A	R	T	A

Decrypted text                        :           ABSTRACT

            This might look simple since we have used a small message. But this message is almost impossible to hack when we use rows and columns and increase the key size. Lets see another example which could explain it better.

Plain text         :           PACK$MY$BOX$WITH$FIVE$DOZEN$LIQUOR$JUGS$

1	2	3	4	5	6	7	8
P	A	C	K	$	M	Y	$
B	O	X	$	W	I	T	H
$	F	I	V	E	$	D	O
Z	E	N	$	L	I	Q	U
O	R	$	J	U	G	S	$

Here we have used the ‘$’ symbol instead of spaces.

Cipher text      :           YTDQSCXIN$AOFER$HOU$PB$ZO$WELUK$V$JMI$IG

Now the encrypted message is impossible to hack. We can even apply again this method to the encrypted message to make it further random. In this case we can use the same key or other key. Same key can be used for simplicity.

Decryption:

Decryption is as simple as encryption. Just use the same key and rewrite the indexed values. Lets do the decryption for the Cipher text 1.

Cipher text      :           YTDQSCXIN$AOFER$HOU$PB$ZO$WELUK$V$JMI$IG

7	3	2	8	1	5	4	6
Y	C	A	$	P	$	K	M
T	X	O	H	B	W	$	I
D	I	F	O	$	E	V	$
Q	N	E	U	Z	L	$	I
S	$	R	$	O	U	J	G

Now the original table can be formed using the indexing technique as said earlier.

1	2	3	4	5	6	7	8
P	A	C	K	$	M	Y	$
B	O	X	$	W	I	T	H
$	F	I	V	E	$	D	O
Z	E	N	$	L	I	Q	U
O	R	$	J	U	G	S	$

Decrypted text            : PACK$MY$BOX$WITH$FIVE$DOZEN$LIQUOR$JUGS$

Advantages of Columnar Transposition technique :

            The columnar transposition technique of encryption is easy to understand but still complex to break by brutal force attack or cryptanalysis. This method get enhances as the key size is increased and by re applying the same technique. The hacker or the intermediate person cannot break this code unless otherwise he knows the method. Even he knows the method, it is still impossible to decrypt the encrypted cipher text without the knowledge of the key and the length of it and the no. of columnar transpositions that were made. As we’ve seen, we can enhance this technique by applying to the encrypted text over and over. In that case, we have to decrypt that many times we have encrypted and use the keys in the reverse order (FILO).

Columnar Transposition technique using TMSC5402:

           

            This technique can be implemented in the 5402 processor. We can enter the text message from a starting address say 3FFFh. The key is got from the user or is specified in some predefined location rather than getting in the run time. Then the transposition technique as given above is done using the instruction set available and is stored from say some starting address 43FFh. The data is transmitted serially(assumption) and is retrieved in the same manner.

            The decryption is done in the same scale. Here we assume that the received message is error free and is available from the location 43FFh. The decryption is similarly performed as encryption with slight difference and is put in some other location. We might be using a special symbol in order to mark the end of message. In this method we will be implementing depth1 columnar transposition for simplicity and ease of use.

Progress software - interview coding problem

This is one of the problems that have been asked in a company called Progress Software, Hyderabad. I have posted the question as well as the working Java code for the same.

Question

Sports Associations in India
-------

The Sports Associations in India (SAI) wants to choose 2 teams of 4 people each
to send to Asain games. There are 13 people who want to be members of
the teams. The SAI tries grouping them in various ways to see which
athletes perform well together. Each grouping gets one test run on the
test track and their time is recorded. Your task is to help the SAI
choose two disjoint teams of 4 such that the sum of their practice times
is minimal.

Input
-----

There will be several input instances. The first line of each instance
gives the total number of practice runs. This will be followed by n lines.
Each of those lines will contain 5 numbers: p1 p2 p3 p4 t
t is the time taken (in milliseconds) by the team consisting of p1, p2, p3 and p4.

The time taken will not be more than 2 minutes.

The end of the input will be indicated by a line with n=0.

Output
------

Output the best total time for the two teams that you choose.
If it is impossible to choose two disjoint teams from the test runs given, output -1.

Sample Input
------------

6
1 2 3 4 30000
10 11 12 13 15000
5 6 7 8 37800
1 5 10 12 20000
5 6 9 11 43000
1 9 12 13 11000
3
1 4 7 9 10000
3 5 7 11 17890
6 7 12 13 20000
0

Sample Output
-------------

45000
-1

Along this you will get a file consisting of an input and they ask you to send the output. I am sharing the solution to this problem.

package main;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;

public class Main {

 /**
  * @param args
  */
 public static void main(String[] args) {
  new Main().start();
 }

 private ArrayList<Event> events = null;

 public static final String DIR = "D:/Question2/";

 private String filename = DIR + "input.txt";

 public void start() {
  readInput();
  printInput();
  solve();
  writeToFile();
 }
 
 private void printInput() {
  Event eventRound = null;

  for (int i = 0; i < events.size(); i++) {
   eventRound = events.get(i);
   System.out.println("Round Count: " + eventRound.roundCount);
   System.out.println("Rounds : " + eventRound.toString());
  }
 }
 
 public void readInput() {
  FileRead read = new FileRead(filename);
  events = read.getEvents();
 }

 public void solve() {
  Event eventRound = null;
  for (int i = 0; i < events.size(); i++) {
   eventRound = events.get(i);
   eventRound.findMinTime();
   eventRound.printVal();
  }

 }
 
 private void writeToFile() {
  try {
   BufferedWriter out = new BufferedWriter(new FileWriter(DIR
     + "output.txt"));

   Event eventRound = null;
   for (int i = 0; i < events.size(); i++) {
    eventRound = events.get(i);
    out.write(eventRound.minTime+System.getProperty("line.separator"));
   }
   out.close();
  }catch(IOException e) {
   e.printStackTrace();
  }
 }
}

package main;

import java.util.StringTokenizer;

/**
 * Class to reprsent a round. A round consist of an array of players and time taken 
 * by them on that particular round.
 * @author Bragadeesh
 *
 */
public class Round {
 public int[] players;
 public int time;
 
 /**
  * Represents the player count for the event
  */
 public static final int PLAYER_COUNT = 4;
 
 public Round(String line){
  StringTokenizer tokens = new StringTokenizer(line);
  players = new int[PLAYER_COUNT];
  for(int i=0;i<PLAYER_COUNT;i++){
   players[i] = Integer.parseInt(tokens.nextToken());
  }
  time = Integer.parseInt(tokens.nextToken());
 }
 
 /**
  * Returns the formatized string for a particular Round
  */
 public String toString(){
  String op = "";
  for(int i=0;i<players.length;i++){
   op = op + players[i] + " ";
  }
  
  op = op + time;
  
  return "[" + op + "]";
 }
 
}

package main;


/**
 * Event is a class which is comprises an array of Rounds.
 * @author Bragadeesh
 *
 */
public class Event {
 
 public Round[] rounds;
 public int roundCount;
 private static final int MAX_VAL = 99999999;
 
 public int minTime = -1;
 
 /**
  * Variable used to show the the minimum round1 should there be any
  */
 public Round minRound1;
 
 
 /**
  * Variable used to show the the minimum round2 should there be any
  */
 public Round minRound2;
 
 
 /**
  * Returns the formatized string for a particular Event
  */
 public String toString(){
  
  String op = "";
  
  for(int i=0;i<rounds.length;i++){
   op+=rounds[i].toString();
  }
  
  return "{" + op + "}";
 }
 
 /**
  * Method to calculate the minimum time
  * @return
  */
 public int findMinTime(){
  int min = MAX_VAL;
  Round roundA = null;
  Round roundB = null;
  
  for(int i=0;i<roundCount;i++){
   for(int j=0;j<roundCount&&i!=j;j++){
    roundA = rounds[i];
    roundB = rounds[j];
    
    if(!disjoint(roundA, roundB)){
     if(roundA.time + roundB.time < min){
      minRound1 = roundA;
      minRound2 = roundB;
     }
     min = Math.min(roundA.time + roundB.time, min);
    }
   }
  }
  
  if(min != MAX_VAL){
   minTime = min; 
  }
  
  return minTime;
 }
 
 /**
  * Method to print the Round values and the minimum time for a 
  * given event. Prints -1 if there is no minimum time set.
  */
 public void printVal(){
  if(minRound1!=null){
   System.out.println(minRound1.toString());
   System.out.println(minRound2.toString());
   System.out.println(minTime);
  }else{
   System.out.println("-1");
  }
 }
 
 /**
  * Simple bubble sort that does the sorting of the events based on the round time
  * @return void
  */
 public void sortRounds() {
     for(int i=0;i<roundCount;i++){
      for(int j=i;j<roundCount;j++){
       if(rounds[i].time > rounds[j].time){
        Round temp = rounds[i];
        rounds[i] = rounds[j];
        rounds[j] = temp;
       }
      }
     }
 }

 
 /**
  * Given two arbitrary rounds A and B, returns whether they are disjoint or not
  * @param roundA
  * @param roundB
  * @return boolean value whether given set is disjoint or not
  */
 public boolean disjoint(Round roundA, Round roundB){
  for(int i=0;i<Round.PLAYER_COUNT;i++){
   for(int j=0;j<Round.PLAYER_COUNT;j++){
    if(roundA.players[i] == roundB.players[j]){
     return true;
    }
   }
  }
  return false;
 }
 
}

package main;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class FileRead {
 
 private String filename = null;
 private ArrayList<Event> events;
 
 public FileRead(String filename){
  this.filename = filename;
  events = new ArrayList<Event>();
  load();
 }
 
 private void load(){
  
  FileInputStream fstream = null;
  DataInputStream in = null;
  BufferedReader br = null;
  Event event = null;
  
  
  try {
   fstream = new FileInputStream(filename);
   in = new DataInputStream(fstream);
   br = new BufferedReader(new InputStreamReader(in));
   
   for(;;){
    event = new Event();
    event.roundCount = Integer.parseInt(br.readLine());
    if(event.roundCount == 0){
     break;
    }
    event.rounds = new Round[event.roundCount];
    for(int i=0;i<event.roundCount;i++){
     event.rounds[i] = new Round(br.readLine());
    }
    event.sortRounds();
    events.add(event);
   }
   
   
  } catch (Exception e) {
   System.err.println("Error: " + e.getMessage());
  } finally{
   try {
    in.close();
   } catch (IOException e) {
    e.printStackTrace();
   }
  }
 }
 
 public ArrayList<Event> getEvents(){
  return events;
 }
}

Input file : Input.txt
Output file : Output.txt
Cheers,
Bragaadeesh.

Find common sequence that is out of order between two given strings in Java

Hi,
Recently i faced this question from Amazon. Given two strings, find the longest common sequence that is out of order. Initially it was royally confusing to me what the question meant, but I was able to come up with a solution. Please see the following program implemented in Java. The sample inputs and outputs have been provided at the end.

package dsa.stringmanipulation;

import java.util.LinkedHashMap;
import java.util.Map;

public class Sequence {
 public static void main(String[] args) {
  Sequence seq = new Sequence();
  String str1 = "a111b3455yy";
  String str2 = "byy115789";
  System.out.println("Input1: "+str1);
  System.out.println("Input2: "+str2);
  String solution = seq.findCommonSequnce(str1, str2);
  System.out.println("Output: "+solution);
 }
 
 public String findCommonSequnce(String str1, String str2){
  if(str1==null || str2==null){
   return "";
  }
  if(str1.length() == 0 || str2.length() == 0){
   return "";
  }
  //parse first String store the frequency of characters
  //in a hashmap
  Map<Character,Integer> firstStringMap = frequencyMap(str1);
  
  StringBuilder output = new StringBuilder();
  
  for(int i=0;i<str2.length();i++){
   int count = 0;
   if(firstStringMap.containsKey(str2.charAt(i)) && (count=firstStringMap.get(str2.charAt(i)))>0){
    output.append(str2.charAt(i));
    firstStringMap.put(str2.charAt(i), --count);
   }
  }
  
  return output.toString();
 }

 /**
  * Returns a map with character as the key and its occurence as the value
  * @param str
  * @return
  */
 private Map<Character,Integer> frequencyMap(String str) {
  Map<Character, Integer> freqMap = new LinkedHashMap<Character,Integer>();
  for(int i=0;i<str.length();i++){
   Integer count = freqMap.get(str.charAt(i));
   if(count==null){//means the frequency is yet to stored
    freqMap.put(str.charAt(i), 1);
   }else{
    freqMap.put(str.charAt(i), ++count);
   }
  }
  return freqMap;
 }
}

//SAMPLE OUTPUTS
//Input1: a111b3455yy
//Input2: byy115789
//Output: byy115
//
//Input1: lsjfa9fjdsajf
//Input2: dsklajfdkl99
//Output: dslajf9

Cheers,
Bragaadeesh.

Difference between two days implemented in C

Although Java is my forte, I started my early days by coding with C. The below program is to get the difference in days between two dates. The program is simple and has well defined comments to explain for itself. Thought I would post it here.

#include<stdio.h>
#include<conio.h>
#include<dos.h>
int datecmp(struct date,struct date);
int leap(int);
void main()
{
 struct date a,b;
 int leep;
 clrscr();
 b.da_year=2000;
 b.da_mon=7;
 b.da_day=1;
 getdate(&a);
 printf("%u\t%u\t%u\t",b.da_day,b.da_mon,b.da_year);
 printf("\n%u\t%u\t%u\t",a.da_day,a.da_mon,a.da_year);
 datecmp(a,b);
 /*if((leep=leap(b.da_year))==1)
  printf("\nThe year is leep year");
 else
  printf("\nThe year is an ordinary year");*/
 getch();
}


int datecmp(struct date a,struct date b)
{
 struct date c;
 char days[12]={31,28,31,30,31,30,31,31,30,31,30,31};
 int y=365;
 int i,j;
 int td=0;
 c.da_year=a.da_year-b.da_year;
 c.da_mon=a.da_mon-b.da_mon;
 if(c.da_year==0)//SAME YEAR BUT DIFFERENT MONTH OR SAME MONTH
 {
  if(c.da_mon==0)
   td=a.da_day-b.da_day;
  else
  {
   for(i=0,j=b.da_mon;i<(c.da_mon-1);i++,j++)
    td+=days[j];
   td+=days[b.da_mon-1]-b.da_day;
   td+=a.da_day-1;
  }
 }
 else if(c.da_year>1 && c.da_mon>1)//YEAR DIFF B/W TWO INPUTS IS >THAN 1 YEAR
 {
  if(b.da_mon<3 && leap(b.da_year)==1)
   td=1;
  else
   td=0;
  for(i=0,j=b.da_year+1;i<(c.da_year);i++,j++)
    td=td+365+leap(j);
  if(c.da_mon==0)
   td+=a.da_day-b.da_day;
  else
  {
   for(i=0,j=b.da_mon;i<(c.da_mon-1);i++,j++)
    td+=days[j];
   td+=days[b.da_mon-1]-b.da_day;
   td+=a.da_day-1+leap(a.da_year);
  }
 }
 else if(c.da_year==1)//YEAR DIFF B/W TWO INPUTS IS==1 YEAR
 {
  if(c.da_mon>0)
  {
   if(b.da_mon>1 && leap(b.da_year)==1)
    td=1;
   else
    td=0;
   for(i=0,j=b.da_year+1;i<(c.da_year);i++,j++)
     td=td+365+leap(j);
   if(c.da_mon==0)
    td+=a.da_day-b.da_day;
   else
   {
    for(i=0,j=b.da_mon;i<(c.da_mon-1);i++,j++)
     td+=days[j];
    td+=days[b.da_mon-1]-b.da_day;
    td+=a.da_day-1+leap(a.da_year);
   }
  }
  else if(c.da_mon==0 && c.da_day>0)
  {
    if(b.da_mon>1)
    td=0;
   else
    td=1;
   for(i=0,j=b.da_year+1;i<(c.da_year);i++,j++)
     td=td+365+leap(j);
    td+=a.da_day-b.da_day;
  }
 }
 else if(c.da_year==1)
 {

 }

 printf("\n The days are %d",td);
 getch();
}
int leap(int year)//LEAP YEAR FUNCTION
{
 if(year%4==0)
 {
  if(year%100==0)
  {
   if(year%400==0)
    return(1);
   else
    return(0);
  }
 else
  return(1);
 }
 else
  return(0);
}

Cheers,
Bragaadeesh.

Searching in a Binary Search Tree in Java

Now that we have a working version of a binary search tree fully implemented in Java, lets go a step ahead and start analyzing that piece of code.

Binary search tree is a data structure which has the following public methods exposed

public void add(int data);
public boolean search(int searchData);
public void printOrdered();

Ofcourse, the above three methods are not the only methods present in a binary search tree, but once these methods are understood and analyzed, understanding the rest of the binary tree should not be a big problem.

Adding elements to a binary tree : In the example program that I've written, I am using only integers as the node data to hold values and ofcourse you need something that is comparable to make binary search trees realistic (refer my previous post on comparable objects). While adding data to a binary search tree, we need to follow the simple rule - lesser should go left and greater then or equal should go to the right of the parent node. By taking a snap at the code, the add(int data) method internally calls a private method that does the job in recursion.

Searching elements in a tree : Searching elements in any data structure is a essential part that reflects the space and time complexity and Binary search tree is no exception. To search from a balanced binary search tree, it would take only O(logn) whereas the same is not so in case of an Array. The simple reason being, for arrays, we need to traverse the entire array sequentially in which the worst case would produce O(n). Consider the below example where in we need to search the element 5.

Whereas in a binary search, the depth count would simply provide the desired result.
Consider a situation in a balanced binary search tree of 7 elements, when the value given to search is at its leaf (which would be the worst case here). The example shown below is a balanced and a perfect binary search tree (which we would look into future posts). Assume the element we need to find is 5. First inspect the root (4), our value is greater, so go the right node, then inspect it (6), our value is lesser so go the left node, bingo! we found our result. This took only 2 comparisons of a tree of depth 2 whereas it look 7 comparisons in an array of length 7! Through this we can come to conclusion that binary trees perform search in O(logn) time.

The method printOrdered() is something we have to allocate time and look into a different post. As for now, lets convince ourselves that binary tree's search is powerful enough to perform the search operation in O(logn) time.
Rest, later. Cheers,
Bragaadeesh.

Binary Search Trees in Java

Now that we've seen how a binary tree is structured, lets take a look at one of the most common and powerful implementations - Binary Search Trees.
Binary Search trees are binary trees with some defined rules. Binary search trees can be formed only to nodes which are comparable. By Comparable, i mean which objects in real life that can be compared with each giving outputs as equal, greater or lesser. Numerals are the simplest example of comparables.
The rule of binary search tree follows that all the nodes that are lesser than the root will be on the left and the nodes that are greater than will be on the right. Equal valued nodes can come on either side.
Following is a simple illustration of a binary search tree formed using numerals

The following is a comprehensive Java code on how to construct and then manipulate from a binary tree.

The abstract Data Structure for Tree and the class Node.

package dsa.tree;

public interface Tree {
 public void add(int currentData);
 public Node search(int data);
}

package dsa.tree;

public  class Node {
 Node left;
 Node right;
 Node parent;
 int data;
}

package dsa.tree;

public class BinarySearchTree implements Tree{
 
 private Node root;
 
 public void add(int currentData){
  if(root == null){
   root = new Node();
   root.data = currentData;
   return;
  }
  add(currentData, root);
 }
 
 private void add(int currentData, Node position){
  if(currentData<position.data){
   if(position.left==null){
    position.left = new Node();
    position.left.data = currentData;
    position.left.parent = position;
    return;
   }
   add(currentData, position.left);
  }else{
   if(position.right==null){
    position.right = new Node();
    position.right.data = currentData;
    position.right.parent = position;
    return;
   }
   add(currentData, position.right);
  }
 }
 
 public Node search(int searchData){
  if(root == null){
   return null;
  }
  return search(searchData, root);
 }
 
 /*
  * O(log n) on average case
  */
 private Node search(int searchData, Node node){
  if(node.data == searchData){
   return node;
  }
  if(searchData < node.data){
   return search(searchData, node.left);
  }else{
   return search(searchData, node.right);
  }
 }
 
 public void printOrdered(){
  if(root == null){
   return;
  }
  printOrdered(root);
 }
 
 //DO A IN ORDER TRAVERSAL
 //VISIT LEFT
 //VISIT ROOT
 //VISIT RIGHT
 public void printOrdered(Node node){
  if(node.left != null){
   printOrdered(node.left);
  }
  System.out.println(node.data);
  if(node.right!=null){
   printOrdered(node.right);
  }
 }
 
 public void printValues(){
  print(root);
 }
 
 private void print(Node node){
  if(node == null){
   return;
  }else{
   print(node.left);
   print(node.right);
  }
 }
 
 public static void main(String args[]){
  BinarySearchTree bTree = new BinarySearchTree();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println(t);
   bTree.add(t);
  }
  bTree.printValues();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println("For i="+t+": "+bTree.search(t));
  }
  System.out.println();
  bTree.printOrdered();
 }
}

We shall discuss about the various features used in this program in the following post.

Bragaadeesh.

Binary Trees in Java

One of the coolest data structures that is both highly efficient and very simple is a Binary Tree. Binary Tree is a data structure where a there will be a node having at most two child nodes.

Lets briefly define the concepts of a binary tree and lets take look at a working Java program in the future posts. Binary Tree has three pointers, one pointing to the left child, one pointing to the right child and one pointer to the parent. These are the terms we use with respect to a binary tree.

• Root - The uppermost node in a binary tree. The parent node is always null for a root or we can say Root does not have a parent.
• Child - A child is a sub-node to a parent node. A child can be either a left child or a right child
• Leaf - A node which does not have any right or left nodes to it.
• Node - constitutes to an element of a tree which has three pointers one to parent, one to right child and one to left child. And it has a place holder to store the data as well.
  

There are more jargons available with regard to a binary tree but as of now these terms are sufficient.

One of the most common misunderstanding that many have is to tell the definition of a "Binary search tree" when asked for a "Binary tree". They are not the same!!. Although we can say binary search tree is a form of binary tree with some condition. All Binary search trees are Binary trees and not vice versa!!!!

If asked to write a binary tree structure in Java, the following code would be more than sufficient. Note: This is just a raw structure.

public class BinaryTree{
 
 class Node {
  Node left;
  Node right;
  Node parent;
  int data;
 }
 
 private Node root;

}

More trees to come in the following posts.
Cheers,
Bragaadeesh.