Google Foobar Challenge Solutions with Animations

Share Buy me a coffee

Recently, I was invited to Google's secret coding interview, Foobar Challange. From Markov chains to cellular automata, this challenge was the hardest and most fun coding experience I have ever had. I have decided to share my solutions with the animations I have made for questions, which make them easier to understand.

TL;DR? Check the GitHub repository.

Go back to the blogs

---

One day, while I was working on my projects, a message appeared at the top of my Google search results. I don't exactly remember what I was searching for, but I guess it was about multi-threading.

After clicking the message, I was redirected to a website, and the challenge has started. The challenge consists of 5 levels and 9 questions in total.

Level 1

1. Re-ID

Level 2

2.1. Hey, I Already Did That!

2.2. Elevator Maintenance

Level 3

3.1. Prepare the Bunnies' Escape

3.2. Doomsday Fuel

3.3. Don't Get Volunteered!

Level 4

4.1. Free the Bunny Workers

4.2. Bringing a Gun to a Trainer Fight

Level 5

5. Expanding Nebula

For context, we are in a space station where Commander Lambda is on charge, and we are trying to help the bunnies used as workers.

1. Re-ID

Question

Solution

This one is pretty straight-forward. Since the question states that the value of n will always be between 0 and 10000, we can simply create a string to store the prime numbers until the length of the string is 10005. Then we can ask for the n value and return the next 5 digits from the string.

To find the prime numbers, we can use a for loop. Starting from 2, we can check if the number is divisible by any other number. If it is not divisible by any number, then it is a prime number. We can add this number to our string.

It is not possible to calculate prime numbers without brute forcing (for now, 2024), so if you come up with a formula to find the prime numbers, congratulations on your Nobel Prize.

It is also possible to use i/2 as the upper limit of the range in the for loop for better optimization, since a number is not divisible by any number greater than half of itself.

Code

# Creating a string of prime numbers
prime_string = ""

# Finding the primes until the length of the string is 10005
i = 2
while len(prime_string) < 10005:
    for j in range(2, i):
        if i % j == 0:
            break
    else:
        prime_string += str(i)
    i += 1

def solution(n):
    # Returning the next five digits in the string
    return prime_string[n:n+5]

2.1. Hey, I Already Did That!

Question

Solution

My approach to this question is to create a list to store the values of z and check if the new value of z is in the list after each iteration. If it is, then we can return the length of the list minus the index of the new value of z. If it is not, then we can add the new value of z to the list and continue the iteration.

To find the value of z, we can convert the string n to a list of integers, sort it in descending order to find x, sort it in ascending order to find y, and then find z by subtracting y from x. We can convert the list of integers back to a string and add leading zeros if necessary to maintain the length of k.

Python's int function has a base parameter that can be used to convert a string to an integer, with the base parameter specifying the base of the number in the string.

print(int('210111', 3)) # Prints 580

However, Python doesn't have a built-in function to convert an integer to a string with a specific base. We can create a function to do this by using the divmod function to find the quotient and remainder of the division.

def to_base_b(n, b):
    if n == 0:
        return '0'
    numbers = []
    while n:
        n, r = divmod(n, b)
        numbers.append(str(r))
    return ''.join(reversed(numbers))

We know that 580 in base 3 is 210111. Let's test our function with this example.

print(to_base_b(580, 3)) # Prints 210111

Now we can implement our algorithm to find the length of the ending cycle of the algorithm.

Code

def to_base_b(n, b):
    """
    Converts an integer n to a string in base b.
    """
    if n == 0:
        return '0'

    numbers = []

    while n:
        n, r = divmod(n, b)
        numbers.append(str(r))

    return ''.join(reversed(numbers))

def solution(n, b):
    list_of_z = []

    while True:
        # Converting n to a string
        n = str(n)

        # Creating x by sorting n in descending order
        x = ''.join(sorted(n, reverse=True))

        # Creating y by sorting n in ascending order
        y = ''.join(sorted(n))

        # Converting x and y to base b
        x = int(x, b)
        y = int(y, b)

        # Calculating z
        z = x - y

        # Converting z to base b
        z = to_base_b(z, b)

        # Adding leading zeros to z to maintain length k if necessary
        while len(z) < len(n):
            z = '0' + z

        # Checking if z is in the list of z's
        if z in list_of_z:
            return len(list_of_z) - list_of_z.index(z)
        else:
            list_of_z.append(z)
            n = z

2.2. Elevator Maintenance

Question

Solution

Surprisingly easy question. Python's sort method has a key parameter that can be used to sort a list of strings based on a custom key function. We can define a custom key function that splits the string on the '.' character, converts each part of the split string to an integer, and returns the list of integer parts. This way, we can sort the list of strings based on the major, minor, and revision numbers.

Code

def sort_key(s):
    """
    Splits the string on the '.' character, 
    converts each part of the split string to an integer,
    and returns the list of integer parts.
    """
    # Splitting the string on the '.' character
    split_string = s.split('.')

    # Converting each part of the split string to an integer
    integer_parts = map(int, split_string)

    return list(integer_parts)

def solution(l):
    # Sorting the list using the defined key function
    l.sort(key=sort_key)

    # Returning the sorted list
    return l

3.1. Prepare the Bunnies' Escape

Question

Solution

Here is where things get interesting. After this question, the difficulty of the questions increases rapidly, which makes them more fun to solve.

My approach to this question is to create every single possible maze and use brute force. I defined a function called wall_breaker, which creates mazes by replacing a different 1 with 0 every step. Then we can feed the astar function, which solves the mazes by using the astar algorithm. After that we can return the shortest one.

At first, I tried solving the mazes using the BFS algorithm, but it failed some of the test cases. Later, I noticed that BFS fails to solve the mazes unless the path is some sort of tunnel.

Code

def astar(map):
    """
    A* algorithm to find the shortest path in a binary maze,
    starting from the top left and ending at the bottom right.
    """
    start = (0, 0)
    goal = (len(map) - 1, len(map[0]) - 1)

    # Defining movement directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # Initializing open and closed lists
    open_list = []
    closed_set = set()

    # Adding start node to open list
    open_list.append((0, start, 0))  # (total_cost, node, g_cost)

    while open_list:
        open_list.sort(key=lambda x: x[0])  # Sort by total_cost
        total_cost, current_node, g_cost = open_list.pop(0)
        closed_set.add(current_node)

        # Checking if current node is goal node
        if current_node == goal:
            return g_cost + 1

        # Generating successors (neighbors) of current node
        for dr, dc in directions:
            neighbor_row, neighbor_col = current_node[0] + dr, current_node[1] + dc

            # Checking if neighbor is within bounds and not a wall
            if 0 <= neighbor_row < len(map) and 0 <= neighbor_col < len(map[0]) and map[neighbor_row][neighbor_col] == 0:
                neighbor_node = (neighbor_row, neighbor_col)
                # Calculating heuristic (h value)
                heuristic = abs(neighbor_row - goal[0]) + abs(neighbor_col - goal[1])
                # Calculating total cost (f value)
                total_cost = g_cost + 1 + heuristic  # Cost to move to neighbor is 1
                # Checking if neighbor is already in closed set
                if neighbor_node in closed_set:
                    continue
                # Checking if neighbor is already in open list and has a lower total cost
                for i, (tc, n, _) in enumerate(open_list):
                    if n == neighbor_node and total_cost >= tc:
                        break
                else:
                    open_list.append((total_cost, neighbor_node, g_cost + 1))

    # If no path found
    return len(map) * len(map[0])

def wall_breaker(map):
    """
    For a given map, generates all possible maps with
    breaking one wall at a time (Converting 1 to 0) and returns the dictionary
    of the newly generated maps.
    """
    new_maps = {}
    # Before creating new maps, we append the original map to the dictionary
    new_maps["original_map"] = map

    for i in range(len(map)):
        for j in range(len(map[0])):
            if map[i][j] == 1:
                new_map = [row[:] for row in map]
                new_map[i][j] = 0
                new_maps["map_{0}_{1}".format(i, j)] = new_map

    return new_maps

def solution(map):
    # Get all possible maps by breaking one wall at a time
    new_maps = wall_breaker(map)

    # Finding the shortest path for each map
    shortest_paths = {}

    for key, value in new_maps.items():
        shortest_paths[key] = astar(value)

    # Returning the minimum path length
    return min(shortest_paths.values())

3.2. Doomsday Fuel

Question

Solution

This question reminds me of my stochastic differential equation lectures from my university, which makes it my favorite question in this challenge. Aside from fancy stuff, the problem can be reduced to an absorbing Markov chain. Watch this video series to learn how to solve the equation.

Let's look at the absorbing Markov chain in our example. The given matrix is:

\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 1 \\ 4 & 0 & 0 & 3 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix}

We can get the probabilities by dividing each number by the sum of the rows. Visualization can make it easier to grasp.

We need to convert this matrix to a transition matrix with probabilities. In the code, the create_transition_matrix function handles this conversion. Notice the terminal states are in the first rows.

\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 1/3 & 2/9 & 0 & 4/9 & 0 \\ \end{bmatrix}

Now we have I, $0$, R, and Q matrices.

\[ I = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} % , % \:\: % 0 = % \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 0 \\ 0 & 0 \\ \end{bmatrix} \] \[ R = \begin{bmatrix} 0 & 0 & 0 & 1/2 \\ 0 & 1/3 & 2/9 & 0 \\ \end{bmatrix} % , % \:\: % Q = % \begin{bmatrix} 0 & 1/2 \\ 4/9 & 0 \\ \end{bmatrix} \]

We can calculate the matrix F.

\begin{align} F &= (I - Q)^{-1} = \left( \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} - \begin{bmatrix} 0 & 1/2 \\ 4/9 & 0 \\ \end{bmatrix} \right)^{-1} \\ &= \begin{bmatrix} 1 & -1/2 \\ -4/9 & 1 \\ \end{bmatrix}^{-1} = \begin{bmatrix} 9/7 & 9/14 \\ 4/7 & 9/7 \\ \end{bmatrix} \end{align}

Finally, we can calculate the absorbing matrix FR.

\begin{align} FR = F \cdot R &= \begin{bmatrix} 9/7 & 9/14 \\ 4/7 & 9/7 \\ \end{bmatrix} \cdot \begin{bmatrix} 0 & 0 & 0 & 1/2 \\ 0 & 1/3 & 2/9 & 0 \\ \end{bmatrix} \\ &= \begin{bmatrix} 0 & 3/14 & 1/7 & 9/14 \\ 0 & 3/7 & 2/7 & 2/7 \\ \end{bmatrix} \\ \end{align}

Check out the first row of the FR matrix. These are the probabilities we are looking for. Making a common denominator gives us the answer in the form of [s2.numerator, s3.numerator, s4.numerator, s5.numerator, denominator], which is [0, 3, 2, 9, 14].

You will also notice the greatest_common_divisor and least_common_multiple functions in the code, which are used to find the common denominator.

Code

from fractions import Fraction

def create_transition_matrix(m):
    """
    Converts the given matrix to a transition matrix with probabilities.

    Creates the form
    I | 0
    --|--
    R | Q
    where I is the identity matrix, 0 is the zero matrix, R and Q are the submatrices.
    
    To achieve the desired form, we need to do the following:
    1. Convert the given numbers to probabilities by dividing each number by the sum of the row.
    2. Determine the terminal states (rows with all zeros).
    3. Convert the 0 in the self directed positions to 1.
    4. Reorder the columns and rows where the terminal states are first.
    """

    # Convert the given numbers to probabilities
    for i in range(len(m)):
        row_sum = sum(m[i])
        for j in range(len(m[i])):
            m[i][j] /= row_sum if row_sum != 0 else 1

    # Determine the terminal states
    terminal_states = []
    non_terminal_states = []
    for i in range(len(m)):
        if sum(m[i]) == 0:
            terminal_states.append(i)
        else:
            non_terminal_states.append(i)

    # Convert the 0 in the self directed positions to 1
    for i in range(len(m)):
        if i in terminal_states:
            m[i][i] = 1

    # Reorder the columns and rows where the terminal states are first
    new_m = []
    for i in terminal_states:
        new_m.append([m[i][j] for j in terminal_states + non_terminal_states])
    for i in non_terminal_states:
        new_m.append([m[i][j] for j in terminal_states + non_terminal_states])

    # Return the transition matrix and the number of terminal states
    return new_m, len(terminal_states)

def inverse_matrix(matrix):
    """
    Returns the inverse of the given matrix using the Gauss-Jordan elimination method.
    """
    size = len(matrix)
    inverse = [[0 if row != column else 1 for column in range(size)] for row in range(size)]

    for i in range(size):
        if matrix[i][i] == 0:
            for j in range(i + 1, size):
                if matrix[j][i] != 0:
                    matrix[i], matrix[j] = matrix[j], matrix[i]
                    inverse[i], inverse[j] = inverse[j], inverse[i]
                    break
            else:
                raise ValueError("Matrix is not invertible")
        for j in range(i + 1, size):
            ratio = matrix[j][i] / matrix[i][i]
            for k in range(size):
                matrix[j][k] -= ratio * matrix[i][k]
                inverse[j][k] -= ratio * inverse[i][k]
    for i in range(size - 1, -1, -1):
        for j in range(i - 1, -1, -1):
            ratio = matrix[j][i] / matrix[i][i]
            for k in range(size):
                matrix[j][k] -= ratio * matrix[i][k]
                inverse[j][k] -= ratio * inverse[i][k]
        div = matrix[i][i]
        for k in range(size):
            matrix[i][k] /= div
            inverse[i][k] /= div
    return inverse

def calculate_fr(transition_matrix, terminal_states):
    """
    Calculates the fundamental matrix and the absorbing matrix from the given transition matrix.
    """
    # Split the transition matrix into the fundamental matrix and the absorbing matrix
    Q = []
    R = []

    # The matrix is in the form of
    # I | 0
    # --|--
    # R | Q
    # so R is on the bottom left and Q is on the bottom right
    
    # Q is the submatrix of transition_matrix containing transitions between non-terminal states
    # R is the submatrix of transition_matrix containing transitions from non-terminal states to terminal states
    for i in range(terminal_states, len(transition_matrix)):
        Q.append(transition_matrix[i][terminal_states:])
        R.append(transition_matrix[i][:terminal_states])

    # Calculate the fundamental matrix
    I = []
    for i in range(len(Q)):
        I.append([0] * len(Q))
        I[i][i] = 1

    # F = (I - Q)^-1
    F = []
    for i in range(len(Q)):
        F.append([I[i][j] - Q[i][j] for j in range(len(Q))])

    F = inverse_matrix(F)

    # Calculate the absorbing matrix which is F*R
    FR = []
    for i in range(len(F)):
        FR.append([0] * len(R[0]))
        for j in range(len(R[0])):
            for k in range(len(R)): 
                FR[i][j] += F[i][k] * R[k][j]

    return FR

def greates_common_divisor(list_of_numbers):
    """
    Returns the greatest common divisor of the given numbers.
    """
    if len(list_of_numbers) == 2:
        a, b = list_of_numbers
        while b:
            a, b = b, a % b
        return a
    else:
        return greates_common_divisor([list_of_numbers[0], greates_common_divisor(list_of_numbers[1:])])

def least_common_multiple(list_of_numbers):
    """
    Returns the least common multiple of the given numbers.
    """
    lcm = list_of_numbers[0]
    for i in list_of_numbers[1:]:
        lcm = lcm * i // greates_common_divisor([lcm, i])
    return lcm

def solution(m):
    if len(m) == 1:
        return [1, 1]
    
    # Convert the given matrix to a transition matrix with probabilities
    transition_matrix, terminal_states_count = create_transition_matrix(m)

    # Calculate the fundamental matrix and the absorbing matrix from the given transition matrix
    FR = calculate_fr(transition_matrix, terminal_states_count)

    # Converting the probabilities to fractions
    FR = [[Fraction(x).limit_denominator() for x in FR[i]] for i in range(len(FR))]

    # Since the starting state is 0, we can directly return the first row of the absorbing matrix
    probabilities = FR[0]

    # Now we need to find the least common multiple of the denominators
    denominators = [x.denominator for x in probabilities]
    lcm = least_common_multiple(denominators)

    # Return the result
    result = [x.numerator * (lcm // x.denominator) for x in probabilities] + [lcm]
    
    return result

3.3. Don't Get Volunteered!

Question

Solution

I have played a lot of chess. I mean, a lot. After reading the question, I grabbed my chessboard and the knight piece and tried to figure out a pattern, if there was any. Then I came up with the following table:

What you are seeing here is the minimum number of moves to reach that square from the square that the knight is on. You may notice the size of the table is greater than 8x8, which is the size of a chessboard. This is because I thought it would be easier to move the board on this map instead of recalculating the moves every time with different knight placements.

Then I noticed an exception in the pattern. If the knight is placed on the corner, the nearest corner becomes reachable after 4 moves.

And another exception is If the knight is placed on one diagonal away from the corner, the closest corner square becomes reachable in 4 moves.

Changing the grid according to these exceptions, I wrote the solution function. You will also notice the helper functions get_directions, is_valid_move, move, and navigator in the code. These are used to find the directions from the source to the destination and to move the knight on the grid. I am certain that there are more efficient ways to solve the navigation part, but I didn't want to dwell on it too much.

Code

grid = [
[6,5,4,5,4,5,4,5,4,5,4,5,4,5,6,],
[5,4,5,4,3,4,3,4,3,4,3,4,5,4,5,],
[4,5,4,3,4,3,4,3,4,3,4,3,4,5,4,],
[5,4,3,4,3,2,3,2,3,2,3,4,3,4,5,],
[4,3,4,3,2,3,2,3,2,3,2,3,4,3,4,],
[5,4,3,2,3,4,1,2,1,4,3,2,3,4,5,],
[4,3,4,3,2,1,2,3,2,1,2,3,4,3,4,],
[5,4,3,2,3,2,3,0,3,2,3,2,3,4,5,],
[4,3,4,3,2,1,2,3,2,1,2,3,4,3,4,],
[5,4,3,2,3,4,1,2,1,4,3,2,3,4,5,],
[4,3,4,3,2,3,2,3,2,3,2,3,4,3,4,],
[5,4,3,4,3,2,3,2,3,2,3,4,3,4,5,],
[4,5,4,3,4,3,4,3,4,3,4,3,4,5,4,],
[5,4,5,4,3,4,3,4,3,4,3,4,5,4,5,],
[6,5,4,5,4,5,4,5,4,5,4,5,4,5,6,],
]

def get_directions(start, end, grid_size=8):
    """
    Returns the directions from start to end in the grid.
    """
    # Calculate row and column for start and end
    start_row, start_col = divmod(start, grid_size)
    end_row, end_col = divmod(end, grid_size)

    # Calculate the number of steps in each direction
    steps_right = end_col - start_col
    steps_down = end_row - start_row

    # Generate the directions based on the steps
    directions = (
        "R" * max(steps_right, 0)
        + "L" * max(-steps_right, 0)
        + "D" * max(steps_down, 0)
        + "U" * max(-steps_down, 0)
    )

    return directions

def is_valid_move(x, y, grid):
    """
    Returns True if the move is valid, False otherwise.
    """
    return 0 <= x < len(grid) and 0 <= y < len(grid[0])

def move(x, y, direction):
    """
    Returns the new position after moving in the given direction.
    """
    directions = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
    dx, dy = directions[direction]
    new_x, new_y = x + dx, y + dy
    return new_x, new_y

def navigator(path, grid):
    """
    Returns the value of the destination cell after following the given path.
    """
    current_x, current_y = 7, 7  # Starting position

    for move_direction in path:
        current_x, current_y = move(current_x, current_y, move_direction)
        if not is_valid_move(current_x, current_y, grid):
            return None  # Invalid move, return None

    return grid[current_x][current_y]

def solution(src, dest):
    # There are few exceptions where grid is changed depending on the knight's position

    # The knight being in the corners
    if src in [0, 7, 56, 63]:
        grid[6][6] = 4
        grid[6][8] = 4
        grid[8][6] = 4
        grid[8][8] = 4

    # The knight being in one diagonal away from the corners
    elif src == 9:
        grid[6][6] = 4

    elif src == 14:
        grid[6][8] = 4

    elif src == 49:
        grid[8][6] = 4

    elif src == 54:
        grid[8][8] = 4

    else:
        pass

    # Finding directions from src to dest
    directions = get_directions(src, dest)

    min_moves = navigator(directions, grid)

    return min_moves

4.1. Free the Bunny Workers

Question

Solution

I think this question was the most challenging one for me in this challenge. I spent most of my time trying to understand what the question was asking. But it can be summarized like this:

Randomly select the required bunnies from the total bunnies. Selected bunnies should have all the unique keys together.

Say we have 5 bunnies in total and 3 required bunnies. If we select any 3 bunnies, they should have all the keys (from 0 to 9) together.

How do we find the number of unique keys? It is the number of combinations of the total bunnies with the required bunnies. In this case, it is $5 \choose 3$.

I have found these patterns by trial and error:

• Total number of keys: Combination(number of total bunnies, number of required bunnies) * number of required bunnies
• Number of keys each bunny has: total number of keys / number of total bunnies
• Number of copies each key has: number of total bunnies - number of required bunnies + 1
• Number of unique keys: Combination(number of total bunnies, number of copies each key has)

Assuming that we have 5 bunnies in total, we can get the following table using the formulas above:

Bunnies	Required bunnies	Total keys	Key per bunny	Copy per key	Unique key
5	1	5	1	5	1
5	2	20	4	4	5
5	3	30	6	3	10
5	4	20	4	2	10
5	5	5	1	1	5

But how do we assign the keys to the bunnies? After brainstorming for a long time, it clicked. We shouldn't assign keys to bunnies; we should assign bunnies to key pairs. We can find the key pairs using the combinations function from the itertools module.

from itertools import combinations
num_buns = 5
num_required = 3

replicas = num_buns - num_required + 1

print(list(combinations(range(num_buns), replicas))

# Output
# [(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), (0, 3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

Then we can create a dictionary to store the keys for each bunny.

keys = {}
for i in range(num_buns):
    keys[i] = []

print(keys)

# Output
# {0: [], 1: [], 2: [], 3: [], 4: []}

After that, we can assign the keys to the bunnies.

for i in range(len(key_pairs)):
    for j in key_pairs[i]:
        print('Assigning key', i, 'to bunny', j)
        keys[j].append(i)

# Output
# Assigning key 0 to bunny 0
# Assigning key 0 to bunny 1
# Assigning key 0 to bunny 2
# Assigning key 1 to bunny 0
# Assigning key 1 to bunny 1
# Assigning key 1 to bunny 3
# Assigning key 2 to bunny 0
# Assigning key 2 to bunny 1
# Assigning key 2 to bunny 4
# Assigning key 3 to bunny 0
# Assigning key 3 to bunny 2
# Assigning key 3 to bunny 3
# Assigning key 4 to bunny 0
# Assigning key 4 to bunny 2
# Assigning key 4 to bunny 4
# Assigning key 5 to bunny 0
# Assigning key 5 to bunny 3
# Assigning key 5 to bunny 4
# Assigning key 6 to bunny 1
# Assigning key 6 to bunny 2
# Assigning key 6 to bunny 3
# Assigning key 7 to bunny 1
# Assigning key 7 to bunny 2
# Assigning key 7 to bunny 4
# Assigning key 8 to bunny 1
# Assigning key 8 to bunny 3
# Assigning key 8 to bunny 4
# Assigning key 9 to bunny 2
# Assigning key 9 to bunny 3
# Assigning key 9 to bunny 4

Code

from itertools import combinations

def solution(num_buns, num_required):
    # Tricky part is to figure out how many copies of each key to give to the bunnies
    replicas = num_buns - num_required + 1
    
    key_pairs = list(combinations(range(num_buns), replicas))

    # Creating a dictionary to store the keys for each bunny
    keys = {}
    for i in range(num_buns):
        keys[i] = []

    # Assigning the keys to the bunnies
    for i in range(len(key_pairs)):
        for j in key_pairs[i]:
            keys[j].append(i)

    # Creating a list of the keys for each bunny
    key_list = []
    for i in range(num_buns):
        key_list.append(keys[i])

    return key_list

4.2. Bringing a Gun to a Trainer Fight

Question

Solution

Thanks to the optics lectures in high school, figuring this out took me only a few minutes, but coding the solution wasn't that easy. The idea is to find the reflection points of the trainer and, depending on the range of the beam, find the possible shots to hit the trainer.

Like in the example given in the question, assume that you are on the point (1, 1), the trainer is on the point (2, 1), and the room is 3x2. When you find the reflections and draw a circle around yourself with a radius of 4, you will notice that there are 9 reflection points of the trainer inside the circle.

One thing to consider here is if there are any reflections of yourself between you and the trainer's reflection points. If there are, you should eliminate those shots, since the beam will hit you before hitting the trainer by bouncing off the walls.

Another one is to check if there are any reflections behind the trainer and the trainer's reflection points. The question is asking how many distinct directions you can fire to hit the trainer, so counting the reflections behind the trainer or the trainer's reflection points leads to the wrong results.

In our example, there are 2 reflection points that satisfy the conditions above. So the answer is 9-2=7.

I spent almost all of my time on this question, optimizing my approach. You will notice the helper functions calculate_angle_and_distance and calculate_reflection_points in the code, which serve the purpose explained above.

Code

from math import sqrt, atan2

def calculate_angle_and_distance(point):
    '''
    Returns the angle and distance of the point from the origin.
    '''
    x, y = point
    return atan2(y, x), sqrt(x**2 + y**2)

def calculate_reflection_points(the_point, dimensions, loop_count):
    '''
    Returns the reflection points of the given point depending on the dimensions and the loop count.
    Dimensions are the width and height of the room, assumed to have mirrored walls.
    Loop count is the number of times the room is mirrored.
    '''
    reflection_points = {tuple(the_point)}
    max_x, max_y = dimensions
    new_reflection_points = set()

    for _ in range(loop_count):
        for point in reflection_points:
            x, y = point
            reflections = {(x, 2 * max_y - y), (2 * max_x - x, y), (2 * max_x - x, 2 * max_y - y)}
            new_reflection_points.update(reflections - reflection_points)
        max_x *= 2
        max_y *= 2
        reflection_points.update(new_reflection_points)
        new_reflection_points.clear()

    final_reflection_points = set()
    for point in reflection_points:
        x, y = point
        final_reflection_points.update({(x, y), (-x, y), (x, -y), (-x, -y)})

    return final_reflection_points

def solution(dimensions, your_position, trainer_position, distance):
    loop_count = min(distance // min(dimensions), 9)
    trainer_reflection_points = calculate_reflection_points(trainer_position, dimensions, loop_count)

    vectors = [(point[0] - your_position[0], point[1] - your_position[1]) for point in trainer_reflection_points]
    possible_shots = [(x, y) for x, y in vectors if sqrt(x**2 + y**2) < distance]

    # Calculate angle and distance for each shot
    shots_with_angle_and_distance = [(calculate_angle_and_distance(shot), shot) for shot in possible_shots]

    # Sort shots by angle and then by distance
    shots_with_angle_and_distance.sort()

    # Remove shots that have the same angle and a greater distance
    previous_angle = None
    shots_to_keep = []
    for (angle, distance), shot in shots_with_angle_and_distance:
        if angle != previous_angle:
            shots_to_keep.append(shot)
            previous_angle = angle

    possible_shots = shots_to_keep

    your_reflection_points = calculate_reflection_points(your_position, dimensions, loop_count)
    your_reflection_vectors = [(point[0] - your_position[0], point[1] - your_position[1]) for point in your_reflection_points]

    max_x = max(point[0] for point in possible_shots)
    min_x = min(point[0] for point in possible_shots)
    max_y = max(point[1] for point in possible_shots)
    min_y = min(point[1] for point in possible_shots)

    your_reflection_vectors = [vector for vector in your_reflection_vectors if min_x < vector[0] < max_x and min_y < vector[1] < max_y]
    origin = (0, 0)
    if origin in your_reflection_vectors:
        your_reflection_vectors.remove(origin)

    reflection_angles_distances = [calculate_angle_and_distance(reflection) for reflection in your_reflection_vectors]

    valid_shots = []

    for point in possible_shots:
        shot_angle, shot_distance = calculate_angle_and_distance(point)

        if any(angle == shot_angle and distance < shot_distance for angle, distance in reflection_angles_distances):
            continue

        valid_shots.append(point)

    possible_shots = valid_shots

    return len(possible_shots)

5. Expanding Nebula

Question

Solution

This is a nondeterministic cellular automaton problem, meaning there is no direct way to find the previous states of a given grid. The problem with the classical brute force approach is that the number of possible previous states is huge. For a given 3x3 grid, there are $2^{16}=65536$ possible previous states and that is an optimistic scenario. Your RAM is not going to like this. So we need to do this search with pruning.

If a cell has gas, its previous state has 4 possibilities: 1 cell has gas, others are empty.

If a cell is empty, its previous state has 12 possibilities, there is no gas, 2 cells have gas, 3 cells have gas, and 4 cells have gas.

true_predecessors = [
    # One true
    [[False, False], [False, True]],
    [[False, False], [True, False]],
    [[True, False], [False, False]],
    [[False, True], [False, False]],
]

false_predecessors = [
    # All false
    [[False, False], [False, False]],
    # Two false
    [[False, True], [True, False]],
    [[False, True], [False, True]],
    [[True, False], [True, False]],
    [[True, False], [False, True]],
    [[True, True], [False, False]],
    [[False, False], [True, True]],
    # One false
    [[False, True], [True, True]],
    [[True, False], [True, True]],
    [[True, True], [False, True]],
    [[True, True], [True, False]],
    # All true
    [[True, True], [True, True]],
]

Let's assume that given grid is:

$$ \begin{bmatrix} O & . & O \\ . & O & . \\ O & . & O \\ \end{bmatrix} $$

Let's convert it to a boolean for simplicity:

$$ \begin{bmatrix} True & False & True \\ False & True & False \\ True & False & True \\ \end{bmatrix} $$

The grid is 3x3, so we will have a 4x4 grid for the previous state.

$$ \begin{bmatrix} - & - & - & - \\ - & - & - & - \\ - & - & - & - \\ - & - & - & - \\ \end{bmatrix} $$

The first element of the given grid is True, we can start generating the previous states from there. Since there are 4 possibilities for the first element, we will have 4 different grids.

\[ 1: \begin{bmatrix} False & False & - & - \\ False & True & - & - \\ - & - & - & - \\ - & - & - & - \\ \end{bmatrix} % , % \:\: % 2: % \begin{bmatrix} False & False & - & - \\ True & False & - & - \\ - & - & - & - \\ - & - & - & - \\ \end{bmatrix} \] \[ 3: \begin{bmatrix} True & False & - & - \\ False & False & - & - \\ - & - & - & - \\ - & - & - & - \\ \end{bmatrix} % , % \:\: % 4: % \begin{bmatrix} False & True & - & - \\ False & False & - & - \\ - & - & - & - \\ - & - & - & - \\ \end{bmatrix} \]

Let's go one cell to the bottom of the given grid. The value is False, so it should have 12 different possibilities. This is where the pruning comes in. If we check the first row of the possible previous states and match them with the generated grids, we can eliminate some of the possibilities.

Applying this logic until the last row, we get 8 possibilities. Without restricting the search like this, there would be $2^{8}=256$ grids that we would need to check. List of the possible previous states at the moment if you are curious:

[
[[False, False, None, None], [False, True, None, None], [True, False, None, None], [False, False, None, None]],
[[False, False, None, None], [False, True, None, None], [False, True, None, None], [False, False, None, None]],
[[False, False, None, None], [True, False, None, None], [True, False, None, None], [False, False, None, None]],
[[False, False, None, None], [True, False, None, None], [False, True, None, None], [False, False, None, None]],
[[True, False, None, None], [False, False, None, None], [False, False, None, None], [False, True, None, None]],
[[True, False, None, None], [False, False, None, None], [False, False, None, None], [True, False, None, None]],
[[False, True, None, None], [False, False, None, None], [False, False, None, None], [False, True, None, None]],
[[False, True, None, None], [False, False, None, None], [False, False, None, None], [True, False, None, None]]
]

With the same idea but with a twist on the algorithm, now we need to check the second column while generating the first two rows of the third column.

\begin{bmatrix} - & (check \: this) & (while \: generating \: this) & - \\ - & (check \: this) & (while \: generating \: this) & - \\ - & - & - & - \\ - & - & - & - \\ \end{bmatrix}

Moving on to the third row, since we have three already generated neighbors, we only need to generate the remaining one with respect to its neighbors.

\begin{bmatrix} - & - & - & - \\ - & (check \: this) & (check \: this) & - \\ - & (check \: this) & (while \: generating \: this) & - \\ - & - & - & - \\ \end{bmatrix}

Looping through the columns and rows, we can find the possible previous states of the given grid. Returning the length of the list will give us the answer.

Code

true_predecessors = [
    # One true
    [[False, False], [False, True]],
    [[False, False], [True, False]],
    [[True, False], [False, False]],
    [[False, True], [False, False]],
]

false_predecessors = [
    # All false
    [[False, False], [False, False]],
    # Two false
    [[False, True], [True, False]],
    [[False, True], [False, True]],
    [[True, False], [True, False]],
    [[True, False], [False, True]],
    [[True, True], [False, False]],
    [[False, False], [True, True]],
    # One false
    [[False, True], [True, True]],
    [[True, False], [True, True]],
    [[True, True], [False, True]],
    [[True, True], [True, False]],
    # All true
    [[True, True], [True, True]],
]

def solution(g):
    current_state = g
    # Creating the array for the previous state, where the dimensions are the same as the current state's dimensions + 1
    previous_state = []

    for i in range(len(current_state) + 1):
        previous_state.append([None] * (len(current_state[0]) + 1))

    # Now we will check the first column of the current state and fill the first two columns of the previous state accordingly
    possible_previous_states = []

    if current_state[0][0]:
        for predecessor in true_predecessors:
            previous_state[0][0] = predecessor[0][0]
            previous_state[1][0] = predecessor[1][0]
            previous_state[0][1] = predecessor[0][1]
            previous_state[1][1] = predecessor[1][1]
            possible_previous_states.append([list(sublist) for sublist in previous_state])
    else:
        for predecessor in false_predecessors:
            previous_state[0][0] = predecessor[0][0]
            previous_state[1][0] = predecessor[1][0]
            previous_state[0][1] = predecessor[0][1]
            previous_state[1][1] = predecessor[1][1]
            possible_previous_states.append([list(sublist) for sublist in previous_state])

    # Now we check current_state[1][0] and depending on the values in the possible_previous_states we will make a decision from predessors

    for i in range(1, len(current_state)):
        new_possible_previous_states = []
        for previous_state in possible_previous_states:
            common_row = [previous_state[i][0], previous_state[i][1]]
            if current_state[i][0]:
                for predecessor in true_predecessors:
                    if predecessor[0] == common_row:
                        new_state = [list(sublist) for sublist in previous_state] 
                        new_state[i + 1][0] = predecessor[1][0] 
                        new_state[i + 1][1] = predecessor[1][1] 
                        new_possible_previous_states.append(new_state)
            else:
                for predecessor in false_predecessors:
                    if predecessor[0] == common_row:
                        new_state = [list(sublist) for sublist in previous_state] 
                        new_state[i + 1][0] = predecessor[1][0] 
                        new_state[i + 1][1] = predecessor[1][1] 
                        new_possible_previous_states.append(new_state)
        possible_previous_states = new_possible_previous_states

    # Now we will do the same thing until we reach the last column of the current state
    # We need to do this without hardcoding the indexes, since the dimensions of the current state can change
    # But there is a trick here,
    # While generating the third column, if we are genearting the first step (first two rows), checking the common column will be enough
    # But if we are generating the other rows we need to check the other three

    for i in range(len(current_state[0])):
        for j in range(len(current_state)):
            new_possible_previous_states = []
            if j == 0:
                for previous_state in possible_previous_states:
                    common_column = [previous_state[j][i], previous_state[j+1][i]]
                    if current_state[j][i]:
                        for predecessor in true_predecessors:
                            if predecessor[0][1] == common_column[0] and predecessor[1][1] == common_column[1]:
                                new_state = [list(sublist) for sublist in previous_state] 
                                new_state[j][i+1] = predecessor[0][0]
                                new_state[j+1][i+1] = predecessor[1][0]
                                new_possible_previous_states.append(new_state)
                    else:
                        for predecessor in false_predecessors:
                            if predecessor[0][1] == common_column[0] and predecessor[1][1] == common_column[1]:
                                new_state = [list(sublist) for sublist in previous_state] 
                                new_state[j][i+1] = predecessor[0][0]
                                new_state[j+1][i+1] = predecessor[1][0]
                                new_possible_previous_states.append(new_state)
                possible_previous_states = new_possible_previous_states
            else:
                for previous_state in possible_previous_states:
                    common_elements = [previous_state[j][i], previous_state[j+1][i], previous_state[j][i+1]]
                    if current_state[j][i]:
                        for predecessor in true_predecessors:
                            if predecessor[0][1] == common_elements[0] and predecessor[1][1] == common_elements[1] and predecessor[0][0] == common_elements[2]:
                                new_state = [list(sublist) for sublist in previous_state] 
                                new_state[j][i+1] = predecessor[0][0]
                                new_state[j+1][i+1] = predecessor[1][0]
                                new_possible_previous_states.append(new_state)
                    else:
                        for predecessor in false_predecessors:
                            if predecessor[0][1] == common_elements[0] and predecessor[1][1] == common_elements[1] and predecessor[0][0] == common_elements[2]:
                                new_state = [list(sublist) for sublist in previous_state] 
                                new_state[j][i+1] = predecessor[0][0]
                                new_state[j+1][i+1] = predecessor[1][0]
                                new_possible_previous_states.append(new_state)
                possible_previous_states = new_possible_previous_states

    # Removing the states appearing more than once
    possible_previous_states = list(set([tuple([tuple(sublist) for sublist in result]) for result in possible_previous_states]))

    return len(possible_previous_states)

Conclusion

This challenge was a great experience for me. I learned a lot of things, and I had a lot of fun. I hope you did too.

If you like these kinds of challenges, I recommend you check out Project Euler and Codeforces. They are great platforms to improve your problem-solving skills.

If you have any questions or suggestions, please feel free to contact me (you can find my email on the home page). I will be happy to help you.

---

Go back to the blogs