Recursion

I found it very useful to explain the recursion. I read it at everything2.com.

A child couldn't sleep, so her mother told her a story about a little frog,
who couldn't sleep, so the frog's mother told her a story about a little bear,
who couldn't sleep, so the bear's mother told her a story about a little weasel...
who fell asleep.
...and the little bear fell asleep;
...and the little frog fell asleep;
...and the child fell asleep.

This is the best explanation of recursion I've heard. It could probably
be recast to be less cutesy, but it really gets to what's going on with recursion in a very nice way: Stuff happens on the way in, you hit an endpoint, and other stuff happens in reverse order on the way back out as it all unwinds. For somebody who doesn't "get" recursion yet, this is not a bad map to start with.

Tricky Java Code

Java class without main method:

class Main
{
    static
    {
        System.out.println("This java program have run without the run method");
        System.exit(0);
    }
}

Java syntax quirk:

public class Oddity
{
    public static void main(String[] args)
    {
        http://amadamala.blogger.com
        System.out.println("Why is the URL allowed above?");
    }
}

Ans:   
----
 http://amadamala.blogger.com ==   lable : // comment here
                                     |              |
                                     |              |
                                     v              v 
                                   http:         //amadamala.blogger.com             


References:
[1] http://www.java-tips.org/
[2] http://www.javapuzzlers.com/

FifteenPuzzle Game :: SourceCode

I'm posting the code of a game that I wrote recently. Game name is FifteenPuzzle or N-Puzzle.

You can download the file here.

File Name: FifteenPuzzle.java

import java.awt.*; import java.awt.event.*; import javax.swing.*; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; /** * It is a sliding puzzle that consists of a grid of numbered squares * with one square missing, and the labels on the squares jumbled up * * <p> The <code><b>n-puzzle</b></code> is known in various versions, * including the <code></b>8 puzzle, the 15 puzzle</code></b>, and with * various names. If the grid is <b>3×3</b>, the puzzle is called the * <code><b>8-puzzle </b></code> or <code><b>9-puzzle</b></code>. If * the grid is <b>4×4</b>, the puzzle is called the <code><b>15-puzzle * </b></code> or <code><b> 16-puzzle </b></code>. The goal of the * puzzle is to unjumble the squares by only making moves which slide * squares into the empty space, in turn revealing another empty space * in the position of the moved piece.</p> */ /** * * @author Anil Madamala * Copyright (c) 2007,2008 Anil Madamala * Any problems contact: amadamala+code@gmail.com * */ public class FifteenPuzzle implements ActionListener { /* Dimention of the Board */ private static final int DIM = 4; // For N * N board DIM = N /* Total number of cells in the board */ final int SIZE = DIM * DIM; /* Win state */ final String[] WIN = new String[SIZE-1]; /* Initial Height of the board*/ private static final int HEIGHT = 400; /* Initial Width of the board*/ private static final int WIDTH = 400; /* Initial empty cell in the board*/ private int emptyCell = DIM * DIM; /* 15 puzzle Board, of size (4 X 4)*/ private JButton[][] board = new JButton[DIM][DIM]; private JFrame frame; private JPanel panel = new JPanel(); // Suppresses default constructor, ensuring non-instantiability. public FifteenPuzzle() { if(DIM <= 1){ JOptionPane.showMessageDialog(null, "You Win The Game."); System.err.println("Dimention Should be greater than 1 to play"); System.exit(0); } // Initialize the win state for (int i = 1; i < SIZE; i++) { WIN[i-1] = Integer.toString(i); } System.out.println("Win State:" + Arrays.asList(WIN) ); } public static void main(String[] args) { FifteenPuzzle game = new FifteenPuzzle(); game.initializeBoard(); /* Initializes the 15-puzzle game board */ } /** * Gives index value corresponding to [row,col] of a square * @param i, row * @param j, column * @return the index of the corresponding to the row and column */ private int getIndex(int i, int j) { return ((i * DIM) + j); // i * 4 + j } /** * Generates the random intitial state for the game. * Assigns unique random number to each square */ private void initializeBoard() { ArrayList<Integer> intialList = new ArrayList<Integer>(SIZE); // Repeat until creation of solvable initial board for (boolean isSolvable = false; isSolvable == false;) { // create ordered list intialList = new ArrayList<Integer>(SIZE); for (int i = 0; i < SIZE; i++) { intialList.add(i, i); } // Shuffle the list Collections.shuffle(intialList); // Check list can be solvable or not isSolvable = isSolvable(intialList); } System.out.println("Initial Board state:" + intialList); // Assigns unique random number to each square for (int index = 0; index < SIZE; index++) { final int ROW = index / DIM; // row number from index final int COL = index % DIM; // column number from index board[ROW][COL] = new JButton(String.valueOf(intialList.get(index))); // intializes the empty square and hide it if (intialList.get(index) == 0) { emptyCell = index; board[ROW][COL].setVisible(false); } // Decorating each square board[ROW][COL].setCursor(Cursor.getPredefinedCursor(Cursor.HAND_CURSOR)); board[ROW][COL].setBackground(Color.BLACK); board[ROW][COL].setForeground(Color.GREEN); board[ROW][COL].addActionListener(this); panel.add(board[ROW][COL]); } // Initializes the Frame frame = new JFrame("Shuffle Game"); frame.setLocation(400, 200); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.pack(); frame.setSize(HEIGHT, WIDTH); // Initializes the panel panel.setLayout(new GridLayout(DIM, DIM)); panel.setBackground(Color.GRAY); // Initializes the content pane java.awt.Container content = frame.getContentPane(); content.add(panel, BorderLayout.CENTER); content.setBackground(Color.GRAY); frame.setVisible(true); } /** * Verifies the board for solvability. * For more detals of solvability goto URL: * http://mathworld.wolfram.com/15Puzzle.html * @param initialList * @return true, if the initial board can be solvable * false, if the initial board can't be solvable */ private boolean isSolvable(ArrayList<Integer> list) { int inversionSum = 0; // If this sum is even it is solvable for (int i = 0; i < list.size(); i++) { // For empty square add row number to inversionSum if (list.get(i) == 0) { inversionSum += ((i / DIM) + 1); //add Row number continue; } int count = 0; for (int j = i + 1; j < list.size(); j++) { // No need need to count for empty square if (list.get(j) == 0) { continue; } else if (list.get(i) > list.get(j)) { // If any element greater count++; // than seed increse the } // inversionSum } inversionSum += count; } // if inversionSum is even return true, otherwise false return ((inversionSum & 1) == 0) ? true : false; } /** * If any button in the board is pressed, it will perform the * required actions associated with the button. Actions like * checking isAdjacent(), swapping using swapWithEmpty() and also * checks to see whether the game is finished or not. * * @param event, event performed by the player * @throws IllegalArgumentException, if the <tt>index = -1 </tt> */ public void actionPerformed(ActionEvent event) throws IllegalArgumentException { JButton buttonPressed = (JButton) event.getSource(); int index = indexOf(buttonPressed.getText()); if (index == -1) { throw (new IllegalArgumentException("Index should be between 0-15")); } int row = index / DIM; int column = index % DIM; // If pressed button in same row or same column makeMove(row, column); // If the game is finished, "You Win the Game" dialog will appear if (isFinished()) { JOptionPane.showMessageDialog(null, "You Win The Game."); } } /** * Gives the index by processing the text on sqare * @param cellNum, number on the button * @return the index of the button */ private int indexOf(String cellNum) { for (int ROW = 0; ROW < board.length; ROW++) { for (int COL = 0; COL < board[ROW].length; COL++) { if (board[ROW][COL].getText().equals(cellNum)) { return (getIndex(ROW, COL)); } } } return -1; // Wrong input returns -1 } /** * Checks the row or column with empty square * @return true, if we pressed the button in same row or column * as empty square * false, otherwise */ private boolean makeMove(int row, int col) { final int emptyRow = emptyCell / DIM; // Empty cell row number final int emptyCol = emptyCell % DIM; // Empty cell column number int rowDiff = emptyRow - row; int colDiff = emptyCol - col; boolean isInRow = (row == emptyRow); boolean isInCol = (col == emptyCol); boolean isNotDiagonal = (isInRow || isInCol); if (isNotDiagonal) { int diff = Math.abs(colDiff); // -ve diff, move row left if (colDiff < 0 & isInRow) { for (int i = 0; i < diff; i++) { board[emptyRow][emptyCol + i].setText( board[emptyRow][emptyCol + (i + 1)].getText()); } } // + ve Diff, move row right else if (colDiff > 0 & isInRow) { for (int i = 0; i < diff; i++) { board[emptyRow][emptyCol - i].setText( board[emptyRow][emptyCol - (i + 1)].getText()); } } diff = Math.abs(rowDiff); // -ve diff, move column up if (rowDiff < 0 & isInCol) { for (int i = 0; i < diff; i++) { board[emptyRow + i][emptyCol].setText( board[emptyRow + (i + 1)][emptyCol].getText()); } } // + ve Diff, move column down else if (rowDiff > 0 & isInCol) { for (int i = 0; i < diff; i++) { board[emptyRow - i][emptyCol].setText( board[emptyRow - (i + 1)][emptyCol].getText()); } } // Swap the empty square with the given square board[emptyRow][emptyCol].setVisible(true); board[row][col].setText(Integer.toString(0)); board[row][col].setVisible(false); emptyCell = getIndex(row, col); } return true; } /** * Checks whehere game is finished or not * @return true, if the board is in final state * false, if the board is not in final state */ private boolean isFinished() { // Check 1-15 elements whether they are in right position or not for (int index = WIN.length - 1; index >= 0; index--) { String number = board[index / DIM][index % DIM].getText(); if (!number.equals(WIN[index])) { return false; // If any of the index is not aligned } } return true; } }

Comments and suggestions will be great.



           -Anil Madamala

Loop Unrolling

Loop Unrolling

Topic : Loop Unrolling
source of the topic : Code Complete2

Loop Unrolling, is a technique for optimizing parts of computer programs. The goal of loop unrolling is to reduce the amount of loop housekeeping.
Note: Loop unrolling undesirable if you are concerned about readability of the code.

// Example of normal loop i=0 while ( i < count ) { a[ i ] = i; i++; }

Use this technique only when you desire for code optimization. It will severely hurts program readability

// Loop unrolled once i = 0; while ( i < count -1 ) { a[ i ] = i; a[ i + 1 ] = i + 1; // Unrolling once i = i + 2; } if ( i == count) { // These lines pick up the case a[ i - 1 ] = i - 1;// that might fall through the } // cracks if the loop went by // twos instead of by ones

The technique replaced the original a[ i ] = i line with two lines, and i is incremented by 2 rather than by 1. The extra code after the while loop is needed when count is odd and the loop has one iteration left after the loop terminates.
We can see a gain of 43% in performance with loop unrolling once.

// Loop unrolled twice i = 0; while ( i < count - 2 ) { a[ i ] = i; a[ i + 1 ] = i+1; a[ i + 2 ] = i+2; i = i + 3; } if ( i <= count - 1 ) { a[ count - 1 ] = count - 1; } if ( i == count - 2 ) { a[ count -2 ] = count - 2; }

We can see a gain of 43% in performance with loop unrolling once.
The results indicate that further loop unrolling can result in further time savings, but not necessarily so, as the Java measurement shows.

Tips on Using loop statement in Java

Topic: Tips on using the loops statements
Source of Topic: Effective Java, Programming Language Guide, by Joshua Bloch.

"The most powerful technique for minimizing the scope of a local variable is to declare it
where it is first used."

Prefer for loop over to while loop.
Reason: for loop has a chance of initializing the loop variables, limiting the scope to exact region where they're needed.

For example, here is the preferred way of iterating over a collection:

for ( Iterator i = c.iterator(); i.hasNext(); i++ ) { doSomething ( i.next() ) ; }

To see why this for loop is preferable to the more obvious while loop, consider the following
code fragment

Iterator i = c.iterator(); while (i.hasNext()) { doSomething(i.next()); } ... Iterator i2 = c2.iterator(); while (i.hasNext()) { // BUG! doSomethingElse(i2.next()); }

Above error is resulted with the habit of cut-and-paste the code: It initializes a new loop variable, i2, but uses the old one,
i, which unfortunately is still in scope. Above code doesn't give any compile error or doesn't throw any exception. Runs silently.
Instead of iterating over c2, the second loop terminates immediately, giving the false impression that c2 is empty. Because the
program errs silently, the error can remain undetected for a long time.

If the analogous cut-and-paste error were made in conjunction with the preferred for loop
idiom, the resulting code wouldn't even compile. The loop variable from the first loop would
not be in scope at the point where the second loop occurred:

for (Iterator i = c.iterator(); i.hasNext(); ) { doSomething(i.next()); } ... // Compile-time error - the symbol i cannot be resolved for (Iterator i2 = c2.iterator(); i.hasNext(); ) { doSomething(i2.next()); }

Moreover, if you use the for loop idiom, it's much less likely that you'll make the cut-and-
paste error, as there's no incentive to use a different variable name in the two loops. The loops
are completely independent, so there's no harm in reusing the loop variable name. In fact, it's
stylish to do so.

Iterating over random access list: ( examples of random access lists: ArrayList, Vector etc. )

//Common Practice for (int i = 0; i < list.size(); i++) { doSomething(list.get(i)); } // High-performance idiom for iterating over random access lists for (int i = 0, list.size(); i < n; i++) { doSomething(list.get(i)); }

This idiom is useful for random access List implementations such as ArrayList and Vector
because it is likely to run faster than the “preferred idiom” above for such lists. The important
thing to notice about this idiom is that it has two loop variables, i and n, both of which have
exactly the right scope. The use of the second variable is essential to the performance of the
idiom. Without it, the loop would have to call the size method once per iteration, which
would negate the performance advantage of the idiom. Using this idiom is acceptable when
you're sure the list really does provide random access; otherwise, it displays quadratic
performance.

Printing the arrays in Java programming language

// Common practice of printing the array in Java for( int i = 0; i < array.length; i++) { System.out.println(array[i]); } // Best way of printing the array in Java System.out.println( Arrays.asList(array) ) ;

Loop over an Array in java:

// Loop through an Array using for each for( int intVal : array ) { doSomething(intVal); }

Divide and Conquer algorithms, trick

Possible mistake in implementing Divide and Conquer algorithms is, In many cases you may need to divide the input range.

Take Binary search as an example:
in each step we need to calculate "mid".

//Common practice of doing this:
// Broke - if (start + end) > Integer.MAX_VALUE
// Mid value will be assigned with -ve value.
mid = (start + end) / 2;                                                      

// Better way to avoid the problem
mid = start + (end - start)/2 ;

checking the oddity of a integer number in java

From Jashua Bloch's "Java Puzzlers" book.

// Worng way to check the oddity
public boolean isOdd(int num){
return (num % 2 == 1) // Broken- for all -ve odd numbers
}

// Right Solution
public boolean isOdd(int num){
return (num % 2 != 0)
}

// Much better and Faster
public boolean isOdd(int num){
return (num & 1)
}

Binary Search in java by Joshua Bloch

1:     public static int binarySearch(int[] a, int key) {
2:         int low = 0;
3:         int high = a.length - 1;
4:
5:         while (low <= high) {
6:             int mid = (low + high) / 2;
7:             int midVal = a[mid];
8:
9:             if (midVal < key)
10:                 low = mid + 1
11:             else if (midVal > key)
12:                 high = mid - 1;
13:             else
14:                 return mid; // key found
15:         }
16:         return -(low + 1);  // key not found.
17:     }

The bug is in this line:   int mid =(low + high) / 2;

It
fails for large values of the int variables low and high. Specifically,
it fails if the sum of low and high is greater than the maximum
positive int value (pow(2 , 31) - 1). The sum overflows to a negative
value, and the value stays negative when divided by two. In C this
causes an array index out of bounds with unpredictable results. In
Java, it throws ArrayIndexOutOfBoundsException.

So what's the best way to fix the bug? Here's one way:

    int mid = low + ((high - low) / 2);

Probably faster, and arguably as clear is:

  int mid = (low + high) >>> 1;

How to design a good API and Why it matters

How to Design a Good API and Why it Matters by Joshua Bloach(author of Effective Java)