Cuando busqué en Google información sobre la comprensión de la lista de Python, me ofrecieron un desafío de Google Foobar, en el que he estado trabajando lentamente en los últimos días por diversión. El último desafío:

enter image description here

Efectivamente llama a generar una lista de ID, ignorando un número creciente de cada nueva línea hasta que quede una ID. Entonces se supone que debes XOR (^) las ID para producir una suma de verificación. Creé un programa de trabajo que genera la respuesta correcta, sin embargo, no es lo suficientemente eficiente como para pasar todos los casos de prueba (pases 6/10) en el tiempo asignado. Una longitud de 50,000 debería producir un resultado en menos de 20 segundos, pero se necesitan 320.

¿Podría alguien dirigirme en la dirección correcta, pero por favor no lo haga por mí , me estoy divirtiendo empujándome con este desafío. ¿Quizás haya una estructura de datos o algoritmo que pueda implementar para acelerar el tiempo de cálculo?

Lógica detrás del código:

  1. Primero, se toman la ID de inicio y la longitud

  2. Se genera una lista de ID, ignorando un número creciente de ID de cada nueva línea, comenzando por ignorar 0 de la primera línea.

  3. XORs todos los números en la lista de IDS utilizando un bucle for

  4. La respuesta se devuelve como int


import timeit
def answer(start,length):
    x = start
    lengthmodified = length
    answerlist = []
    for i in range (0,lengthmodified): #Outter for loop runs an amount of times equal to the variable "length".
        prestringresult = 0
        templist = []
        for y in range (x,x + length): #Fills list with ids for new line
            templist.append(y)
        for d in range (0,lengthmodified): #Ignores an id from each line, increasing by one with each line, and starting with 0 for the first
            answerlist.append(templist[d])
        lengthmodified -= 1
        x += length    
        for n in answerlist: #XORs all of the numbers in the list via a loop and saves to prestringresult
            prestringresult ^= n
        stringresult = str(prestringresult) 
        answerlist = [] #Emptys list
        answerlist.append(int(stringresult)) #Adds the result of XORing all of the numbers in the list to the answer list
    #print(answerlist[0]) #Print statement allows value that's being returned to be checked, just uncomment it
    return (answerlist[0]) #Returns Answer



#start = timeit.default_timer()
answer(17,4)
#stop = timeit.default_timer()
#print (stop - start) 
4
Mrcitrusboots 11 ene. 2017 a las 05:53

3 respuestas

La mejor respuesta

Probablemente necesitará un enfoque diferente, no solo mejoras menores como la de John. Acabo de escribir una solución que puede hacer answer(0, 50000) en aproximadamente 2 segundos en mi PC. Todavía lo hago fila por fila, pero en lugar de grabar todos los números en el rango de la fila, lo hago poco a poco. ¿Cuántos números en la fila tiene el conjunto de 1 bit? [*] ¿Un número impar de números? Luego volteo el 1 bit de mi respuesta. Y luego lo mismo para el bit de 2 bits, el de 4 bits, el de 8 bits, etc., hasta el 2s 30 . Entonces, para cada fila, son solo 31 pequeños cálculos (en lugar de extraer decenas de miles de números).

[*] Se puede calcular rápidamente en tiempo constante solo desde el inicio / parada del rango.

Editar: ya que solicitó otra pista, aquí le mostramos cómo calcular la frecuencia con la que se establece el 1 bit en algún rango (a, b). Calcule con qué frecuencia se establece en el rango (0, a) y reste eso de la frecuencia con la que se establece en el rango (0, b). Es más fácil si el rango comienza en cero. ¿Con qué frecuencia se establece el 1 bit en algún rango (0, c)? Fácil: c//2 veces. Entonces, ¿con qué frecuencia se establece el 1 bit en algún rango (a, b)? Simplemente b//2 - a//2 veces. Los bits más altos son similares, solo un poco más complicados.

Edición 2: Oh, espera, acabo de recordar ... hay una manera fácil de calcular el xor de todos los números en algún rango (a, b). Nuevamente divida el trabajo en rango (0, a) y rango (0, b). El xor de todos los números en algún rango (0, c) es fácil porque hay un patrón agradable (lo verá si lo hace para todos los c desde 0 hasta digamos 30). Con esto, ahora resuelvo answer(0, 50000) en aproximadamente 0.04 segundos .

5
Stefan Pochmann 17 ene. 2017 a las 16:36

La mayoría de las personas obtendrían un límite de tiempo excedido en esta pregunta. ¡Yo hice! Esta pregunta puede concluirse de esta manera: "Encuentre el XOR de todos los números que se encuentran entre cierto rango en tiempo constante". Sí, tiempo constante!

Entonces, de 3 a 6, la respuesta debe ser 3 ^ 4 ^ 5 ^ 6 = 4 en O (1) tiempo.

Solución: los XOR son de naturaleza asociativa. Entonces, A ^ B ^ C puede escribirse como B ^ A ^ C. Además, sabemos que XOR significa: 'Y' que los mismos bits resultan en Verdadero, es decir, 1 y diferentes bits resultan en 2.

De estas 2 naturaleza podemos escribir: XOR entre todos los números del 3 al 6 se puede escribir como:

3^4^5^6 = (0^1^2)^(0^1^2) ^ (3^4^5^6)
        = (0^1^2^3^4^5^6) ^ (0^1^2) (this comes from the associative nature of xor)
        = XOR betn all the numbers from (0-6) ^ XOR betn all the numbers from (0-2)...eq(1)

Entonces, si podemos encontrar XOR de todos los números de 0 a cierto entero en un tiempo constante, obtendremos nuestra respuesta.

Por suerte, existe un patrón para nosotras:

Vea esto para un ejemplo:

(0-1): 0 ^ 1 = 1 (1)
(0-2): 0 ^ 1 ^ 2 = 3 (2+1)
(0-3): 0 ^ 1 ^ 2 ^ 3 = 0 (0)
(0-4): 0 ^ 1 ^ 2 ^ 3 ^ 4 = 4 (4)

(0-5): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 = 1 (1)
(0-6): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7 (6+1)
(0-7): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^  7 = 0 (0)
(0-8): 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 = 8 (8)


So the pattern for finding the xor between all the integers between 0 to n is:
if n%4 == 1 then, answer = 1
if n%4 == 2 then, answer = n+1
if n%4 == 3 then, answer = 0
if n%4 == 0 then answer = n 

Therefore, XOR(0-6) becomes 7 (since 6%4 ==2) and XOR(0-2) becomes 3 (since 2%4 ==2)

Therefore, the eq(1) now becomes:
3^4^5^6 = 7 ^ 3 = 4

Ahora la pregunta es bastante fácil, la mayoría de nosotros nos quedamos atrapados debido al error de límite de tiempo excedido, porque tratamos de hacer xor en cada ciclo que sería enorme si aumentara el número de entrada / iteración. Aquí está mi solución de trabajo en Python para la cual Google pasó todos los casos de prueba:

#Main Program
def answer(start, length):
    checkSum = 0
    for l in range(length, 0, -1):
        checkSum = checkSum ^ (getXor(start + l-1) ^ getXor(start-1))
        start = start + length
    return checkSum

def getXor(x):
    result = [x, 1, x+1, 0]
    return result[x % 4]
1
Suresh Lamichhane 22 ago. 2017 a las 02:32

Pude obtener una pequeña mejora sin usar la lista, pero todavía fallará en grandes cantidades. Los bucles anidados matan la velocidad. Creo que debe seguir la lógica de Pochmann, ya que la fuerza bruta rara vez es el camino a seguir para este tipo de problemas.

enter image description here

1
Michael 11 ene. 2017 a las 04:52