Estás remando una canoa por un río de aguas blancas bastante rápido. De repente, tus remos explotan, y te encuentras en una situación peligrosa que se precipita río abajo rápidamente sin remos. Afortunadamente, todavía tiene sus habilidades de programación, por lo que decide tallar un programa en el costado de su canoa para ayudarlo a sobrevivir a los rápidos. Sin embargo, no hay mucha superficie en el costado de la canoa para escribir su programa, por lo que debe hacer que el programa sea lo más corto posible.
El río se puede representar como una cuadrícula de 8 por 16. Vamos a etiquetar las columnas con los números 0
a 7
y las filas con los números0
a 15
.
y
--------15
--------14
--------13
--------12
--------11
--------10
--------9
--------8
--------7
--------6
--------5
--------4
--------3
--------2
--------1
--------0
01234567
x
Arriba: un río completamente tranquilo y ordinario sin obstrucciones. Naturalmente, este no es el río en el que estás.
Usted comienza en la coordenada (4, 0) y desde allí se mueve incontrolablemente río arriba (es decir, el vector (0,1)
) hasta que golpea una roca (representada por una o
en estos ejemplos). Cuando golpeas una roca, tendrás una probabilidad del 55% de pasar la roca hacia la izquierda (es decir, el vector (-1,1)
) y una probabilidad del 45% de pasar la roca hacia la derecha (es decir, el vector(1,1)
). Si la canoa está en las columnas del extremo izquierdo o derecho, siempre se moverá hacia el centro. Si no hay rocas, se moverá hacia arriba.
y
----x---15
----xo--14
-o--x---13
----x---12
---ox---11
---x----10
---xo---9
---ox---8
----xo--7
-----x--6
----ox--5
-o--x---4
----x---3
----xo--2
----x---1
----x---0
01234567
Arriba: una posible ruta que puede tomar la canoa, representada usando el personaje x
Dado el mapa del río, escriba un programa que genere la probabilidad de que la canoa termine en una columna dada.
Acepte la entrada en cualquier método que sea conveniente para su programa (por ejemplo, STDIN, argumento de línea de comando, raw_input()
, lectura de un archivo, etc.). La primera parte de la entrada es un número entero único de 0 a 7, que representa la columna para la que el programa encontrará la probabilidad. A continuación hay una lista de tuplas en la forma que x,y
representa la posición de las piedras.
Un ejemplo:
Entrada:
4 4,1 5,5 3,5
Esto indicaría un río con rocas en las posiciones (4,1), (5,5) y (3,5), y solicita la probabilidad de que la canoa termine en la cuarta columna.
Salida:
0.495
Tenga en cuenta que en este ejemplo, las posiciones de las rocas eran simétricas, lo que permitió resolver el problema con una distribución binomial. ¡Este no siempre será el caso!
Además, el río siempre será transitable. Es decir, nunca habrá dos rocas que se coloquen adyacentes horizontalmente. Ver el comentario de Glenn para un ejemplo de un caso imposible.
Este es el código de golf, por lo que gana el menor número de caracteres. Siéntase libre de hacer preguntas en los comentarios si la especificación no es clara.
Respuestas:
GolfScript, 105 caracteres
Una versión de GolfScript que se hizo mucho más larga de lo previsto, pero cada intento con un enfoque diferente fue aún más largo. La entrada debe darse en STDIN.
Ejemplo:
Código anotado:
fuente
Rubí,
204191172 caracteresSimula recursivamente todos los resultados posibles mientras realiza un seguimiento de la probabilidad de cada resultado individual, luego agrega esa probabilidad a un contador acumulativo cuando
y == 15
.Trucos de lujo:
c,*r=gets.split
- el operador "splat" (*
) toma todos los elementos restantesgets.split
y los pega en lar
matriznext {something} if {condition}
: esencialmente equivalente a"Descubierto" al evolucionar deif condition; something; return; end
unreturn something if condition
a otrobreak something if condition
, y luego pensé que probaría con un "operador de bucle" más corto para ver si funcionaba (lo cual sí, por supuesto).Gracias a @ MartinBüttner por sugerir utilizar operadores ternarios encadenados (que terminaron convirtiéndose en la tercera línea enorme en el código de golf anterior) y eliminar el punto anterior (que salvó 19 (!) Caracteres).
Sin embargo, utilicé un truco un tanto elegante con ellos: me di cuenta de que
s[foo],s[bar]
no funciona en Ruby para dos llamadas a métodos en una sola declaración. Así que al principio me cambió a(_=s[foo],s[bar])
(una variable ficticia), pero luego me di cuenta de que sólo podía sumar y tirar a la basura los valores de retorno:s[foo]+s[bar]
. Esto solo funciona porque las llamadas as
solo "devolverán" otras llamadass
ao un número (o[x]+=p
), por lo que no tengo que preocuparme por verificarnil
.Otras diversas optimizaciones: en
p
lugar deputs
imprimir números, en<1
lugar de==0
(dado que la canoa nunca abandona el río) y comparaciones similares en otros lugares,[0]*8
para probabilidades iniciales, ya que los números de Ruby siempre son "pasados por valor"Sin golf:
fuente
next X if Y
reunirlos en operadores ternarios anidados? Buen hallazgo, sin embargo, es posible que desee agregarlo a los consejos RubyC #
418364bytesComplete el programa C # esperando la entrada de STDIN. Funciona leyendo las rocas en una matriz de todas las ubicaciones en el río, creando efectivamente un mapa, y luego solo realiza 16 iteraciones de probabilidades de movimiento alrededor de una matriz decimal de 8 anchos antes de generar el resultado.
Código formateado:
fuente
for(;j-->0;)
). Sin embargo, puedes deshacerte de un par de personajes reemplazando el últimoC.WriteLine
porC.Write
. Además, si usa enfloat
lugar dedecimal
puede guardar un par de bytes más.decimal
porquefloat
no será preciso, pero el decimal debería funcionar para estos problemas, pero probablemente podría salirse con la suya como usted dice. Lo pondréC.Write
si logro jugar más golf, ya que probablemente esté más cerca de la especificación queC.WriteLine
porque no creo que 4 bytes justifiquen una edición para este programa de tamaño;)Haskell, 256 bytes
Aquí hay una versión muy poco fiel junto con algunos trucos que se usaron:
El último truco que utilicé fue notar que puedes actuar como si las rocas en una sola fila estuvieran realmente separadas por una cantidad infinitesimal. En otras palabras, puede aplicar el transformador de distribución de probabilidad para cada roca en la misma fila secuencialmente y en el orden que desee, en lugar de aplicarlos todos simultáneamente. Esto solo funciona porque el problema no permite dos rocas adyacentes horizontalmente.
Entonces, el programa convierte la ubicación de cada roca en un transformador de distribución de probabilidad, ordenado por la coordenada y de la roca. Los transformadores se encadenan en orden y se aplican a la distribución de probabilidad inicial. ¡Y eso es eso!
fuente
Perl 169 Bytes
Lecturas de STDIN.
Bastante sencillo, implícitamente usa las columnas -1 y 8 para suavizar los casos de borde. Las probabilidades se pueden propagar de manera segura a cada nivel siguiente porque no hay piedras adyacentes, por lo tanto, una sola carrera es suficiente.
fuente
PHP, 358
Usar la capacidad intelectual para determinar los posibles caminos y sus probabilidades es difícil, y probablemente requeriría más código que simplemente simular 1,000,000 de accidentes en canoas. ¡Oh la humanidad!
Ejemplo:
Golfizado:
Esta versión no hace ninguna impresión bonita y genera la probabilidad de flotación del aterrizaje de la canoa en la posición especificada.
fuente
PHP, 274
No puedo leer / escribir GolfScript para salvar mi vida, pero echar un vistazo a la presentación de @ Howard me indicó una mejor dirección que simplemente simular 1 millón de accidentes en canoa.
Comenzando con una serie de probabilidades para las posiciones iniciales, simplemente podemos dividir esos números cada vez que se encuentra una roca.
Salida de ejemplo:
Golfizado:
Ejemplo de ejecución:
fuente
Haskell, 237
Solo espero que la canoa venga con ghc instalado ...
El truco con la lista infinita es robado de Matt Noonan, ¡felicitaciones a él!
Espero tener la lógica correcta, pero el ejemplo de Matt
"5 4,4 1,5 5,3 3,6 2,9 4,12 3,13"
rinde0.5613750000000001
y el ejemplo de OP"4 4,1 5,5 3,5"
rinde0.49500000000000005
, lo que parece ser correcto aparte de algunos errores de coma flotante.Aquí está en acción:
fuente