Introducción
Hay un recaudador de impuestos que tiene algunos problemas para administrar los impuestos de su reino: los registros históricos se han incendiado en un gran incendio.
Quiere saber cuántos pasados posibles podría haber en términos de dónde se heredó el dinero actual. Afortunadamente, su reino es muy simple.
El reino puede ser modelado por una matriz booleana 2D, donde l
representa a alguien que ha heredado dinero y O
representa a alguien que no lo ha hecho. Por ejemplo:
l O l l
O O O l
l O l O
O O O l
(Siempre será un rectángulo)
En la próxima generación, el reino es más pequeño (¡Los lobos son fuertes!).
La próxima generación se vería así, superpuesta a la generación anterior ( x
es un marcador de posición para un descendiente en la próxima generación)
l O l l
x x x
O O O l
x x x
l O l O
x x x
O O O l
Un descendiente se verá en los antepasados que son directamente alrededor de ellos (tanto la parte superior izquierda x
verá { l
, O
, O
, O
}, llamado un barrio rectangular Unaligned )
Si solo un antepasado ha heredado dinero, el descendiente heredará dinero de ellos. Si más de un antepasado ha heredado dinero, se pelearán y el descendiente terminará no heredando dinero. Si nadie ha heredado dinero, el descendiente no heredará dinero.
(Más de un descendiente puede heredar de un antepasado)
Entonces, la próxima generación se vería así:
l l O
l l O
l l O
Desafío
Entrada
El estado actual de la generación, como una matriz de matrices de dos valores distintos, donde las matrices internas tienen la misma longitud.
Por ejemplo, para el ejemplo anterior, podría ser:
[
[True, True, False],
[True, True, False],
[True, True, False]
]
Salida
Un entero que representa el número de generaciones anteriores únicas donde la siguiente generación es la entrada.
Puede suponer que la respuesta siempre será menor que 2 ^ 30 - 1. (o 1073741823).
La generación anterior se llamaría una "preimagen" y este desafío sería contar las preimágenes .
Puntuación
Este es un desafío de código más rápido , por lo que cada envío se probará en mi computadora y el envío que demore menos será el ganador.
Ejemplo de entrada y salida
(¿Dónde 1
está un descendiente que heredó dinero y 0
es un descendiente que no heredó dinero)
Entrada:
[[1, 0, 1],
[0, 1, 0],
[1, 0, 1]]
Salida:
4
Entrada:
[[1, 0, 1, 0, 0, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0],
[1, 1, 1, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 1, 1, 1]]
Salida:
254
Entrada:
[[1, 1, 0, 1, 0, 1, 0, 1, 1, 0],
[1, 1, 0, 0, 0, 0, 1, 1, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 1, 1, 0, 0]]
Salida:
11567
fuente
Respuestas:
C ++ usando la biblioteca BuDDy
Esto parecía una buena excusa para jugar con diagramas de decisión binarios . El reino se convierte en una gran fórmula booleana donde tenemos que contar la cantidad de formas en que se puede satisfacer. Eso puede (a veces) hacerse de manera más eficiente de lo que parece.
El reino debe darse como un programa constante como una matriz plana y dimensiones explícitamente dadas. (Se deja una buena entrada como ejercicio para el lector :-)
Aquí está el código vergonzosamente simple:
Para compilar con debian 8 (jessie), instálalo
libbdd-dev
y hazlog++ -std=c++11 -o hist hist.cpp -lbdd
. (Las opciones de optimización no hacen casi ninguna diferencia porque el trabajo real se realiza en la biblioteca).Grandes ejemplos pueden conducir a mensajes sobre recolección de basura. Podrían ser suprimidos, pero prefiero verlos.
bdd_satcount
devuelve adouble
, pero eso es lo suficientemente bueno para el rango esperado de resultados. La misma técnica de conteo es posible con enteros (grandes) exactos.El código está optimizado para
ROWS<COLS
. Si tiene muchas más filas que columnas, puede ser una buena idea transponer la matriz.fuente
Python 2.7
Este es solo un primer intento ingenuo. No es particularmente rápido, pero es correcto.
La primera observación es que cada celda depende exactamente de cuatro celdas en la generación anterior. Podemos representar esas cuatro celdas como un número de 4 bits (0-15). De acuerdo con las reglas, si exactamente hay una celda vecina en la generación anterior
1
, entonces una celda dada en la generación actual será1
, de lo contrario, lo será0
. Los que corresponden a las potencias de dos, a saber,[1, 2, 4, 8]
. Cuando los cuatro antepasados se representan como un número de 4 bits, cualquier otro número dará como resultado un0
en la generación actual. Con esta información, al ver una celda en la generación actual, podemos reducir las posibilidades del vecindario en la generación anterior a una de cuatro o una de doce posibilidades, respectivamente.Elegí representar el vecindario de la siguiente manera:
donde 0 es el bit menos significativo, y así sucesivamente.
La segunda observación es que para dos celdas adyacentes en la generación actual, los dos vecindarios de la generación anterior se superponen:
o:
En el caso horizontal, el
2
vecindario de la izquierda se superpone con el3
del vecindario de la derecha, y de manera similar con el0
de la izquierda y el1
de la derecha. En el caso vertical, el1
vecindario superior se superpone con el3
vecindario inferior, y de manera similar con0
el superior y2
el inferior.Esta superposición significa que podemos reducir las posibilidades de vecindarios aún no elegidos en función de lo que ya hemos elegido. El código funciona de izquierda a derecha, de arriba a abajo, en una búsqueda recursiva en profundidad de posibles preimágenes. El siguiente diagrama indica qué vecindarios anteriores debemos tener en cuenta al observar los posibles vecindarios de una celda actual:
Aquí está el código:
Para ejecutarlo:
fuente
O(<something>^n)
creo)