Friday, July 22, 2011

JavaScript to become a new technology stack?

Last month I mentioned about the Microsoft's effort towards HTML5 and JavaScript adoption. This month I have more interesting news :) ... JavaScript is about to become a new technology stack.

For example:

1. Do you need a cloud IDE for JavaScript coding? No problems, see cloud9ide.com. Code and host your code.

2. Do you need server side JavaScript? No problems use node.js. This is a "tool" pretty much like Java (i.e. compile and execute - JIT). It integrates perfectly with WebSockets and WebWorkers added as part of HTML5.

3. Do you need anything more complex (e.g. enterprise oriented)? Use services like Wakanda, it even has a built in data store. Alternatively, use MongoDB (JSON storage) with node.js.

To conclude, it is possible to build quite complex web, mobile, desktop (in terms of HTML5 offline apps) applications using just JavaScript.

Sunday, July 10, 2011

Sudoku game or humans vs. machines (computers in this case)

Few days ago, a friend of mine posted the following link on his wall on Facebook. The main question from that article was "how long will it take to crack ...the world's hardest Sudoku?". I felt like being challenged.

I am not a Sudoku fan, however my wife and my son are. Just to annoy them (not because I am a bad person :), but because I was looking for a way to sort the Sudoku puzzles in a quicker way, when being asked to assist them ... so, "I am lazy" is a more precise definition) and because I am a software engineer, I wrote a long time ago (of course I was inspired, it's not entirely my contribution) a little piece of Java code to resolve such puzzles. As a result, I decided to test it.

Here is the code:

import java.util.*;
import java.io.*;

public class ResolveSudoku {
 private static final int[] sudokuMatrix = {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,0,0,0,0,0,0,0,0,
         0,0,0,0,0,0,0,0,0};

 // load the content from file
 public static void load(String file) throws Exception {
  String str = null;
  int line = 0;
  BufferedReader br = new BufferedReader(new FileReader(file));

  while ((str = br.readLine()) != null) {
   if (str.trim().length() == 0 || str.startsWith("#")) 
    continue;

   if (line >= 9) {
    line = 10;
    break;
   }

   String[] vls = str.split(",");
   if (vls.length != 9) {
    br.close();
    throw new Exception("Line " + (line + 1) + 
     " has illegal number of elements!");
   }

   for (int i = 0; i < 9; ++i) {
    int value = Integer.parseInt(vls[i].trim());
    if (value < 0 || value > 9) {
     br.close();
     throw new Exception("Line " + (line + 1) + 
      " position " + (i + 1) + " has illegal value!");
    }
    sudokuMatrix[line*9 + i] = value;
   }

   ++line;
  }

  br.close();
  if (line != 9) throw new Exception("File " + file + 
   " has illegal number of lines!");
 }

 // print the content of the sudoku matrix
 public static void printMatrix() {
  for (int i = 0; i < 81; ++i) {
   if (i != 0 && i % 3  == 0) System.out.print(" ");
   if (i != 0 && i % 9  == 0) System.out.println();
   if (i != 0 && i % 27 == 0) System.out.println();

   if (sudokuMatrix[i] == 0) System.out.print(".");
   else System.out.print(sudokuMatrix[i]);
  }
  System.out.println("\n");
 }

 private static boolean check(int row, int col, int value) {
  // check if row is ok
  int tmp = row * 9;
  for (int i = 0; i < 9; ++i) {
   if (sudokuMatrix[tmp + i] == value) 
    return false;
  }

  // check if column is ok
  for (int i = 0; i < 9; ++i) {
   if (sudokuMatrix[i*9 + col] == value) 
    return false;
  }

  // check if box is ok
  tmp = (row / 3)*27 + (col / 3)*3;
  if (sudokuMatrix[tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;

  tmp += 7;
  if (sudokuMatrix[tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;

  tmp += 7;
  if (sudokuMatrix[tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;
  if (sudokuMatrix[++tmp] == value) return false;

  return true;
 }

 public static boolean findSolution(int row, int col) {
  if (row == 9) {
   row = 0;
   if (++col == 9) return true;
  }

  int pos = row * 9 + col;
  if (sudokuMatrix[pos] != 0) return findSolution(row + 1, col);

  for (int i = 1; i <= 9; ++i) {
   if (check(row, col, i)) {
    sudokuMatrix[pos] = i;
    if (findSolution(row + 1, col)) return true;
   }
  }

  // reset the value back to zero 
  sudokuMatrix[pos] = 0; 
  return false;
 }

 public static void main(String[] args) throws Exception {
  load(args[0]);
  printMatrix();

  long start = System.currentTimeMillis();
  boolean res = findSolution(0, 0);
  long ex_time = System.currentTimeMillis() - start;

  if (res) printMatrix();
  else System.out.println("No solution!");

  System.out.println("Execution time: " + ex_time + "ms.");
 }
}

It's, basically, a routine that reads the puzzle's matrix from a file and another one that performs a brute force (i.e. analysing all the possible cases) in form of (I would say) an elegant recursive method call. Having the following input:

0,0,5,3,0,0,0,0,0
8,0,0,0,0,0,0,2,0
0,7,0,0,1,0,5,0,0
4,0,0,0,0,5,3,0,0
0,1,0,0,7,0,0,0,6
0,0,3,2,0,0,0,8,0
0,6,0,5,0,0,0,0,9
0,0,4,0,0,0,0,3,0
0,0,0,0,0,9,7,0,0
The problem was solved in ~30 milliseconds (after the byte code was JIT-ed on my "2.13Ghz, Core 2 Duo with SSD on board" laptop). And the answer was:

145 327 698
839 654 127
672 918 543

496 185 372
218 473 956
753 296 481

367 542 819
984 761 235
521 839 764