Monday, June 20, 2011

Fun with Prime numbers

Fun with prime numbers

When I am trying to understand the importance of prime numbers, I am really surprised to know that prime numbers have influance not in just mathamatics and computer science but has influance on nature too.

Periodical cicadas, Magicicada species, such as the 17-year and 13-year "locusts," are the longest-lived cicadas. They emerge during synchronized periods, often in spectacular numbers, every 17th or 13th year, respectively. More details refer: Cicadas and Magicicada .If you observe 13 and 17 both are prime numbers. Glenn Webb : A mathamatician found that periodical cicadas have prime number life cycles to avoid syncronization from predators.
If cicadas reprductive cycles are not follwed prime and lets think it as 12 years and if predators reproduce at 4 then predators will get complete feast as both lifecycles are syncronized. For more details please refer : http://philosci40.unibe.ch/lehre/winter06/wtwg_bio/webb01.pdf

Prime numbers have great infulance on hashing and cryptography.



package blog.prime;

import java.util.List;

public interface PrimeGenerator<T extends Number> {
// Return prime numbers between 'from' to  'upto'
    public List<T> getPrimeNumbersUpto(int from, int upto);
// Return prime numbers between 0 to  'upto'
    public List<T> getPrimeNumbersUpto(int upto);
// Returns fixed size of primes numbers from 0
    public List<T> getPrimeNumbersSet(int size);
// Returns fixed size of primes numbers from int
    public List<T> getPrimeNumbersSet(int from, int size);
//Get near prime
    public T getNextProbablePrime(T val);
//Get previous prime
    public T getPreProbablePrime(T val);
// To checks for prime
    public boolean isPrime(T val);
// Returns next prime near to val
}



package blog.prime;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

@ThreadSafe
public enum IntPrimeGenerator implements PrimeGenerator<Integer>  {
    integerSingletonPrime;

    private final int CACHE_INI_SIZE = 5000;
    private List<Integer> primeCache;
    private final Lock lock;
    private IntPrimeGenerator() {
        lock = new ReentrantLock();
        primeCache = Collections.unmodifiableList
                            (getPrimeNumbersSet(0,CACHE_INI_SIZE));
    }

    @Override
    public List<Integer> getPrimeNumbersUpto(int from, int upto) {
        if(from < upto)
            throw new IllegalStateException("'from' cann't be greater than 'upto'");
        int maxCachePrime =  primeCache.get(CACHE_INI_SIZE);
        if(upto == maxCachePrime) return primeCache;
        if(upto < maxCachePrime) 
            return primeCache.subList(
                primeCache.lastIndexOf(findNextNearPrime(from)),
                primeCache.lastIndexOf(findPreNearPrime(upto)));

        if(upto > maxCachePrime && from < maxCachePrime) 
            return getList(
                primeCache.size(), upto,
                primeCache.subList(
                primeCache.lastIndexOf(findNextNearPrime(from)), upto));
        else 
            return getList(from, upto);
    }

    @Override
    public List<Integer> getPrimeNumbersUpto(int to) {
        return getPrimeNumbersUpto(2,to);
    }

    @Override
    public List<Integer> getPrimeNumbersSet(int size) {
        if(size <= CACHE_INI_SIZE)
            return primeCache.subList(0, size);
        else
            throw new IllegalStateException(
                "IntegerPrime doen't support more than "+CACHE_INI_SIZE+"size");
    }

    @Override
    @jdk7("Coin : Improved type inference for generic instance creation (diamond)") 
    public List<Integer> getPrimeNumbersSet(int from, int size) {
        lock.lock();
        try {
            List<Integer> primes;
            if(primeCache == null) {
                primeCache = new CopyOnWriteArrayList<>();
                primes = primeCache;
        } else {
            primes = new CopyOnWriteArrayList<>();
        }
        while(primes.size() != size) {
            if(isPrime(from)) primes.add(from);   from++;
        }
        return primes;
        } finally {
            lock.unlock();
        }
    }

    @Override
    public boolean isPrime(Integer value) {
        int val = value.intValue();
        if(val == 1) return false;
        if(val == 2 || val == 3) return true;
        //Ignore even numbers
        if((val & 0b0001) == 0) return false;
        //Search in cache.
        if(primeCache.contains(val)) return true;
        if(primeCache.get(primeCache.size()-1) > val) return false;
        int flag=1;
        for(int i=2; i<=Math.sqrt(val); i++) {
            if(primeCache.size() > i) {
                if(val%primeCache.get(flag++) == 0) return false;
            } else {
                if(val%i == 0) return false;
            }
        }
        return true;
    }

    private Integer findNextNearPrime(Integer val) {
        while(true)
            if(isPrime(++val)) return val;
    }

    private Integer findPreNearPrime(Integer val) {
        while(true)
        if(isPrime(--val)) return val;
    }

    private List<Integer> getList(int from, int upto) {
        return getList(from, upto, new ArrayList<Integer>());
    }

    private List<Integer> getList(int from, int upto, List<Integer> primeList) {
        for(int i=from;i<=upto; i++)
            if(isPrime(i)) primeList.add(i);
        return primeList;
    }

    private int getNearInBasePrime(int val) {
        if(val > primeCache.get(CACHE_INI_SIZE-1))
            throw new IllegalStateException("Value is out of scope");
        int left = 0, right = CACHE_INI_SIZE, mid=0;
        while(left != right-1) {
            mid = (left + right) >> 1;
            if(primeCache.get(mid) > val)  right = mid;
            else left = mid;
        }
        return left;
    }
    public Integer getNextProbablePrime(Integer value) {
     int val = value.intValue();
        if(val < 2) return 2;
        if(primeCache.get(CACHE_INI_SIZE-1) > val) {
            int left = getNearInBasePrime(val);
            if(left != CACHE_INI_SIZE)
                return primeCache.get( left + 1);
        }
        return findNextNearPrime(val);
    }
     
    public Integer getPreProbablePrime(Integer value) {
        int val = value.intValue();
        if(val <= 2) throw new IllegalStateException("Not possible");
        if(primeCache.get(CACHE_INI_SIZE-1) > val) {
            if(!primeCache.contains(val)) {
                int left = getNearInBasePrime(val);
                if(left != 0)
                    return primeCache.get(left);
            } 
        }
        return findPreNearPrime(val);
    }
}

@interface ThreadSafe {

}
@interface jdk7 {
String value();
}




Monday, May 16, 2011

JDK7 NIO.2 Change

JDK7 NIO.2 API change

My initial blog code ShuffelMP3 and AstuteSync will not work as some of JDK7 NIO.2 methods are refactored. The copy and exists methods have been moved to Files. I have updated my code and added some of JDK7 coin features. RED colored statement for recent NIO.2 JDK chnages.

========= ShuffleMP3 ==================

package javatrails;

import java.io.IOException;
import java.nio.file.*;
import java.nio.file.attribute.*;
import java.util.UUID;
import static java.nio.file.StandardCopyOption.*;

public class ShuffleMp3 {

    private static final String SOURCE = "/home/dhanvi/TEMP";
    private static final String TARGET = "/home/dhanvi/TEST";

    private static void copyThisFile(Path file)  {
        try {
            Path targetPath = Paths.get(TARGET + System.getProperty("file.separator")
                         + UUID.randomUUID().toString().replaceAll("-", "") + ".mp3");

            Files.copy(file,targetPath, REPLACE_EXISTING);
            System.out.println("Copied " + file.toString() + " to " + targetPath.toString());
        } catch (IOException | Exception ex) {
            ex.printStackTrace();
        }
    }

    static class Mp3FileVisitor extends SimpleFileVisitor<Path> {
        @Override
        public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) {   
            if (file.toString().lastIndexOf(".mp3") >= 0  ||
                            file.toString().lastIndexOf(".MP3") >= 0)
                copyThisFile(file);
            return FileVisitResult.CONTINUE;
        }
    }

    public static void main(String... arg) {
        try {
            final Path path = Paths.get(SOURCE);
            if(!Files.exists(path))  throw new IllegalStateException("Sorry file doen't exists");
                Files.walkFileTree(path, new Mp3FileVisitor());
        } catch (@jdk7("Coin : Multi-catch and more precise rethrow") final IOException | IllegalStateException ex) {
            ex.printStackTrace();
        }
    }
}
  


========= AstuteSync ==================

package javatrails;
import java.io.IOException;
import java.nio.file.*;
import java.nio.file.attribute.*;
import java.util.*;
import java.util.Map.Entry;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.locks.*;
import static java.nio.file.FileVisitResult.*;
import static java.nio.file.StandardCopyOption.*;
import java.util.logging.Level;
import java.util.logging.Logger;

public class AstuteSync {
    private final static Lock lock = new ReentrantLock();
    @jdk7("Coin : Improved type inference for generic instance creation (diamond)")
    private final Map<String,String> diffList = new ConcurrentSkipListMap<>();
    private class SyncFileVisitor extends SimpleFileVisitor<Path> {
        private String head;
        public SyncFileVisitor(String head) {
            this.head = head.endsWith(System.getProperty("file.separator"))
                             ? head.substring(0,head.length()-1) : head;
        }
        @Override
        public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) {
            toList(dir);
            return CONTINUE;
        }
        @Override
        public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) {
            toList(file);
            return CONTINUE;
        }
        private void toList(Path file) {
            lock.lock();
            try {
                if (diffList.remove(file.toString().replace(head, "")) == null) 
                    diffList.put(file.toString().replace(head, ""), file.toString());
            } finally {
                lock.unlock();
            }
        }
    }
    private void printDiffList() {
        if(diffList.isEmpty())
            System.out.println("Both folders are in Sync.");
        else {
            System.out.println("Folder Diff:");
            for(String s : diffList.values())  
            System.out.println(s);
        }
    }
    private void sync(final Path source, final Path target) {
        Set<Entry<String, String>> entries = diffList.entrySet();
        for(Map.Entry<String,String> entry : entries) {
            try {
                Path tmpSource = Paths.get(entry.getValue());
                Path tmpTarget = Paths.get(
                    (entry.getValue().startsWith(target.toString()) ? source.toString() : target.toString()) +
                System.getProperty("file.separator") + entry.getKey());
                Files.copy(tmpSource, tmpTarget, COPY_ATTRIBUTES);
            } catch (Exception ex) {ex.printStackTrace();}
        }
    }
    public void startSync(final String SOURCE, final String TARGET) {
        final Path source = Paths.get(SOURCE);
        final Path target = Paths.get(TARGET);
        if(!Files.exists(source) || !Files.exists(target))  
            throw new IllegalStateException("Sorry file doen't exists");
        new Thread(new Runnable() {public void run() {
            try {
                Files.walkFileTree(source, new SyncFileVisitor(SOURCE));
            } catch (IOException ex) {
                Logger.getLogger(AstuteSync.class.getName()).log(Level.SEVERE, null, ex);
            }
        }}).start();
        new Thread(new Runnable() {public void run() {
            try {
                Files.walkFileTree(target, new SyncFileVisitor(TARGET));
            } catch (IOException ex) {
                Logger.getLogger(AstuteSync.class.getName()).log(Level.SEVERE, null, ex);
            }
        }}).start();
        Runtime.getRuntime().addShutdownHook(new Thread() {
        @Override public void run() {
            printDiffList();
            if(!diffList.isEmpty()) sync(source, target);
        }
        });
    }
    public static void main(String... arg)  {
        new AstuteSync().startSync("/home/dhanvi/TEMP", "/home/dhanvi/TEST");
    }
}
@interface jdk7 {
    String value();
}
  




Thursday, March 10, 2011

Eight Queens - 2

I have tested my code with different board sizes and it is throwing the correct number of solutions :).

When I started thinking of optimization. First thing came in mind was set of strings used for tracking blocked cells. Instead of having different heavy data structure, we can use the same board with different numeric for blocked cell. I have used '-1' for the same.

import java.util.Set;
import java.util.TreeSet;
public class Chess8Queens {
        private static final int BOARD_SIZE = 8;
        private static final int[][] chessBoard = new int[BOARD_SIZE][BOARD_SIZE];
        private static final Set<String> result = new TreeSet<String>();
        static {
               for(int i=0; i < BOARD_SIZE; i++)
                       for(int j=0; j < BOARD_SIZE; j++)
                              chessBoard[i][j] = 0;
        }
        private static void printBoard(boolean isSuccess) {
               StringBuffer sb = new StringBuffer();
               for (int i = 0; i < BOARD_SIZE; i++) {
                       for (int j = 0; j < BOARD_SIZE; j++) {
                               System.out.print(chessBoard[i][j] == -1 

                                                 ? "* " : chessBoard[i][j] + " ");
                               if(chessBoard[i][j] > 0 && isSuccess) 

                                         sb.append(j).append("|");
                       }
                       System.out.println("");
               }
               if(isSuccess) result.add(sb.toString());
               sb = null;
               System.out.println("Done :" + result.size());
        }
        private static void updateBlockedSet(int row, int col, boolean isAdd) {
               int flag1 = 0, flag2 = 0;
               if (col > row) {
                       flag1 = col - row;
                       flag2 = col + row;
                       for (int i = 0; i < BOARD_SIZE; i++) {
                               if (col < BOARD_SIZE)
                                      chessBoard[i][col] = isAdd ? -1 : 0;
                               if (row < BOARD_SIZE && col < BOARD_SIZE)
                                      chessBoard[row][i] = isAdd ? -1 : 0;
                               if ((flag1 + i) < BOARD_SIZE)
                                      chessBoard[i][flag1+i] = isAdd ? -1 : 0;
                               if ((flag2 - i) >= 0 && (flag2 - i) < BOARD_SIZE)
                                      chessBoard[i][flag2-i] = isAdd ? -1 : 0;
                       }
               } else if (col < row) {
                       flag1 = row - col;
                       flag2 = col + row;
                       for (int i = 0; i < BOARD_SIZE; i++) {
                               if (col < BOARD_SIZE)
                                       chessBoard[i][col] = isAdd ? -1 : 0;
                               if (row < BOARD_SIZE)
                                      chessBoard[row][i] = isAdd ? -1 : 0;
                               if ((flag1 + i) < BOARD_SIZE)
                                      chessBoard[flag1+i][i] = isAdd ? -1 : 0;
                               if ((flag2 - i) >= 0 && (flag2 - i) < BOARD_SIZE)
                                      chessBoard[flag2-i][i] = isAdd ? -1 : 0;
                       }
               } else {
                       for (int i = 0; i < BOARD_SIZE; i++) {
                               flag1 = col > (BOARD_SIZE/2) ? (BOARD_SIZE-1)-col : col;
                               flag2 = col + flag1;
                               flag1 = col - flag1;
                               chessBoard[i][col] = isAdd ? -1 : 0;
                               chessBoard[row][i] = isAdd ? -1 : 0;
                               chessBoard[i][i] = isAdd ? -1 : 0;
                               if((flag2-i) >= 0 && (flag2-i) < BOARD_SIZE && 

                                   (flag1 + i) >= 0 && (flag1 + i) < BOARD_SIZE)
                                      chessBoard[flag2-i][flag1+i] = isAdd ? -1 : 0;
                       }
               }
        }
        private static void adjustBadPosition(int row) {
               if(row < 0) return;
               int tempj=0;
               boolean changed = false;
               for(int j= 0; j < BOARD_SIZE; j++ )
                       if(chessBoard[row][j] > 0) {
                               chessBoard[row][j] = 0;
                               tempj = j;
                               changed = true; break;
                       }
               if(changed) {
                       for(int j=tempj+1; j<BOARD_SIZE; j++)
                               chessBoard[row][j] = 0;
                       for(int i=row+1; i<BOARD_SIZE; i++)
                               for(int j= 0; j<BOARD_SIZE; j++ )
                                      chessBoard[i][j] = 0;
                       resetUpdateList();
                       chessBoard[row][tempj] = -1;
               }
        }
        private static void resetUpdateList() {
               for(int i=0; i<BOARD_SIZE; i++)
                       for(int j= 0; j<BOARD_SIZE; j++ )
                               if(chessBoard[i][j] > 0 ) {
                                      int temp = chessBoard[i][j];
                                      updateBlockedSet(i,j,true);
                                      chessBoard[i][j] = temp;
                               }      
        }
        public static Set<String> getPositions() {
               if(result.isEmpty()) {
                       for( int row = 0; row < BOARD_SIZE; row++) {
                               if(row < 0) break;
                               for(int col = 0; col< BOARD_SIZE; col++) {
                                      if(chessBoard[row][col] == 0) {
                                              updateBlockedSet(row,col,true);
                                              chessBoard[row][col] = row+1;
                                              break;
                                      } else if(col == (BOARD_SIZE-1)){
                                              adjustBadPosition(row-1);
                                              row = row - 2; break;
                                      }
                               }
                               if(row == (BOARD_SIZE-1)) {
                                      printBoard(true);
                                      adjustBadPosition(row);
                                      row--;
                               }
                       }
               }
               return result;
        }
        public static void main(String... arg) {
               for(String s: getPositions())
                       System.out.println(s);
               System.out.println(getPositions().size());
        }
}

The output differ slightly from previous as 'B' is getting mixed with 8. I am printing *.

* * * * * * * 1
* * * 2 * * * *
3 * * * * * * *
* * 4 * * * * *
* * * * * 5 * *
* 6 * * * * * *
* * * * * * 7 *
* * * * 8 * * *


Still lot of optimization can be done. Only 12 unique solutions are possible with 8 size board, instead of having many recursive loops, using simple mathematics rest 80 can be generated.

Sunday, March 6, 2011

Eight Queens

Eight Queens problem :
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that none of them can capture any other using the standard chess queen's moves.



I really enjoyed solving Eight queens problem manually as well as programatically. 

Initially my code was returning 98. I literally diged a mountain to find the small rat (A small condition issue was throwing extra 6 wrong combination). Now I am getting unique 92 combination :). 

Thank you very much 'Ranga Vure' for pointing out the issue.


import java.util.Set;
import java.util.TreeSet;


public class Chess8Queens {


   private static final int chessBoard[][] = {{0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0}};
   private static final Set<String> blockedList = new TreeSet<String>();
   private static final Set<String> result = new TreeSet<String>();
   private static void printBoard(boolean isSuccess) {
      StringBuffer sb = new StringBuffer();
      for (int i = 0; i < 8; i++) {
         for (int j = 0; j < 8; j++) {
            System.out.print(chessBoard[i][j] == 0 ?
                                 blockedList.contains(i + "" + j) ? "B " : "O "
                                 : chessBoard[i][j]+" ");
            if(chessBoard[i][j] != 0 && isSuccess) sb.append(j).append("|");
         }
         System.out.println("");
      }
      if(isSuccess)
         result.add(sb.toString());
      sb = null;
      System.out.println("Done :" + result.size());
   }
   private static void updateBlockedSet(int row, int col, boolean isAdd) {
      int flag1 = 0, flag2 = 0;
      boolean temp;
      if (col > row) {
         flag1 = col - row;
         flag2 = col + row;
         for (int i = 0; i < 8; i++) {
            if (col < 8) {
               temp = isAdd ? blockedList.add(i + "" + col + "")
                            : blockedList.remove(i + "" + col + "");
            }
            if (row < 8 && col < 8) {
                temp = isAdd ? blockedList.add(row + "" + i + "")
                             : blockedList.remove(row + "" + i + "");
            }
            if ((flag1 + i) < 8) {
                temp = isAdd ? blockedList.add(i + "" + (flag1 + i) + "")
                             : blockedList.remove(i + "" + (flag1 + i) + "");
            }
            if ((flag2 - i) < 8) {
                temp = isAdd ? blockedList.add(i + "" + (flag2 - i) + "")
                             : blockedList.remove(i + "" + (flag2 - i) + "");
             }
        }
     } else if (col < row) {
        flag1 = row - col;
        flag2 = col + row;
        for (int i = 0; i < 8; i++) {
           if (col < 8) {
              temp = isAdd ? blockedList.add(i + "" + col + "")
                           : blockedList.remove(i + "" + col + "");
           }
           if (row < 8) {
              temp = isAdd ? blockedList.add(row + "" + i + "")
                           : blockedList.remove(row + "" + i + "");
           }
           if ((flag1 + i) < 8) {
              temp = isAdd ? blockedList.add((flag1 + i) + "" + (i) + "")
                           : blockedList.remove((flag1 + i) + "" + (i) + "");
           }
           if ((flag2 - i) < 8) {
              temp = isAdd ? blockedList.add((flag2 - i) + "" + (i) + "")
                           : blockedList.remove((flag2 - i) + "" + (i) + "");
           }
        }
    } else {
       for (int i = 0; i < 8; i++) {
          flag1 = col > 4 ? 7-col : col;
          flag2 = col + flag1;
          flag1 = col - flag1;
          temp = isAdd ? blockedList.add(i + "" + col + "")
                       : blockedList.remove(i + "" + col + "");
          temp = isAdd ? blockedList.add(row + "" + i + "")
                       : blockedList.remove(row + "" + i + "");
          temp = isAdd ? blockedList.add(i + "" + i + "")
                       : blockedList.remove(i + "" + i + "");
          if((flag2-i) >= 0 && (flag2-i) < 8 && (flag1 + i) >= 0 && (flag1 + i) < 8)
              temp = isAdd ? blockedList.add((flag2-i) + "" + (flag1 + i))
                           : blockedList.remove((flag2-i) + "" + (flag1 + i));
       }
    }
  }
  private static boolean adjustBadPosition(int row) {
     int tempj=0;
     boolean changed = false;
     for(int j= 0; j<8; j++ ) {
        if(chessBoard[row][j] != 0) {
           chessBoard[row][j] = 0;
           tempj = j;
           changed = true;
        }
     }
     if(changed) {
        for(int j=tempj+1; j<8; j++)
            blockedList.remove(row+""+j);
        for(int i=row+1; i<8; i++) {
           for(int j= 0; j<8; j++ ) {
              chessBoard[i][j] = 0;
              blockedList.remove(i+""+j);
           }
        }
        resetUpdateList();
        blockedList.add(row+""+tempj);
        return true;
     }
     return false;
  }
  private static void resetUpdateList() {
     for(int i=0; i<8; i++) {
        for(int j= 0; j<8; j++ ) {
           if(chessBoard[i][j] != 0 ) {
               updateBlockedSet(i,j,true);
           }
        }
     }
   }
   public static Set<String> getPositions() {
      if(result.isEmpty()) {
         for( int row = 0; row < 8; row++) {
            if(row < 0) break;
            for(int col = 0; col< 8; col++) {
               if(!blockedList.contains(row+""+col)) {
                  chessBoard[row][col] = row+1;
                  updateBlockedSet(row,col,true);
                  break;
               } else if(col == 7){
                  adjustBadPosition(row-1);
                  row = row -2;
                  break;
               }

            }
            if(row == 7) {
               printBoard(true);
               adjustBadPosition(row);
               row--;
            }

         }
     }
     return result;
   }


   public static void main(String... arg) {
      //System.out.println(result);
      System.out.println(getPositions().size());
   }
}


Sample output :

1 B B B B B B B

B B B B 2 B B B
B B B B B B B 3
B B B B B 4 B B
B B 5 B B B B B
B B B B B B 6 B
B 7 B B B B B B
B B B 8 B B B B
Done1

92 positions :  I have listed only columns.
0|4|7|5|2|6|1|3| = 0,0 | 1,4| 2,7 | 3,5| 4,2| 5,6 | 6,1| 7,3 = Top Listed board
0|5|7|2|6|3|1|4|
0|6|3|5|7|1|4|2|
0|6|4|7|1|3|5|2|
1|3|5|7|2|0|6|4|
1|4|6|0|2|7|5|3|
1|4|6|3|0|7|5|2|
1|5|0|6|3|7|2|4|
1|5|7|2|0|3|6|4|
1|6|2|5|7|4|0|3|
1|6|4|7|0|3|5|2|
1|7|5|0|2|4|6|3|
2|0|6|4|7|1|3|5|
2|4|1|7|0|6|3|5|
2|4|1|7|5|3|6|0|
2|4|6|0|3|1|7|5|
2|4|7|3|0|6|1|5|
2|5|1|4|7|0|6|3|
2|5|1|6|0|3|7|4|
2|5|1|6|4|0|7|3|
2|5|3|0|7|4|6|1|
2|5|3|1|7|4|6|0|
2|5|7|0|3|6|4|1|
2|5|7|0|4|6|1|3|
2|5|7|1|3|0|6|4|
2|6|1|7|4|0|3|5|
2|6|1|7|5|3|0|4|
2|7|3|6|0|5|1|4|
3|0|4|7|1|6|2|5|
3|0|4|7|5|2|6|1|
3|1|4|7|5|0|2|6|
3|1|6|2|5|7|0|4|
3|1|6|2|5|7|4|0|
3|1|6|4|0|7|5|2|
3|1|7|4|6|0|2|5|
3|1|7|5|0|2|4|6|
3|5|0|4|1|7|2|6|
3|5|7|1|6|0|2|4|
3|5|7|2|0|6|4|1|
3|6|0|7|4|1|5|2|
3|6|2|7|1|4|0|5|
3|6|4|1|5|0|2|7|
3|6|4|2|0|5|7|1|
3|7|0|2|5|1|6|4|
3|7|0|4|6|1|5|2|
3|7|4|2|0|6|1|5|
4|0|3|5|7|1|6|2|
4|0|7|3|1|6|2|5|
4|0|7|5|2|6|1|3|
4|1|3|5|7|2|0|6|
4|1|3|6|2|7|5|0|
4|1|5|0|6|3|7|2|
4|1|7|0|3|6|2|5|
4|2|0|5|7|1|3|6|
4|2|0|6|1|7|5|3|
4|2|7|3|6|0|5|1|
4|6|0|2|7|5|3|1|
4|6|0|3|1|7|5|2|
4|6|1|3|7|0|2|5|
4|6|1|5|2|0|3|7|
4|6|1|5|2|0|7|3|
4|6|3|0|2|7|5|1|
4|7|3|0|2|5|1|6|
4|7|3|0|6|1|5|2|
5|0|4|1|7|2|6|3|
5|1|6|0|2|4|7|3|
5|1|6|0|3|7|4|2|
5|2|0|6|4|7|1|3|
5|2|0|7|3|1|6|4|
5|2|0|7|4|1|3|6|
5|2|4|6|0|3|1|7|
5|2|4|7|0|3|1|6|
5|2|6|1|3|7|0|4|
5|2|6|1|7|4|0|3|
5|2|6|3|0|7|1|4|
5|3|0|4|7|1|6|2|
5|3|1|7|4|6|0|2|
5|3|6|0|2|4|1|7|
5|3|6|0|7|1|4|2|
5|7|1|3|0|6|4|2|
6|0|2|7|5|3|1|4|
6|1|3|0|7|4|2|5|
6|1|5|2|0|3|7|4|
6|2|0|5|7|4|1|3|
6|2|7|1|4|0|5|3|
6|3|1|4|7|0|2|5|
6|3|1|7|5|0|2|4|
6|4|2|0|5|7|1|3|
7|1|3|0|6|4|2|5|
7|1|4|2|0|6|3|5|
7|2|0|5|1|4|6|3|
7|3|0|2|5|1|6|4|

Sunday, February 20, 2011

Numbers to India Phrases

When I was going through the articles on black money, it was surprising to see the numbers are bigger than crores. However, these were discussed atmost in crores, though the numbers were lakh times more to a crore.


I started searching for next level above crore. Wikipedia helped me upto 10 pow 39. For more details on Indian number system refer http://en.wikipedia.org/wiki/Indian_numbering_system

Using Java BigInteger, I did conversion of number to possible Indian Number System. I tried English numbering system till thousand as they are most commonly used.

import java.math.BigInteger;
import java.util.Random;
import java.util.Stack;


public class NumberToIndianPhrase {
   private static final String[] basic = {"","ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX",
                                          "SEVEN", "EIGHT", "NINE", "TEN", "ELEVEN",
                                          "TWELVE", "THIRTEEN", "FOURTEEN", "FIFTEEN",
                                          "SIXTEEN", "SEVENTEEN", "EIGHTEEN", "NINETEEN"};


   private static final String[] tys = {"","","TWENTY", "THIRTY", "FORTY",
                                        "FIFTY", "SIXTY", "SVENTY", "EIGHTY", "NINETY"};


   private static final String[] denom = {"","tys","HUNDRED", "THOUSAND", "tys", "LAKH",
                                          "tys", "CRORE", "tys", "ARAB", "tys", "KHARAB", "tys",
                                          "NEEL", "tys", "PADMA", "tys", "SHANKH", "tys",
                                          "UDPADHA", "tys", "ANK", "tys", "PADHA", "tys",
                                          "MADH", "tys", "PARAARDHA", "tys", "ANT", "tys",
                                          "MAHA ANT", "tys", "SHISHT", "tys", "SINGHAR", "tys",
                                          "MAHA SINGHAR", "tys", "ADANT SINGHAR", "tys"};
   private static final BigInteger bigTen = BigInteger.TEN;


   private static String getPhrase(BigInteger bigIntVal) {
      if(denom.length < bigIntVal.toString().length())
           throw new IllegalStateException("Out of range for pharse");

      int rem, count=0;
      if(bigIntVal.compareTo(BigInteger.ZERO) < 0) bigIntVal = bigIntVal.negate();
      System.out.print(bigIntVal + " :");
      Stack <String> stack = new Stack<String>();
      if(bigIntVal.compareTo(BigInteger.valueOf(20)) < 0)    return basic[bigIntVal.intValue()];
      int lastVal=0;
       while (!bigIntVal.equals(BigInteger.ZERO)) {
         rem = bigIntVal.remainder(bigTen).intValue();
         if(denom[count].equals("tys")) {
             if(rem != 1) {
                if(lastVal==0 && rem !=0)
                   stack.push(tys[rem] + " " + denom[count-1]);
                else
                   stack.push(tys[rem]);
             } else {
             if(!stack.isEmpty() && lastVal != 0) stack.pop();
                stack.push(basic[lastVal+10] + " " + denom[count-1]);
             }
          } else {
             if(rem !=0)
                stack.push(basic[rem] + " " + denom[count]);
          }
          bigIntVal = bigIntVal.divide(bigTen);
          lastVal=rem;
          count++;
      }
      StringBuilder sb = new StringBuilder();
      while(!stack.isEmpty()) {
            String tmp = stack.pop();
            if(tmp.trim() == null ? "" != null :!tmp.trim().equals(""))
                sb.append(tmp).append(" ");

            tmp=null;
      }

      return sb.toString();
   }
   private static String getPhrase(long val) {
      return getPhrase(BigInteger.valueOf(val));
   }
   public static void main (String... arg) {
      Random random = new Random();
      StringBuilder sb = new StringBuilder();
      for(int i=5 ; i< 404; i++) {
         sb.append(random.nextInt(Integer.MAX_VALUE));
         if((i % 4) == 0) {
            System.out.println(getPhrase(new BigInteger(sb.toString())));
            sb = sb.delete(0, sb.length());
         }
      }
      System.out.println(getPhrase(new BigInteger("10000000000000000000000000000000000000")));
      System.out.println(getPhrase(new BigInteger("1000000000000000000000000000000000000000")));
      System.out.println(getPhrase(12));
   }
}

Sample output :

2019084295145236989942767198734845132 :TWENTY SINGHAR NINETEEN SHISHT EIGHT MAHA ANT FORTY TWO ANT NINETY FIVE PARAARDHA FOURTEEN MADH FIFTY TWO PADHA THIRTY SIX ANK NINETY EIGHT UDPADHA NINETY NINE SHANKH FORTY TWO PADMA SVENTY SIX NEEL SVENTY ONE KHARAB NINETY EIGHT ARAB SVENTY THREE CRORE FORTY EIGHT LAKH FORTY FIVE THOUSAND ONE HUNDRED THIRTY TWO



17685736938032205301469886857658602952 :ONE MAHA SINGHAR SVENTY SIX SINGHAR EIGHTY FIVE SHISHT SVENTY THREE MAHA ANT SIXTY NINE ANT THIRTY EIGHT PARAARDHA THREE MADH TWENTY TWO PADHA FIVE ANK THIRTY UDPADHA FOURTEEN SHANKH SIXTY NINE PADMA EIGHTY EIGHT NEEL SIXTY EIGHT KHARAB FIFTY SEVEN ARAB SIXTY FIVE CRORE EIGHTY SIX LAKH TWO THOUSAND NINE HUNDRED FIFTY TWO


188075721934012020118426066451328688285 :EIGHTEEN MAHA SINGHAR EIGHTY SINGHAR SVENTY FIVE SHISHT SVENTY TWO MAHA ANT NINETEEN ANT THIRTY FOUR PARAARDHA ONE MADH TWENTY PADHA TWENTY ANK ELEVEN UDPADHA EIGHTY FOUR SHANKH TWENTY SIX PADMA SIX NEEL SIXTY FOUR KHARAB FIFTY ONE ARAB THIRTY TWO CRORE EIGHTY SIX LAKH EIGHTY EIGHT THOUSAND TWO HUNDRED EIGHTY FIVE


1948118649156585325517962972061668035829 :ONE ADANT SINGHAR NINETY FOUR MAHA SINGHAR EIGHTY ONE SINGHAR EIGHTEEN SHISHT SIXTY FOUR MAHA ANT NINETY ONE ANT FIFTY SIX PARAARDHA FIFTY EIGHT MADH FIFTY THREE PADHA TWENTY FIVE ANK FIFTY ONE UDPADHA SVENTY NINE SHANKH SIXTY TWO PADMA NINETY SEVEN NEEL TWENTY KHARAB SIXTY ONE ARAB SIXTY SIX CRORE EIGHTY LAKH THIRTY FIVE THOUSAND EIGHT HUNDRED TWENTY NINE


204863758419285559291413447710559361980 :TWENTY MAHA SINGHAR FORTY EIGHT SINGHAR SIXTY THREE SHISHT SVENTY FIVE MAHA ANT EIGHTY FOUR ANT NINETEEN PARAARDHA TWENTY EIGHT MADH FIFTY FIVE PADHA FIFTY NINE ANK TWENTY NINE UDPADHA FOURTEEN SHANKH THIRTEEN PADMA FORTY FOUR NEEL SVENTY SEVEN KHARAB TEN ARAB FIFTY FIVE CRORE NINETY THREE LAKH SIXTY ONE THOUSAND NINE HUNDRED EIGHTY


3916657783179516484698379641343107348 :THIRTY NINE SINGHAR SIXTEEN SHISHT SIXTY FIVE MAHA ANT SVENTY SEVEN ANT EIGHTY THREE PARAARDHA SEVENTEEN MADH NINETY FIVE PADHA SIXTEEN ANK FORTY EIGHT UDPADHA FORTY SIX SHANKH NINETY EIGHT PADMA THIRTY SEVEN NEEL NINETY SIX KHARAB FORTY ONE ARAB THIRTY FOUR CRORE THIRTY ONE LAKH SEVEN THOUSAND THREE HUNDRED FORTY EIGHT


1917366768157998405319508789161849348702 :ONE ADANT SINGHAR NINETY ONE MAHA SINGHAR SVENTY THREE SINGHAR SIXTY SIX SHISHT SVENTY SIX MAHA ANT EIGHTY ONE ANT FIFTY SEVEN PARAARDHA NINETY NINE MADH EIGHTY FOUR PADHA FIVE ANK THIRTY ONE UDPADHA NINETY FIVE SHANKH EIGHT PADMA SVENTY EIGHT NEEL NINETY ONE KHARAB SIXTY ONE ARAB EIGHTY FOUR CRORE NINETY THREE LAKH FORTY EIGHT THOUSAND SEVEN HUNDRED TWO


138032179816868494848413728402016652665 :THIRTEEN MAHA SINGHAR EIGHTY SINGHAR THIRTY TWO SHISHT SEVENTEEN MAHA ANT NINETY EIGHT ANT SIXTEEN PARAARDHA EIGHTY SIX MADH EIGHTY FOUR PADHA NINETY FOUR ANK EIGHTY FOUR UDPADHA EIGHTY FOUR SHANKH THIRTEEN PADMA SVENTY TWO NEEL EIGHTY FOUR KHARAB TWO ARAB ONE CRORE SIXTY SIX LAKH FIFTY TWO THOUSAND SIX HUNDRED SIXTY FIVE


1263492396193160191019064383581246894343 :ONE ADANT SINGHAR TWENTY SIX MAHA SINGHAR THIRTY FOUR SINGHAR NINETY TWO SHISHT THIRTY NINE MAHA ANT SIXTY ONE ANT NINETY THREE PARAARDHA SIXTEEN MADH ONE PADHA NINETY ONE ANK ONE UDPADHA NINETY SHANKH SIXTY FOUR PADMA THIRTY EIGHT NEEL THIRTY FIVE KHARAB EIGHTY ONE ARAB TWENTY FOUR CRORE SIXTY EIGHT LAKH NINETY FOUR THOUSAND THREE HUNDRED FORTY THREE


10000000000000000000000000000000000000 :ONE MAHA SINGHAR


1000000000000000000000000000000000000000 :ONE ADANT SINGHAR


12 :TWELVE