Challenge 119 - objective C for Mac OS - command line

gistfile1.c

//
//  Maze.h
//  119 maze shortest path
//

#import <Foundation/Foundation.h>

#define NOT_DEFINED -1

// These are valid maze inputs

#define START_ROOM 'S'
#define END_ROOM 'E'
#define WALL 'W'
#define ROOM '.'

@interface Maze : NSObject
{
    int size;             // the maze will be a size x size grid
    int startNode;        // node number where maze begins
    int endNode;          // node number where maze ends
    NSMutableArray *maze; // our maze stored in an single array vs 2 dimension array
    
}

- (id) init;
- (id) initWithSize: (int) s;
- (void) addNode: (char) c;
- (void) displayMaze;
- (void) computeH;

+ (int) isValidRoom: (char) c;

- (int) isShortPath;


@property (nonatomic) int size;
@property (nonatomic) int startNode;
@property (nonatomic) int endNode;
@property (strong) NSMutableArray *maze;



@end

//
//  Maze.m
//  119 maze shortest path
//


#import "Maze.h"
#import "MazeNode.h"

@implementation Maze

// create set/get accessors

@synthesize size, startNode, endNode, maze;

- (id) init
{
    self = [super init];
    if (self)
    {
        self = [self initWithSize: 0];
        [self setStartNode: NOT_DEFINED];
        [self setEndNode: NOT_DEFINED];

    }
    return self;
}

- (id) initWithSize: (int) s
{
    self = [super init];
    if (self)
    {
        [self setSize:s];
        [self setStartNode: NOT_DEFINED];
        [self setEndNode: NOT_DEFINED];
    }
    return self;
}

+ (int) isValidRoom: (char) c
{
    switch (c) {
        case START_ROOM:
        case END_ROOM:
        case WALL:
        case ROOM:
            return TRUE;
        default:
            return FALSE;
    }
}

- (void) addNode: (char) c
{
    MazeNode *node = nil;
    
    node = [[MazeNode alloc] initWithNode: c];
    if (!maze) {
        maze = [[NSMutableArray alloc] init];
    }
    [maze addObject: node];
    
    // set room number to current index in the maze array
    
    [node setRoomNumber: (int) ([maze count] - 1)];
    
    if (c == START_ROOM)
    {
        [self setStartNode: (int) ([maze count] -1)];
    }
    if (c == END_ROOM)
    {
        [self setEndNode: (int) ([maze count] -1)];
    }
}

- (void) displayMaze
{
    MazeNode *node = nil;
    int n;
    int c = 0;
    
    printf("\n");
    for (n = 0; n < ([self size] * [self size]); n++)
    {
        c++;
        node = [maze objectAtIndex: n];
        if (node) {
           printf("%c", [node room]);
           if (c == [self size])
           {
               printf("\n");
               c = 0;
           }
        } else {
            printf("?");
        }
    }
}


// compute H value using a simple manhattan heuristic of distance away

- (void) computeH
{
    int beginCol;
    int beginRow;
    
    int endCol;
    int endRow;
    
    int deltaCol;
    int deltaRow;
    
    int nodeNum;
    int h;
    
    NSMutableArray *m = [self maze];
    MazeNode *n;
    
    endCol = [self endNode] % [self size] + 1;
    endRow = [self endNode] / [self size] + 1;
    
    // To compute H our heuristic for distance from cell to end we have to find the
    // distance. So I convert the nodenumber (array location) into a row/col pairs
    // and take the delta and add it together. Essentially that is how many squares
    // from the node to the end node.
    //
    // so for example a 3x3 grid would have 9 elements in it
    //  1   2   3 col/row
    // [0] [1] [2] 1
    // [3] [4] [5] 2
    // [6] [7] [8] 3
    //
    // to get column from nodenumber you just take the nodenumber and modulus grid size + 1
    // to get row from the nodenumber you just take the nodenumber and divide grid size + 1
    //
    // then I subract (I think I could have done an absolute vs conditional but it works)
    
    
    // populate all nodes with the H value to the end node for A * algorithm.
    
    for (nodeNum = 0; nodeNum < [m count]; nodeNum++)
    {
        n = [m objectAtIndex:nodeNum];
        
        if (nodeNum == [self endNode])
        {
            h = 0;
        }
        else
        {
           beginCol = nodeNum % [self size] + 1;
           beginRow = nodeNum / [self size] + 1;
        
           (beginCol > endCol) ? deltaCol = beginCol - endCol : endCol - beginCol;
           (beginRow > endRow) ? deltaRow = beginRow - endRow : endRow - beginRow;
        
           h = deltaCol + deltaRow;
        }
        [n setH: h];
        [n setG: 1];
        [n setF: (h + 1)];
    }
}

// Main Shortest Path check using A* Algorithm

- (int) isShortPath
{
    NSMutableArray *closed = [[NSMutableArray alloc] initWithObjects: nil];
    NSMutableArray *open = nil;
    NSMutableArray *neighbor = [[NSMutableArray alloc] initWithObjects: nil];
    
    NSSortDescriptor *byLowF = [NSSortDescriptor sortDescriptorWithKey: @"f" ascending: YES];
    
    MazeNode *node = nil;
    
    int tentativeG = 0;
    int current;
    int n;
    int found;
    int i;
    
    if ([self startNode] == NOT_DEFINED ||
        [self endNode] == NOT_DEFINED)
    {
        printf("False - no start/end room\n");
        return 0;
    }
    
    //
    // A* Algorithm - okay lets find a path
    //
    
    // populate H for the A* Algorithm
    
    [self computeH];

    // zero G at the start room
    
    current = [self startNode];
    node = [[self maze] objectAtIndex:current];
    [node setG: 0];
    
    // calculate F for current room f = g + h
    
    [node setF: ([node g] + [node h])];
    
    open = [[NSMutableArray alloc] initWithObjects: node, nil];
    
    // while the open set is not empty
    
    while ([open count] > 0)
    {

        // sort the open set by lowest F to find the current room to handle.
        
        [open sortUsingDescriptors: [NSArray arrayWithObjects: byLowF, nil]];
        
        // first node in open is the current room we want to handle with lowest F value
        
        node = [open objectAtIndex: 0];
        current = [node roomNumber];
        
        if (current == [self endNode])
        {
            // found end of the maze -- we can return true/false
            //
            // return number of rooms in path since this is a positive number
            // more than 0 it will be considered true.
            //
            // F value of the end room should now have the distance.
            
            return [[[self maze] objectAtIndex:current] f];
        }
        
        // pop the current room from open and put it on closed
    
        [open removeObjectAtIndex: 0];
        [closed addObject: node];
        

        // north -- calculate by subtracting size
        
        n = current - [self size];
        
        if (n > 0)  // if n < 0 there is no valid north
        {
            if ([[[self maze] objectAtIndex: n] room] != 'W') // room is not a wall
            {
                // okay we have a north neighbor that is not a wall add to neighbor queue
                [neighbor addObject: [[self maze] objectAtIndex: n]];
            }
        }
        
        // south -- calculate by adding size
        
        n = current + [self size];
        
        if (n < (size * size)) // if we go more/equal to size * size we went south too far
        {
            if ([[[self maze] objectAtIndex: n] room] != 'W') // room is not a wall
            {
                // okay we have a south neighbor that is not a wall add to neighbor queue
                [neighbor addObject: [[self maze] objectAtIndex: n]];
            }
        }
        
        // west -- calculate by subtracting 1
        
        n = current - 1;
        
        if (n >= 0 && (current / [self size] == n / [self size])) // make sure still on same row
        {
            if ([[[self maze] objectAtIndex: n] room] != 'W') // room is not a wall
            {
                // okay we have a west neighbor that is not a wall add to neighbnor queue
                [neighbor addObject: [[self maze] objectAtIndex:n]];
            }
        }
        
        // east -- calculate by adding + 1
        
        n = current + 1;
        
        if (n < [self size] * [self size] && current / [self size] == n / [self size]) // make sure still on same row
        {
            if ([[[self maze] objectAtIndex: n] room] != 'W') // room is not a wall
            {
                // okay we have a east neighbor that is not a wall add to neighbor queue
                [neighbor addObject: [[self maze] objectAtIndex: n]];
            }
        }
        
        // now we walk the neighbor queue/array and handle every neighbor.
        // if the neighbor is closed - do nothing
        // otherwise
        
        while ([neighbor count] > 0)
        {
            
            // check to see if neighbor is in the closed queue
            
            i = 0;
            found = 0;
            while (i < [closed count])
            {
                if ([[closed objectAtIndex: i] roomNumber] == [[neighbor objectAtIndex:0] roomNumber]) {
                    found = 1;
                    break;
                }
                i++;
            
            }
            
            if (found)
            {
                [neighbor removeObjectAtIndex: 0];
            }
            else
            {
                tentativeG = [node g] + 1;
                
                // if neighbor is not in the open set and the tentative g <= neighbor's g
                // then we need to adjust f, g and push on open set
                
                i = 0;
                found = 0;
                while (i < [open count])
                {
                    if ([[open objectAtIndex: i] roomNumber] == [[neighbor objectAtIndex:0] roomNumber]) {
                        found = 1;
                        break;
                    }
                    i++;
                    
                }
                
                if (!found || tentativeG <= [[neighbor objectAtIndex:0] g])
                {
                    // update the g, f and prev room of the neighbor
                    
                    [[neighbor objectAtIndex:0] setG: tentativeG];
                    [[neighbor objectAtIndex:0] setF: (tentativeG + [[neighbor objectAtIndex: 0] h])];
                    [[neighbor objectAtIndex:0] setPrevRoom: current];
                    
                    // if neighbor is not in the open set -- push it on
                    
                    if (!found)
                    {
                        [open addObject: [neighbor objectAtIndex:0]];
                    }
                }
                
                // pop the current neighbor as we handled it.
                
                
                [neighbor removeObjectAtIndex: 0];
                
            } // if else
            
        } // while we still have neighbors to process
        
    } // while open has rooms
    
    // return a FAILURE -- if we get this far we did not find the end room we exhausted a search -- just return failed
    
    return FALSE;
}



@end

//
//  MazeNode.h
//  119 maze shortest path
//

#import <Foundation/Foundation.h>
#import "Maze.h"

@interface MazeNode : NSObject
{
    int roomNumber; // index into the single dimension array
    int g; // movement cost
    int h; // heuristic cost to get to end
    int f; // f = g+h
    
    int prevRoom; // room previous to this one on shortest path
    
    char room; // room type
    
}

- (void) displayRoom;

- (id) init;
- (id) initWithNode: (char) c;

@property (nonatomic) int roomNumber;
@property (nonatomic) int g;
@property (nonatomic) int h;
@property (nonatomic) int f;
@property (nonatomic) char room;
@property (nonatomic) int prevRoom;

@end

//
//  MazeNode.m
//  119 maze shortest path
//

#import "MazeNode.h"

@implementation MazeNode

@synthesize roomNumber, g, h, f, room, prevRoom;

- (id) init
{
    return [self initWithNode: ROOM];
}


- (id) initWithNode: (char) c
{
    self = [super init];
    if (self) {
       [self setG: 0];
       [self setH: 0];
       [self setF: 0];
       [self setRoom: c];
    }
    return self;
}


- (void) displayRoom
{
    printf("[%c]Room Number[%d]  F[%d] = G[%d] + H[%d]\n",
            [self room],
            [self roomNumber],
            [self f],
            [self g],
            [self h]);
            
}


@end

//
//  main.m
//  119 maze shortest path
//


#import <Foundation/Foundation.h>
#import "Maze.h"
#import "MazeNode.h"

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

    @autoreleasepool {
        
        int size = 0;
        int row;
        int col;
        
        int nodeNum;
        char room;
        char enterKey;
        int answer;
        
        Maze *maze = nil;
        
        
        printf("Enter Size (n) for a NxN Maze-->");
        scanf("%d", &size);
        
        if (size > 0) // read in rest of the maze
        {
            maze = [[Maze alloc] initWithSize: size]; // alloc a new maze;
            if (maze)
            {
                nodeNum = 0;
                for (row = 0; row < size; row++ )
                {
                    scanf("%c", &enterKey);
                    for (col = 0; col < size; col++)
                    {
                        scanf("%c", &room);
                        if ([Maze isValidRoom: room])
                        {
                            [maze addNode: room];
                        }
                        else
                        {
                            printf("Error not a valid room type!\n");
                            return 1;
                        }
                    }
                }
                // [maze displayMaze];
            }
            else
            {
                printf("Error!! Could not allocate and create a maze/n");
                return 1;
            }
        }
        else // error message non-decimal, 0 or negative number entered
        {
            printf("\nError!!! Please enter a valid maze size!\n\n");
            return 1;
        }
        
        // do we have a short path?
        
        answer = [maze isShortPath];
        
        if (answer)
        {
            printf("TRUE, %d\n", answer);
        }
        else
        {
            printf("FALSE\n");
        }
        
    }
    return 0;
}