Kata 3 – Magic Numbers

This kata comes from the website of one of my old lecturers. It was an interesting problems to tackle and there are a lot of different ways to approach it.

159 * 48 = 7632 contains each of the numbers 1-9. The program finds and displays all the other simple multiplications that also contain each of the numbers 1-9.

I started by creating an algorithm that generated a string containing all the numbers I wanted. This was exceptionally tricky to do. So my algorithm just starts counting from 123456789. Each number is checked that it contains only one of each number. Because I’m using only 9 digit numbers there isn’t any need to validate any further than that. If the number is valid it’s passed through to another checker that systematically changes the number into a simple multiplication equation. If the equation is valid I win.

The application takes a ridiculously long time to run. After completion I thought of a way to potentially half the run time but I didn’t implement it because I’ve been obsessing about this for far too long.

This was done largely using TDD but I actually wrote the test in Obj C and then transferred the program to C# because of a memory problem I was having in XCode.

 static void Main(string[] args)  
{
string equationString;
List createdStrings = new List();
//create an array of strings ///159 * 48 = 7632
for (int i = 123456789; i <= 987654321; i++){
equationString = i.ToString();
//validate strings with the checker
if (equationCharacterChecker(equationString)){
if (equationChecker(equationString)){
createdStrings.Add(equationString);
}
}
}
}
public static bool equationCharacterChecker(string equation) {
SortedSet setOfEquationCharacters = new SortedSet();
setOfEquationCharacters.Add("1"); setOfEquationCharacters.Add("2"); setOfEquationCharacters.Add("3");
setOfEquationCharacters.Add("4"); setOfEquationCharacters.Add("5"); setOfEquationCharacters.Add("6");
setOfEquationCharacters.Add("7"); setOfEquationCharacters.Add("8"); setOfEquationCharacters.Add("9");
string character;
for (int i = 0; i < equation.Count(); i++)
{
character = equation[i].ToString();
if (setOfEquationCharacters.Contains(character)){
setOfEquationCharacters.Remove(character);
} else {
return false;
}
}
return true;
}
//159 * 48 = 7632
public static bool equationChecker(string equation) {
int length = equation.Length;
for (int m = 1; m < equation.Length-2; m++){
for (int e = m+1; e < equation.Length-1; e++){
int multiplicand = Convert.ToInt32(equation.Substring(0, m));
int multiplier = Convert.ToInt32(equation.Substring(m, e-m));
int product = Convert.ToInt32(equation.Substring(e));
if (multiplicand * multiplier == product) {
Console.Write(multiplicand + " * " + multiplier + " = " + product + "\n");
return true;
}
}
}
return false;
}

Kata2 Binary Search

I did my second Kata this morning. I thought I’d tackle the binary search problem in following with http://codekata.pragprog.com
The idea here is that you have some huge, but sorted, list and you need to find a single element within that list as efficiently as possible. As lists grow in size just traversing through the list element by element can take a really long time for higher numbers.

The binary search solution basically means you start in the middle continually divide the list in half until you find your element. For huge lists it’s excellent because it doesn’t matter where the desired element is in the list, it will always find it quickly, one drawback though it will more often than not, take several searches to locate the element. So you need to weigh the efficiency lost against the efficiency gained. 

I’m quite proud of my attempt. I’ve tested it with a list of 50,000,000 integers and it never takes more than 26 searches to find any element. It’ll support an array of any size and it should support any data type, but I’ll need to test that at a later time. This is a recursive approach as it was the approach that comes most naturally to me. I’m going to have a look at an iterative at a later time.

This was developed using TDD, kind of. I had to test this from a few different directions at once, namely efficiency and accuracy. I couldn’t work out a good way of testing for them both at the same time so I’m leaving what test code I did end up with out of this post.

 -(NSNumber*)binarySearch:(NSArray*)array forInt:(NSNumber*)anInt {  
int numberOfSearches = 1;
int min = 0;
int max = array.count;
int searchingFor = [anInt integerValue];
int indexOfGuess = [array indexOfObject:[array objectAtIndex:(max + min) / 2]];
int guess = [[array objectAtIndex:indexOfGuess] integerValue];
NSLog(@"%d searches", numberOfSearches);
while (searchingFor != guess){
if (max - min <= 2){
return [NSNumber numberWithInt:-1];
}
if (searchingFor < guess){
max = indexOfGuess;
}
if (searchingFor > guess){
min = indexOfGuess;
}
guess = [[array objectAtIndex:(max + min) / 2] integerValue];
indexOfGuess = [array indexOfObject:[array objectAtIndex:(max + min) / 2]];
numberOfSearches++;
NSLog(@"%d searches", numberOfSearches);
}
return [NSNumber numberWithInt:indexOfGuess];
}

My First TDD Kata – Objective C – Xcode 4.5 – OCUnit – ARC

Ok, so I’ve taken the entire day to work on a programming Kata using TDD.

I started with the same exercise that I was given during an interview for an industrial placement a few weeks ago http://codekata.pragprog.com/2007/01/code_kata_one_s.html just so that I had an idea of where to start.

This code has taken me all day but for good reason.
Firstly I’ve never used TDD before, nor do I have any idea of how to use OCUnit. I have quite limited experience in programming generally so this was all a bit of a learning curve for me.
Secondly, this paradigm is basically the opposite of the way in which I’ve learned to program. I find it very, very difficult to think this way.

I’m actually quite pleased with the result. As applications go it’s functional, seems robust and the design isn’t far off from what I would have designed otherwise. It will be interesting to come back to this Kata later and see what differences there are.

What did I learn?

TDD is a concept, I could hear the criticisms screaming out at me as I did it but once I got going it actually started to come really naturally.

Two problems.
From time to time a tricky change comes up. For example in my application I made the decision to change from scanning in Strings to scanning in item objects. Looking back now I can see how I maybe could have handled this differently and maybe made things a little bit easier on myself. But still there was a lot of time spend pondering this, while outside of TDD the change would have been a no-brainer, just change an argument here and a return type there an done. TDD meant that I wound up writing a whole new function for it to save failing the older tests. I’m hoping that some more practice in TDD will help me to handle this type of situation in the future.

There was a real sense of fragility when programming. When implementing the BOGOF feature I found myself tip-toeing around the code trying to change as little as possible as not to fail my older tests, again I hope that experience will take care of this but I’m not so sure.

The design comes from the refactoring stage really. Refactoring seems to be the time to do a little bit of ‘Crystal Balling’ a little bit and try to introduce some good code and design practices.

Oh and if you’re wondering about the weird way I’ve worked with NSNumber, well I can’t really explain myself, I just had a really hard time with it and the primitives. I may do my next kata in a different language.

My Code.
Tests

 -(void)testCheckOut {  
NSNumber *expected = [NSNumber numberWithDouble:0.0];
NSNumber *result = [scanner checkOut];
STAssertEquals([expected doubleValue], [result doubleValue], @"Expected %g, but returned %g", [expected doubleValue], [result doubleValue]);
}
-(void)testScanItem {
NSNumber *expected = [NSNumber numberWithDouble:0.60];
[scanner scanItem:(@"apple")];
NSNumber *result = [scanner checkOut];
STAssertEquals([expected doubleValue], [result doubleValue], @"Expected %g, but returned %g", [expected doubleValue], [result doubleValue]);
}
-(void)testScanningTwoItems {
NSNumber *expected = [NSNumber numberWithDouble:1.20];
[scanner scanItem:(@"apple")];
[scanner scanItem:(@"apple")];
NSNumber *result = [scanner checkOut];
STAssertEquals([expected doubleValue], [result doubleValue], @"Expected %g, but returned %g", [expected doubleValue], [result doubleValue]);
}
-(void)testScanningAnItemWithADifferentPrice{
double expected = 0.7;
[scanner scanItem:@"banana"];
double result = [[scanner checkOut] doubleValue];
STAssertEquals(expected, result, @"Expected %g, but returned %g", expected, result);
}
-(void)testScanningTwoItemsWithDifferentPrices {
double expected = 0.7+0.6;
[scanner scanItem:@"apple"];
[scanner scanItem:@"banana"];
double result = [[scanner checkOut] doubleValue];
STAssertEquals(expected, result, @"Expected %g, but returned %g", expected, result);
}
-(void)testScanningMultipleItemsObjectsOfVaryingPrice {
Item* apple = [[Item alloc] initWithDescription:@"apple" andPrice:[NSNumber numberWithDouble:0.6]];
Item* banana = [[Item alloc] initWithDescription:@"banana" andPrice:[NSNumber numberWithDouble:0.7]];
Item* orange = [[Item alloc] initWithDescription:@"orange" andPrice:[NSNumber numberWithDouble:0.5]];
double expected = 0.0;
[scanner scanItem:apple.description];
expected += [apple.price doubleValue];
[scanner scanItem:banana.description];
expected += [banana.price doubleValue];
[scanner scanItem:orange.description];
expected += [orange.price doubleValue];
[scanner scanItem:apple.description];
expected += [apple.price doubleValue];
double result = [[scanner checkOut] doubleValue];
STAssertEquals(expected, result, @"Expected %g, but returned %g", expected, result);
}
-(void)testScanningItemAsObject {
Item* apple = [[Item alloc] initWithDescription:@"apple" andPrice:[NSNumber numberWithDouble:0.6]];
double expected = 0.6;
[scanner scanObject:apple];
double result = [[scanner checkOut] doubleValue];
STAssertEquals(expected, result, @"Expected %g, but returned %g", expected, result);
}
-(void)testScanningMultipleObjects {
Item* apple = [[Item alloc] initWithDescription:@"apple" andPrice:[NSNumber numberWithDouble:0.6]];
Item* banana = [[Item alloc] initWithDescription:@"banana" andPrice:[NSNumber numberWithDouble:0.7]];
double expected = apple.price.doubleValue + banana.price.doubleValue;
[scanner scanObject:apple];
[scanner scanObject:banana];
double result = [[scanner checkOut] doubleValue];
STAssertEquals(expected, result, @"Expected %g, but returned %g", expected, result);
}
-(void)testBOGOFWithTwoOfTheSameItem {
Item* apple = [[Item alloc] initWithDescription:@"apple" andPrice:[NSNumber numberWithDouble:0.6]];
double expected = apple.price.doubleValue;
[scanner scanObject:apple];
[scanner scanObject:apple];
double result = [[scanner checkOut] doubleValue];
STAssertEquals(expected, result, @"Expected %g, but returned %g", expected, result);
}
-(void)testBOGOFWithMultipleVaryingItems {
Item* apple = [[Item alloc] initWithDescription:@"apple" andPrice:[NSNumber numberWithDouble:0.6]];
Item* banana = [[Item alloc] initWithDescription:@"banana" andPrice:[NSNumber numberWithDouble:0.7]];
double expected = 0.0;
[scanner scanObject:apple];
expected += apple.price.doubleValue;
[scanner scanObject:apple];
[scanner scanObject:banana];
expected += banana.price.doubleValue;
[scanner scanObject:banana];
[scanner scanObject:banana];
expected += banana.price.doubleValue;
double result = [[scanner checkOut] doubleValue];
STAssertEquals(expected, result, @"Expected %g, but returned %g", expected, result);
}

Application

 -(PriceScanner*)init {  
self.total = [NSNumber numberWithDouble:0.0];
self.list = [[NSMutableArray alloc] init];
return self;
}
-(void)scanObject:(Item*)item {
[self.list addObject:item];
}
-(void)scanItem:(NSString*)item {
if ([item isEqualToString:@"apple"]){
self.total = [NSNumber numberWithDouble:[self.total doubleValue] + 0.6];
}
if ([item isEqualToString:@"banana"]){
self.total = [NSNumber numberWithDouble:[self.total doubleValue] + 0.7];
}
if ([item isEqualToString:@"orange"]){
self.total = [NSNumber numberWithDouble:[self.total doubleValue] + 0.5];
}
}
-(void)applyBOGOF{
double newTotal = [self.total doubleValue];
NSMutableSet *tempSet = [[NSMutableSet alloc] init];
for (Item* i in self.list){
if ([tempSet containsObject:i.description]){
newTotal -= [i.price doubleValue];
[tempSet removeObject:i.description];
} else {
[tempSet addObject:i.description];
}
}
self.total = [NSNumber numberWithDouble:newTotal];
}
-(NSNumber*)checkOut {
double newTotal = [self.total doubleValue];
for (Item* i in self.list){
newTotal += i.price.doubleValue;
}
self.total = [NSNumber numberWithDouble:newTotal];
[self applyBOGOF];
return self.total;
}