Jumping on the clouds

Question

I have started the Hackerrank interview preparation kit. The first problem I have solved with Swift is as follows:

Emma is playing a new mobile game that starts with consecutively numbered clouds. Some of the clouds are thunderheads and others are cumulus. She can jump on any cumulus cloud having a number that is equal to the number of the current cloud plus 1 or 2. She must avoid the thunderheads. Determine the minimum number of jumps it will take Emma to jump from her starting position to the last cloud.

For each game, Emma will get an array of clouds numbered 0 if they are safe or 1 if they must be avoided.

func jumpingOnClouds(c: [Int]) -> Int {
    var jump = 0
    var location = 0
    repeat {
        if (location + 2 < c.count) && 
        (c[location + 2] == 0) {
            location += 2
        } else {
            location += 1
        }
        if location >= c.count {
            break
        }
        jump += 1
    } while location < c.count
    return jump
}

It's time complexity is \$O(n)\$. Are there any ways I could reduce this? I am also interested in improving the code quality. Are there ways I can take better advantage of Swift to improve my code?

Answer 1

Your program is clearly written, and works correctly (to the best of my knowledge). I don't think that the time complexity is \$O(n)\$ can be improved, because the array must be traversed in order to locate the dangerous thunderheads. Your algorithm already optimizes that by checking only every second element (if that is a safe spot), relying on the fact that a solution is guaranteed.

The program can be improved a bit though. The while location < c.count condition of the main loop will always be true because the loop is always “early left” at

if location >= c.count {
    break
}

As a consequence, the program computes one location beyond the array bounds which is not needed (and not counted). This can be simplified by using a while-loop instead:

while location < c.count - 1 {
    if (location + 2 < c.count) &&
        (c[location + 2] == 0) {
        location += 2
    } else {
        location += 1
    }
    jump += 1
}

This is shorter and easier to understand because there is only one terminating condition for the loop instead of two.

A possible improvement might be to run the loop until one of the last two positions it reached, because then the test against the array count is done only once per iteration and not twice:

while location < c.count - 2 {
    if c[location + 2] == 0 {
        location += 2
    } else {
        location += 1
    }
    jump += 1
}
return location == c.count - 1 ? jump : jump + 1

A further optimization would be to use that if we do a size 1 jump because of a thunderhead, the following jump will always be of size 2:

while location < c.count - 2 {
    if c[location + 2] == 0 {
        // Jump two positions:
        location += 2
        jump += 1
    } else {
        // Jump one position and then two positions:
        location += 3
        jump += 2
    }
}
return location == c.count - 1 ? jump : jump + 1

But the performance increase will probably be negligible since the arrays have at most 100 elements.

Some minor points: The parentheses in

if (location + 2 < c.count) &&
    (c[location + 2] == 0)

are not needed because the comparison operators have a higher precedence than the logical operators:

if location + 2 < c.count && c[location + 2] == 0

Finally, I would name the counter variable jumps or jumpCount to better describe its purpose.