Counting inversions in NSArray

Question

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.");
    }

The condition will be false when we access element 0 with test[j]. Please see this: http://www.geeksforgeeks.org/check-instance-8-puzzle-solvable/ — denysowova, Jul 23 '17 at 17:41
@VolodymyrDenysov test[j] never returns 0 coz it's a pointer to an instance of NSNumber — ninjaproger, Jul 23 '17 at 17:43
Yeah, I ment if this algorithm would be written in another language. That commentator didn't get the algorithm right. — denysowova, Jul 23 '17 at 17:56

ninjaproger · Accepted Answer · 2017-07-23T17:37:21.643

0

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 .

edited Jul 23 '17 at 17:37

answered Jul 23 '17 at 17:31

ninjaproger

2,024
1
27
26

Thank you! It worked! But why does this work: if(test[3]>test[1]) NSLog(@"works") – denysowova Jul 23 '17 at 17:42
I thought when I use subscript notation, it calls the method [objectAtIndex:] which returns type id right? That's why I need conversion to NSNumber? – denysowova Jul 23 '17 at 17:45
@VolodymyrDenysov because `id` is a pointer to any type ;) if(test[3]>test[1]) NSLog(@"works") may work if pointer of test[3] located in higher address in device memory – ninjaproger Jul 23 '17 at 17:47
1

@VolodymyrDenysov - Re: `test[3]>test[1]`. This compares pointers, which is legal though in Objective-C you would rarely do this (you might in C). *However* you might have observed that it *appears to work* ordering some `NSNumber` objects by their *value*. This is an "accident of implementation" and if you are curious look up "tagged pointers". – CRD Jul 23 '17 at 17:52
Yeah, I also thought about that! Thanks a lot! And one more question, can I convert straight to NSInteger like: (NSInteger)test[index] and compare? Or I should convert to the NSNumber first? – denysowova Jul 23 '17 at 17:54
@CRD thanks for reference, I'll definitely check that! – denysowova Jul 23 '17 at 17:59
1

The expression `((NSNumber*)test[j]).integerValue` is *casting* not *converting*, it is telling the compiler that `test[j]` of type `id` - meaning a reference to *any* object - is in fact a reference to an `NSNumber`. The cast is used here so that the compiler can process the `.integerValue` property reference. You *cannot* just case an `NSNumber` reference to `NSInteger` to obtain the value, such a cast would return the integer equivalent of the reference value and would not call `integerValue`. – CRD Jul 23 '17 at 18:03

Counting inversions in NSArray

1 Answers1