Code 4 Life: September 2015

Sunday, September 27, 2015

Password hash with SHA-1

In cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographic hash function designed by the United States National Security Agency and is a U.S. Federal Information Processing Standard published by the United States NIST. SHA-1 is a member of the Secure Hash Algorithm family. The four SHA algorithms are structured differently and are named SHA-0, SHA-1, SHA-2, and SHA-3. SHA1 is a one-way hash function and it computes a 160-bit message digest. SHA-1 often appears in security protocols for example, many HTTPS websites use RSA with SHA-1 to secure their connections. BitTorrent uses SHA-1 to verify downloads. Git and Mercurial use SHA-1 digests to identify commits.

SHA1("UiTM Jasin Melaka 2015. Fare Well Everyone!")
Hexadecimal: 0eb2acda4c34c9a13097a299f561c7b2d592e8bf

Even a small change in the message will, with overwhelming probability, result in a completely different hash due to the avalanche effect.

SHA1("UiTM Jasin Melaka 2015. FareWell Everyone!")
Hexadecimal: 543232d470af26e6b25644f820cbab88c214d1f1

import java.security.*; 
public class HashTextTest {

    public static void main(String[] args){
        System.out.println(sha1("UiTM Jasin Melaka 2015. Fare Well Everyone!"));
    }
     
    public static String sha1(String str){        
        StringBuffer shasum = new StringBuffer();
        try{
           MessageDigest mDigest = MessageDigest.getInstance("SHA1");
           byte[] result = mDigest.digest(str.getBytes());   
           for (int i = 0; i < result.length; i++) {
               shasum.append(Integer.toString((result[i] & 0xff) + 0x100, 16).substring(1));
           }
        }
        catch(NoSuchAlgorithmException e){
           e.printStackTrace();   
        }
        
        return shasum.toString();
    }
}

Thursday, September 24, 2015

Matlab: Removing silence part in signal processing

I am just try and error in this matlab thing about a month ago tried to figure out a way to remove silence in signal. And at last i have found this solution on youtube.


[x,Fs] = audioread('Matlab\data\wav\example.wav');
no_silence_sig = silence_removal(Fs,x);

function no_silence_sig = silence_removal(fs,get_audio)
    
    frame_len = 0.01*fs; % 0.01 per frame
    N = length(get_audio);
    num_frames = floor(N/frame_len);
    new_sig = zeros(N,1);
    count = 0;
    
    for k=1:num_frames
       frame = get_audio((k-1)*frame_len+1 : frame_len*k);
       max_val = max(frame);
        %only append signal at amplitude >0.02
       if(max_val > 0.02)
            count = count+1;
            new_sig((count-1)*frame_len+1 : frame_len*count) = frame;
       end
    end
    
    % remove trailing zero in signal
    no_silence_sig=new_sig(1:find(new_sig, 1, 'last'));
end

Merge Sort

The merge sort is a recursive sort of order n*log(n). It is notable for having a worst case and average complexity of O(n*log(n)), and a best case complexity of O(n) (for pre-sorted input). The basic idea is to split the collection into smaller groups by halving it until the groups only have one element or no elements (which are both entirely sorted groups). Then merge the groups back together so that their elements are in order. This is how the algorithm gets its "divide and conquer" description.

Worst case performance : O(n log n)
Best case performance : O(n log n)
Average case performance : O(n log n)

Conceptually, a merge sort works as follows:

Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

This is the pseudocode of merge sort

function mergesort(m)
   var list left, right, result
   if length(m) ≤ 1
       return m
   else
       var middle = length(m) / 2
       for each x in m up to middle - 1
           add x to left
       for each x in m at and after middle
           add x to right
       left = mergesort(left)
       right = mergesort(right)
       if last(left) ≤ first(right) 
          append right to left
          return left
       result = merge(left, right)
       return result

function merge(left,right)
   var list result
   while length(left) > 0 and length(right) > 0
       if first(left) ≤ first(right)
           append first(left) to result
           left = rest(left)
       else
           append first(right) to result
           right = rest(right)
   if length(left) > 0 
       append rest(left) to result
   if length(right) > 0 
       append rest(right) to result
   return result

Quick Sort

Quicksort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation is defined. On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is at one end of the spectrum of divide-and-conquer algorithms, which does most of the work during the partitioning and the recursive calls.

Steps

Choose any element of the array to be the pivot.
Divide all other elements (except the pivot) into two partitions which is all elements less than the pivot must be in the first partition and all elements greater than the pivot must be in the second partition.
Use recursion to sort both partitions.
Join the first sorted partition, the pivot, and the second sorted partition.

The best pivot creates partitions of equal length (or lengths differing by 1). The worst pivot creates an empty partition, for example if the pivot is the first or last element of a sorted array. The runtime of Quicksort ranges from O(n log n) with the best pivots, to O(n2) with the worst pivots, where n is the number of elements in the array.

What is the programming competition?

What is the programming competition?

The programming competition is just that, a competition during which teams compete by attempting to code correct solutions to as many of the problems that they can within 5 hours. The problems are not just 'undergrad assignment' questions, they are scenarios that will require you to develop a non-trivial algorithm that correctly simplifies the problem into a form that can be solved very quickly (solutions must generally be able to solve a multi-thousand solution in under 3 minutes).

Why should i join programming competition

Aside from ego, pride or otherwise acquired bragging rights, the is also a very good opportunity to develop your skills of problem solving under pressure which every person this side of the wilderness will need to have throughout their life style. Understanding how you came to a given solution and even understanding why that solution was wrong (or inelegant), can help you to develop your problem solving skills. By reading only textbook you will never improved yourself.

Student/people usually will think that "oh man, that sounds hard". Actually, it is and it isn't. The most common misconception is that you need to be a 'wizard' coder to do well. In fact, many successful teams bring with them printed notes of how to perform the more tedious coding tasks so that they can spend their time working on finding a good solution rather than wasting it trying to remember the correct algorithm for a depth-first search.

Team Strategy Tips

If you are not sure about your solution, discuss it with your teammates. If stuck, explain problem to a teammate. Use good judgement if it is worth the interruption of him/her.
If you are stuck on a problem, take a walk or go to the toilet. The best ideas come to mind here.
Look at the scoreboard every now and then. If there is a problem that many other teams solved, it should be easy.
Usually there are 10 question. Split every question with your teammate, read and choose the easiest one.
Discus with your teammate who is the coder, who is thinker and who is the algorithmer.
Don't spend to much time on one question. Try to solve other while your teammate think another solution.
When you are done with a problem, separate it. Don't mess your table.
Eat to release tension..that is i always do.

Hint

I am too not a expert in this, but I would recommend the following things according to my experiences :

Choose a programming language you are going to use in all the competitions. I would say the best choice is Java because java have a lot of library that i can use and easy to remember rather than hard coder.
Learn algorithm such as Sorting, Searching, Combination, Permutation, Graph, Palindrome, Bruce force, Dynamic Programming, etc..
Mathematics algorithm also important such as Algebra, Summation, Cubic, Angle and etc But it is not necessary for me.
For people using Java as their programming language, i use library such as StringBuilder, BigInteger, HashMap, Scanner, BufferedReader, Math, Arrays, HashMap, Vector, String, Character. Its really help me.
Get some theoretical knowledge of algorithms. Book written by Steven Halim shows you how to solve problem in vary such way. It contains pretty much all the algorithms, math and data structures you need to know for programming competitions.
Go to website called Hackerearth, Hackerrank, Codechef or else, they provide platform where you can practice to solve the problem provided.

Wednesday, September 23, 2015

Password hash with MD5

The MD5 message-digest algorithm is a widely used cryptographic hash function producing a 128-bit (16-byte) hash value, typically expressed in text format as a 32 digit hexadecimal number. MD5 has been utilized in a wide variety of cryptographic applications, and is also commonly used to verify data integrity.

MD5 is very collision resistant. The algorithm was designed to generate unique hash values for each unique input. However, lately there have been rumblings in the security community about the weaknesses in MD5. Many government agencies will be required to move to a stronger algorithm in a few years.

Advantages of MD5

Utilizes a fast computation algorithm
Provides collision resistance
Is in widespread use
Provides a one-way hash

Disadvantages of MD5

Has known security flaws and vulnerabilities
Is less secure than the SHA-1 algorithm

Note : MD5 now are not relevant and not secure anymore. Using salted md5 for passwords is a bad idea. Not because of MD5's cryptographic weaknesses, but because it's fast. This means that an attacker can try billions of candidate passwords per second on a single GPU.

import java.security.*;

public class MD5
{
    public static void main(String[] args)
    {
        String passwordToHash = "HELLOWORLD";
        StringBuilder sb = new StringBuilder();
        try {
           MessageDigest md = MessageDigest.getInstance("MD5");
           md.update(passwordToHash.getBytes());
           byte[] bytes = md.digest();
           for(int x=0; x< bytes.length ;x++){
               sb.append(String.format("%02x", bytes[x]));
           }
        }
        catch (NoSuchAlgorithmException e)
        {
            e.printStackTrace();
        }
        System.out.println(sb.toString());
    }
}

Password Validator and Generator

import java.util.regex.*;
import java.util.*;
import java.lang.*;
import java.text.*;
import java.math.*;

public class PasswordValidator {
    public static boolean validate(String password) {
        if (password.matches("((?=.*\\d)(?=.*[a-z])(?=.*[A-Z])(?=.*[@#$%]).{8,20})"))
            return true;

        return false;
    }

    public static boolean symbol(String password) {
        if (password.matches(".*[@#$%].*"))
            return true;

        return false;
    }

    public static boolean uppcase(String password) {
        if (password.matches(".*[A-Z].*"))
            return true;

        return false;
    }

    public static boolean lowerCase(String password) {
        if (password.matches(".*[a-z].*"))
            return true;

        return false;
    }

    public static boolean digit(String password) {
        if (password.matches(".*\\d.*"))
            return true;

        return false;
    }

    public static boolean validate2(String pass) {
        boolean flag = true;

        if (pass.length() < 8) {
            System.out.println("Password must more than 8");
            flag = false;
        } else if (!digit(pass)) {
            System.out.println("Password must contains digit");
            flag = false;
        } else if (!symbol(pass)) {
            System.out.println("Password must contains symbol");
            flag = false;
        } else if (!uppcase(pass)) {
            System.out.println("Password must contains Upper case");
            flag = false;
        } else if (!lowerCase(pass)) {
            System.out.println("Password must contains Lower case");
            flag = false;
        }

        return flag;
    }

    public static String randomString(int len) {
        Random rnd = new Random();
        String AB = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz@#$%&";
        StringBuilder sb = new StringBuilder(len);
        for (int i = 0; i < len; i++)
            sb.append(AB.charAt(rnd.nextInt(AB.length())));
        return sb.toString();
    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        System.out.print("1. Generatae password 2. Test Password :");
        int option = scan.nextInt();

        switch (option) {
            case 1:
                String pass = "";
                System.out.print("Length of password >8 : ");
                int len = scan.nextInt();
                int count = 0;
                while (true) {
                    if (len < 8)
                        break;

                    pass = randomString(len);
                    if (validate(pass)) {
                        break;
                    } else {
                        System.out.println("Retrying..");
                        count++;
                    }
                }

                System.out.print("Password generated = " + pass);
                break;
            case 2:
                System.out.print("Password : ");
                String password = scan.next();
                if (validate2(password)) {
                    System.out.println("Pass");
                }
                break;
            default:
                break;
        }


    }
}

Columnar Transposition Cipher With Key

In cryptography, a transposition cipher is a method of encryption by which the positions held by units of plaintext (which are commonly characters or groups of characters) are shifted according to a regular system, so that the ciphertext constitutes a permutation of the plaintext. That is, the order of the units is changed (the plaintext is reordered). Mathematically a bijective function is used on the characters' positions to encrypt and an inverse function to decrypt.

The Columnar Transposition is one of the transposition cipher implementation.

In a columnar transposition, the message is written out in rows of a fixed length, and then read out again column by column, and the columns are chosen in some scrambled order. Both the width of the rows and the permutation of the columns are usually defined by a keyword. For example, the word ZEBRAS is of length 6 (so the rows are of length 6), and the permutation is defined by the alphabetical order of the letters in the keyword. In this case, the order would be "6 3 2 4 1 5".

In a regular columnar transposition cipher, any spare spaces are filled with nulls; in an irregular columnar transposition cipher, the spaces are left blank. Finally, the message is read off in columns, in the order specified by the keyword. For example, suppose we use the keyword ZEBRAS and the message WE ARE DISCOVERED. FLEE AT ONCE. In a regular columnar transposition, we write this into the grid as follows:

ZEBRAS = 632415

6 3 2 4 1 5
W E A R E D
I S C O V E 
R E D F L E 
E A T O N C 
E Q K J E U

To decipher it, the recipient has to work out the column lengths by dividing the message length by the key length. Then he can write the message out in columns again, then re-order the columns by reforming the key word.

In a variation, the message is blocked into segments that are the key length long and to each segment the same permutation (given by the key) is applied. This is equivalent to a columnar transposition where the read-out is by rows instead of columns.

Columnar transposition continued to be used for serious purposes as a component of more complex ciphers at least into the 1950s.

Sunday, September 20, 2015

Do you ever heard of Greenfoot programming??

I heard about greenfoot about 2 days ago and decide to join the greenfoot workshop. That was very interesting workshop where you learn how to move an object from left to right, control the motion of the object and create a simple games. About 2 hours i managed to create a simple rocket games (very noob games)..LOL..

What is Greenfoot??

Greenfoot is an interactive Java development environment designed primarily for educational purposes at the high school and undergraduate level. It allows easy development of two-dimensional graphical applications, such as simulations and interactive games. it also an educational software designed to make learning programming easy and fun.

Greenfoot is being developed and maintained at the University of Kent, with support from Oracle. It is free software, released under the GPL license. Greenfoot is available for Microsoft Windows, Mac OS X, Linux, Sun Solaris, and any recent JVM.

Sierpinski Triangles

The Sierpinski triangle (also with the original orthography Sierpiński), also called the Sierpinski gasket or the Sierpinski Sieve, is a fractal and attractive fixed set with the overall shape of an equilateral triangle, subdivided recursively into smaller equilateral triangles.

The concept of the Sierpinski triangle is very simple:

Take a triangle
Create four triangles out of that one by connecting the centers of each side
Cut out the middle triangle
Repeat the process with the remaining triangles

The Sierpinsky Triangle is a fractal created by taking a triangle, decreasing the height and width by 1/2, creating 3 copies of the resulting triangle, and place them such each triangle touches the other two on a corner. This process is repeated over and over again with the resulting triangles to produce the Sierpinski triangle, as illustrated below.

FizzBuzz Problem

Write a short program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

examples :

3 => Fizz

5 => Buzz

...

15 => FizzBuzz

...

so on..

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

Learn ASCII Code

What is It and Why Should I Care?

An "ASCII" is a data or text file that contains only characters coded from the standard ASCII character set. Characters 0 through 127 comprise the Standard ASCII Set and characters 128 to 255 are considered to be in the Extended ASCII Set. These codes, however, may not be the same in all computers and files containing these characters may not display or convert properly by another ASCII program.

Saturday, September 19, 2015

The Wacmian Number

In the supposedly uninhabited Wacmahara Desert, a tribe of unusual people has been discovered. The Wacmians have only 2 fingers and a thumb on each hand, and have invented their own numbering system. The digits they use and the symbols they use for digits are quite unusual, but anthropologists have been able to represent them as follows:

% represents 0
) represents 1
~ represents 2
@ represents 3
? represents 4
\ represents 5
$ represents -1 (yes, they even have a negative digit)

As you may expect, their system is base 6 where each place value is 6 times the value to its right, as in the following examples:

)@% is 1*62+3*6+0 = 36+18+0 = 54
?$~~ is 4*63+(–1)*62+2*6+2 = 864–36+12+2 = 842
$~~ is (–1)*62+2*6+2 = –36+12+2 = -22

Your task is to take Wacmian numbers and represent them as standard base 10 numbers.

Sample Input
)@%
?$~~
$~~
%
#

Sample Output
54
842
-22
0

import java.util.*;
import java.lang.*;
import java.math.*;

public class P1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String line = scan.next();
        while (line.charAt(0) != '#') {
            System.out.println(convertNumber(line, 6));
            line = scan.next();
        }
    }
    public static int convertDigit(char wdigit) {
        switch (wdigit) {
            case '%':
                return 0;
            case ')':
                return 1;
            case '~':
                return 2;
            case '@':
                return 3;
            case '?':
                return 4;
            case '\\':
                return 5;
            case '$':
                return -1;
        }
        return 0;
    }

    public static int convertNumber(String str, int base) {
        int total = 0;
        for (int x = 0; x < str.length(); x++) {
            total = base * total + convertDigit(str.charAt(x));
        }
        return total;
    }
}

Friday, September 18, 2015

String permutation

A permutation, also called an "arrangement number" or "order," is a rearrangement of the elements of an ordered list into a one-to-one correspondence with itself

Algorithm
To get all the permutations, we will first take out the first char from String and permute the remaining chars.

If String = “ABC”
First char = A and remaining chars permutations are BC and CB.

Now we can insert first char in the available positions in the permutations.
BC -> ABC, BAC, BCA
CB -> ACB, CAB, CBA

So we can write a recursive function call to return the permutations and then another function call to insert the first characters to get the complete list of permutations.

import java.util.*;
public class Permutations {
    public static Set<String> permutationFinder(String str) {
        Set<String> perm = new HashSet<String>();
        
        //whitespaces
        if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        
        char initial = str.charAt(0); // first character
        String rem = str.substring(1); // Full string without first character
        Set<String> words = permutationFinder(rem);
        for (String strNew : words) {
            for (int i = 0;i<=strNew.length();i++){
                perm.add(charInsert(strNew, initial, i));
            }
        }
        return perm;
    }
 
    public static String charInsert(String str, char c, int j) {
        String begin = str.substring(0, j);
        String end = str.substring(j);
        return begin + c + end;
    }
 
    public static void main(String[] args) {
        String s = "1234";
        System.out.println("\nPermutations for " + s + " are: \n" + permutationFinder(s));
    }
}

Thursday, September 17, 2015

The Block Game (Mock KICTM UiTM Jasin 2015)

The citizens of Byteland regularly play a game. They have blocks each denoting some integer from 0 to 9. These are arranged together in a random manner without seeing to form different numbers keeping in mind that the first block is never a 0. Once they form a number they read in the reverse order to check if the number and its reverse is the same. If both are same then the player wins. We call such numbers palindrome

Ash happens to see this game and wants to simulate the same in the computer. As the first step he wants to take an input from the user and check if the number is palindrome and declare if the user wins or not

Input

The first line of the input contains T, the number of test cases. This is followed by T lines containing an integer N.

Output

For each input output "wins" if the number is a palindrome and "losses" if not.
Constraints

1<=T<=20
1<=N<=10000

Input:
3
331
666
343

Output:
losses
wins
wins

import java.util.*;
import java.lang.*;
import java.math.*;

public class Mock4{
   public static void main(String[] args){
      Scanner scan = new Scanner(System.in);
      
      String line =System.getProperty("line.separator");
      scan.useDelimiter(line);
      
      int cases = scan.nextInt();
      
      for(int x=0;x<cases;x++){
         
         String get = scan.next();

         StringBuilder str = new StringBuilder(get);
         
         if(get.equals(str.reverse().toString()))
            System.out.println("wins");
         else
            System.out.println("loses"); 
         
      }
   }
}

Find Remainder (Mock KICTM UiTM Jasin 2015)

Write a program to find the remainder when two given numbers are divided.

Input and Output

The first line contains an integer T, total number of test cases. Then follow T lines, each line contains two integers A and B. Find remainder when A is divided by B

Constraints
1 <= T <= 1000
1 <=A,B <== 10000

Samples Input
3
1 2
100 200
10 40

Samples Output
1
100
10

import java.util.*;
import java.lang.*;
import java.math.*;

public class Mock4{
   public static void main(String[] args){
      Scanner scan = new Scanner(System.in);
      
      String line =System.getProperty("line.separator");
      scan.useDelimiter(line);
      
      int cases = scan.nextInt();
      
      for(int x=0;x<cases;x++){
         
         String [] get = scan.next().split(" ");

         System.out.println(Integer.parseInt(get[0]) % Integer.parseInt(get[1]));
         
      }
   }
}

Typo! (Mock KICTM UiTM Jasin 2015)

A common typing error is to place the hands on the keyboard one row to the right of the correct position. So "Q" is typed as "W" and "J" is typed as "K" and so on. You are to decode a message typed in this manner.

Input

Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above [except back-quote (`)]. Keys labelled with words [Tab, BackSp, Control, etc.] are not represented in the input.

Output

You are to replace each letter or punctuation symbol by the one immediately to its left on the QWERTY keyboard shown above. Spaces in the input should be echoed in the output.

Sample Input

O S, GOMR YPFSU/

Sample Output

I AM FINE TODAY.

import java.util.*;
import java.lang.*;
import java.math.*;

public class Mock3{
   public static void main(String[] args){
      Scanner scan = new Scanner(System.in);
      
      String line =System.getProperty("line.separator");
      scan.useDelimiter(line);
      
      String get = scan.next();
      
      String str = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
      
      String ans="";
      for(int x=0;x<get.length();x++){
         if(get.charAt(x) != ' '){
            for(int y=0;y<str.length();y++){
               if(get.charAt(x) == str.charAt(y)){
                  ans = ans +""+ str.charAt(y-1);
                  break;
               }
            }
         }
         else{
            ans = ans + " ";
         }
      }
      
      System.out.print(ans);
    
   }
}

No Brainer (Mock KICTM UiTM Jasin 2015)

Zombies love to eat brains. Yum.

Input

The first line contains a single integer n indicating the number of data sets.

The following n lines each represent a data set. Each data set will be formatted according to the following description:

A single data set consists of a line "X Y", where X is the number of brains the zombie eats and Y is the number of brains the zombie requires to stay alive.

Output

For each data set, there will be exactly one line of output. This line will be "MMM BRAINS" if the number of brains the zombie eats is greater than or equal to the number of brains the zombie requires to stay alive. Otherwise, the line will be "NO BRAINS".

Sample Input

3
4 5
3 3
4 3

Sample Output

NO BRAINS
MMM BRAINS
MMM BRAINS

import java.util.*;
import java.lang.*;
import java.math.*;

public class Mock2{
   public static void main(String[] args){
      Scanner scan = new Scanner(System.in);
      
      String line =System.getProperty("line.separator");
      scan.useDelimiter(line);
      
      int cases = scan.nextInt();
      
      for(int x=0;x<cases;x++){
         
         String [] get = scan.next().split(" ");
         
         if(Integer.parseInt(get[0]) < Integer.parseInt(get[1]))
            System.out.println("NO BRAINS");
         else
            System.out.println("MMM BRAINS");
         
      }
   }
}