objective-calgorithmsliding-tile-puzzle

Counting inversions in NSArray


I'm new to Objective-C, so I'm trying to learn by implementing algorithms. I'm doing an A* search for solving the 8-puzzle problem. Before running the algorithm itself, I want to check whether the given puzzle combination is solvable. I've written this code in C++ and Swift before, but it doesn't work correctly in Objective-C for me. For this array it gives inversion count of 7, while it should be 0. Maybe I should use [NSArray objectAtIndex:] method to access elements and then convert them to integers to compare? I've tested different ways and the comparison works right. Please help me to find the bug.

    NSArray *test = @[@1, @2, @3, @4, @5, @6, @7, @0, @8];
    NSInteger inv_count = 0;

    for (NSInteger i = 0; i < 8; i++) {
        for (NSInteger j = i + 1; j < 9; j++) {
            if (test[j] && test[i] && test[i] > test[j]) {
                inv_count++;
            }
        }
    }

    NSLog(@"inv_count = %ld", (long)inv_count);

    if (inv_count % 2 == 0) {
        NSLog(@"Solvable.");
    } else {
        NSLog(@"Not solvable.");
    }

Solution

  • Basically this line of code is wrong:

    if(test[j] && test[i] && test[i]>test[j])
    

    test is an array of NSNumber instances, or basically it contains pointers. So to check if an element of that array is equal to zero or compare it you should get an integer value of the element:

    if(((NSNumber*)test[j]).integerValue && ((NSNumber*)test[i]).integerValue && ((NSNumber*)test[i]).integerValue > ((NSNumber*)test[j]).integerValue)
    

    Alternatively you can use - (NSComparisonResult)compare:(NSNumber *)aNumber method of NSNumber

    PS: Please check this for more info .