Az Flights Optimization, Objective-C

Language: Layout:

//gcc 5.0.4

#import <Foundation/Foundation.h>
#include <time.h>
#include <stdlib.h>

void swap (NSInteger *indexes, NSInteger a, NSInteger b) {
    NSInteger temp = indexes [a];
    indexes [a] = indexes [b];
    indexes [b] = temp;
}

NSInteger partition (NSArray *flights, NSInteger count, NSInteger *indexes, NSInteger low, NSInteger high) {
    srand (time(NULL)); 
    NSInteger random = low + rand() % (high - low); 
    swap (indexes, random, high);
    NSInteger pivot = ((NSNumber*)[((NSArray*)[flights objectAtIndex: indexes [high]]) objectAtIndex: 1]).integerValue;
    NSInteger i = low, j;
    
    for (j = low; j < high; j++) {
        if (((NSNumber*)[((NSArray*)[flights objectAtIndex: indexes [j]]) objectAtIndex: 1]).integerValue <= pivot) {
            swap (indexes, i, j);
            i++;
        }
    }
    
     swap (indexes, i, high);
    
    return i;
}

void quickSort (NSArray *flights, NSInteger count, NSInteger *indexes, NSInteger low, NSInteger high) {
    if (low < high) {
        NSInteger pivot = partition (flights, count, indexes, low, high);
        quickSort (flights, count, indexes, low, pivot - 1);
        quickSort (flights, count, indexes, pivot + 1, high);
    }
}

NSInteger *sortFlights (NSArray *flights) {
    NSInteger count = flights.count, *result = (NSInteger *) malloc (sizeof (NSInteger) * count), index;
    
    bool sorted = YES;
    
    result [0] = 0;
    for (index = 1; index < count; index++) {
         result [index] = index;
         if (((NSNumber*)[((NSArray*)[flights objectAtIndex: result [index]]) objectAtIndex: 1]).integerValue < ((NSNumber*)[((NSArray*)[flights objectAtIndex: result [index - 1]]) objectAtIndex: 1]).integerValue) {
            sorted = NO;
         }
    }
    
    if (!sorted)
        quickSort (flights, count, result, 0, count - 1);
    
    return result;
}

NSArray* optimizeFlightDictionary (NSArray *forwardFlights, NSArray *returnFlights, NSInteger maxDistance) {
    NSMutableArray *result = [NSMutableArray array];
    
    NSInteger forwardFlightsCount = forwardFlights.count, index;
    NSInteger *forwardSortedFlights = sortFlights (forwardFlights); 
   
    NSInteger returnFlightsCount = returnFlights.count;
    NSInteger *returnSortedFlights = sortFlights (returnFlights);
    
    bool foundDistance = NO;
    NSArray *shortArray, *longArray;
    NSInteger shortCount, longCount, *shortIndexes, *longIndexes, shortIndex, longIndex, calculatedDistance, decidedDistance = 0;
    NSInteger mode;
    
    if (forwardFlightsCount <= returnFlightsCount) {
        shortArray = forwardFlights;
        shortCount = forwardFlightsCount;
        shortIndexes = forwardSortedFlights;
        
        longArray = returnFlights;
        longCount = returnFlightsCount;
        longIndexes = returnSortedFlights;
        mode = 1;
    }
    else {
        shortArray = returnFlights;
        shortCount = returnFlightsCount;
        shortIndexes = returnSortedFlights;
        
        longArray = forwardFlights;
        longCount = forwardFlightsCount;
        longIndexes = forwardSortedFlights;
        mode = 2;
    }
    
  
    shortIndex = shortCount - 1;
    longIndex = longCount - 1;
    
    while (shortIndex >= 0 && longIndex >= 0) {
        calculatedDistance = ((NSNumber*)[((NSArray*)[shortArray objectAtIndex: shortIndexes [shortIndex]]) objectAtIndex: 1]).integerValue +
            ((NSNumber*)[((NSArray*)[longArray objectAtIndex: longIndexes [longIndex]]) objectAtIndex: 1]).integerValue;
        
        if (calculatedDistance <= maxDistance && calculatedDistance > decidedDistance)
            decidedDistance = calculatedDistance;
        
        if (((NSNumber*)[((NSArray*)[shortArray objectAtIndex: shortIndexes [shortIndex]]) objectAtIndex: 1]).integerValue > maxDistance) {
            shortIndex--;
        }
        else if (((NSNumber*)[((NSArray*)[longArray objectAtIndex: longIndexes [longIndex]]) objectAtIndex: 1]).integerValue > maxDistance) {
            longIndex--;
        }
        else if (((NSNumber*)[((NSArray*)[shortArray objectAtIndex: shortIndexes [shortIndex]]) objectAtIndex: 1]).integerValue > ((NSNumber*)[((NSArray*)[longArray objectAtIndex: longIndexes [longIndex]]) objectAtIndex: 1]).integerValue) {
            if (longIndex > 0)
                longIndex--;
            else
                shortIndex--;
        }
        else {
            if (shortIndex > 0)
                shortIndex--;
            else
                longIndex--;
        }
    }
    
    
    
    
   
    if (decidedDistance > 0) {
    
        NSMutableDictionary *shortFligthsDict = [NSMutableDictionary dictionary];
        NSMutableArray *flightsList;
        
        for (NSArray *flight in shortArray) {
            flightsList = [shortFligthsDict objectForKey: [flight objectAtIndex: 1]];
            if (flightsList) {
                [flightsList addObject: [flight objectAtIndex: 0]];
            }
            else {
                flightsList = [NSMutableArray array];
                [flightsList addObject: [flight objectAtIndex: 0]];
                [shortFligthsDict setObject: flightsList forKey: [flight objectAtIndex: 1]];
            }
        }
        
        NSNumber *distanceToSearch;
        for (NSArray *flight in longArray) {
            distanceToSearch = [NSNumber numberWithInteger: decidedDistance - ((NSNumber*)[flight objectAtIndex: 1]).integerValue];
            flightsList = [shortFligthsDict objectForKey: distanceToSearch];
            
            if (flightsList) {
                for (NSNumber *flightID in flightsList) {
                    if (mode == 1) {//Short is forward
                       [result addObject: [NSArray arrayWithObjects: flightID, [flight objectAtIndex: 0], nil]];
                    }
                    else { //Short is return
                        [result addObject: [NSArray arrayWithObjects: [flight objectAtIndex: 0], flightID, nil]];
                    }
                }
            }
        }
    
    }
    
   
    
    return result;
}

int main (int argc, const char * argv[])
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    
    NSMutableArray *forwardFlights = [NSMutableArray array], *returnFlights = [NSMutableArray array], *workingElement;
    
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 1]];  //Doesn't work @1
    [workingElement addObject: [NSNumber numberWithInteger: 3100]];  //Doesn't work @1000
    [forwardFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 2]];
    [workingElement addObject: [NSNumber numberWithInteger: 5200]];
    [forwardFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 3]];
    [workingElement addObject: [NSNumber numberWithInteger: 1300]];
    [forwardFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 4]];
    [workingElement addObject: [NSNumber numberWithInteger: 2400]];
    [forwardFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 5]];
    [workingElement addObject: [NSNumber numberWithInteger: 500]];
    [forwardFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 6]];
    [workingElement addObject: [NSNumber numberWithInteger: 2600]];
    [forwardFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 7]];  //Doesn't work @1
    [workingElement addObject: [NSNumber numberWithInteger: 9700]];  //Doesn't work @1000
    [forwardFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 8]];
    [workingElement addObject: [NSNumber numberWithInteger: 2400]];
    [forwardFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 9]];
    [workingElement addObject: [NSNumber numberWithInteger: 1300]];
    [forwardFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 10]];
    [workingElement addObject: [NSNumber numberWithInteger: 5200]];
    [forwardFlights addObject: workingElement];
    
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 1]];
    [workingElement addObject: [NSNumber numberWithInteger: 1200]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 2]];
    [workingElement addObject: [NSNumber numberWithInteger: 700]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 3]];
    [workingElement addObject: [NSNumber numberWithInteger: 900]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 4]];
    [workingElement addObject: [NSNumber numberWithInteger: 500]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 5]];
    [workingElement addObject: [NSNumber numberWithInteger: 1900]];
    [returnFlights addObject: workingElement];
    
     workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 6]];
    [workingElement addObject: [NSNumber numberWithInteger: 700]];
    [returnFlights addObject: workingElement];
    
     workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 7]];
    [workingElement addObject: [NSNumber numberWithInteger: 1700]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 8]];
    [workingElement addObject: [NSNumber numberWithInteger: 1]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 9]];
    [workingElement addObject: [NSNumber numberWithInteger: 700]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 10]];
    [workingElement addObject: [NSNumber numberWithInteger: 1900]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 11]];
    [workingElement addObject: [NSNumber numberWithInteger: 5200]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 12]];
    [workingElement addObject: [NSNumber numberWithInteger: 8000]];
    [returnFlights addObject: workingElement];
    
    workingElement = [NSMutableArray array];
    [workingElement addObject: [NSNumber numberWithInteger: 13]];
    [workingElement addObject: [NSNumber numberWithInteger: 7300]];
    [returnFlights addObject: workingElement];
   
    NSInteger maxDistance = 10400;
    
    NSLog (@"forwardFlights: %@",forwardFlights);
    NSLog (@"returnFlights: %@",returnFlights);
    NSLog (@"maxDistance: %ld",maxDistance);
    
    NSArray *optimizedList = optimizeFlightDictionary (forwardFlights, returnFlights, maxDistance);
    
    NSLog (@"optimizedList: %@",optimizedList);
    
    [pool drain];
    return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.42 sec, absolute running time: 0.08 sec, cpu time: 0.04 sec, memory peak: 9 Mb, absolute service time: 0,51 sec