Discussion on Hackerland Radio Transmitters Challenge

23 hours ago+ 0 comments

Maybe not the shortest or most efficient solution but I'm sharing anyway because it illustrates the use of loop invariants (the loop maintains a certain condition). Because of the loop invariant, I was able to debug it without a debugger or even print statements.

The idea behind my algo is to start at the leftmost house, go to the rightmost house I can place an antenna, and then go to the rightmost house that is covered by that antenna I placed.

So how did I implement this? I set up the variables l and i so that in every iteration of the while loop I can be sure that an antenna placed at house x[i] will reach house l or that the antenna placed at house l will reach house x[i] . For example, in the first iteration, l is the leftmost house and i=0 so x[i] is also the leftmost house. In this instance, an antenna placed at house x[i] will certainly reach house l because they're the same house.

So that condition is the loop invariant. Then, when I need to update l and i, I just need to make sure I don't violate the loop invariant. I initially had a bug in my code because of how I updated i and l when I went too far right. But I was able to debug without a debugger or even print statements because I just asked myself if loop invariant is still true after the variable update.

Hope the code below is clear and that this has been helpful!

def hackerlandRadioTransmitters(x, k):
    x = list(set(x))
    x.sort()
    i = 0
    l = x[i]
    placed_transmitter = False
    num_transmitters = 0
    while True: 
        # Every iteration of the loop maintains that a transmitter placed on the current 
        # house will reach the house at l 
        # OR that the current house is reached by the transmitter that has been placed at l
        if i + 1 >= len(x):
            if not placed_transmitter:
                # Place transmitter on current house because there's no more houses left to
                # place them
                num_transmitters += 1
            break
            
        if x[i + 1] - l > k:
            if not placed_transmitter:
                # A transmitter placed at house x[i+1] wouldn't reach hosue l so we put a
                # transmitter on house x[i]
                num_transmitters += 1
                placed_transmitter = True
                l = x[i]
                # Do not increment i because we don't know if a transmitter at house x[i+1]
                # can reach house l
            else:
                # The previously placed transmitter's rightmost house is at x[i] and we 
                # start looking for the next house to place a transmitter
                placed_transmitter = False
                l = x[i + 1]
                i += 1
        else:
            i += 1
        
    return num_transmitters

Cookie support is required to access HackerRank