Code Kata: SuDoKu Solver

This week I am interested in the Sudoku puzzle, I am thinking how to use program to solve the SuDoKu. I almost spent a week for it. At first I was inspired the a book called “Wicked Cool Ruby Scripts”in chapter 5, it provides a ruby source code for the SuDoKu solver. I spent two days to understand the code. The problem is the book does not describe the algorithm in details, and I don’t know how to debug the ruby code in TextMate. So it took me a longer time to finally understand the whole logic.

Actually it uses the brutal backtrack method. Try fill a number in one cell, then recursively call itself, if it works, continue, then return, try another, until it fills all the 81 cells. I made some changes based on the original code, the major changes once the solver find the solution then exit the loop, while in the original code the program will continue loop until the end, I compare my changes with the original code, the total times executed and execution time both drops about 50%.

Here is my modified code:


The logic is really simple: first reads the puzzle, construct the one dimension array.
The key is in Solver method:
From 81 cells, pick one empty cell, calculate the candidate numbers of this cell,
Pick one number, fill the cell,
Recusively call itself, continue try to fill another empty cell.
If the program could not find the candidate for the cell, or the program iterate all the cell’s candidate number, then erase the number, backtrack;
If the program fills all the 81 cells, return true

The algorithm of getCanidates(j) is easy:
Build an array of 1-9
Find each cell with the same row, erase the number in the cell from the array;
Find each cell with the same column, erase the number in the cell from the array;
Find each cell with the same sub block, erase the number in the cell from the array.
The left in the array are candidates


From this code, I understand more about the backtrack and recursive method. This code belongs to the depth-first backtrack search.

Donald Knuth’s Dancing Link algorithm is quite interesting, there are lots of articles and blog about using it solving the SuDoKu. But right now for me it is really hard to understand.

For SuDoKu, there are following thins to do in future:
1. Implement the SuDoKu solver using Dancing Link algorithm
2. Find out the algorithm of SuDoKu Generator, like how to generate a puzzle based on difficulty, and how to find out there is only one solution.
3. How to implement an algorithm that simulate human's solving logic?

Here are several link about dancing link and SoDuKu:
Dancing Link C implementation
Dancing link for Java
Donald Knuth Home page
Donald Knuth's Dancing links paper(pdf)

code Kata 3, How many n-digit binary numbers are there that don't have two adjacent 1 bits?

Today I read a new Kata from Dave's CodeKataCodeKata fifteen: A diversion

The Question:
Think of binary numbers: sequences of 0's and 1's. How many n-digit binary numbers are there that don't have two adjacent 1 bits? For example, for three-digit numbers, five of the possible eight combinations meet the criteria: 000, 001, 010, 011, 100, 101, 110, 111. What is the number for sequences of length 4, 5, 10, n?

Having worked out the pattern, there's a second part to the question: can you prove why that relationship exists?

The answer is in the replied comments, it is a fibonacci series:
f(1) = 2 => 0,1
f(2) = 3 => 00, 01, 10
f(n) = f(n-1) + f(n-2)

Now I will try to explain why it is like this using my own thoughts:
f(3) can be thought of 2 groups, one is begin with 0, and the other is begin with 1
begin with 0 group: 0 + xx, => f(2)
begin with 1 group: since it begins with 1, it must be followed by 0, so it becomes 10 + x , =>f(1)

so f(3) = f(2) + f(1)

same thing with f(n)
begins with 0: 0 + xxx...x ( n-1 digit) => f(n-1)
begins with 1: 10 + xxx..x ( n-2 digit) => f(n-2)

so f(n) = f(n-1) + f(n-2)

Now I will give the solution in Ruby:

def non_adjacent_one_array(n)
if(n == 1)
["0", "1"]
elsif (n== 2)
["00", "01", "10"]
else
array1 = non_adjacent_one_array(n-1).collect { |i| "0"+i}
array2 = non_adjacent_one_array(n-2).collect { |i| "10"+i}
array1+array2
end
end

s=non_adjacent_one_array(5)
puts "n=5, number is #{s.length}\n"
puts s
puts "\n"

1.upto(10) do |i|
s = non_adjacent_one_array(i)
puts "n=#{i} number=#{s.length}\n"
end


And the results are:

n=5, number is 13
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101

n=1 number=2
n=2 number=3
n=3 number=5
n=4 number=8
n=5 number=13
n=6 number=21
n=7 number=34
n=8 number=55
n=9 number=89
n=10 number=144

Build an iPhone application without Interface Builder

I am still a beginner of iPhone developer. I finished a tutorial book. Right now I am trying to read another one. But I found my problem: I only know how to build the application using the Interface Builder, but I don’t know the underlying mechanism of the application, for example; what is the life cycle of the application, how does the application delegate, ViewController and View interact each other?

Using Interface Builder makes the application developing very easy, it separate out the presentation logic with the application logic. I like this idea, but for beginner only know the Interface Builder is not enough:
- It makes your job easier, but also hides the application information, and blocks you to understand the underlying mechanism. For example, When I investigate the sample code LocateMe, it uses UITabBarController and NavigationgController for each tab, when I read the source code, I don’t know the where the variable navigationController come from, I don’t know how it created. It is set in the nib file, and you have to read the reference document to see how it works.

- Sometime you need to customize your app, Interface Builder will not help you, you have to do it programmatically. For example, I tried to add a UIScrollView using the interface builder, but I found it does not scroll as I expected.

I google the solution and found this video is helpful:

Building iPhone Applications without Interface Builder from Troy Mcilvena on Vimeo.


And this blog:Why would you use Interface Builder for iPhone Development?

I just summarize the detailed steps:

1. In Xcode wizard, choose Window-based Application, then delete the MainWindow.xib, remove the property with the key ‘Main nib file base name’ (the raw key name is ‘NSMainNibFile’) from your Info.plist file.

2. In main.m, add your AppDelegate class name in the last argument of the UIApplicationMain method.

int main(int argc, char *argv[]) {

NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
int retVal = UIApplicationMain(argc, argv, nil, @"NoNibAppDelegate");
[pool release];
return retVal;
}

3. In AppDelegate class, initialize and configure the window and Controller object.

For example: NoNibAppDelegate.m

- (void)applicationDidFinishLaunching:(UIApplication *)application {

// Override point for customization after application launch
window = [[UIWindow alloc] initWithFrame:[ [UIScreen mainScreen] bounds]];

RootViewController *root = [[RootViewController alloc] init];
[window addSubview:root.view];
[window makeKeyAndVisible];
}

4. In your ViewController class, implement the loadView() method
From UIViewController Reference document: If you create your views manually, you must override this method and use it to create your views

- (void)loadView
{

UIView *contentView = [[ButtonView alloc] initWithFrame:[[UIScreen mainScreen] applicationFrame]];

self.view = contentView;
[contentView release];


}

5. In View class, implement the initWithFrame: method
“If you create a view object programmatically, this method is the designated initializer for the UIView class.” - From UIView reference document.

- (id)initWithFrame:(CGRect)frame {
if (self = [super initWithFrame:frame]) {

self.backgroundColor = [UIColor lightGrayColor];

UILabel *label = [[UILabel alloc] initWithFrame:CGRectMake(0.0f, 0.0f, 320.0f, 30.0f)];
label.text = @"Hello World";
label.center = self.center;
label.backgroundColor = [UIColor clearColor];
label.textAlignment = UITextAlignmentCenter;

[self addSubview:label];
}
return self;
}

6. You might want to register an UIControl event listener:
- Intitialize the UIControl object, for example a UIButton:

[buttonPress addTarget:self action:@selector(buttonClicked:) forControlEvents:UIControlEventTouchUpInside];

- implement the event call back method:

-(void)buttonClicked:(id)sender
{
UIButton *button = (UIButton *)sender;
NSString *text = button.currentTitle;


NSString *string = [ [NSString alloc] initWithFormat:@"Button %@ pressed.",text];

NSLog(@"button clicked. button title:%@", text);

self.label.text = string;
[string release];

}

You can download my sample code from here.


From this investigation, I understand the iPhone application life cycle and event flow; know the underlying mechanism and get the confidence to customize application in future.

For learning iPhone, I am trying to follow the Shu-Ha-Ri learning model: at the Shu level, which is called following and copying, so I just follow one book: Beginning iPhone 3 Development: Exploring the iPhone SDK. I just follow step by step, copy every line of the code from the book. This is a very good book for the beginner who never touch the apple development environment like me, but it does not cover the deeper information, which I am really want to understand now.

So I think it is time for me to go to Ha level: which is breaking, it means trying to collecting different information and trying to read different article and books, Now I learned that it is time for me and I am ready to read Apple reference document, read advanced iPhone books, investigate the sample code, joining the forum, and practice.


Tutorial gives you a starting point, Interface Builder is a crutch, it is time for you to remove them if you want to get improved.

Here is my reading list for iPhone in fufure:
- Apple iPhone reference documents and API documents
- Apple iPhone sample codes
- The iPhone Developer's Cookbook: Building Applications with the iPhone SDK
This is a really good book, but not for beginner, it tells your more detailed information which is not covered in other books. I am waiting for the 2nd edtion.


References:
- iPhone Application Programming Guide

- The iPhone Developer's Cookbook: Building Applications with the iPhone SDK

Code Kata 2 - Reverse words in a string using Ruby

Last time I posted the blog Code Kata - Reverse words in a string, in that blog I provided the java solution. Today I will try to solve this problem using Ruby.

Question: How to reverse words in a string?
For example, given a string "The quick brown fox jumped over the lazy dog", reversed string needs to be “dog lazy the over jumped fox brown quick The”.
And this time there is no memory constraint, we just focus on providing an elegant and concise code.

The algorithm has two steps:
1. First reverse the entire string by character
For example: "The quick brown fox jumped over the lazy dog" becomes
“god yzal eht revo depmuj xof nworb kciuq ehT”
2. Then reverse each word by character
For example: “god yzal eht revo depmuj xof nworb kciuq ehT” becomes
“dog lazy the over jumped fox brown quick The”

The ruby code would be:

The method reverse_string() will return an array instead of a string, but it does not matter here. You can see how easy to implement using Ruby compare to Java!

My Presentation: The OO design principles

The OO Design Principles from Steve Zhang

This is my presentation about OO software design principles: http://www.slideshare.net/intellizhang/the-oo-design-principles


The whole slide is copied from the following two books:
1. Agile Software Development: Principles, Patterns, and Practices, by Uncle Bob

2. The Pragmatic Programmer: From Journeyman to Master, by Dave Thomas and Andy Hunt