What is a Surrogate Key?

What is a surrogate key? It is a key that is always implemented with the help of an identity column. Then what is an identity column? It is a column that is auto-generated by a SQL Server based on its seed value and its incremental value. Identity columns are always INT, which means a surrogate key is always INT as well. It cannot have any NULL values or repeating values. Surrogate key is a logical key, which means it does not exist on a SQL Server.

Let's take a look how to set up a surrogate key.

CREATE TABLE Temp(
  ID INT IDENTITY(1,2), -- it will go 1,3,5...
  Name VARCHAR(100))

INSERT INTO Temp VALUES ('J-hood') -- no need to insert ID values
GO 5 -- insert 5 times

Three Methods to Create Tables in SQL

These days, I'm being trained to be a SQL developer so I'm going to post a lot of stuff about SQL for my sake of understanding and learning and for your sake of entertainment :) So! When you create tables, there are three methods to consider.

Let's look at the first one. The first method has full control over constraint names that are used to modify constraints later. No particular order of table creation is required, which means there is no code dependency.

-- Create Sales and Product tables
CREATE TABLE Sale (
  SaleID INT NOT NULL,
  ProductID INT NOT NULL,
  ClientID INT NOT NULL,
  Qty INT NOT NULL,
  Total MONEY)

CREATE TABLE Product (
  ProductID INT NOT NULL,
  ProdName VARCHAR(50),
  ProdDesc VARCHAR(100),
  QoH INT,
  UniPrice MONEY)

-- Add a PK on Sale
ALTER TABLE Sale
ADD CONSTRAINT PK_Sale_SaleID
  PRIMARY KEY (SaleID)

-- Dropping a PK
ALTER TABLE Sale
DROP CONSTRAINT PK_Sale_SaleID

-- Add a composite PK
ALTER TABLE Sale
ADD CONSTRAINT PK_Sale_SaleID_ProductID
  PRIMARY KEY (SaleID, ProductID)

-- Add a PK on Product
ALTER TABLE Product
ADD CONSTRAINT PK_Product_ProdID
  PRIMARY KEY (ProductID)

-- Add a FK on Sale
ALTER TABLE Sale
ADD CONSTRAINT FK_Sale_Product_ProductID
  FOREIGN KEY (SaleID) REFERENCES Product(ProductID)

The second method of creating tables is not as good as other methods. You will have no control over constraint names because they are auto-generated by a SQL Server. The order of creating tables are important, which means there is code dependency.

CREATE TABLE Sales2(
  SalesID INT NOT NULL PRIMARY KEY,
  ProductID INT REFERENCES Product(ProductID),
  ClientID INT REFERENCES Client(ClientID),
  Qty INT NOT NULL,
  Total MONEY)

The last method is better than the second one but not as good as the first method since the first one is the best one. You have the full control over the constraint names but still there is code dependency.

CREATE TABLE Sales3(
  SalesID INT NOT NULL
  ProductID INT,
  ClientID INT,
  Qty INT NOT NULL CONSTRAINT DK_Sales3_Qty DEFAULT 10,
  Total MONEY -- No comma here!!
    CONSTRAINT PK_Sales3_SalesID PRIMARY KEY (SalesID)
    CONSTRAINT FK_Sales3_Product_ProductID FOREIGN KEY (ProductID)
        REFERENCES Product(ProductID)
    CONSTRAINT FK_Sales3_Client_ClientID FOREIGN KEY (ClientID)
        REFERENCES Client(ClientID)
    CONSTRAINT CK_Sales3_Qty CHECK (Qty >= 10))

Project Euler Problem 15

As I said on the previous post, I have been doing Project Euler. My goal for now is to finish first 50 problems. I have gotten first 10 so far. Then, I will go for next ten and then next ten and hopefully I can reach to the 50th problem. So I was browsing through other 40 problems and the Problem 15 was more intriguing to me than other problems. Maybe it was because it was more visual unlike other problems I had solved. So I dove right into it. Here is the problem:

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 20x20 grid?

Before talking about a 2x2 grid, let's see a 1 x 1 grid, where top left corner, 1, is the starting point and the bottom right corner, 4, is the goal point.

1-2
| |
3-4

If you can only take right and bottom paths and cannot backtrack as the problem describes, there are only two ways to get to 4 (1 - 2 - 4 and 1 - 3 - 4).

So here is a 2 by 2 grid.

1-2-3
| | |
4-5-6
| | |
7-8-9

As the problem explains, there are six ways to get to 9 from 1.

1 - 2 - 3 - 6 - 9
1 - 2 - 5 - 6 - 9
1 - 2 - 5 - 8 - 9
1 - 4 - 5 - 6 - 9
1 - 4 - 5 - 8 - 9
1 - 4 - 7 - 8 - 9

This isn't really a necessary step to find the solution but I redrew the 2 x 2 grid to a tree form, where you can only take down paths, so I could understand better.

    1
   / \
  2   3
 / \ / \
4   5   6 
 \ / \ /
  7   8
   \ /
    9

Did the same for the 1 x 1 grid.

    1
   / \
  2   3
   \ /
    4 

As you noticed, they form a diamond shape. Do the same thing for a 3 x 3 grid. Then you will find out that a 3 x 3 grid has 20 paths. So a 1 x 1 grid has 2 paths, a 2 x 2 grid has 6 paths and a 3 x 3 grid has 20 paths. This progression of 2, 6 and 20 were familiar to me and I found out that these numbers are related to Pascal's Triangle.

        1  - 0th row
       1 1  
      1(2)1  - 2nd row (1 by 1 grid)
     1 3 3 1
   1 4 (6) 4 1  - 4th row (2 by 2 grid)
  1 5 10 10 5 1
1 6 15 (20) 15 6 1 - 6th row (3 by 3 grid)

So beginning from the 2nd row the going down every other row, the middle number of each row represents the number of paths. Here is the formula to find a certain number in Pascal's Triangle:

r! / i!(r - i)! with rth row from the top and ith position from the left to right.

What we need to find in this problem is the number of paths for a 20x20 grid. Let's plug the numbers into the formula.

40! / 20!(40 - 20)! = 137846528820

The answer is 137,846,528,820 paths. A LOT of paths. Here is an interesting thing. If you place the diamond shape tree, as it is and fitting the top part of the triangle, the very bottom point of the diamond is the same as the number of the paths. For example, let's see the 2x2 grid again.

    1
   / \
  2   3
 / \ / \
4   5   6 
 \ / \ /
  7   8
   \ /
    9

If you place this diamond on the Pascal's Triangle…

    1
   / \
  1   1
 / \ / \
1   2   1 
 \ / \ /
  3   3
   \ /
   (6)

Very interesting, isn't it?! But how the number of paths and Pascal's Triangle are related? I did some research and I found out that it's because Pascal's Triangle determines the coefficients which arise in binomial expansions and this grid problem is also very related to binomial expansions.

Let's analyze problem again. Assuming there is an n x n grid,

1. all the paths have size 2 x n;
2. you can only go R(right) or B(bottom) from each point. For a 2x2 grid, the paths in R and B are RRDD, RDRD, RDDR, DRRD, DRDR and DDRR;
3. the strings for a grid has the same number of R and D.

So if we rephrase the problem observing the three above points:

How many different strings of size 2xn, consisting of n Rs and n Ds, are there?

This is also solved using binomial expansions: 2n! / (n! x n!) with the size n. And this is essentially the same with the formula above: r! / i!(r - i)! with rth row from the top and ith position from the left to right.

To conclude this post, the solving Problem 15 was not hard because luckily I knew the few first number progression of Pascal Triangle. But what I importantly learned from solving this problem was how the Pascal Triangle and binomial coefficient and I look forward to learning experience like this solving next Project Euler problems.

Source:
[1] Wikipedia articles on Pascal's triangle and Binomial coefficient.
[2] The guy who already solved this problem. His way is much simpler and helped me understand the connecting factors between Pascal's triangle and Binomial coefficient (http://joaoff.com/2008/01/20/a-square-grid-path-problem/)

Project Euler Problem 1 to 5

I found this website called Project Euler. They have a bunch of math problems that can be only solved with computer programming (maybe it's because some of the problems are too hard or the numbers are very large).

Here is the link for the website: http://projecteuler.net

It's kinda fun because it has this feature that's similar to PS3 trophies and xBox achievements. For example, if you solve the first three problems, you earn this achievement called 'Baby Steps'. Other fun example is 'Fibonacci Fever' that you can earn if you solve the first twelve Fibonacci numbered problems. And here I have solved five first problems. They are not necessarily hard but I wanted to keep up with my math and Lisp skill. It sucks the pre class brush doesn't support Lisp so I'm uploading it as C. Bare with me with that. Even though I didn't put any comment, it's still very easy to understand. I used both recursive and iterative.

;;;;; ProjectEuler.net 
;;;;; Problem 1 ~ 5
;;;;; Source code by J-hood
;;;;; Last updated on Feb-29-2011

;;;; Problem 1 ;;;;
;; If we list all the natural numbers below 10 that are multiples of 3 or 5, 
;; we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all 
;; the multiples of 3 or 5 below 1000.
;; Run: (problem1)
;; Answer: 233168
(defun problem1 ()
  (let ((sum 0))
    (dotimes (i 1000)
      (if (OR (= 0 (mod i 3)) (= 0 (mod i 5)))
          (setf sum (+ sum i))))
    (print sum)))


;;;; Problem 2 ;;;;
;; Each new term in the Fibonacci sequence is generated by adding the previous 
;; two terms. By starting with 1 and 2, the first 10 terms will be:
;; 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
;; By considering the terms in the Fibonacci sequence whose values do not exceed
;; four million, find the sum of the even-valued terms.
;; Run: (problem2)
;; Answer: 4613732 
(defun problem2 ()
  (let ((sum 0) (i 2))
    (loop
     (setf fibNum (fib i))
     (incf i)
     (when (> fibNum 4000000) (return))
     (if (= 0 (mod fibNum 2))
         (setf sum (+ sum fibNum))))
    (print sum)))

(defun fib (n)
  "Simple fibonacci number function"
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))


;;;; Problem 3 ;;;;
;; The prime factors of 13195 are 5, 7, 13 and 29.
;; What is the largest prime factor of the number 600851475143 ?
;; Run: (problem3 600851475143 2)
;; Answer: 6857
(defun problem3 (n i)
  (cond
    ((= (/ n i) 1) (print n))
    ((= 0 (mod n i)) (problem3 (/ n i) i))
    (t (loop
        (if (OR (= i 2) (= i 3) (/= i 4) (= i 5) (/= i 6) (= i 7)) 
            (incf i)
            (incf i 2))
        (if (is-prime i) (return)))
       (problem3 n i))))

(defun is-prime (n)
  "Check if n is a prime number. 
http://www.informatimago.com/develop/lisp/l99/p31.lisp"
  (cond
    ((minusp n)          (is-prime (- n)))
    ((= 1    n)          nil)
    ((member n '(2 3 5 7)) t)
    ((evenp  n)          nil)
    (t
     (loop
        :with root     = (isqrt n)
        :with divisors = (loop :for i :from 3 :to root :by 2 :collect i)
        :for d = (pop divisors)
        :if (zerop (mod n d))
        :do (return nil)
        :else :do (setf divisors (delete-if (lambda (x) (zerop (mod x d))) divisors))
        :while divisors
        :finally (return t)))))


;;;; Problem 4 ;;;;
;; A palindromic number reads the same both ways. The largest palindrome made 
;; from the product of two 2-digit numbers is 9009 = 91 * 99. Find the largest 
;; palindrome made from the product of two 3-digit numbers.
;; Run: (problem4)
;; Answer: 906609
(defun problem4 ()
  (let ((result 0))
    (loop for num1 from 999 downto 100 do
          (loop for num2 from 999 downto num1 do
                (if (>= result (* num1 num2))
                    (return))
                (if (check-palindrome(* num1 num2))
                    (setf result (* num1 num2)))))
    result))

(defun check-palindrome (n)
  "Check the number is palindrome."
  (let ((num-list (number-to-list n)))
    (if (equalp num-list (reverse num-list))
        (progn 
          (print num-list)
          t)
        nil)))

(defun number-to-list (number)
  "Coerce numbers to lists."
  (assert (and (integerp number)
               (>= number 0)))
  (labels ((number-to-list/recursive (number)
             (cond
               ((zerop number)
                nil)
               (t
                (cons (mod number 10) 
                      (number-to-list/recursive (truncate (/ number 10))))))))
    (nreverse (number-to-list/recursive number))))


;;;; Problem 5 ;;;;
;; 2520 is the smallest number that can be divided by each of the numbers from 
;; 1 to 10 without any remainder. What is the smallest positive number that is 
;; evenly divisible by all of the numbers from 1 to 20?
;; Run: (problem5 0)
;; Answer: 232792560
(defun problem5 (n)
  (cond
    ((= n 0) (problem5 (+ 20 n)))
    (t 
     (let ((isItDivisible t))
       (dotimes (i 20)
         (if (null (= (mod n (1+ i)) 0)) 
             (progn 
               (setf isItDivisible nil)
               (return))))
       (if (eql isItDivisible t)
           (print n)
           (problem5 (+ 20 n)))))))

iTunesU CS193P Fall 2011 iPhone Application Development Assignment 2

Gosh, I finally finished the assignment 2. I blame myself for being lazy and I need to stop that. So this assignment is the addition to the assignment 1. You have to add more features to it. I am gonna talk about the more of the main tasks of this assignment.

1) The program needs to be able to accept the variables as operands. As far as the controller and view, you need to have three variable buttons, in my case a,b and x, and three test buttons that set up different values for the variables. Then the model is where the actual implementation happens. I set up a public NSDictionary variable which contains variables and their corresponding values depends on the different test button. So as the program pops the stack it checks if the top of the stack is equal to a, b, or x. Then it accordingly changes the variable to the number.

2) Re-implement the descriptionOfProgram: method from the last lecture to display the passed program in a more user-friendly manner. It is somewhat similar to the given method, + (double)popOperandOffProgramStack:(NSMutableArray *)stack. Check if the top of the stack is a NSNumber or NSString. If it is a NSString, check if the operation is two, one, or 0 operands operation. If it is a two operands operation, use "operand operation operand" format. If it is a one operand operation, use "operation(operand)" format. If it is a non-operand operation, just present the operation itself.

3) Add an Undo button to your calculator. There are two cases think about, when the user is in the middle of typing and not in the middle of typing. The undo button when the user is in the middle of typing is already implemented as the backspace button in the previous assignment. When the user it not typing, you need to pop the stack in the right manner so that the view displays the correct previous value. My algorithm for this might not be the fastest or the best but it works. So you have to pop the stack at least once no matter what. So I use do-while loop. So pop the stack first and while the top of the stack is a NSNumber or equal to the variables, you keep popping so that it reaches to the previous operation. Then you check the top of the stack (without popping) and update the user interface.

That's pretty much it. There are other little stuff you have to implement as well but they are not that hard so I won't talk about it. Here are the code for my assignment 2. Good luck!



CalculatorViewController.h

#import <UIKit/UIKit.h>

@interface CalculatorViewController : UIViewController

@property (weak, nonatomic) IBOutlet UILabel *display;

@end

CalculatorViewController.m

#import "CalculatorViewController.h"
#import "CalculatorBrain.h"

@interface CalculatorViewController()
@property (nonatomic) BOOL userIsInTheMiddleOfEnteringANumber;
@property (nonatomic) BOOL thereIsADot;
@property (nonatomic, strong) CalculatorBrain *brain;
@property (weak, nonatomic) IBOutlet UILabel *dictionaryDisplay;
@property (weak, nonatomic) IBOutlet UILabel *variableDisplay;
@property (strong, nonatomic) NSArray *valueArray;
@property (weak, nonatomic) IBOutlet UILabel *infixDisplay;
@end

@implementation CalculatorViewController

@synthesize display;
@synthesize variableDisplay;
@synthesize dictionaryDisplay;
@synthesize userIsInTheMiddleOfEnteringANumber;
@synthesize thereIsADot;
@synthesize brain = _brain;
@synthesize valueArray = _valueArray;
@synthesize infixDisplay;

- (CalculatorBrain *)brain
{
    if (!_brain) _brain = [[CalculatorBrain alloc] init];
    return _brain;
}

- (NSArray *)valueArray
{
    if (!_valueArray) 
        _valueArray = [NSArray arrayWithObjects: [NSNumber numberWithInt:0], 
                                                 [NSNumber numberWithInt:0], 
                                                 [NSNumber numberWithInt:0], nil];
    return _valueArray;

}

- (IBAction)digitPressed:(UIButton *)sender 
{
    NSString *digit = [sender currentTitle];
    if (self.userIsInTheMiddleOfEnteringANumber) {
        if (self.thereIsADot) {
            if ([digit isEqualToString:@"."]) {
                // do nothing
            }
            else 
                self.display.text = [self.display.text stringByAppendingString:digit];
        } else {
            if ([digit isEqualToString:@"."]) {
                self.thereIsADot = YES;
                self.display.text = [self.display.text stringByAppendingString:digit];
            } else
                self.display.text = [self.display.text stringByAppendingString:digit];
        }
    } else { 
        if ([digit isEqualToString:@"."])
            self.thereIsADot = YES;
        self.display.text = digit;
        self.userIsInTheMiddleOfEnteringANumber = YES;
    }
}

- (IBAction)enterPressed 
{
    [self.brain pushOperand:[self.display.text doubleValue]];
    self.userIsInTheMiddleOfEnteringANumber = NO;
    self.thereIsADot = NO;
}

- (IBAction)operandPressed:(id)sender 
{
    if (self.userIsInTheMiddleOfEnteringANumber) {
        [self enterPressed];
    }
    NSString *operation = [sender currentTitle];
    double result = [self.brain performOperation:operation];
    self.display.text = [NSString stringWithFormat:@"%g", result];
    [infixDisplay setText:[CalculatorBrain descriptionOfProgram:self.brain.program]];
}

- (IBAction)CPressed 
{
    self.display.text = @"0";
    self.userIsInTheMiddleOfEnteringANumber = NO;
    self.thereIsADot = NO;
    self.variableDisplay.text = @"";
    self.infixDisplay.text = @"";
    [self.brain emptyStack];
    _brain = [[CalculatorBrain alloc] init];
}

- (IBAction)plusMinusPressed:(UIButton *)sender 
{
    if (userIsInTheMiddleOfEnteringANumber) {
        NSString *newString;
        double number = [self.display.text doubleValue];
        if (number > 0) {
            number = -number;
            newString = [NSString stringWithFormat:@"%g",number];
            self.display.text = newString;
        } else if (number < 0) {
            number = abs(number);
            newString = [NSString stringWithFormat:@"%g",number];
            self.display.text = newString;
        }
    }
    else {
        NSString *operation = [sender currentTitle];
        double result = [self.brain performOperation:operation];
        self.display.text = [NSString stringWithFormat:@"%g", result];
    }
}

- (IBAction)testPressed:(UIButton *)sender 
{
    self.variableDisplay.text = @"";
    NSString *testNumber = [sender currentTitle];
    NSNumber *value1, *value2, *value3;
    if ([testNumber isEqualToString:@"Test 1"]) {
        value1 = [NSNumber numberWithInt:3];
        value2 = [NSNumber numberWithInt:4];
        value3 = [NSNumber numberWithInt:0];
    } else if ([testNumber isEqualToString:@"Test 2"]) {
        value1 = [NSNumber numberWithInt:0];
        value2 = [NSNumber numberWithInt:-4];
        value3 = [NSNumber numberWithInt:-10];
    } else if ([testNumber isEqualToString:@"Test 3"]) {
        value1 = [NSNumber numberWithInt:10];
        value2 = [NSNumber numberWithInt:0];
        value3 = [NSNumber numberWithInt:100];
    }  
    _valueArray = [NSArray arrayWithObjects: value1, value2, value3, nil];
}

- (IBAction)variablePressed:(UIButton *)sender
{ 
    NSString *variable = [sender currentTitle];
    NSNumber *value;
    if ([variable isEqualToString:@"x"]) {
        value = [self.valueArray objectAtIndex:0];
    } else if ([variable isEqualToString:@"a"]) {
        value = [self.valueArray objectAtIndex:1];
    } else if ([variable isEqualToString:@"b"]) {
        value = [self.valueArray objectAtIndex:2];
    }
    [self.brain acceptVariables:variable AndItsValue:value];
    
    NSMutableSet *variableDisplaySet = [[NSMutableSet alloc] init];
    NSSet *variableSet = [self.brain returnVariableSet:[self.brain program]];
    NSDictionary *variableDictionary = [self.brain variableDictionary];
    double xValue, aValue, bValue = 0;
    
    if ([variableSet containsObject:@"x"]) {
        xValue = [[variableDictionary valueForKey:@"x"] doubleValue];
        if (xValue != 0)
            [variableDisplaySet addObject:[NSString stringWithFormat:@"x = %g   ", xValue]];
    } 
    if ([variableSet containsObject:@"a"]) {
        aValue = [[variableDictionary valueForKey:@"a"] doubleValue]; 
        if (aValue != 0)
            [variableDisplaySet addObject:[NSString stringWithFormat:@"a = %g   ", aValue]];
    } 
    if ([variableSet containsObject:@"b"]) {
        bValue = [[variableDictionary valueForKey:@"b"] doubleValue]; 
        if (bValue != 0)
            [variableDisplaySet addObject:[NSString stringWithFormat:@"b = %g   ", bValue]];
    }
   
    NSString *newString = @"";
    for (id obj in variableDisplaySet) {
        if ([obj isKindOfClass:[NSString class]])
            newString = [newString stringByAppendingFormat:obj];
    }
    self.variableDisplay.text = newString;
}

- (IBAction)undoPressed 
{
    if (userIsInTheMiddleOfEnteringANumber) {
        if (self.display.text.length == 0)
            userIsInTheMiddleOfEnteringANumber = NO;
        else
            self.display.text = [self.display.text substringToIndex:self.display.text.length - 1];
    } 
    else {
        do {
            [self.brain popTheTopOfTheStack];
        } while ([[self.brain getTheTopOfTheStack] isKindOfClass:[NSNumber class]] ||
                 [[self.brain getTheTopOfTheStack] isEqualToString:@"x"] ||
                 [[self.brain getTheTopOfTheStack] isEqualToString:@"a"] || 
                 [[self.brain getTheTopOfTheStack] isEqualToString:@"b"]);
        if ([self.brain getTheTopOfTheStack])
            self.display.text = [NSString stringWithFormat:@"%g", [CalculatorBrain runProgram:self.brain.program usingVariableValues:self.brain.variableDictionary]];
        else
            self.display.text = nil;
    }
}
@end

CalculatorBrain.h

@interface CalculatorBrain : NSObject

- (void)emptyStack;
- (NSSet *)returnVariableSet:(id)program;
- (void)popTheTopOfTheStack;
- (id)getTheTopOfTheStack;
- (void)pushOperand:(double)operand;
- (double)performOperation:(NSString *)op;
- (void)acceptVariables:(NSString *)variable
            AndItsValue:(NSNumber *)value;

@property (nonatomic, readonly) id program;
@property (nonatomic, strong) NSMutableDictionary *variableDictionary;

+ (double)runProgram:(id)program 
 usingVariableValues:(NSDictionary *)variableValues;
+ (NSSet *)variablesUsedInProgram:(id)program;
+ (NSString *)descriptionOfProgram:(id)program;

@end

CalculatorBrain.m

#import "CalculatorBrain.h"

@interface CalculatorBrain()
@property (nonatomic, strong) NSMutableArray *programStack;
@end

@implementation CalculatorBrain

@synthesize programStack = _programStack;
@synthesize variableDictionary = _variableDictionary;

- (NSMutableArray *)programStack
{
    if (!_programStack) _programStack = [[NSMutableArray alloc] init];
    return _programStack;
}

- (NSMutableDictionary *)variableDictionary
{
    if (!_variableDictionary) _variableDictionary = [[NSMutableDictionary alloc] init];
    return _variableDictionary;
}

- (id)program
{
    return [self.programStack copy];
}

- (void)pushOperand:(double)operand
{
    [self.programStack addObject:[NSNumber numberWithDouble:operand]];
}

- (void)acceptVariables:(NSString *)variable
            AndItsValue:(NSNumber *)value
{
    [self.variableDictionary setObject:value forKey:variable];
    [self.programStack addObject:variable];
}

- (double)performOperation:(NSString *)operation
{
    NSDictionary *dictionary = [self.variableDictionary copy];
    [self.programStack addObject:operation];
    return [[self class] runProgram:self.program usingVariableValues:dictionary];
}

+ (double)popOperandOffProgramStack:(NSMutableArray *)stack
{
    double result = 0;
    
    id topOfStack = [stack lastObject];
    if (topOfStack) [stack removeLastObject];
    
    if ([topOfStack isKindOfClass:[NSNumber class]]) {
        result = [topOfStack doubleValue];
    }
    else if ([topOfStack isKindOfClass:[NSString class]]) {
        NSString *operation = topOfStack;
        
        if ([operation isEqualToString:@"+"]) {
            result = [self popOperandOffProgramStack:stack] + [self popOperandOffProgramStack:stack];
        } else if ([@"*" isEqualToString:operation]) {
            result = [self popOperandOffProgramStack:stack] * [self popOperandOffProgramStack:stack];
        } else if ([operation isEqualToString:@"-"]) {
            double subtrahend = [self popOperandOffProgramStack:stack];
            result = [self popOperandOffProgramStack:stack] - subtrahend;
        } else if ([operation isEqualToString:@"/"]) {
            double divisor = [self popOperandOffProgramStack:stack];
            if (divisor) result = [self popOperandOffProgramStack:stack] / divisor;
        } else if ([operation isEqualToString:@"sin"]) {
            result = sin([self popOperandOffProgramStack:stack]);
        } else if ([operation isEqualToString:@"cos"]) {
            result = cos([self popOperandOffProgramStack:stack]);
        } else if ([operation isEqualToString:@"sqrt"]) {
            result = sqrt([self popOperandOffProgramStack:stack]);
        } else if ([operation isEqualToString:@"pi"]) {
            result = M_PI;
        } else if ([operation isEqualToString:@"e"]) {
            result = M_E;
        } else if ([operation isEqualToString:@"log"]) {
            result = log10([self popOperandOffProgramStack:stack]);
        } else if ([operation isEqualToString:@"+/-"]) {
            result = [self popOperandOffProgramStack:stack];
            if (result > 0) result = -result;
            else if (result < 0) result = abs(result);
        }
    }
    
    return result;
}

+ (double)runProgram:(id)program 
 usingVariableValues:(NSDictionary *)variableValues 
{
    NSMutableArray *stack;
    NSSet *variableSet = [self variablesUsedInProgram:program];
    
    if ([program isKindOfClass:[NSArray class]])
        stack = [program mutableCopy];
    
    for (int i = 0; i < [stack count] - 1; i++) {
        id object = [stack objectAtIndex:i];
        if ([object isKindOfClass:[NSString class]]) {
            if ([variableSet containsObject:object]) {
                if ([object isEqualToString:@"x"])
                    [stack replaceObjectAtIndex:i withObject:[variableValues valueForKey:object]];
                else if ([object isEqualToString:@"a"]) 
                    [stack replaceObjectAtIndex:i withObject:[variableValues valueForKey:object]];
                else if ([object isEqualToString:@"b"]) 
                    [stack replaceObjectAtIndex:i withObject:[variableValues valueForKey:object]];
            }
        }
    }
    
    return [self popOperandOffProgramStack:stack];
}

+ (NSString *)descriptionOfProgram:(id)program
{
    NSMutableArray *stack;
    if ([program isKindOfClass:[NSArray class]]) {
        stack = [program mutableCopy];
    }
    NSString *description = [self descriptionOfTopOfStack:stack];
    if ([self isEnclosedByParentheses:description]) {
        NSRange range;
        range.location = 1;
        range.length = [description length] - 2;
        description = [description substringWithRange:range];
    }
    
    return description;
}

+ (NSString *)descriptionOfTopOfStack:(NSMutableArray *)stack
{
    NSString *description;
    
    id top = [stack lastObject];
    if (top) {
        [stack removeLastObject];
        if ([top isKindOfClass:[NSNumber class]]) {
            description = [top stringValue];
        } else if ([top isKindOfClass:[NSString class]]) {
            NSString *op = top;
            if ([self is2OperandOperation:op]) {
                NSString *secondOperand = [self descriptionOfTopOfStack:stack];
                if ([secondOperand length] == 0) {
                    secondOperand = [NSString stringWithString:@"0"];
                }
                NSString *format = @"(%@ %@ %@)";
                if ([self isMultiplicationOrDivision:op]) {
                    format = @"%@ %@ %@";
                }
                NSString *firstOperand = [self descriptionOfTopOfStack:stack];
                if ([firstOperand length] == 0) {
                    firstOperand = [NSString stringWithString:@"0"];
                }
                description = [NSString stringWithFormat:format, firstOperand, op, secondOperand];
                NSLog(@"%@", description);
            } else if ([self is1OperandOperation:op]) {
                NSString *topDescription = [self descriptionOfTopOfStack:stack];
                if ([topDescription length] == 0) {
                    topDescription = [NSString stringWithString:@"0"];
                }
                NSString *format = @"%@(%@)";
                if ([self isEnclosedByParentheses:topDescription]) {
                    format = @"%@%@";
                }
                if ([@"+/-" isEqualToString:op]) {
                    op = @"-";
                }
                description = [NSString stringWithFormat:format, op, topDescription];
            } else if ([self is0OperandOperation:op] || [self isVariable:op]) {
                description = op;
            }
        } 
    }
    
    return description;
}

+ (BOOL)isEnclosedByParentheses:(NSString *)description
{
    return ([@"(" isEqualToString:[description substringToIndex:1]] && [@")" isEqualToString:[description substringFromIndex:([description length] - 1)]]);
}

+ (BOOL)is2OperandOperation:(NSString *)operation
{
    return [[self twoOperandOperators] containsObject:operation];
}

+ (BOOL)is1OperandOperation:(NSString *)operation
{
    return [[self oneOperandOperators] containsObject:operation];
}

+ (BOOL)is0OperandOperation:(NSString *)operation
{
    return [[self zeroOperandOperators] containsObject:operation];
}

+ (BOOL)isMultiplicationOrDivision:(NSString *)op
{
    return [[self multiplicationAndDivision] containsObject:op];
}

+ (NSSet *)multiplicationAndDivision
{
    return [NSSet setWithObjects:@"*", @"/", nil];
}

+ (NSSet *)twoOperandOperators
{
    NSMutableSet *mutableSet = [[self multiplicationAndDivision] mutableCopy];
    [mutableSet unionSet:[NSSet setWithObjects:@"+", @"-", nil]];
    return mutableSet;
}

+ (NSSet *)oneOperandOperators
{
    return [NSSet setWithObjects:@"sin", @"cos", @"sqrt", @"log", @"+/-", nil];
}

+ (NSSet *)zeroOperandOperators
{
    return [NSSet setWithObjects:@"pi", @"e", nil];
}

+ (BOOL)isVariable:(NSString *)variable
{
    NSSet *VARIABLES = [NSSet setWithObjects:@"a", @"b", @"x", nil];
    return [VARIABLES containsObject:variable];
}

+ (NSSet *)variablesUsedInProgram:(id)program
{
    NSMutableArray *stack;
    NSMutableSet *variableMutableSet = [[NSMutableSet alloc] init];
    if ([program isKindOfClass:[NSArray class]]) 
        stack = [program mutableCopy];
    
    for (id object in stack) {
        if ([object isKindOfClass:[NSString class]])
            if ([object isEqualToString:@"x"])
                [variableMutableSet addObject:object];
            else if ([object isEqualToString:@"a"])
                [variableMutableSet addObject:object];
            else if ([object isEqualToString:@"b"])
                [variableMutableSet addObject:object];
    }
    NSSet *variableSet = [variableMutableSet copy];
    
    return variableSet;
}

- (NSSet *)returnVariableSet:(id)program
{
    NSSet *returnSet = [[self class] variablesUsedInProgram:(id)program];
    return returnSet;
}

- (void)popTheTopOfTheStack
{
    [self.programStack removeLastObject];
}

- (id)getTheTopOfTheStack
{
    return [self.programStack lastObject];
}

- (void)emptyStack
{
    _programStack = [[NSMutableArray alloc] init];
}

@end

iTunesU CS193P Fall 2011 iPhone Application Development Assignment 1

It wasn't my first time being exposed to objective-c and Xcode and other Apple stuff because I have this book called "The Complete Idiot's Guide to iPad & iPhone App Development" by Troy Brent. Don't get me wrong, it is a good book. However, the book was too basic and more importantly it covers its materials based on Xcode 3. I mean Xcode 3 and 4 are, of course, pretty much the same thing but I figured getting used to the latest version is always good and wanted to learn all the cool features of the latest version.

So since I have a lot of time (sadly still job hunting *sad face*), I decided to really get into app development. I heard a lot of good stuff about iTunesU app development courses and I picked the one with highest ratings, Stanford CS193p Fall 2011. I just finished the assignment 1 and I would like to talk about it. This wasn't that hard at all. But I was getting used to and still need to know better about objective-c itself and MVC. For example, you usually *call* methods in Java but you send a message TO methods in objective-c. It was somewhat weird to get used to but it wasn't that bad when I think in the opposite way of Java. MVC, I almost understand but still...I need to completely be able to comprehend it and explain it.

So the first assignment was to build a calculator as an iPhone app. There were seven required tasks to do.

1. Follow the walk-through instructions (separate document) to build and run the calculator in the iPhone Simulator. Do not proceed to the next steps unless your calculator functions as expected and builds without warnings or errors.

First, you just need to follow the walkthrough document that is provided by the instructor. For my first time finishing the walkthrough, my app was giving me an error and since I thought it was gonna take actually longer to find a bug than redo the whole thing, I decided to do it again lol. Then I successfully finished the basic calculator.


2. Your calculator already works with floating point numbers (e.g. if you touch the buttons 3 Enter 4 / it will properly show the resulting value of 0.75), however, there is no way for the user to enter a floating point number. Remedy this. Allow only legal floating point numbers to be entered (e.g. “192.168.0.1” is not a legal floating point number). Don’t worry too much about precision in this assignment.

There is a hint section that talks about this problem but I didn't do it that way. I thought it was easier to do set up a boolean flag that tells if there is a dot or not on the current display. So if there is no dot, you can place a dot or do nothing.


3. Add the following 4 operation buttons:
• sin : calculates the sine of the top operand on the stack.
• cos : calculates the cosine of the top operand on the stack.
• sqrt : calculates the square root of the top operand on the stack.
• π: calculates (well, conjures up) the value of π. Examples: 3 π * should put three times the value of π into the display on your calculator, so should 3 Enter π *, so should π 3 *. Perhaps unexpectedly, π Enter 3 * + would result in 4 times π being shown. You should understand why this is the case. NOTE: This required task is to add π as an operation (an operation which takes no arguments off of the operand stack), not a new way of entering an operand into the display.

This isn't hard either. You make a new operation button sin, cos, sqrt, and pi. Then you write the code for each operation accordingly. In order to understand the last bullet point, just think about how a stack works (First In, First Out) and look at the code and see how it is being pushed and popped. You can always draw! The best way to understand things.


4. Add a new text label (UILabel) to your user-interface which shows everything that has been sent to the brain (separated by spaces). For example, if the user has entered 6.3 Enter 5 + 2 *, this new text label would show 6.3 5 + 2 *. A good place to put this label is to make it a thin strip above the display text label. Don’t forget to have the C button clear this too. All of the code for this task should be in your Controller (no changes to your Model are required for this one). You do not have to display an unlimited number of operations and operands, just a reasonable amount.

For this, I added a new display called brainDisplay that pretty much does the same thing as display. You just need to make it to display operations to the label. I will talk about C next.


5. Add a “C” button that clears everything (for example, the display in your View, the operand stack in your Model, any state you maintain in your Controller, etc.). Make sure 3 7 C 5 results in 5 showing in the display. You will have to add API to your Model to support this feature.

Just initialize everything. Set display to 0 and brainDisplay to blank. Also, I made a function on the model called emptyStack which empties the operand stack. I used that in order to empty the it. One more thing, don't forget to set the flags (in my case, userIsInTheMiddleOfEnteringANumber and thereIsADot) to NO.


6. If the user performs an operation for which he or she has not entered enough operands, use zero as the missing operand(s) (the code from the walkthrough does this already, so there is nothing to do for this task, it is just a clarification of what is required). Protect against invalid operands though (e.g. divide by zero).

As the problem says, it is already done. About protecting against dividing by zero, I didn't do anything because the code itself doesn't do anything if that happens. I could make it show an error message but I just didn't do it.


7. Avoiding the problems listed in the Evaluation section below is part of the required tasks of every assignment. This list grows as the quarter progresses, so be sure to check it again with each assignment.

OK!


So that's that. Here are my source code for this assignment. I did all the extra credit too! If you've gotten yours done this far, the extra credit problems would not be hard at all. By the way, I really don't think this is perfect at all but it works well so far (might not work for something I haven't tested). If you see any suggestion or error, please let me know. I'm not really a great programmer!! (...yet)

CalculatorBrain.h
CalculatorBrain.m
CalculatorViewController.h
CalculatorViewController.m

If any of those links is broken, let me know. Thank you for reading!

Inserting a new node in a doubly linked list

As explained on the previous linked list post, doubly linked lists have two links for each node, which are the next link and previous link. So when it comes to inserting a new node in the middle of the list, you have to be careful with the order of assigning the links. Otherwise, you could easily lose the link so the whole list would be messed up. I'll explain how to but see the figure first. You can assume that there are multiple nodes before the node 1 and after the node 2.


First of all, you gotta link the new node to its previous and next nodes AND THEN you link the new node's previous and next to the new node. In Java code, it would be like this.

newNode.next = node2;
newNode.prev = node1;
node1.next = newNode;
node2.prev = newNode;