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, June 20, 2011
Fun with Prime numbers
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|
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;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.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
Subscribe to:
Posts (Atom)