Estrategia óptima para un juego abstracto.

Me dieron el siguiente problema en una entrevista (que ya no pude resolver, sin tratar de engañarme): El juego comienza con un número entero positivo . (Por ejemplo, ) Este número se convierte en representación binaria, y es el número de bits establecido en . (Por ejemplo, , ) $A_0$ $A_0 = 1234$ $N$ $1$ $A_0 = b100\ 1101\ 0010$ $N = 5.$

El jugador 1 elige un número menor que . debe tener un solo bit establecido en 1. (Ej. ) Sea . (Por ejemplo, ) Un movimiento es válido si $B_0$ $A_0$ $B_0$ $B_0 = b10\ 0000\ 0000 = 512$ $A_1 = A_0 - B_0$ $A_1 = 1234-512 = 722 = b10 1101 0010$ $B_0$ satisface las restricciones anteriores, y si el número de bits puestos en sigue siendo igual a N . $A_1$

El jugador 2 continúa desde eligiendo un válido , luego el jugador 1 continúa desde , y así sucesivamente. Un jugador pierde si no le quedan movimientos válidos. $A_1$ $B_1$ $A_2$

Asumiendo que ambos jugadores juegan de manera óptima, determine al jugador ganador usando un método razonablemente eficiente. (En mi definición del problema, las restricciones en esto fueron que el programa debe ser capaz de entregar una solución para unos pocos millones de números de entrada que se ajustan a un entero de 32 bits con signo). Es decir, la solución no necesita ser Totalmente analítico.

Mi interés personal aquí es determinar si la expectativa de que yo haya encontrado e implementado la solución correcta sin ningún comentario sobre la corrección en los 120 minutos que me dieron fue razonable; o si esta fue una de esas preguntas de "veamos si han visto este rompecabezas antes".

Fallé porque elegí implementar lo que parecía una estrategia razonable, que me dio resultados correctos para los pocos casos de prueba que me dieron por adelantado, perdí demasiado tiempo haciendo que esto corriera rápido y terminé entregando incorrectos salida completa cuando se me acabó el tiempo.

En retrospectiva, debería haber implementado una búsqueda de fuerza bruta y memorizar soluciones parciales para números iniciales pequeños, pero en retrospectiva siempre es 20/20. Sin embargo, tengo curiosidad si hay un enfoque común diferente que me eludió como un flunkee.

algorithms optimization milimoose
fuente

De la descripción no entendí que los movimientos elegidos deben tener un solo bit establecido en 1 (pensé que era solo parte del ejemplo).

jjmontes

@jjmontes: se establece como la primera regla para elegir un número B: todos los ejemplos se indican como tales, todo lo que está fuera de los paréntesis es general. ¿Tiene alguna sugerencia de cómo podría haber sido más claro?

millimoose

B_{0}

$B_0$

A_{0}

$A_0$

@Veedrac - Hombre, si hubiera sabido eso, todo mi esfuerzo puesto en hacer que la cuenta de bits funcione razonablemente rápido no habría sido un desperdicio. Una respuesta que explique por qué funciona sería excelente.

millimoose

¡@millimoose Bitcount está en hardware para la mayoría de las CPU modernas!

Veedrac

Respuestas:

$01$ $10$ $01$

$10 \rightarrow 01$

Entonces, el único factor determinante en un juego es cuántos intercambios se necesitan para llegar al estado en el que todos están a la derecha, y no hay una estrategia de ganar o perder. La paridad del número de swaps que toma es el único factor determinante.

$1$

$i$ $1$ $1$ $0$ $1$ $k$ $k - i$

i = 0
k = 0
total = 0
while n > 0:
    if n & 1:
       total += k - i
       i += 1
    n >>= 1
    k += 1

total $O(\log n)$

orlp
fuente

Esto parece correcto, me he tropezado con partes de este enfoque después de la entrega. Supongo que terminé saltando el arma al comenzar a codificar y quedar atrapado en la persecución del ganso salvaje resultante.

millimoose

Pensando en esto, el hecho de que la estrategia no importe significa que tengo un error bastante oscuro en mi implementación, o debería haber producido los mismos resultados que cualquier otra implementación que juegue correctamente ...

millimoose

Una forma de resolver este problema es la siguiente:

Encuentre la solución para algunos valores simples utilizando el enfoque de "fuerza bruta memorizada" que sugiere.
Adivina la respuesta (qué posiciones están ganando y cuáles están perdiendo).
Intenta demostrar tu respuesta. Si tienes éxito, genial. De lo contrario, intente encontrar un contraejemplo y úselo para adivinar otra respuesta. Aquí podría ser útil resolver algunos casos más.

Es realmente difícil decir cuánto tiempo lleva eso. Sin embargo, en las entrevistas no necesariamente se espera que encuentre la solución. Por el contrario, los entrevistadores quieren saber cómo te acercaste a resolver el problema y qué progreso lograste hacer.

Yuval Filmus
fuente

Sí, no, me rechazaron porque mi producción era incorrecta y se me acabó el tiempo.

millimoose

El enfoque de la fuerza bruta memorizado habría sido correcto, ya que no requiere atajos con respecto a la estrategia. Sin embargo, también, pensé, sería insoportablemente lento, y la memorización podría haber sido demasiado trabajo para posiblemente no mucha ayuda sin usar cantidades tontas de memoria. O tal vez no, lo intentaré más tarde solo para eliminar esto de mi sistema.

millimoose

Observe en la respuesta de @ orlp que queremos la paridad de la suma de los desplazamientos desde la posición inicial hasta la posición final. Anotemos esto:

       9876543210
       9 76 4  1    (positions at start)
start: 1011010010
end:   0000011111
            43210   (positions at end)

Entonces queremos

  ((1 - 0) + (4 - 1) + (6 - 2) + (7 - 3) + (9 - 4)) & 1
= ((1 + 4 + 6 + 7 + 9) - (0 + 1 + 2 + 3 + 4)) & 1
= ((1 + 0 + 0 + 1 + 1) - (0 + 1 + 0 + 1 + 0)) & 1

La primera parte es solo la paridad del número de bits en las posiciones impares. Puede enmascarar eso tomando el número entero máximo sin signo, dividiendo entre 0b11 y negando.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (0 + 1 + 0 + 1 + 0)) & 1

La segunda parte es la paridad de la mitad del número de bits x.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (bitcount(x) >> 1)) & 1

bitcountpuede usar la popcntinstrucción de hardware o puede implementarse manualmente utilizando que solo se necesita el último o el penúltimo bit, con reducciones rápidas como esta .

Veedrac
fuente