Problema de la bala rebotada

Question

Este es un problema que se me presentó a través del reto de google foobar, pero mi tiempo ya ha expirado y habían decidido que no completara el problema. Sospecho de un posible bug por parte de ellos, porque pasé 9/10 casos de prueba (que se me ocultan) pero no estoy seguro. Me gustaría saber dónde o si he cometido un error, así que voy a preguntar el problema aquí.

El problema es el siguiente: usted está de pie en una habitación con dimensiones enteras, donde la pared izquierda existe en $x=0$ y la pared derecha existe en $x=x_0$ . Del mismo modo, la pared inferior existe en $y=0$ y la pared superior existe en $y=y_0$ . Dentro de esta sala, usted y otro individuo (al que llamamos guardia) se sitúan en el entramado de números enteros de forma que sus coordenadas están en $[x_{s}, y_{s}]$ , y el guardia se encuentra en $[x_g, y_g]$ , donde

$$ 0<x_s<x_0 \\ 0<x_g<x_0 \\ 0<y_s<y_0 \\ 0<y_g<y_0 \\ y_s \neq y_g~\text{or}~x_s \neq x_g \\ $$

es decir, ni tú ni el guardia estáis sobre una pared, y ocupáis posiciones distintas en la habitación. Si tienes una bala que puede recorrer una distancia total $d$ entonces determina el número de direcciones distintas en las que puedes disparar la bala de manera que alcance al otro individuo, recorra una distancia menor o igual a $d$ y no se golpea en el proceso. Esto se escribe como una función:

solution(room_dimensions, your_position, guard_position, d)

Lo que había notado en mi solución era que las direcciones permitidas se pueden escribir como un vector de la distancia total recorrida por la bala en una dimensión específica, donde un signo negativo indica un movimiento inicial hacia $x=0$ o $y=0$ y un signo positivo indica un movimiento inicial hacia $x=x_0$ o $y=y_0$ . Pongamos un ejemplo de lo que esto significa.

Supongamos que la habitación tiene dimensiones $[2, 3]$ y tú te quedas en $[1, 2]$ y la guardia está en $[1, 1]$ . Entonces, por supuesto, la bala podría ir directamente hacia abajo: $[0, -1]$ es un rodamiento válido. Sin embargo, podríamos hacer rebotar la bala en la pared de la izquierda, y luego hacer que la bala golpee al guardia: $[-2, -1]$ . Que $-2$ es válido porque la distancia total recorrida es $2$ : $1$ unidad se desplaza en el movimiento de su posición a la pared de la izquierda, y un $1$ de retroceder hacia la guardia. Es negativo porque nos movemos hacia la pared izquierda $x=0$ . Esto puede extenderse a cualquier número de rebotes en cada pared, y cada dimensión puede considerarse independientemente. Así, para cada dimensión, genero una lista de las distancias permitidas (con el signo que indica la dirección) que da como resultado que la bala llegue a la misma coordenada que el guardia en esa dimensión.

Si generamos las listas mencionadas (allowed_x, allowed_y) para el $x$ y $y$ dimensiones, entonces $[X, Y]$ $X\in$ permitido_x, $Y\in$ allowed_y es un rodamiento válido que llevará la bala desde usted hasta el guardia, con dos problemas creados: 1) La bala puede pasar primero a través de usted, y 2) Algunos de estos rodamientos pueden apuntar en la misma dirección y recorrer diferentes distancias.

Si determinamos todas las direcciones que resultan en que seas alcanzado por la bala, podemos ver si existe una dirección paralela en la lista de direcciones que resultan en que el guardia sea alcanzado, y si existe y el camino para que seas alcanzado es más corto, entonces esa no es una dirección válida ya que requiere que la bala pase a través de ti. Esto resuelve 1).

2) Se resuelve comprobando si las direcciones son paralelas antes de contarlas, y si lo son, registramos la menor de las dos distancias. De este modo, sólo obtenemos direcciones distintas.

Como he dicho, mi código funciona para 9/10 pruebas, que se me ocultan. Por lo tanto, es probable que el caso 1/10 sea elegido específicamente para probar un extremo que, al azar, no encontraría. He probado a fondo mi código, por lo que no creo que tal extremo exista, pero me sentiría muy aliviado si alguien pudiera señalar mi descuido. Saludos.

He adjuntado mi código de python 2.7.13 a continuación por si alguien quiere implicarse mucho.

from fractions import gcd 
from random import randint 

def get_1D_bearings(t, m, g, distance):
    '''
    Returns a list of the total distance travelled in 1D which results in the beam arriving at the guard's t-coordinate.

    Parameters:
        t(int): The length of this dimension.
        m(int): The t-coodinate of the shooter (me). 
        g(int): The t-coordinate of the guard.
        distance(int): The maximum allowed distance that the beam may travel. 
    '''
    i = 0 
    bearings = [] 
    path = g - m # Direct path from the shooter to the guard with no bounces. 
    if abs(path) <= distance:
        bearings.append(path)
    while True:
        # Initial bounce off of the positive wall and final bounce off of the positive wall. 
        path = (t - m) + (t-g) + 2*i*t 
        if abs(path) <= distance:
            bearings.append(path)
        # Initial bounce off of the negative wall and final bounce off of the negative wall. 
        path = - (m+g+2*i*t)
        if abs(path) <= distance:
            bearings.append(path)
        # Initial bounce off of the positive wall and final bounce off of the negative wall. 
        path = (t - m) + g + (2*i+1)*t 
        if abs(path) <= distance:
            bearings.append(path)
        # Initial bounce off of the negative wall and final bounce off of the positive wall.
        path = - ( m + (t - g) + (2*i+1)*t)
        if abs(path) <= distance:
            bearings.append(path)
        else:
            break 
        i += 1
    return bearings 

def are_parallel(a, b):
    '''
    Returns if the bearings given by a and b are parallel vectors. 

    Parameters:
        a(array-like): A 2D-array of integers. 
        b(array-like): A 2D-array of integers. 
    '''
    x1, y1 = a
    x2, y2 = b 
    div1 = abs(gcd(x1, y1))
    div2 = abs(gcd(x2, y2) ) 
    if div1 == 0 or div2 ==0:
        if not div1 == 0 and div2 == 0:
            return False 
        elif (x1 == 0 and x2 == 0) and (y1 // abs(y1) == y2 // abs(y2)):
            return True 
        elif (y1 == 0 and y2 ==0) and (x1 // abs(x1) == x2 // abs(x2)):
            return True 
        else:
            return False 
    else:
        if x1 // div1 == x2 // div2 and y1 // div1 == y2 // div2:
            return True 
        else:
            return False 

class VectorsNotParallel(Exception):
    '''Raise this exception when handling vectors which are assumed to be parallel but are not.'''
    def __init__(self):
        pass 

def get_shorter_bearing(a, b):
    '''
    Returns the shorter vector of a and b. If they are not parallel, raises VectorsNotParallel.

    Parameters:
        a(array-like): A 2D-array of integers indicating a direction. 
        b(array-like): A 2D-array of integers indicating a direction. 
    '''
    if not are_parallel(a, b):
        raise VectorsNotParallel("These bearings point in different directions: " + str(a) + " and " + str(b))
    x1, y1 = a
    x2, y2 = b
    if x1 == 0:
        if abs(y1) < abs(y2):
            return a
        else:
            return b 
    if y1 == 0:
        if abs(x1) < abs(x2):
            return a
        else:
            return b           
    div1 = abs(gcd(x1, y1))
    div2 = abs(gcd(x2, y2) ) 
    if div1 < div2:
        return a 
    else:
        return b    

def get_all_bearings(dimensions, your_position, guard_position, distance):
    '''
    Combines the allowed distances from each of the two dimensions to generate a list of all of the 
    allowed directions that can be shot in which take a beam from your_position to guard_position 
    while not travelling further than the provided distance. Note that some of these directions include
    passing through your_position. 

    Parameters:
        dimensions(array-like): A 2D-array of integers indicating the size of the room.
        your_position(array-like): A 2D-array of integers indicating your position in the room.
        guard_position(array-like): A 2D-array of integers indicating the guard's position in the room.
        distance(int): An integer indicating the maximum distance the beam can travel. 

    Returns:
        bearings(array-like): An array of 2D-arrays indicating the bearings which move the beam from your_position
                              to guard_position.
    '''
    dx, dy=  dimensions
    sx, sy = your_position
    gx, gy = guard_position
    allowed_x = get_1D_bearings(dx, sx, gx, distance)
    allowed_y = get_1D_bearings(dy, sy, gy, distance) 
    bearings = [] 
    for x in allowed_x:
        for y in allowed_y:
            if x**2 + y**2 < 1 or x**2 + y**2 > distance **2:
                continue 
            res = [x, y]
            append = True  # Do we need to append to the list of bearings or just update an existing one
            for bearing in bearings:
                if are_parallel(res, bearing):
                    append = False 
                    res_2 = get_shorter_bearing(res, bearing)
                    bearing[0] = res_2[0]
                    bearing[1] = res_2[1] 
            if append:
                bearings.append(res) 
    return bearings 

def count_friendly_fires(friendly_bearings, guard_bearings):
    '''
    Returns the number of bearings which result in the guard being hit only after the beam 
    passes through the shooter (which is not allowed). 

    Parameters:
        friendly_bearings(array-like): An array of 2D arrays which indicate bearings that reach the shooter. 
        guard_bearings(array-like): An array of 2D arrays which indicate bearings that reach the guard. 
    '''
    count = 0 
    for f_bearing in friendly_bearings:
        for g_bearing in guard_bearings:
            if are_parallel(f_bearing, g_bearing):
                if get_shorter_bearing(f_bearing, g_bearing) == f_bearing:
                    print(f_bearing, g_bearing)
                    count += 1 
    return count 

def solution(dimensions, your_position, guard_position, distance):
    '''
    Returns the number of distinct directions that take a bullet from your_position to 
    guard_position within the allowed distance. 

    Parameters:
        dimensions(array-like): A 2D-array of integers indicating the size of the room.
        your_position(array-like): A 2D-array of integers indicating your position in the room.
        guard_position(array-like): A 2D-array of integers indicating the guard's position in the room.
        distance(int): An integer indicating the maximum distance the beam can travel. 
    '''
    guard_hitting_bearings = get_all_bearings(dimensions, your_position, guard_position, distance)
    self_hitting_bearings = get_all_bearings(dimensions, your_position, your_position, distance)
    count = count_friendly_fires(self_hitting_bearings, guard_hitting_bearings)
    return len(guard_hitting_bearings) - count

Answer 1

He inspeccionado su código a fondo y no encuentro ningún problema; me parece totalmente robusto, al menos en términos de corrección. Sin embargo, soy consciente de que Foobar impone límites de tiempo a los problemas; sospecho que su código falló en ese caso de prueba porque era demasiado lento.

Para ser precisos, definamos $B$ como el producto máximo de los tamaños de allowed_x y allowed_y (en un sentido vago, el máximo de los tamaños de guard_hitting_bearings y self_hitting_bearings aunque lo normal es que sea mucho mayor). Investigaremos los tiempos de ejecución de cada una de las funciones en su código, y proporcionaremos un límite asintótico vago.

En primer lugar, are_parallel es claramente $O(1)$ por lo que podemos agruparla con las demás operaciones de tiempo constante. Lo mismo ocurre con get_shorter_bearing .

Ahora, para get_all_bearings tenemos un par de bucles exteriores que iteran por todos los $O(B)$ posibilidades; y para cada una de las realmente válidas, itera a través de toda la lista hasta el momento, para una complejidad total de $O(B^2)$ .

Del mismo modo, para count_friendly_fires iteramos sobre todos los pares de rodamientos entre friendly_bearings y guard_bearings y, por lo tanto, tienen de nuevo una complejidad de $O(B^2)$ .

En general, este código es $O(B^2)$ (además de otras pequeñas cosas que no nos importan especialmente), y podemos mejorar significativamente eso. Además, y esto es muy importante, este límite superior cuadrático puede ser forzado por una entrada suficientemente mala; por ejemplo, si se fija la posición inicial en $(1, 1)$ la posición de guardia a $(2, 2)$ y las dimensiones de la sala a $p \times p$ para algún primo $p$ debe forzar los tamaños de guard_hitting_bearings y self_hitting_bearings sea como máximo un factor constante menor que el producto de los tamaños de allowed_x y allowed_y . Sospecho que el último caso de prueba era probablemente algo en este sentido, diseñado para romper las soluciones que eran demasiado lentas (probablemente pasó los otros casos de prueba porque todos tenían muchos vectores paralelos, por lo que los tamaños se redujeron significativamente). En cualquier caso, está claro que habrá que mejorar los dos $O(B^2)$ funciones mencionadas anteriormente.

Mirando su código, surge un patrón en los lugares que degeneran en $O(B^2)$ : todos ellos implican una comprobación ingenua de vectores paralelos, por lo que la optimización de esto es la clave para hacer que el código se ejecute más rápido. La idea clave es la siguiente. Dejemos que $x \parallel y$ si y sólo si are_parallel(x, y) . Se trata de una relación de equivalencia ( $x \parallel x$ para todos $x$ y $x \parallel y$ y $y \parallel z$ implica $x \parallel z$ ). Ahora defina $r(v)$ para ser el vector de menor magnitud tal que $r(v) \parallel v$ es fácil ver que este vector está definido de forma única, y una función para calcular $r(v)$ en $O(1)$ se puede obtener mediante una simple modificación de are_parallel . Ahora bien, como $r(v)$ está definida de forma única, tenemos el hecho $$ x \parallel y \iff r(x) = r(y). $$ Esta es la clave para optimizar su solución. En particular, en lugar de arrays, podemos utilizar un diccionario indexado por $r(v)$ .

En lugar de la $O(B)$ bucle interno en get_all_bearings para comprobar si el nuevo vector es paralelo a algo ya existente en bearing simplemente comprobamos el elemento en bearing[r(v)] (si existe tal elemento); esto reduce el bucle a un simple $O(1)$ búsqueda en el diccionario, y por lo tanto, en general get_all_bearings se reduce a $O(B)$ . De la misma manera, count_friendly_fires puede iterar sobre todos los pares clave-valor en friendly_bearings y simplemente buscar el elemento de guard_bearings paralelo a la clave actual (si existe tal elemento); de nuevo el $O(B)$ el bucle interno se reduce a $O(1)$ haciendo que la función $O(B)$ en general. Por lo tanto, con esta sencilla modificación, su código puede hacerse funcionar bastante más rápido.

Paul tiene un código agradable y legible que implementa esta idea en otra respuesta. Su $r(v)$ se llama get_direction para que sirva de referencia.

Answer 2

He hecho mi propia implementación basada en tu idea y he añadido código para comparar los resultados entre tu implementación y la mía. Son iguales. Así que tu código probablemente está bien.

Aquí está el código, probado en Python 3.7:

import math

################################### Original solution ##########################################

def get_1D_bearings(t, m, g, distance):
    '''
    Returns a list of the total distance travelled in 1D which results in the beam arriving at the guard's t-coordinate.

    Parameters:
        t(int): The length of this dimension.
        m(int): The t-coodinate of the shooter (me).
        g(int): The t-coordinate of the guard.
        distance(int): The maximum allowed distance that the beam may travel.
    '''
    i = 0
    bearings = []
    path = g - m # Direct path from the shooter to the guard with no bounces.
    if abs(path) <= distance:
        bearings.append(path)
    while True:
        # Initial bounce off of the positive wall and final bounce off of the positive wall.
        path = (t - m) + (t-g) + 2*i*t
        if abs(path) <= distance:
            bearings.append(path)
        # Initial bounce off of the negative wall and final bounce off of the negative wall.
        path = - (m+g+2*i*t)
        if abs(path) <= distance:
            bearings.append(path)
        # Initial bounce off of the positive wall and final bounce off of the negative wall.
        path = (t - m) + g + (2*i+1)*t
        if abs(path) <= distance:
            bearings.append(path)
        # Initial bounce off of the negative wall and final bounce off of the positive wall.
        path = - ( m + (t - g) + (2*i+1)*t)
        if abs(path) <= distance:
            bearings.append(path)
        else:
            break
        i += 1
    return bearings

def are_parallel(a, b):
    '''
    Returns if the bearings given by a and b are parallel vectors.

    Parameters:
        a(array-like): A 2D-array of integers.
        b(array-like): A 2D-array of integers.
    '''
    x1, y1 = a
    x2, y2 = b
    div1 = abs(math.gcd(x1, y1))
    div2 = abs(math.gcd(x2, y2) )
    if div1 == 0 or div2 ==0:
        if not div1 == 0 and div2 == 0:
            return False
        elif (x1 == 0 and x2 == 0) and (y1 // abs(y1) == y2 // abs(y2)):
            return True
        elif (y1 == 0 and y2 ==0) and (x1 // abs(x1) == x2 // abs(x2)):
            return True
        else:
            return False
    else:
        if x1 // div1 == x2 // div2 and y1 // div1 == y2 // div2:
            return True
        else:
            return False

class VectorsNotParallel(Exception):
    '''Raise this exception when handling vectors which are assumed to be parallel but are not.'''
    def __init__(self):
        pass

def get_shorter_bearing(a, b):
    '''
    Returns the shorter vector of a and b. If they are not parallel, raises VectorsNotParallel.

    Parameters:
        a(array-like): A 2D-array of integers indicating a direction.
        b(array-like): A 2D-array of integers indicating a direction.
    '''
    if not are_parallel(a, b):
        raise VectorsNotParallel("These bearings point in different directions: " + str(a) + " and " + str(b))
    x1, y1 = a
    x2, y2 = b
    if x1 == 0:
        if abs(y1) < abs(y2):
            return a
        else:
            return b
    if y1 == 0:
        if abs(x1) < abs(x2):
            return a
        else:
            return b
    div1 = abs(math.gcd(x1, y1))
    div2 = abs(math.gcd(x2, y2) )
    if div1 < div2:
        return a
    else:
        return b

def get_all_bearings(dimensions, your_position, guard_position, distance):
    '''
    Combines the allowed distances from each of the two dimensions to generate a list of all of the
    allowed directions that can be shot in which take a beam from your_position to guard_position
    while not travelling further than the provided distance. Note that some of these directions include
    passing through your_position.

    Parameters:
        dimensions(array-like): A 2D-array of integers indicating the size of the room.
        your_position(array-like): A 2D-array of integers indicating your position in the room.
        guard_position(array-like): A 2D-array of integers indicating the guard's position in the room.
        distance(int): An integer indicating the maximum distance the beam can travel.

    Returns:
        bearings(array-like): An array of 2D-arrays indicating the bearings which move the beam from your_position
                              to guard_position.
    '''
    dx, dy=  dimensions
    sx, sy = your_position
    gx, gy = guard_position
    allowed_x = get_1D_bearings(dx, sx, gx, distance)
    allowed_y = get_1D_bearings(dy, sy, gy, distance)
    bearings = []
    for x in allowed_x:
        for y in allowed_y:
            if x**2 + y**2 < 1 or x**2 + y**2 > distance **2:
                continue
            res = [x, y]
            append = True  # Do we need to append to the list of bearings or just update an existing one
            for bearing in bearings:
                if are_parallel(res, bearing):
                    append = False
                    res_2 = get_shorter_bearing(res, bearing)
                    bearing[0] = res_2[0]
                    bearing[1] = res_2[1]
            if append:
                bearings.append(res)
    return bearings

def count_friendly_fires(friendly_bearings, guard_bearings):
    '''
    Returns the number of bearings which result in the guard being hit only after the beam
    passes through the shooter (which is not allowed).

    Parameters:
        friendly_bearings(array-like): An array of 2D arrays which indicate bearings that reach the shooter.
        guard_bearings(array-like): An array of 2D arrays which indicate bearings that reach the guard.
    '''
    count = 0
    for f_bearing in friendly_bearings:
        for g_bearing in guard_bearings:
            if are_parallel(f_bearing, g_bearing):
                if get_shorter_bearing(f_bearing, g_bearing) == f_bearing:
                    #print(f_bearing, g_bearing)
                    count += 1
    return count

def solution(dimensions, your_position, guard_position, distance):
    '''
    Returns the number of distinct directions that take a bullet from your_position to
    guard_position within the allowed distance.

    Parameters:
        dimensions(array-like): A 2D-array of integers indicating the size of the room.
        your_position(array-like): A 2D-array of integers indicating your position in the room.
        guard_position(array-like): A 2D-array of integers indicating the guard's position in the room.
        distance(int): An integer indicating the maximum distance the beam can travel.
    '''
    guard_hitting_bearings = get_all_bearings(dimensions, your_position, guard_position, distance)
    self_hitting_bearings = get_all_bearings(dimensions, your_position, your_position, distance)
    count = count_friendly_fires(self_hitting_bearings, guard_hitting_bearings)
    return len(guard_hitting_bearings) - count

################################### My solution ##########################################

def get_range (a, b, max_distance):
    """
    Gets values of a + bk for integers k such that -max_distance <= a + bk <= max_distance.
    :param a: integer
    :param b: positive integer
    :param max_distance: non-negative integer
    """
    return list(range((a + max_distance) % b - max_distance, max_distance + 1, b))

def get_1d_list (size, source, to, max_distance):
    return get_range(to - source, 2*size, max_distance) + get_range(-source - to, 2*size, max_distance)

def get_direction (dx, dy):
    gcd = math.gcd(dx, dy)
    return dx // gcd, dy // gcd

def get_direction_distance_map (dx_list, dy_list, max_squared_distance):
    """Returns a map which has directions as key and squared distances as value"""
    map = {}
    for dx in dx_list:
        for dy in dy_list:
            sd = dx*dx + dy*dy
            if 0 < sd <= max_squared_distance:
                dir = get_direction(dx, dy)
                if sd < map.get(dir, max_squared_distance + 1):
                    map[dir] = sd
    return map

def my_solution (dimensions, your_position, guard_position, distance):
    self_x = get_1d_list(dimensions[0], your_position[0], your_position[0], distance)
    self_y = get_1d_list(dimensions[1], your_position[1], your_position[1], distance)
    guard_x = get_1d_list(dimensions[0], your_position[0], guard_position[0], distance)
    guard_y = get_1d_list(dimensions[1], your_position[1], guard_position[1], distance)
    map_self = get_direction_distance_map(self_x, self_y, distance*distance)
    map_guard = get_direction_distance_map(guard_x, guard_y, distance*distance)

    # Remove friendly fires
    for dir, sd_self in map_self.items():
        sd_guard = map_guard.get(dir)
        if sd_guard is not None and sd_self < sd_guard:
            del map_guard[dir]

    return len(map_guard)

################################### Test code ##########################################

for w in range(2, 8):
    print(f"Testing width {w}")
    for d in range(16):
        for h in range(2, 8):
            for xs in range(1, w):
                for ys in range(1, h):
                    for xg in range(1, w):
                        for yg in range(1, h):
                            if xs != xg or ys != yg:
                                s1 = solution([w, h], [xs, ys], [xg, yg], d)
                                s2 = my_solution([w, h], [xs, ys], [xg, yg], d)
                                if s1 != s2:
                                    print(w, h, xs, ys, xg, yg)