We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Hackerland Radio Transmitters
  5. Discussions

Hackerland Radio Transmitters

Sort by

recency

|

421 Discussions

|

  • RocketshipToastr
     + 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

  • mrweisu
     + 0 comments

    def hackerlandRadioTransmitters(x, k): x = sorted(set(x)) count = 0 next_start = -float('inf')

    for pos, val in enumerate(x):

    if val < next_start:
        continue

    for rg in range(k, -1, -1):
        if pos + rg < len(x) and val + k >= x[pos+rg]:
            next_start = x[pos+rg] + k + 1
            count += 1
            break

return count

  • jono_reshef
     + 0 comments

    In Python, don't forget to run set on the house locations ("x") first. We only need to order the unique house locations.

  • anatoltbcm
     + 0 comments

    Java. Not the best solution, I think, but it works.

    public static int hackerlandRadioTransmitters(List<Integer> x, int k) {
    x.sort(Integer::compareTo);
    int count = 1;
    int currentBranchStart = x.get(0);
    boolean isLeftBranch = true;

    for (int i = 1; i < x.size(); i++) {
        int currentLocation = x.get(i);
        int prevLocation = x.get(i - 1);

        if (currentLocation - prevLocation > k) {
            count++;
            currentBranchStart = currentLocation;
            isLeftBranch = true;
            continue;
        }

        if (currentLocation - currentBranchStart > k) {
            if (isLeftBranch) {
                currentBranchStart = prevLocation;
            } else {
                currentBranchStart = currentLocation;
                count++;
            }
            isLeftBranch = !isLeftBranch;
        }
    }

    return count;
}

  • cherkashin_i_a
     + 0 comments
    def hackerlandRadioTransmitters(x, k):
    locations = sorted(x)
    station_location = first_house_outside_coverage = one_side_covered = two_side_coverage_counter = 0

    while station_location < len(locations):
        station_location_0 = station_location

        while first_house_outside_coverage < len(locations) and locations[first_house_outside_coverage] <= locations[station_location] + k:
            first_house_outside_coverage += 1

        if first_house_outside_coverage == station_location_0 + 1 or one_side_covered:
            station_location = first_house_outside_coverage
            two_side_coverage_counter += 1
            one_side_covered = 0
        else:
            station_location = first_house_outside_coverage - 1
            one_side_covered = 1

    return two_side_coverage_counter