Dada una máquina de estado finita determinista binaria arbitraria, ¿cuántas cadenas binarias de longitud n serán aceptadas por ella?
La idea parece complicada, pero el concepto es bastante simple.
Apuesto a que si tuviera media hora con algunas tazas y M&M podría explicárselo a un niño de 6 años.
Realmente me gustó este porque tuve que pasar rápidamente por este tipo de evolución de pensamiento para llegar a la solución.
Primero tuve que descubrir qué demonios era un DFSM binario.
Básicamente son solo diagramas de flujo como este:
Usted pasa una cadena de dígitos (digamos 10101101), que comienzan en el estado 0 y, en función de cada dígito posterior, mueven la posición actual a un estado diferente (o el mismo).
Básicamente solo toma una cuerda y sigue las flechas un dígito a la vez. Estas cadenas pueden ser bastante largas, aunque creo que el problema estableció un límite en 50 estados.
¿Ves cómo S0 tiene 2 círculos a su alrededor? Eso se llama un estado “aceptado”.
Si su cadena termina en uno de esos estados aceptados, entonces su cadena se considera aceptada. De lo contrario, se niega .
Entonces, la pregunta era básicamente preguntar: para todas las cadenas de 1s y 0s de longitud n, ¿cuántas de ellas serán aceptadas?
Entonces, como para n = 2, los estados serían 00, 01, 10 y 11. ¿Cuántos serían aceptados?
(Sugerencia: en la imagen de arriba, la respuesta sería 2 de 4).
La razón por la que es difícil es porque en este problema, n podría ser de hasta 10,000.
2 ^ 10,000 estados es … bueno, digamos que es un gran número.
Entonces, podría haber muchos estados aceptados, por lo que nos hicieron aplicar un módulo de 10 ^ 9 + 7 para reducirlo.
Spoilers más allá de este punto si estás interesado … es un problema muy divertido.
Así que comencé realmente simple con algo de fuerza bruta …
Como, eh … déjame hacer una función que evalúe aceptado o rechazado para cualquier cadena dada y devuelva verdadero o falso.
Luego repase todos los números y devuelva la respuesta.
Comencé a implementar esto e inmediatamente me di cuenta de que la cantidad de cálculos requeridos sería ridícula y fuera del alcance de la viabilidad, así que me detuve.
Luego lo pensé como un árbol o una estructura gráfica tradicional.
Puede hacer una búsqueda amplia en estos … Así que preparé una implementación rápida de BFS con una cola …
Básicamente, en cada estado se dividiría en ambas direcciones posibles hasta que se agotara la longitud restante, y luego verificaría si ese punto final era un estado aceptado o no.
Esto no fue tan tonto como el anterior, porque ahora no necesitaría construir + evaluar cada cadena desde cero, y fue una mejora en cómo pensé en atravesar la estructura.
Pero, en última instancia, aún se vio frenado por la misma explosión de cheques, por lo que, por supuesto, se agotó el tiempo para un n muy pequeño.
Creo que mi plan había sido memorizarlo de alguna manera, pero no era obvio y ya se sentía demasiado complicado.
Luego me di cuenta de que era un problema de programación dinámica, y se formó una solución casi final:
- Cree una matriz de recuentos de estados que contenga el número de cadenas que actualmente terminan en un estado determinado.
- Comience con 1 en el estado inicial.
- Bucle n veces.
- Cada vez, para cada estado de la matriz, agregue el recuento de estado actual a sus siguientes 0 y 1 estados.
Entonces, si comenzamos con 1 en el estado 0 y se ramifica a los estados 2 y 3, agregamos ese 1 a ambos estados 2 y 3.
En este punto me encontré con un problema: los datos del estado anterior todavía estaban allí.
En otras palabras, no movía los recuentos de estado a estado, los duplicaba . Esto condujo a una explosión incorrecta en los recuentos.
¿Cómo podría deshacerme de los datos antiguos de un recuento de estados y, al mismo tiempo, diferenciarlos de los datos que los estados anteriores acababan de agregar en la ronda actual?
Finalmente, me di cuenta de que todo lo que tenía que hacer era crear una nueva matriz donde los resultados fueran intercambiados en cada iteración.
Así que lo último funcionó así:
- Para todos los estados, agregue su conteo actual a sus siguientes ubicaciones de estado 0 y 1 en una nueva matriz
- Reemplace la matriz anterior con la nueva matriz
- Modula todo para mantenerlo por debajo del límite
Sume todos los recuentos en los estados aceptados y regrese (asegurándose de aplicar el módulo a medida que agreguemos)
Y eso fue todo.
Realmente simple cuando miras el resultado final, pero nunca antes había hecho ese tipo de intercambio delta.
Muchos problemas son simplemente regurgitaciones aburridas de las mismas cosas viejas, pero este requería que descubriera una nueva forma de resolver algo que lo hizo divertido.
