Closures with let and var lexical context

See the Pen Closure behavior with let and var by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Intersecting clickstream data

See the Pen Intersecting Clickstream data by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Length of the longest substring

See the Pen Length of the longest substring by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Jaccard Similarity

# similarity: count(intersection) / count(union)
# arr1 = [3,7,9,12,4...]
# arr2 = [5,9,10,1,2...]

#Case 1
# not sorted
# no duplicates

function computeSimilarity(arr1, arr2){
    
    var map = {};
    var i;
    for(i=0; i < arr1.length; i++){
      map[arr1[i]] = true;
    }
    
    var intersection = 0;
    for(i=0; i < arr2.length; i++){
      var val = arr2[i];
      if(map[val] != null){
          intersection++;
      }
    }
    
    var union = arr1.length + arr2.length - intersection;
    return (intersection/union);
}



# Case 2: sorted arr inputs
# O(n)
# arr1 = [3,7,9,12...]
# arr2 = [5,9,10,...]

function computeSortedSim(arr1, arr2){
    var intersection = 0;
    var i, j;
    for(i =0, j=0; i < arr1.length && j < arr2.length; ){
        if(arr1[i] < arr2[j]) i++;
        else if(arr1[i] > arr2[j]) j++;
        else { i++; j++; intersection++; }
    }
    
    var union = arr1.length + arr2.length - intersection;
    return (intersection/union);
}

Access an iframe and its contents using selectors

document.getElementById('frame_id').contentWindow.$('#' + idOfElementInFrame);

Subtree Sum

Problem

Find subtrees with nodes that add to a given sum

Example Input:

Sum = 5
Tree is:

            1
    /   \
           2     3
         / \   / \
      2  -1 0   8
      /\   /\           /\   /\
   0  3 -5 4     6 -9 -6 1

Output: 

2 

0 3 

null null null null 

--------------------

2 

2 -1 

0 3 -5 4 

null null null null null null null null 

--------------------

Solution

package Tree;

import java.util.ArrayList;

public class SubtreeSum {

	private ArrayList sumPaths;

	private Integer traverse(Tree t, int sum){
		if(t == null) return 0;

		Integer leftSum = traverse(t.left, sum);
		Integer rightSum = traverse(t.right, sum);
//		if(leftSum == null || rightSum == null) return null;
		Integer curSum = leftSum + rightSum + t.val;

//		if(curSum > sum) return null;
		if(curSum == sum) { sumPaths.add(t);}
		return curSum;
	}
	
	public void printSubTreeWithSum(Tree t, int sum){
		sumPaths = new ArrayList();
		traverse(t, sum);
		
		for(int i = 0; i < sumPaths.size(); i++){
			TreeOperations.printTree(sumPaths.get(i));
			System.out.println("--------------------");
		}
	}
	
	public static void main(String[] args) {
		SubtreeSum ob = new SubtreeSum();
		Tree t = TreeTestData.getSampleTree3();
		ob.printSubTreeWithSum(t, 5);
	}
}

Tree - Sum Paths

Problem

Given a binary tree, not necessarily a BST return all paths with sum x:
Example for sum =5 and tree given below:

         1
        /   \
           2     3
         / \          / \
      2  -1      0   8
      /\   /\       /\     /\
   0  3 -5 4   6 -9 -6 1

Output is: [[1,2,2],[2,3],[1,2,2,0],[2,-1,4],[3,8,-6]]

Solution

public class Tree{
	int val;
	Tree left;
	Tree right;
} 

package Tree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class TreeSumPath {

	Set< ArrayList<Integer> > sumPaths2;
	
	void doTraversal(Tree t, int remain, int oSum, ArrayList temp){
		temp.add(t.val);
		if(remain == 0) sumPaths2.add(temp);
		traverse2(t.left, remain, temp, oSum);
		traverse2(t.right, remain, temp, oSum);
	}
	
	void traverse2(Tree t, int sum, ArrayList curNodes, int oSum){
		if(t==null) return;
		ArrayList temp = new ArrayList(curNodes);
		doTraversal(t, sum - t.val, oSum, temp);
		
		temp = new ArrayList();
		doTraversal(t, oSum-t.val, oSum, temp);
	}

	Set< ArrayList<Integer> > getSumPaths(Tree t, int sum){
		sumPaths2 = new HashSet< ArrayList>();
		traverse2(t, sum, new ArrayList(), sum);
		System.out.println(sumPaths2);
		return sumPaths2;
	}
	
	public static void main(String[] args) {
		Tree t = TreeTestData.getSampleTree3();
		TreeSumPath ob = new TreeSumPath();
		ob.getSumPaths(t, 5);
	}
}

Autosolve Substitution Cipher

Problem 

Extend the program developed in Problem 11 so that it initially tries to decrypt the message. Here is one sensible way to proceed. Use the computed letter frequencies and the known frequencies of English for an initial guess at the key. Then from the resulting putative decryption, count the number of dictionary words that appear and use this as a “score.” Next, for each letter in the key, try swapping it with a letter that is adjacent (with respect to frequency counts) and recompute the score. If the score improves, update the key; if not, don’t update the key. Iterate this process until the score does not improve for an entire pass through the alphabet. At this point you will pass your putative decryption to the analyst. In order to aid the analyst in the manual phase, your program should maintain all of the functionality of the program for Problem 11.

Problem 11 refers to Substitution Ciphers post (the previous post - http://ddsgibberish.blogspot.com/2015/09/substitution-ciphers.html).

Dictionary class used below uses code from http://ddsgibberish.blogspot.com/2015/09/dictionary-subwords.html

Alpha Shift class in code below uses code from http://ddsgibberish.blogspot.com/2015/09/shift-cipher.html

Note: This is from Mark Stamp's Information Security: Principles and Practice book, chapter 2. Solution below was submitted as homework for CS265 Cryptography and Information Security class at San Jose State University.

Input text to decrypt

MXDXBVTZWVMXNSPBQXLIMSCCSGXSCJXBOVQXCJZMOJZCVCTVWJCZAAXZBCSSCJXBQCJZCOJZCNSPOXBXSBTVWJCJZDXGXXMOZQMSCSCJXBOVQXCJZMOJZCNSPJZHGXXMOSPLHJZDXZAAXZBXHCSCJXTCSGXSCJXBOVQX

Steps used to decrypt

Pseudocode of the commands called in the program for problem 13 options to solve:
1. Use the monogram frequencies to map x to e, c to t
2. Use trigram frequencies to map j to h, to form a max trigram word the
3. Run the auto solve algorithm. Notice that it decodes the word them, by replacing t with m. But we are not sure of this. So we’ll put it on hold.
4. Use 4 gram frequencies to map s to o to form the top 4 gram word as ‘othe’
5. Run auto solve again. We see words ‘them’ and ‘to oth’ revealing
6. Use 5 gram frequencies to map b to r to form a top frequency word ‘other’
7. Run autosolve again. We see words such as NEVER, OTHER, OTTO, THEM, TOKE, TOOT, TOOTH, WERE appearing.
8. Use monogram frequencies to map z to a
9. Run the auto solve function to see possible words. We see more words revealing: NEVE, NEVER, OTHER, OTTO, TALL, THAN, THAT, THEM, TOKE, TOOT, TOOTH, VEAL, WERE, WHAT
10. Since NEVER has been appearing for quite some time in the autosolve for the partially decoded ‘MeDer’, we try n for m and v for d.
11. For the part ’otherQthat’, we see that the Q can only be s. So we map that using option 3.
12. We see that the A in aAAear can be guessed as p. So we map that too using option 3.
13. We see “haveGeen” and guess G to be b and map using option 3.
14. We guess “appeareH” to be ’appeared’ & map H to d
15. We guess “theT” to be ‘them’ since we already got it using the auto solve algorithm and also based on the words around it and map T to m.
16. We guess “otherOVse” to be ‘otherwise’. So map O to w, V to i.
17. We guess “woPLd” to be ‘would’. So map P to u, L to l.
18. We guess “miWht” to ‘might’, ‘ourselI’ to “ourself”, ‘Nou’ to be ‘You’, ‘imaWine’ to ‘imagine’ and finally Nourself’ to be ‘yourself ’ and map their corresponding characters again.
19. This unravels the plaintext. We add spaces and verify the quote in alice and wonderland ebook.

Autosolve options provided in Solution

**** Possible Operations: ****

1. Print monogram frequencies

2. Try auto solve

3. Map letters & replace

4. Guess a key

5. See current mappings

6. Reset to beginning

7. Print possible shift cipher plaintexts

8. Exit

9. Print trigram frequencies

10. Print bigram frequencies

11. Print quad letter frequencies

12. Print 5 gram frequencies

13. Print n gram frequencies

14. Show what's been guessed so far

*********************************

References

Trigram frequencies: http://practicalcryptography.com/cryptanalysis/letter-frequencies-various-languages/english-letter-frequencies/

Letter Frequencies: http://www.math.cornell.edu/~mec/2003-2004/cryptography/subs/digraphs.html

Words to build the Dictionary in the code - http://www-personal.umich.edu/~jlawler/wordlist

Alice in wonderland story to verify decrypted text: https://www.gutenberg.org/files/11/11-h/11-h.htm

An awesome free tool that breaks nearly every simple cipher - http://quipqiup.com/ 

Solution

package Cypto;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class SubstitutionCipher2 {

 BufferedReader reader;
 String ciphertext;
 String plaintext;
 String guessed;
 String cipherLetterFreq = "";
 Map currentMapping;


 static String letterFreqOrder ="";

 public SubstitutionCipher2(){
  storeOneLetterCounts();
  //  reset();
 }

 void printEnglishLetterFrequency()
 {
  System.out.println("English letter frequency counts"); 
  System.out.println("E - 1202 | T - 910 | A - 812 | O - 768 | I - 731");
  System.out.println("N - 695 | S - 628 | R - 602 | H - 592 | D - 432");
  System.out.println("L - 398 | U - 288 | C - 271 | M - 261 | F - 230 | Y - 211 | W - 209 | G - 203");
  System.out.println("B - 182 | P - 149 | V - 111 | K - 69 | X - 17 | Q - 11 | J - 10 | Z - 7"); 
 }

 void storeOneLetterCounts() {
  StringBuffer temp = new StringBuffer();
  temp.append("E"); temp.append("T"); temp.append("A"); temp.append("O"); temp.append("I");
  temp.append("N"); temp.append("S"); temp.append("R"); temp.append("H"); temp.append("D");
  temp.append("L"); temp.append("U"); temp.append("C"); temp.append("M"); temp.append("F");
  temp.append("Y"); temp.append("W"); temp.append("G"); temp.append("");
  temp.append("B"); temp.append("P"); temp.append("V"); temp.append("K"); temp.append("X");
  temp.append("Q"); temp.append("J"); temp.append("Z");
  letterFreqOrder = temp.toString();
  //  System.out.println(letterFreqOrder.length());
 }

 private void reset(){
  currentMapping = new LinkedHashMap();
  for(int i = 'A'; i <= 'Z'; i++){
   currentMapping.put((char)i, '-');
  }
  plaintext = ciphertext;
  StringBuffer temp = new StringBuffer();
  for(int i=0; i< ciphertext.length(); i++){
   temp.append("-");
  }
  guessed = temp.toString();
 }

 private void createInputBuffer(){
  reader = new BufferedReader(new InputStreamReader(System.in));
 }

 private void closeInputBufer() throws Exception{
  if(reader!=null)
   try {
    reader.close();
   } catch (IOException e) {

    e.printStackTrace();
    throw new Exception("Error while trying to close the input stream");
   }
 }

 private void getCipherText() throws Exception {
  System.out.println("***** Substitution Cipher Cracker *****");
  System.out.print("Enter ciphertext: ");

  reader = new BufferedReader(new InputStreamReader(System.in));
  try {
   ciphertext = reader.readLine();
  } catch (IOException e) {
   e.printStackTrace();
   throw new Exception("Error while reading the ciphertext");
  }

//    ciphertext = "MXDXBVTZWVMXNSPBQXLIMSCCSGXSCJXBOVQXCJZMOJZCVC"
//      + "TVWJCZAAXZBCSSCJXBQCJZCOJZCNSPOXBXSBTVWJC"
//      + "JZDXGXXMOZQMSCSCJXBOVQXCJZMOJZCNSPJZHGXXMOSPLH"
//      + "JZDXZAAXZBXHCSCJXTCSGXSCJXBOVQX";

  //  ciphertext = "LTKHNMEVKGKECVHVRTMHECCVKNBKNCVHWXTFMCXHAGFRKNKCENXCEXQHCVKNBYXPFHRTNKNEZVXXFOPCKLYXPVRIHNCFHRTNHMCVHQHRNKNBXLLTKHNMEVKGYXPTHRFFYVRIHNCFHRTNHMRNYCVKNBQPVRQQRMRFK";
  ciphertext = ciphertext.toUpperCase();
  reset();
  System.out.println("Ciphertext (in upper case) entered is '" + ciphertext + "'");
 }

 private void getCurrentOneLetterCounts(){
  printEnglishLetterFrequency();
  getnLetterCounts(1);
 }

 private boolean isCapLetter(char c){
  return (c >= 'A' && c <= 'Z');
 }


 public void problem13() {
  try {
   createInputBuffer();
   getCipherText();
   computeLetterFreq();
   provideOptions();
  } catch (Exception e) {
   e.printStackTrace();
  } 
  finally {
   try {
    closeInputBufer();
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
 }

 private void provideOptions() {
  int input = 0;
  do {
   System.out.println("**** Possible Operations: ****");
   System.out.println("1. Print monogram frequencies");
   System.out.println("2. Try auto solve");
   System.out.println("3. Map letters & replace");
   System.out.println("4. Guess a key");
   System.out.println("5. See current mappings");
   System.out.println("6. Reset to beginning");
   System.out.println("7. Print possible shift cipher plaintexts");
   System.out.println("8. Exit");
   System.out.println("9. Print trigram frequencies");
   System.out.println("10. Print bigram frequencies");
   System.out.println("11. Print quad letter frequencies");
   System.out.println("12. Print 5 gram frequencies");
   System.out.println("13. Print n gram frequencies ");
   System.out.println("14. Show what's been guessed so far");
   System.out.println("*********************************");
   System.out.println("Choose an operation by providing the number for it:");
   try {
    String temp = reader.readLine();
    if(temp.length() == 0) continue;
    input = Integer.valueOf(temp);
    if(input!= 8) processInput(input);
    else break;
   } catch (Exception e) {
    e.printStackTrace();
    System.out.println("Invalid input. Print enter to continue");
   }
  } while(input != 8);
  System.out.println("Exiting Program");
 }

 private void processInput(int input) throws Exception {

  switch(input) {
  case 1:  getCurrentOneLetterCounts(); break;
  case 2: autoSolve(); break;
  case 3: mapLetter(); break;
  case 4: guessAKey(); break;
  case 6: reset(); break;
  case 5: System.out.println(currentMapping); break;
  case 7: AlphaShift as = new AlphaShift();
  as.possibleDecryptions(plaintext.toLowerCase());
  break;
  case 9: getCurrentThreeLetterCounts(); break;
  case 10: getCurrentTwoLetterCounts(); break;
  case 11: getQaudFreq(); break;
  case 12: getFiveGramFreq(); break;
  case 13: getnGramFreq(); break;
  case 14: showGuessed(); break;

  default: System.out.println("Invalid Input. Try again!"); break;
  }

 }

 private void showGuessed() {

  System.out.println("What's been guessed so far: " + guessed);
  System.out.println("Partially decoded text: " + plaintext);
  System.out.println(currentMapping);
 }

 private void getnGramFreq() {

  System.out.println("Enter n: ");
  try {
   String temp = reader.readLine();
   int n = Integer.valueOf(temp);
   getnLetterCounts(n);
  } catch (IOException e) {
   e.printStackTrace();
   System.out.println("Invalid input!!!! ");
  }

 }

 private void getFiveGramFreq() {

  System.out.println("English Five gram frequencies:");
  System.out.println("OFTHE :  0.18        ANDTH :  0.07        CTION :  0.05"
    +"ATION :  0.17        NDTHE :  0.07        WHICH :  0.05"
    +"INTHE :  0.16        ONTHE :  0.07        THESE :  0.05"
    +"THERE :  0.09        EDTHE :  0.06        AFTER :  0.05"
    +"INGTH :  0.09        THEIR :  0.06        EOFTH :  0.05"
    +"TOTHE :  0.08        TIONA :  0.06        ABOUT :  0.04"
    +"NGTHE :  0.08        ORTHE :  0.06        ERTHE :  0.04"
    +"OTHER :  0.07        FORTH :  0.06        IONAL :  0.04"
    +"ATTHE :  0.07        INGTO :  0.06        FIRST :  0.04"
    +"TIONS :  0.07        THECO :  0.05        WOULD :  0.04");
  getnLetterCounts(5);
 }

 private void autoSolve() {

  char[] reverseKey = initializeAutoKey();
  Dictionary dict = new Dictionary();
  String in;
  do {
   String decodedText = decode(reverseKey);
   System.out.println(decodedText + " =>  ");
   int score = dict.countSubWords(decodedText);

   score = autoUpdateKey(reverseKey, dict, score);

   System.out.println("Repeat using the above key?(0 for no, 1 for yes)");
   in ="";
   try {
    in = reader.readLine();
   } catch (IOException e) {
    e.printStackTrace();
   }
  } while("1".equals(in));
 }

 private int autoUpdateKey(char[] reverseKey, Dictionary dict, int score) {
  boolean swap;
  do 
  {
   swap = false;
   for(int i=0; i< reverseKey.length-1; i++) {
    //   for(int i=0; i  ");
     int newScore = dict.countSubWords(newDecodedtext);

     if(newScore > score) {
      swap = true;
      score = newScore; 
     }
     else swap(reverseKey, i, j);
    }
   }
  }while (swap ==  true);

  char[] key = printKey(reverseKey);

  System.out.println("Putative Key that maps ciphertext letters to plaintext = " + Arrays.toString(key));
  System.out.println("Decoded Text = " + decode(reverseKey));
  System.out.println("Cipher text =  " + ciphertext);
  return score;
 }

 private char[] printKey(char[] reverseKey) {
  char[] key = new char[26];
  for(int i=0; i added = new HashMap();
  int i=0;
  for(int j=0; i < letterFreqOrder.length() && j < cipherLetterFreq.length();j++) {

   char curCipherLetter = cipherLetterFreq.charAt(j);
   int pos = curCipherLetter - 'A';
   //   System.out.println(curCipherLetter);
   if(currentMapping.get(curCipherLetter) != '-' && !added.containsKey(currentMapping.get(curCipherLetter))){
    reverseKey[pos] = currentMapping.get(curCipherLetter);

   } else {
    while(added.containsKey(letterFreqOrder.charAt(i)) && i < letterFreqOrder.length()) i++;
    if(i< letterFreqOrder.length()) reverseKey[pos] = letterFreqOrder.charAt(i++);
   }

   added.put(reverseKey[pos], true);
   //   System.out.println("currentCipherchar = " + curCipherLetter 
   //     + ", Pos = " + pos + ", plainchar = " + reverseKey[pos]);
  }


  for(int j=0; j < reverseKey.length; j++){
   if(reverseKey[j] == '-'){
    while(added.containsKey(letterFreqOrder.charAt(i)) && i < letterFreqOrder.length()) i++;
    if(i< letterFreqOrder.length()) reverseKey[j] = letterFreqOrder.charAt(i++);
   }
  }

  printKey(reverseKey);
  System.out.println(Arrays.toString(reverseKey));
  return reverseKey;
 }

 private void getCurrentTwoLetterCounts() {

  System.out.println("English Bigram frequencies");
  System.out.println("TH :  2.71        EN :  1.13        NG :  0.89"
    +" HE :  2.33        AT :  1.12        AL :  0.88"
    +"IN :  2.03        ED :  1.08        IT :  0.88"
    +"ER :  1.78        ND :  1.07        AS :  0.87"
    +"AN :  1.61        TO :  1.07        IS :  0.86"
    +"RE :  1.41        OR :  1.06        HA :  0.83"
    +"ES :  1.32        EA :  1.00        ET :  0.76"
    +"ON :  1.32        TI :  0.99        SE :  0.73"
    +"ST :  1.25        AR :  0.98        OU :  0.72"
    +"NT :  1.17        TE :  0.98        OF :  0.71");

  getnLetterCounts(2);

 }

 private Map getnLetterCounts(int n) {
  HashMap mapCounts = new HashMap();
  for(int i=0; i < plaintext.length(); i++){
   if((i+n-1) >= plaintext.length()) break;
   String s = plaintext.substring(i, i+n);
   Integer cnt = mapCounts.get(s);
   if(cnt == null) mapCounts.put(s, 1);
   else mapCounts.put(s, cnt+1);
  }
  @SuppressWarnings("unchecked")
  LinkedHashMap sortedMapCount = sortByValue(mapCounts);
  System.out.println(sortedMapCount);
  return sortedMapCount;
 }

 private void computeLetterFreq(){

  Map temp = getnLetterCounts(1);
  for (String s : temp.keySet()) {
   cipherLetterFreq += s;
  }
  //  System.out.println(cipherLetterFreq.length());
 }
 private void guessAKey() throws Exception {

  System.out.print("Guess a key for abcdefghijklmnopqrstuvwxyz: ");
  String putativeKey = "";

  try {
   putativeKey = reader.readLine();
  } catch (IOException e) {
   e.printStackTrace();
   throw new Exception("Error while reading the putative key");
  } 

  createKeyMap(putativeKey);
 }

 private void getPlaintext(Map key) {
  StringBuffer plaintextBuf = new StringBuffer();
  for(int i = 0; i < ciphertext.length(); i++) {
   Character c = key.get(ciphertext.charAt(i));
   if(c == null) {
    System.out.println("Error: Character " + ciphertext.charAt(i)
      + " in ciphertext is not mapped to any alphabet");
    plaintextBuf.append(ciphertext.charAt(i));
   }
   else plaintextBuf.append(c);
  }
  System.out.println("Putative Plaintext is: " + plaintextBuf.toString());
  System.out.println("Note: Mapping not updated");
 }

 private void createKeyMap(String putativeKey) {
  Map key = new HashMap();
  if(putativeKey.length() < 26) {
   System.out.println("Key input is less than 26 characters. Invalid Key!");
   return;
  }
  putativeKey = putativeKey.toUpperCase();

  for(int i=0; i = input.length()){
    System.out.println("No character entered for cipherLetter:" + c
      + ". No changes made");
   }
   char p = input.charAt(i);
   if(!isCapLetter(p)){
    System.out.println("Invalid character entered for cipherletter");
    return;
   }

   currentMapping.put(c, p);
  }

  guessed =  ciphertext;
  plaintext = ciphertext;
  for(int i='A'; i <= 'Z'; i++){
   char c = currentMapping.get((char)i);
   guessed = guessed.replace((char)i, Character.toLowerCase(c));
   if(c != '-') plaintext = plaintext.replace((char)i, Character.toLowerCase(c));
  }

  showGuessed();
 }

 @SuppressWarnings({ "unchecked", "rawtypes" })
 private static LinkedHashMap sortByValue(Map unsortMap) {  
  List list = new LinkedList(unsortMap.entrySet());

  Collections.sort(list, new Comparator() {
   public int compare(Object o1, Object o2) {
    return ((Comparable) ((Map.Entry) (o2)).getValue())
      .compareTo(((Map.Entry) (o1)).getValue());
   }
  });

  LinkedHashMap sortedMap = new LinkedHashMap();
  for (Iterator it = list.iterator(); it.hasNext();) {
   Map.Entry entry = (Map.Entry) it.next();
   sortedMap.put(entry.getKey(), entry.getValue());
  }
  return sortedMap;
 }

 private void getCurrentThreeLetterCounts(){
  printTrigramFreq();
  getnLetterCounts(3);
 }

 private void printTrigramFreq() {

  System.out.println("English Trigram counts:");
  System.out.println("THE: 1.81   ERE:  0.31        HES :  0.24"
    + "AND :  0.73        TIO :  0.31        VER :  0.24"
    + "ING :  0.72        TER :  0.30        HIS :  0.24"
    + "ENT :  0.42        EST :  0.28        OFT :  0.22"
    + "ION :  0.42        ERS :  0.28        ITH :  0.21"
    + "HER :  0.36        ATI :  0.26        FTH :  0.21"
    + "FOR :  0.34        HAT :  0.26        STH :  0.21"
    + "THA :  0.33        ATE :  0.25        OTH :  0.21"
    + "NTH :  0.33        ALL :  0.25        RES :  0.21"
    + "INT :  0.32        ETH :  0.24        ONT :  0.20"
    + "");
  System.out.println("******************");

 }

 public static void main(String[] args) {

  SubstitutionCipher2 sc = new SubstitutionCipher2();
  sc.problem13();

 }

}

Substitution Ciphers

Problem

Write a program to help an analyst decrypt a simple substitution cipher.Your program
should take the ciphertext as input, compute letter frequency counts, and display
these for the analyst. The program should then allow the analyst to guess the key
and display the results of “decryption” with the putative key.

Note: This is from Mark Stamp's Information Security: Principles and Practice book, chapter 2. Solution below was submitted as homework for CS265 Cryptography and Information Security class at San Jose State University.

Solution

package Cypto;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class SubstitutionCipher {

 Map letterFreqMap;
 Map key;
 String ciphertext;
 String plaintext;
 BufferedReader reader;
 

 private void createInputBuffer(){
  reader = new BufferedReader(new InputStreamReader(System.in));
 }

 private void closeInputBufer() throws Exception{
  if(reader!=null)
   try {
    reader.close();
   } catch (IOException e) {

    e.printStackTrace();
    throw new Exception("Error while trying to close the input stream");
   }
 }

 private void getCipherText() throws Exception {
  System.out.println("***** Substitution Cipher Cracker *****");
  System.out.print("Enter ciphertext: ");

  reader = new BufferedReader(new InputStreamReader(System.in));
  try {
   ciphertext = reader.readLine();
  } catch (IOException e) {
   e.printStackTrace();
   throw new Exception("Error while reading the ciphertext");
  }
  ciphertext = ciphertext.toUpperCase();
  System.out.println("Ciphertext (in upper case) entered is '" + ciphertext + "'");
 }

 private void displayLetterFreq(){
  letterFreqMap = new LinkedHashMap();

  for(int i = 0; i < ciphertext.length(); i++){
   Character c = ciphertext.charAt(i);
   if (!(c >= 'A' && c <= 'Z')) continue;
   Integer count = letterFreqMap.get(c);
   if(count == null){
    letterFreqMap.put(c, 1);
   } else {
    letterFreqMap.put(c, count+1);
   }
  }
  System.out.println(letterFreqMap);
 }


 private void guessAKey() throws Exception {

  System.out.print("Guess a key for abcdefghijklmnopqrstuvwxyz: ");
  String putativeKey = "";

  try {
   putativeKey = reader.readLine();
//   System.out.println(putativeKey);
  } catch (IOException e) {
   e.printStackTrace();
   throw new Exception("Error while reading the putative key");
  } 

  createKeyMap(putativeKey);
 }

 private void getPlaintext() {
  StringBuffer plaintextBuf = new StringBuffer();
  for(int i = 0; i < ciphertext.length(); i++) {
   Character c = key.get(ciphertext.charAt(i));
   if(c == null) {
    System.out.println("Error: Character " + ciphertext.charAt(i)
      + " in ciphertext is not mapped to any alphabet");
    plaintextBuf.append(ciphertext.charAt(i));
   }
   else plaintextBuf.append(c);
  }
  plaintext = plaintextBuf.toString();
  System.out.println("Plaintext is: " + plaintext);
 }


 private void createKeyMap(String putativeKey) {
  if(putativeKey.length() < 26) {
   System.out.println("Key input is less than 26 characters. Invalid Key!");
   return;
  }
  key = new HashMap();
  putativeKey = putativeKey.toUpperCase();

  for(int i=0; i < putativeKey.length(); i++){
   key.put(putativeKey.charAt(i), (char)(i+'A'));
  }
 }

 public void problem12() {
  try {
   createInputBuffer();
   getCipherText();
   displayLetterFreq();
   guessAKey();
   getPlaintext();
  } 
  catch (Exception e) {
   e.printStackTrace();
  } 
  finally {
   try {
    closeInputBufer();
   } catch (Exception e) {
    e.printStackTrace();
   }
  }
 }

 public static void main(String[] args) {

  SubstitutionCipher sc = new SubstitutionCipher();
  sc.problem12();
 }
}

Dictionary Subwords

Problem

Find all possible subwords from a given text.

Note: This code was written to solve one part of problem 13 in Chapter 2 of Mark Stamp's Cryptography and Information (CS265) course (Information Security: Principle and Practice book).

Words to build the Dictionary in the code - http://www-personal.umich.edu/~jlawler/wordlist

Solution

package Cypto;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class Dictionary {

 ArrayList dict = new ArrayList(); //in sorted order

 
 public int countSubWords(String ciphertext) {
  
  return getSubWords(ciphertext).size();
 }
 
 public ArrayList getSubWords(String ciphertext){
  
  ArrayList wordsFound = new ArrayList();
  if(ciphertext.length() == 0) return wordsFound;
  
  ciphertext = ciphertext.toUpperCase();
  
  for(String word: dict){
   if(word.length() > 3 && ciphertext.contains(word)){
    wordsFound.add(word);
   }
  }
  System.out.println(wordsFound);
  return wordsFound;
 }
 
 public boolean isWord(String word){
//  System.out.println(Collections.binarySearch(dict, word.toUpperCase()));
  return Collections.binarySearch(dict, word.toUpperCase()) >= 0 ? true: false;
 }
 
 public Dictionary()
 {
  FileReader fin = null;
  BufferedReader buf = null;
  
  try {
   fin = new FileReader(new File("dictionary.txt"));
   buf = new BufferedReader(fin);
   String input = "";
   while((input = buf.readLine()) !=null){
//    System.out.println(input);
    dict.add(input.toUpperCase());
   }
  } catch (Exception e) {
   e.printStackTrace();
  } finally {
    try {
     if(fin != null) fin.close();
     if(buf != null) buf.close();
    } catch (IOException e) {
     e.printStackTrace();
    }
   
  }
 }
 
 public static void main(String[] args) {
  Dictionary d = new Dictionary();
  System.out.println(d.isWord("been"));
  System.out.println(d.getSubWords("haHbeenwould"));
 }

}

Shift Cipher

Problem 

The code below decrypts a shift cipher and outputs all possible shift ciphers (26 of them), From which you can easily detect if the given text is a shift cipher or if it is a shift cipher, find out the plaintext manually from the output.

Note: This code was written to decrypt shift ciphers (such as caesar's cipher) for Chapter 2 Problems of Mark Stamp's Cryptography and Information Security book for CS265 module at San Jose State University

Example

Input:VSRQJHEREVTXDUHSDQWV
Output:
0= WTSRKIFSFWUYEVITERXW
1= XUTSLJGTGXVZFWJUFSYX
2= YVUTMKHUHYWAGXKVGTZY
3= ZWVUNLIVIZXBHYLWHUAZ
4= AXWVOMJWJAYCIZMXIVBA
5= BYXWPNKXKBZDJANYJWCB
6= CZYXQOLYLCAEKBOZKXDC
7= DAZYRPMZMDBFLCPALYED
8= EBAZSQNANECGMDQBMZFE
9= FCBATROBOFDHNERCNAGF
10= GDCBUSPCPGEIOFSDOBHG
11= HEDCVTQDQHFJPGTEPCIH
12= IFEDWURERIGKQHUFQDJI
13= JGFEXVSFSJHLRIVGREKJ
14= KHGFYWTGTKIMSJWHSFLK
15= LIHGZXUHULJNTKXITGML
16= MJIHAYVIVMKOULYJUHNM
17= NKJIBZWJWNLPVMZKVION
18= OLKJCAXKXOMQWNALWJPO
19= PMLKDBYLYPNRXOBMXKQP
20= QNMLECZMZQOSYPCNYLRQ
21= RONMFDANARPTZQDOZMSR
22= SPONGEBOBSQUAREPANTS
23= TQPOHFCPCTRVBSFQBOUT
24= URQPIGDQDUSWCTGRCPVU

From the above list, we can find out that text at #22 is the decrypted text.

Solution

package Cypto;
import java.util.ArrayList;
import java.util.HashMap;

public class AlphaShift {

 char[] alphabets = new char[26];
 ArrayList> mapList 
 = new ArrayList >();
 
 public AlphaShift(){
  initAlphabet();
  storePermutations();
 }

 public void initAlphabet() {
  for(int i = 0; i < 26; i++){
   alphabets[i] = (char)('A' + i); 
  }
//  System.out.println(alphabets);
 }


 public void storePermutations()
 {
  int increment = 1;
  while(increment<= 25){
   HashMap map =  new HashMap();
   for(int i=0; i< alphabets.length; i++)
   {
    int newAlpha = (alphabets[i] - alphabets[0] + increment)%alphabets.length;
    map.put(alphabets[i], (char) alphabets[newAlpha]);
   }
//   System.out.println(map);
   mapList.add(map);
   increment++;
  }
 }

 public void possibleDecryptions(String input)
 {
  for(int i=0; i < mapList.size(); i++) {
   System.out.print(i + "= ");
   for(int j = 0; j < input.length(); j++) {
    System.out.print(mapList.get(i).get(input.charAt(j)));
   }
   System.out.println();
  }
 }
 
 public static void main(String[] args) {

  AlphaShift ob =  new AlphaShift();
//  ob.initAlphabet();
//  ob.storePermutations();
//  ob.possibleDecryptions("MXDXBVTZWVMXNSPBQXLIMSCCSGXSC");
  ob.possibleDecryptions("VSRQJHEREVTXDUHSDQWV"); 
 }
}

Telephone letter mapping

Problem: 

Given a number from the digits of a phone dialpad, output the letter permutations it could form, using the letters on the dialpad for that each digit given.

Note: This was an assignment for Chapter 7, CS265 Cryptography and Information Security class at San Jose State University.

Solution:

import java.util.ArrayList;

public class NumLetter {
 String[] letters = new String[10];
 
 void prepopulate(){
  NumLetter[] a = new NumLetter[5];
  letters[0] = "";
  letters[1] = "";
  letters[2] = "ABC";
  letters[3] = "DEF";
  letters[4] = "GHI";
  letters[5] = "JKL";
  letters[6] = "MNO";
  letters[7] = "PQRS";
  letters[8] = "TUV";
  letters[9] = "WXYZ";  
  System.out.println(letters);
 }
 
 private void findPermutations(int n) {

  int digitCnt = 0, temp = n;
  while(temp != 0){
   temp/=10;
   digitCnt++;
  }
  if(digitCnt == 0) return;
  
  int maxDigits = digitCnt;
  
  ArrayList result = new ArrayList();
  String chars = letters[(int) (n/Math.pow(10, digitCnt-1))];
  n = (int) (n % Math.pow(10, digitCnt-1));digitCnt--;
  for(int j = 0; j< chars.length(); j++){
   result.add(chars.charAt(j) + "");
  }
  
  for(int i=1; i< maxDigits; i++)
  {
   chars = letters[(int) (n/Math.pow(10, digitCnt-1))];
   ArrayList tempRes = new ArrayList();
   for(int j = 0; j< chars.length(); j++)
   {
    for(int k = 0; k< result.size(); k++)
    {
     tempRes.add(result.get(k) + chars.charAt(j));
    }
   }
   result = tempRes;
   n = (int) (n % Math.pow(10, digitCnt-1));digitCnt--;
  }
  System.out.println(result);
 }
 
 public static void main(String[] args) {
  NumLetter ob = new NumLetter();
  ob.prepopulate();
  ob.findPermutations(5465);
 }
}

Example

Input: 5465

Output: 

[JGMJ, KGMJ, LGMJ, JHMJ, KHMJ, LHMJ, JIMJ, KIMJ, LIMJ, JGNJ, KGNJ, LGNJ, JHNJ, KHNJ, LHNJ, JINJ, KINJ, LINJ, JGOJ, KGOJ, LGOJ, JHOJ, KHOJ, LHOJ, JIOJ, KIOJ, LIOJ, JGMK, KGMK, LGMK, JHMK, KHMK, LHMK, JIMK, KIMK, LIMK, JGNK, KGNK, LGNK, JHNK, KHNK, LHNK, JINK, KINK, LINK, JGOK, KGOK, LGOK, JHOK, KHOK, LHOK, JIOK, KIOK, LIOK, JGML, KGML, LGML, JHML, KHML, LHML, JIML, KIML, LIML, JGNL, KGNL, LGNL, JHNL, KHNL, LHNL, JINL, KINL, LINL, JGOL, KGOL, LGOL, JHOL, KHOL, LHOL, JIOL, KIOL, LIOL]

Max Profit

Problem

You are given an array containing prices for a share during a day. The index of the array is the time (in minutes) at which the price of the share had the value at that index. Write a function to return the maximum profit you can get. You can buy the share at any point in time and sell it at any point in time.

Solution

  int[] price = {-1,10,7,6,2};
  
  public int getMaxProfit() {
    
    int min = price[0], maxProfit =0;
    int profit = 0;
    
    for(int i=1; i< price.length; i++) {      
      if(price[i] < min) min = price[i];
      else {
        profit = price[i] - min;
        if(profit > maxProfit) maxProfit = profit;
      }
    }   
    return maxProfit;
  }

  

FizzBuzz

Problem

For integers 1 to 100, print 'Fizz' if its divisible by 3, print 'Buzz' if its divisible by 5, 'FizzBuzz' if its divisible by 3 and 5, print the number alone otherwise.

Solution

public class FizzBuzz {

 public void printFizzBuzz(){
  
  String temp;
  for(int i=1; i< 100; i++)
  {
   temp = "";
   if(i%3 == 0) temp = "Fizz";
   if(i%5 == 0) temp += "Buzz";
   if(temp.length() == 0) temp = i + ""; 
   
   System.out.println(temp);
  }
  
 }
 public static void main(String[] args) {

  FizzBuzz fb = new FizzBuzz();
  fb.printFizzBuzz();
 }

}

First Character Appearing Once

Problem

No. 13 - First Character Appearing Only Once
Implement a function to find the first character in a string which only appears once.
For example: It returns ‘b’ when the input is “abaccdeff”.

Solution Least Time

 Character getFirstUnique(char[] w)
 {
  HashMap m = new LinkedHashMap();
  for(int i=0; i< w.length; i++)
  {
   Integer cnt = m.get(w[i]);
   if(cnt == null) m.put(w[i], 1);
   else m.put(w[i], cnt+1);
  }
  
  for(int i=0; i< w.length; i++)
  {
   if(m.get(w[i]) == 1) return w[i];
  }

  return null;
 }

Solution Least Space

 public Character solnNoMem(char[] w)
 {
  for(int i=0; i< w.length; i++)
  {
   int cnt = 0;
   for(int j=0; j< w.length; j++)
   {
    if(i!=j && w[i] == w[j]) {
     cnt =1; break;
    }
   }
   if(cnt==0) return w[i];
  }
  return null;
 }

String compression

Problem

Implement a method to perform basic string compression using the counts
of repeated characters. For example, the string aabcccccaaa would become
a2blc5a3. If the "compressed" string would not become smaller than the original
string, your method should return the original string.

Note; this if from cracking the coding interview book

Solution

 public String compress(String s)
 {
  if(s.length()==0) return s;

  StringBuffer temp = new StringBuffer();
  Character lastChar = null;
  char currentChar = s.charAt(0);
  int count =1;
  for(int i=1; i< s.length(); i++)
  {
   if(s.charAt(i)==currentChar)
   {
    count++;
   }
   else 
   {
    temp.append(currentChar);
    temp.append(count);
    lastChar = currentChar;
    count = 1;
    currentChar = s.charAt(i);
   }
   System.out.println(temp.toString());
  }
  if(lastChar != currentChar) 
  {
   temp.append(currentChar);
   temp.append(count);
  }
  System.out.println(temp.toString());

  if(temp.length() < s.length())  return temp.toString();
  return s;
 }

Pass by value Javascript

Problem

Correct the below code. It's simple—you click on one of three boxes to see what nice thing you've won. You always win something nice. Because we love you. Here's what we have so far. Something's going wrong though. Can you tell what it is?

<button id="btn-0">Button 1!</button>

<button id="btn-1">Button 2!</button>

<button id="btn-2">Button 3!</button>

<script type="text/javascript">

    var prizes = ['A Unicorn!', 'A Hug!', 'Fresh Laundry!'];

    for (var btnNum = 0; btnNum < prizes.length; btnNum++) {
        // for each of our buttons, when the user clicks it...
        document.getElementById('btn-' + btnNum).onclick = function() {
            // tell her what she's won!
            alert(prizes[btnNum]);
        };
    }
</script>

Solution

<!doctype html>
<html> 
<button id="btn-0">Button 1!</button>
<button id="btn-1">Button 2!</button>
<button id="btn-2">Button 3!</button>
</html>

<script type="text/javascript">
var prizes = ['A Unicorn!', 'A Hug!', 'Fresh Laundry!'];
for (var btnNum = 0; btnNum < prizes.length; btnNum++) {
// for each of our buttons, when the user clicks it...
        document.getElementById('btn-' + btnNum).onclick 
  = ((function(btnNUm){
    return function(){window.alert(prizes[btnNUm]);};
  })(btnNum));   
}
</script>

Add Spaces using Javascript

Problem

Create a textbox and a button. When button is clicked, replace the text in the textbox, with spaces between each character in the original text.

Note: window.alert was used to debug

Solution

<!doctype html>
<html>
 Input Text: <input id='inText' type='text'>
 <button onClick='addSpaces();'>Click to add spaces :)</button> 
</html>

<script language='javascript' type='text/javascript'>
function addSpaces() {
  var text = document.getElementById('inText');
  var newtext = text.value.split('').join(' ');
  //window.alert(newtext);
  text.value = newtext; 
}
</script>

Morris Tree Traversal (Pre & In order)

package Tree;

public class MorrisTraversal {
 //nlogn time complexity
 //but 1 space complexity => saves memory
 
 public void morrisPreorder(Tree t)
 {
  while(t!= null) 
  {
   if(t.left == null)
   {
    System.out.print(t.val + " ");
    t = t.right;
   }
   else
   {
    Tree pre =  t.left;
    while(pre.right != null && pre.right != t) 
     pre = pre.right;
    
    if(pre.right == null)
    {
     System.out.print(t.val + " ");
     pre.right = t;
     t = t.left;
    }
    else
    {
     pre.right  = null;
     t = t.right;
    }
   }
  }
 }
 
 public void morrisInorder(Tree t){
  while(t != null) 
  {
   if(t.left == null) 
   {
    System.out.print(t.val + " ");
    t = t.right;
   }
   else 
   {
    Tree temp = t.left;
    while(temp.right != null && temp.right != t)
    {
     temp = temp.right;
    }
    
    if(temp.right == null)
    {
     temp.right = t;
     t = t.left;
    }
    else 
    {
     temp.right = null;
     System.out.print(t.val + " ");
     t = t.right;
    }
   }
  }
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int[] pre = {10,5,1,2,7,50,100};
  BSTFromPre ob = new BSTFromPre();
  Tree t = ob.reContructTree(pre);
  TreeOperations.printTree(t);
  System.out.println("-------------------------");
  
  MorrisTraversal morris =  new MorrisTraversal();
//  morris.morrisInorder(t);
  morris.morrisPreorder(t);
  
 }
}

Strings are permutations?

Problem

Find out if 2 strings are permutations of each other.

Solution

 private HashMap convertStringToMap(String s)
 {
  HashMap map = new HashMap();
  Integer mapValue;
  Character c;
  for(int i=0; i< s.length(); i++)
  {
   c = s.charAt(i);
   mapValue = map.get(c);
   if(mapValue == null) map.put(c, 1);
   else map.put(c, mapValue+1);
  }
  return map;
 }

 private boolean permutation(String string1, String string2) {

  if(string1.length() != string2.length()) return false;

  HashMap map1 = convertStringToMap(string1);
  HashMap map2 = convertStringToMap(string2);

  return map1.equals(map2);
 }