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:

def reverse_string(s)
s.reverse().scan(/[\w]+/).collect { |w| w.reverse()}
end

r = reverse_string("The quick brown fox jumped over the lazy dog")
puts r

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

View more presentations from Steve Zhang.

This is my presentation about OO software design principles: http://www.slideshare.net/intellizhang/the-oo-design-principles
I created this presentation at least 4 months ago in July this summer. I realized the problem in our team: there is no software design, no refactoring, so many duplicated code ... etc, the code is just messy and hard to maintain. The worse is that most of my colleagues does not realize the problem, it seems they are quite comfortable with the messy code, seems that messy code is reasonable; or they feel the problem but don't know how to solve it, and my manager think that we are so busy now, we don't have time to think about the design, and refactoring is just some extra stuff. WHICH IS TOTALLY WRONG!
That is the reason I made this presentation, try to inspire my colleagues and my manager that there are better ways to coding, we should follow the right way, then we can deliver faster and better product.

So far there are not many feedback in my team for this slide, I don't know when I can make this presentation in my team, so I decide to put it in public, hope this can be useful for other people.

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

Code Kata – Reverse words in a string

Dave Thomas creates a website called Code Kata, Who encourage developers improve their skills by keep practicing coding, trying to find better solutions for some questions.

Today I met an interesting 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”. The thing is you can not use extra memory to do it, you had better manipulate the reverse logic in the original text string.

To solve this question, I remembered I read a good book several years ago, it is called Programming Pearls ,written by John Bentley.

In chapter 2, section “The power of Primitive”, the author gives the solution of transform an array vector, which is clean, elegant and efficient. I used this solution to solve this problem.
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”

You see it is pretty easy, right? No need extra memeory, no need substring.This is the power of the algorithm.

Here I post the java version of the solution, you can easily implement this algorithm in C or other language.

public class StringRerverse {

private int wordStartIndex;
private int wordEndIndex;
private StringBuffer sBuffer;

String reverse(String string)
{

this.sBuffer = new StringBuffer(string);

sBuffer.reverse();

int size = sBuffer.length();
int pos = 0;

while(pos < size)
{
if(findNextWord(pos) == true)
{
reverseWord(sBuffer,wordStartIndex,wordEndIndex);
pos = wordEndIndex+1;
}
else
{
break;
}
}


return sBuffer.toString();

}
boolean findNextWord(int startFrom)
{
int start = startFrom;

while (start< sBuffer.length()-1 && sBuffer.charAt(start) == ' ')
{
start++;
}
if(start == sBuffer.length() -1 )
{
return false;
}

wordStartIndex = start;

int end = start+1;
while(end < sBuffer.length()-1 && sBuffer.charAt(end) != ' ' )
{
end++;
}
if(end == sBuffer.length() -1 )
{
wordEndIndex = end;
}
else
{
wordEndIndex= end-1;
}
return true;
}

void reverseWord(StringBuffer sBuffer,int wordStartIndex, int wordEndIndex)
{
int length = wordEndIndex - wordStartIndex + 1;
for(int j = 0; j<length/2; j++)
{

int startIndex = wordStartIndex + j;
int endIndex = wordEndIndex - j;
char c = sBuffer.charAt(startIndex);
sBuffer.setCharAt(startIndex, sBuffer.charAt(endIndex));
sBuffer.setCharAt(endIndex, c);
}
}



public static void main(String[] args)
{
StringRerverse reverse = new StringRerverse();

String string = new String("The quick brown fox jumped over the lazy dog");
String reverseString = reverse.reverse(string);
System.out.println("reversed String: "+reverseString);

}
}

From Good to Great Developer

Last week I watch a presentation called “From good to great developer“ from www.infoq.com.
Here is the link : http://www.infoq.com/presentations/Good-to-Great-Developer-Chris-Hedgate

Chris Hedgate made a really great presentation. He pointed out that good developer writes code quickly but hard to maintain; but great developer has long term goal and try to write clean code and make it easier to maintain.

He also gave the advices how to become a great developer. I really like the 4-stage learning model he introduced: unconscious incompetence, conscious incompetence, conscious competence and unconscious competence. The learner in different stage will take different actions: inspiration, training, practice and reflection.
I am an agile believer; I’ve been trying my best to write clean code and trying to improve the design. But I am really frustrated by my colleagues and my manager. They don’t think keep code clean and refactoring is necessary, just something extra features make it looks beautiful. Now I know the reason: they are at the first state - unconscious incompetence, the best solution is inspiring them first. You need to be a good coach. You need to be lead by example. You have to become great first.

Talking about becoming a great developer, which is the same idea coming from Agile. It means craftsmanship, professionalism, discipline, and mastery. I think every serious developer should have a goal to become a great developer or master programmer, just like kong-fu master or samurai. It is a whole life’s practice.

Being a great developer is not an easy job. You need to understand the agile principles, understand design patterns, have disciplines and patience to write clean codes and keep refactoring; you have to constantly reflect yourself; you need to keep learning new technologies. And you need to help other people and try to motivate and inspire them. This is raising the bar, it is hard, but this is the only way to create a remarkable career for you, the only way to give you a passion, and the only way to transcend yourself.

Here I add some other videos which share the same philosophy:

1. Craftsmanship and Ethics, by Robert Martin:
http://www.infoq.com/presentations/craftmanship-ethics

2. Developing Expertise: Herding Racehorses, Racing Sheep, by Dave Thomas
http://www.infoq.com/presentations/Developing-Expertise-Dave-Thomas

Dave Thomas is the author of “Pragmatic Programmer, from journeyman to master”. This video talks about the Dreyfus model, which is 5-stage learning model. The details about it is in the Book “Pragmatic learning and thinking” by Andy Hunt.

3. I Come to Bury Agile, Not to Praise It, by Alistar CockBurn
http://www.infoq.com/presentations/cockburn-bury-not-praise-agile
This video talks about a Shu-Ha-Ri, a 3-stage learning model, I first learned Shu-Ha-Ri from his book “Agile Software Development”

4. Deliberate Practice in Software Development, by Marry Poppendieck,
http://www.infoq.com/presentations/poppendieck-deliberate-practice-in-software-development
Marry Poppendieck is regarded the first person who apply Toyota’s Lean technology into software development, this video she provide the 10-year rule theory, emphasizes the craftsmanship and clean code.

5. Productive Programmer: On the Lam from the Furniture Police, by Neal Ford
http://library.theserverside.com/detail/RES/1242309506_447.html?asrc=vcatssc_sitepost_05_14_09
The author of “Productive programmer”, he talked about the principles in his book, the book of “Peopleware” and “pragmatic learning and thinking”

6. Transcendence and Passing Through the Gate, by Dave West
http://www.infoq.com/presentations/transcendence-gate-dave-west

This video is really interesting, it talks about agile, but he use the concept of Zen. He mentioned the famous 10 Bulls pictures which describe 10 different stages of a human being to describe the agile development.

Learning from the Book Of Five Rings

Miamoto Musashi was a very famous Japanese saumari, who wrote a book called The book of Five Rings. I first heard of him by Alistir CockBurn’s book – Agile Software Devleopment.

The good thing is Alistair pointed out what we can learn from his book into our software development. Here is what Alistair pointed out:

• Do not develop an attachment to any one weapon or anyone school of fighting.
Use the rang of them without getting stuck in anyone.
• Practice and observe reflectively.
Practice hard, win big (pointed out by Jeff Sutherland, the SCRUM creator)
• Win
Pay more attention to winning than to looking good,
“Do not do anything useless”

Here I also would like to copy what his rules for learning the art ( from page 41):
1. Think of what is right and true.
2. Practice and cultivate the science.
3. Become acquainted with the arts.
4. Know the principles of the crafts.
5. Understand the harm and benefit in everything.
6. Learn to see everything accurately.
7. Become aware of what is not obvious.
8. Be careful even in small matters.
9. Do not do anything useless.

The interesting thing is that in the book, Mushasi use carpentry as a metaphor for mastering his science of martial art. (from page 9, Likening the Science of Martial Arts to Carpentry). It seems every word can be used to software development, used as principles of mastering programmer's skills.

In future I will post more about this book.