1

I am trying to complete the google-foobar challenge #4 - escape-pods, my code passes 3 of 4 test cases on google-foobar I am not sure what is wrong with my code. Here is the question.

Write a function solution(entrances, exits, path) that takes an array of integers denoting where the groups of gathered bunnies are, an array of integers denoting where the escape pods are located, and an array of an array of integers of the corridors, returning the total number of bunnies that can get through at each time step as an int. The entrances and exits are disjoint and thus will never overlap. The path element path[A][B] = C describes that the corridor going from A to B can fit C bunnies at each time step. There are at most 50 rooms connected by the corridors and at most 2000000 bunnies that will fit at a time.

For example, if you have:

entrances = [0, 1]
exits = [4, 5]
path = [
  [0, 0, 4, 6, 0, 0],  # Room 0: Bunnies
  [0, 0, 5, 2, 0, 0],  # Room 1: Bunnies
  [0, 0, 0, 0, 4, 4],  # Room 2: Intermediate room
  [0, 0, 0, 0, 6, 6],  # Room 3: Intermediate room
  [0, 0, 0, 0, 0, 0],  # Room 4: Escape pods
  [0, 0, 0, 0, 0, 0],  # Room 5: Escape pods
]

Then in each time step, the following might happen: 0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3 1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3 2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5 3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5

So, in total, 16 bunnies could make it to the escape pods at 4 and 5 at each time step. (Note that in this example, room 3 could have sent any variation of 8 bunnies to 4 and 5, such as 2/6 and 6/6, but the final solution remains the same.)

I have tried to re-write my code multiple times but I do not understand what I am doing wrong.

def solution(entrances, exits, layout):
    exit_rooms = layout[exits[0]:]

    new_layout = []
    for i in layout:
        temp = []
        for item in i:
            if item != 0:
                temp.append(item)
        new_layout.append(temp)

    entrance = sorted(new_layout[:entrances[-1]+1])[::-1]

    rooms_to_remove = sorted(entrances + exits)[::-1]
    for i in rooms_to_remove:
        del new_layout[i]

    intermediate_rooms = new_layout

    max_exit_room = []
    for pods in exit_rooms:
        max_exit_room.append(max(pods))
    max_exit_room = max(max_exit_room)

    count = 0
    while True:
        max_room_switch = len(intermediate_rooms)
        current_room = 0 # switch intermediate rooms
        for room in entrance:
            xroom = room
            # if the number of intermediate rooms are less than number of bunnies in rooms
            if (max_room_switch != len(room) and len(room) > 1):
                xroom = sorted(room)
                xroom.remove(min(room))

            for bunnies in xroom:
                max_room = max(intermediate_rooms[current_room])
                n = max_room - bunnies

                if n <= 0:
                    count += max_room
                elif n > 0:
                    count += bunnies

                # room swtiching
                if max_room_switch > 1:
                    if max_room_switch == current_room:
                        break
                    else:
                        if current_room == max_room_switch-1:
                            current_room = 0
                        else:
                            current_room += 1

        break
    # print(count)
    return count

For the first two given tests the code passes(6, 16) and for the last one the answer is 935

1 Answer 1

2

I hope you got through that question. Anyways let me post a possible solution for the problem:

Notice that at each intermediate room level, the index of the room is the index of number of bunnies. Eg. For intermediate room 2 the bunnies that pass through the room 2 is "4 + 5" these values are at index 2 in the bunnies list respectively. So using that we can draft a possible solution:

def solution(entrances, exits, path):
    le = len(entrances)
    lp = len(path)
    lx = len(exits)
    bunn_count = 0
    inter_paths = path[le:(lp-lx)]                # To find all intermediate rooms
    for i in range(lp - le - lx):                 # Loop through range of length of intermediate rooms
        sum_range = sum(inter_paths[i])           # Sum of an intermediate room's possible number of bunnies allowed
        sum_enter = 0                             # Sum of bunnies that enter that room
        for j in entrances:
            sum_enter += path[j][le + i]          # Get all bunnies that enter a room
        bunn_count += min(sum_enter, sum_range)
    return bunn_count

Note: This is just my solution for the problem. Maybe you can reference https://surajshetiya.github.io/Google-foobar/ and https://vitaminac.github.io/Google-Foobar-Escape-Pods/ for better solutions.

2
  • 2
    That's not correct solution. This is max flow problem and you don't consider that for some nodes outputs may have smaller capacity than inputs
    – Jsowa
    Sep 11, 2020 at 22:56
  • 1
    ... well, it passes the tests...
    – hans
    Aug 14, 2022 at 19:08

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