4
\$\begingroup\$

I am going through coding challenges and I would like to get feedback on one of them. I am not sure if i can post the link to the challenge but here it is. CodeEval Challenge

Outside of your window, there's a wire between two buildings. Bats love to hang there but you notice they never hang closer than "d" centimeters from each other. They also don't hang closer than 6 centimeters from any of the buildings.

Your goal is to determine the maximum number of additional bats that can fit on that wire assuming they have zero width.

INPUT SAMPLE:

Each line of input contains three space separated integers: the length of the wire "l", distance "d" and number of bats "n" already hanging on the wire.

"n" numbers contain the positions of the bats in any order. All number are integers. You can assume that the bats already hanging on the wire are at least 6 cm from the poles and at least "d" centimeters apart from each other.:

22 2 2 9 11
33 5 0
16 3 2 6 10
835 125 1 113
47 5 0

Output
3
5
0
5
8

Here is my solution. I commented it a bit. I had to convert the method to C to get it passed through the automated system. Any suggestions to improve it would be greatly appreciated.

#define CENTIMETERS_FROM_WALL 6


int howManyBatsBetween(int pointOne, int pointTwo, int distanceBetween)
{
    //calculates how many bats you can put between two bats already on the wire
    //Have to make sure that it would be proper distance between the first bat and second bat
    int nextBatPosition = pointOne+distanceBetween;
    int batCount = 0;
    while ((nextBatPosition+distanceBetween) <= pointTwo) {
        batCount++;
        nextBatPosition+=distanceBetween;
    }
    return batCount;
}

-(void)batCount
{
    NSString *line = @"47 5 0"; //input
    //extract input
    NSArray *inputArray = [line componentsSeparatedByString:@" "];
    int lengthWire = [[inputArray objectAtIndex:0] intValue];
    int distanceFromEachOther = [[inputArray objectAtIndex:1] intValue];
    int batsOnWire = [[inputArray objectAtIndex:2] intValue];

    //create an array with bats already on the wire
    NSMutableArray *batsOnWireArray = [[NSMutableArray alloc]init];
    for (int indx = 1; indx <= batsOnWire; indx ++){
        [batsOnWireArray addObject:[inputArray objectAtIndex:indx+2]];
    }
    [batsOnWireArray sortedArrayUsingSelector:@selector(compare:)];
    int firstLocation = 0;
    int secondLocation = 0;
    int additionalBats = 0;

    if ([batsOnWireArray count] == 0) {
        //if there are no bats on the wire
        additionalBats = floor((lengthWire-(CENTIMETERS_FROM_WALL*2))/distanceFromEachOther)+1;
    }else{
        //calculate how many bats can be added between the beginig of the wire + 6cm and the first bat
        additionalBats = floor(([[batsOnWireArray objectAtIndex:0] integerValue]-CENTIMETERS_FROM_WALL)/distanceFromEachOther);

        for(int indx = 0; indx < [batsOnWireArray count]; indx++){
            firstLocation =[[batsOnWireArray objectAtIndex:indx] intValue];
            //calculate how many bats you can add between bats already on the wire
            if (indx < [batsOnWireArray count]-1) {
                secondLocation = [[batsOnWireArray objectAtIndex:indx+1] intValue];
                additionalBats += howManyBatsBetween(firstLocation, secondLocation, distanceFromEachOther);
            }else{
                //calculate how bats you can fit between the last bat and the end of the wire - 6cm
                additionalBats += floor(((lengthWire - CENTIMETERS_FROM_WALL) - firstLocation) / distanceFromEachOther);
            }

    }

    }

    NSLog(@"Result %d", additionalBats);
}
\$\endgroup\$
5
\$\begingroup\$

You posted this question with the tag, and made this comment:

I had to convert the method to C to get it passed through the automated system.

As such, I'm going to assume you're perhaps more interested in a review of the Objective-C stuff, so that's what this'll be. (Essentially, I'm ignoring the howManyBatsBetween function for this.)


As a start, the first problem I notice is that our method takes no arguments and returns nothing. The problem statement gives sample inputs in the form of strings and expects an integer return. Our method should be changed to reflect this:

- (NSInteger)batsOnWire:(NSString *)wire;

Now we can remove the hardcoded // input.


componentsSeparatedByString: is a good approach at breaking up the string, but we also need to make sure our input is in a good format.

NSArray *batPositions = [wire componentsSeparatedByString:@" "];

if (batPositions.count < 3) {
    return NSNotFound;
}

We'll use NSNotFound as a return result representing some sort of problem with the input. Truly we should actually take an NSError ** as an argument, but I won't get into that mess. I'll keep it simple for now. The point here is, we're dealing with inputs, either typed by a user or read from a file... and inputs always have a chance of having errors, so we have to deal with that.


Grabbing lengthWire, distanceFromEachOther, and batsOnWire as you do is fine.

But again, we are dealing with user input. The problem with calling intValue is that if the string in question can't be parsed as an int, the method just returns 0. It's impossible to tell the difference between @"0" and @"Hello World" when looking at what they return intValue.

[@"0" intValue] == [@"Hello World" intValue]

Instead, we can convert these strings to NSNumber objects... which we'll want to do later for another reason which I'll address, but here's how we do it:

NSNumberFormatter *formatter = [[NSNumberFormatter alloc] init];
formatter.numberStyle = NSNumberFormatterDecimalStyle;

NSNumber lengthWire = [formatter numberFromString: batPositions[0]];
if (!lengthWire) {
    return NSNotFound;
}

NSNumberFormatter's numberFromString: method returns nil if the string cannot be parsed to a number. Otherwise, it returns an NSNumber object representing the value. Once we do the if(!lengthWire) check, we know we have a valid number. We can always extract the raw int value by calling the same intValue on this NSNumber object.


But there's another reason we're going to want the entire array of strings converted into an array of NSNumber objects.

Given the following mutable array of strings:

@[@"1", @"2", @"40", @"10", @"300", @"100", @"9"];

If we sort if using sortedArrayUsingSelector:@selector(compare:)];, the result would be an array of this order:

@[@"1", @"10", @"100", @"2", @"300", @"40", @"9"];

And this isn't the right order. The compare: method of NSString compares the strings character by character.

If we have to strings we want to compare individually, we can call another method:

[@"2" compare:@"100" options:NSNumericSearch];

And we'll get the correct numeric result (2 would be sorted before 100 correctly).

But when using sortedArrayUsingSelector:, we can't use a method that takes other arguments. We can't specify that our strings our compared numerically.

However, if they are NSNumber objects, they'll of course be compared as numbers and sorted appropriately. So if we turn our array of strings into an array of NSNumber objects, and then call the same:

[arrayOfNumberObjects sortedArrayUsingSelector:@selector(compare:)];

We'll get our array sorted in the proper order.

And once again, NSNumber responds to the intValue method in exactly the same way NSString does, so we can still use this to get a workable int out of the object.


#define CENTIMETERS_FROM_WALL 6

As one final note about Objective-C, we don't really care for #define variables. I can't discourage it enough. In fact, Apple agrees with me. As evidence, you can't even use the #define functionality in their new language, Swift, at all.

Instead, we should opt for a typed constant:

static const int kCentimetersFromWall = 6;
\$\endgroup\$
  • \$\begingroup\$ Thank you very much for the detailed response. It's really great help. I didn't realize that the sort wouldn't work well because i am storing the numbers as string. Make sense. I will switch to using static const instead of define. Also because it's a challenge i copy paste part of the code and do not need to return anything from the method. I wanted to ask you as far as logic of solving the challenge. Does it make sense or could be improved? \$\endgroup\$ – Yan Nov 5 '14 at 2:40
1
\$\begingroup\$

One small addition regarding Objective-C:

[batsOnWireArray sortedArrayUsingSelector:@selector(compare:)];

returns a new array with the sorted elements, but leaves the receiver batsOnWireArray unmodified. What need is

[batsOnWireArray sortUsingSelector:@selector(compare:)];

or, taking @nhgrifs answer into account,

[arrayOfNumberObjects sortUsingSelector:@selector(compare:)];

otherwise your code will not work correctly with unsorted data.


The howManyBatsBetween method can be simplified, you don't need a loop:

int howManyBatsBetween(int pointOne, int pointTwo, int distanceBetween) {
    int batCount = (pointTwo - pointOne)/distanceBetween - 1;
    return batCount < 0 ? 0 : batCount;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the reply. It makes sense as far as sorting array. I should have converted to NSNumber before adding them to the array. As far as howManyBatsBetween that's what i tried first but this wouldn't work because the bats that are already on the wire are spaced at least distanceBetween but could be anywhere on the wire and i have to make sure that they are spaced properly from the last one. For example if the bat is at 6cm and 10cm and they have to be apart 3cm i would get batcount 1 but its wrong because it would be sitting 9cm and thats too close to the second bat had to use a loop. \$\endgroup\$ – Yan Nov 5 '14 at 16:34
  • 1
    \$\begingroup\$ @Yan: There was an error in the formula, it should work now for all cases. For example, howManyBatsBetween(6, 10, 3) = (10 - 6)/3 - 1 = 4/3 - 1 = 1 - 1 = 0, and howManyBatsBetween(6, 12, 3) = (12 - 6)/3 - 1 = 6/3 - 1 = 2 - 1 = 1. \$\endgroup\$ – Martin R Nov 5 '14 at 17:16
  • \$\begingroup\$ That make sense. This way it would make sure that the last bat would not be too close to the bat at point two. Thanks! \$\endgroup\$ – Yan Nov 5 '14 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.