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. |
Thursday, March 10, 2011
Eight Queens - 2
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
Sunday, February 6, 2011
Stacks are crazy - 3
As thinking further, about fixed number of iterations, we can use insertion sort. Start inserting the element into the right position.
import java.util.Random;
import java.util.Stack;
public class Main3 {
static Random rg = new Random();
static int temp;
public static void main(String... arg) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
for(int i=0; i<15; i++)
s1.push(rg.nextInt(100));
System.out.println("Unsorted : " + s1.toString());
while(!s1.isEmpty()) {
temp = s1.pop();
while(!s2.isEmpty() && s2.peek() < temp)
s1.push(s2.pop());
s2.push(temp);
}
System.out.println("Sorted :"+ s2);
}
}
import java.util.Random;
import java.util.Stack;
public class Main3 {
static Random rg = new Random();
static int temp;
public static void main(String... arg) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
for(int i=0; i<15; i++)
s1.push(rg.nextInt(100));
System.out.println("Unsorted : " + s1.toString());
while(!s1.isEmpty()) {
temp = s1.pop();
while(!s2.isEmpty() && s2.peek() < temp)
s1.push(s2.pop());
s2.push(temp);
}
System.out.println("Sorted :"+ s2);
}
}
Stacks are crazy -2
Little better solution for the same problem. This will decrease execution time to half.
Improvements to algorithm:
While moving elements from one stack to other, highest elements will be reaching the bottom of first stack. In the same way while moving the elements back to first stack, I have added the logic to move smaller elements to the bottom of second stack. This way half of the executions can be reduced from first solution.
Improvements to algorithm:
While moving elements from one stack to other, highest elements will be reaching the bottom of first stack. In the same way while moving the elements back to first stack, I have added the logic to move smaller elements to the bottom of second stack. This way half of the executions can be reduced from first solution.
import java.util.Random;
import java.util.Stack;
public class Main2 {
static Random rg = new Random();
static int temp, size;
public static void main(String[] args) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
for(int i=0; i<16; i++)
s1.push(rg.nextInt(100));
System.out.println("Unsorted : " + s1.toString());
size = s1.size()-1;
while(size > 0) {
temp = s1.pop();
for(int j=0; j<size; j++) {
if(temp <= s1.peek()) {
s2.push(temp);
temp=s1.pop();
} else {
s2.push(s1.pop());
}
}
s1.push(temp);
temp= s2.pop();
for(int j=0; j<size-1; j++) {
if(temp >= s2.peek()) {
s1.push(temp);
temp=s2.pop();
} else {
s1.push(s2.pop());
}
}
s2.push(temp);
size= size-2;
}
System.out.println("Sorted :"+ s1 +" "+s2);
while(!s2.empty())
s1.push(s2.pop());
System.out.println("Sorted :"+ s1);
}
}
Output:
Unsorted : [53, 67, 26, 54, 73, 33, 65, 86, 5, 73, 61, 91, 12, 33, 78, 93]
Sorted :[93, 91, 86, 78, 73, 73, 67, 65] [5, 12, 26, 33, 33, 53, 54, 61]
Sorted :[93, 91, 86, 78, 73, 73, 67, 65, 61, 54, 53, 33, 33, 26, 12, 5]
I am sure, still we can optimize a lot :) since irrespective of the stack order it performs fixed number of iterations.
Stacks are crazy
One of my close friend asked me an interesting puzzle (Not sure who asked him :))
Puzzle goes something like this:
“2 stacks are given, one with full of numbers (in random order) and other is empty. Using just one integer variable, order the numbers (ascending or descending) with space and time constraints”.
Please try without seeing my solution. You might solve it in a better way.
It started with bubble sort however we will not be able to solve completely using bubble sort as the data structure is stack. The algorithm went several changes and final result was something different to bubble sort :). This will be of O(n2) space is O(1):
import java.util.Random;
import java.util.Stack;
public class Main {
static Random rg = new Random();
static int temp, size;
public static void main(String[] args) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
for(int i=0; i < 16; i++)
s1.push(rg.nextInt(100));
System.out.println("Unsorted : " + s1.toString());
size = s1.size()-1;
while(size > 0) {
temp = s1.pop();
for(int j=0; j < size; j++) {
if(temp >= s1.peek()) {
s2.push(temp);
temp=s1.pop();
} else {
s2.push(s1.pop());
}
}
s1.push(temp);
for(int k = size; k > 0 ; k--)
s1.push(s2.pop());
size= size-1;
}
System.out.println("Sorted :"+ s1);
}
}
S1 is in decending order moving to S2 will be ascending.
The above algorithm is finding the higest element in stack and moving the same to bottom of S1 and repeating the process upto complete stack is sorted.
Puzzle goes something like this:
“2 stacks are given, one with full of numbers (in random order) and other is empty. Using just one integer variable, order the numbers (ascending or descending) with space and time constraints”.
Please try without seeing my solution. You might solve it in a better way.
It started with bubble sort however we will not be able to solve completely using bubble sort as the data structure is stack. The algorithm went several changes and final result was something different to bubble sort :). This will be of O(n2) space is O(1):
import java.util.Random;
import java.util.Stack;
public class Main {
static Random rg = new Random();
static int temp, size;
public static void main(String[] args) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
for(int i=0; i < 16; i++)
s1.push(rg.nextInt(100));
System.out.println("Unsorted : " + s1.toString());
size = s1.size()-1;
while(size > 0) {
temp = s1.pop();
for(int j=0; j < size; j++) {
if(temp >= s1.peek()) {
s2.push(temp);
temp=s1.pop();
} else {
s2.push(s1.pop());
}
}
s1.push(temp);
for(int k = size; k > 0 ; k--)
s1.push(s2.pop());
size= size-1;
}
System.out.println("Sorted :"+ s1);
}
}
S1 is in decending order moving to S2 will be ascending.
The above algorithm is finding the higest element in stack and moving the same to bottom of S1 and repeating the process upto complete stack is sorted.
Sunday, September 26, 2010
Two way sync
Two way sync |
This time I have attempted to solve another important task - Backup. Everyone understands the importance of taking backup of personal files and it is difficult to find a program which does this job smartly. I googled and explored a few which don't suite my requirements, so I made a small attempt here to write a program myself than using third party tools. As part of this, first I started with two way sync. This code generates the list of missed files in both directories by walking through and sync in both the ways. The following code uses the power of new NIO2 from JDK7. To run this code you need JDK7 |
import java.io.IOException; import java.nio.file.*; import java.nio.file.attribute.*; import java.util.*; import java.util.concurrent.locks.*; import java.util.concurrent.ConcurrentSkipListMap; import java.util.Map.Entry; import static java.nio.file.FileVisitResult.*; import static java.nio.file.StandardCopyOption.*; public class AstuteSync { private final static Lock lock = new ReentrantLock(); private static Map<String,String> diffList = new ConcurrentSkipListMap<String,String>(); private final static String SOURCE = "/extra/movies"; private final static String TARGET = "/extra/movies_back"; static 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) { toList(dir); return CONTINUE; } @Override public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) { toList(file); return CONTINUE; } private void toList(Path file) { try { lock.lock(); if(diffList.remove(file.toString().replace(head, "")) == null) diffList.put(file.toString().replace(head, ""),file.toString()); lock.unlock(); } catch (Exception exc) { exc.printStackTrace(); } } } public static void printDiffList() { if (diffList.isEmpty()) { System.out.println("Both folders are in Sync."); } else { Iterator<String> ite = diffList.values().iterator(); System.out.println("Folder Diff:"); while (ite.hasNext()) System.out.println(ite.next()); } } public static void sync() { Set<Entry<String,String>>entries = diffList.entrySet(); for (Map.Entry<String,String>entry : entries) { try { Paths.get(entry.getValue()).copyTo(Paths.get( (entry.getValue().startsWith(TARGET) ? SOURCE : TARGET) + System.getProperty("file.separator") + entry.getKey()), COPY_ATTRIBUTES); } catch (IOException ex) { ex.printStackTrace(); } } } public static void main(String... arg) throws Exception { final Path source = Paths.get(SOURCE); final Path target = Paths.get(TARGET); if(!source.exists() || !target.exists()) throw new Exception("Path doesn't exists"); new Thread(new Runnable(){ public void run() { Files.walkFileTree(source, new SyncFileVisitor(SOURCE));}}).start(); new Thread(new Runnable() {public void run() { Files.walkFileTree(target, new SyncFileVisitor(TARGET));}}).start(); Runtime.getRuntime().addShutdownHook(new Thread() { @Override public void run() { printDiffList(); if (!diffList.isEmpty()) sync(); } }); } } |
$ java AstuteSync /extra/movies/k.txt /extra/movies/p.txt /extra/movies_back/test.t $java AstuteSync Both folders are in Sync. |
Subscribe to:
Posts (Atom)