El Robot y Montecarlo

Este es el Twitt de @brilliantorg

 

Every time it moves, this robot either hops exactly one dot to the left or one dot to the right.

If the robot starts in the center of this pattern, what is the probability that, after four hops, it’s positioned on top of a blue dot?

Cada vez que se mueve, este robot salta exactamente un punto a la izquierda o un punto a la derecha.

Si el robot comienza en el centro de este patrón, ¿cuál es la probabilidad de que, después de cuatro saltos, se posicione encima de un punto azul?

Para calcular la probabilidad de terminar en los puntos azules, vamos a ejecutar el método Montecarlo mediante la probabilidad sobre el total de resultados. Kotlin es el lenguaje elegido.

fun robotPosition():String  {
    var results = mutableListOf()
    val n = 10000
    (0..n).forEach { _ ->
        var finalPosition = 0
        (0..3).forEach { _ -> finalPosition += if (Random.nextBoolean()) -1 else 1 }
        results.add(abs(finalPosition))
    }
    return "Probability:  ${results.count { k-> k == 2 } / n.toDouble() }"
}

en la función obtenemos una muestra de 10000, simulamos 4 movimientos aleatorios y guardamos la posición. Yo le he dado el valor de 0 a la posición de partida, valores negativos por la izquierda y valores positivos por la derecha, pero a la hora de guardar como ambas partes son simétricas, guardo el valor absoluto para simplificar. Una vez ejecutado obtenemos que la probabilidad aproximada de que el robot caiga en la bola azul es de 1/2 o 0.5.

El número de iteraciones que he usado ha sido 10000, suficiente aunque lo suyo hubiera sido estudiar el promedio y la varianza para determinar que el valor es acertado.

El siguiente consigue el mismo efecto, pero esta vez acumulo las probabilidades obtenidas en un  lista para así al final obtener el promedio. Ejecutamos 100 veces el movimiento del robot y obtenemos la probabilidad la cual guardamos en una lista. ejecutamos esto otras 100 veces para obtener 100 probabilidades distintas, obtenemos la media y resultado igual.

fun probabilityAverage(): String{
    // montecarlo method
    var probTotal = mutableListOf()
    val n = 100
    (0..n).forEach { _ ->
        var successful = 0.0
        (0..n).forEach { _ ->
            var position = 0
            (0..3).forEach { _ -> position += if (Random.nextBoolean()) -1 else 1 }
            successful += if (abs(position)==2) 1 else 0
        }
        probTotal.add(successful / n.toDouble())  
    }

    return "Probability:  ${probTotal.average()}"
}

 

Algoritmo de Luhn

El algoritmo de Luhn fue ideado por Hans Peter Luhn, informático alemán de los primeros, el cual trabajó para IBM y cuyo ingenio nos ha dejado un legado todavía en uso.

El algoritmo de Luhn es el utilizado por las tarjetas de crédito o por el IMEI de nuestros teléfonos para ser validados y otras múltiples aplicaciones, donde podemos verlo en la publicación sobre dígitos de control II de ARITHMOS, aunque en este post, le dedicaremos una líneas exclusivas a él ¿Cómo se calcula el algoritmo de Luhn?

Lo que pretende esencialmente el algoritmo, no es otra cosa que validar que los números de una secuencia son correctos y que no existe ningún error, de modo que su objetivo en este caso es crear un dígito de verificación final que permita indicar si esa secuencia es válida o no. Bien, pues este dígito de verificación se añade al final de secuencia numérica y su cálculo es sencillo siguiendo las siguientes instrucciones.

1. 1. Multiplicar por 2 desde la izquierda a la derecha los números impares
   2. Si cualquiera de estos números multiplicados por 2 es mayor de 9, le calculamos el módulo o resto de 9 para obligar a que tenga solo un dígito.
   3. Efectuamos la suma de estos números impares multiplicados por 2 y simplificados y le llamaremos S_i.
   4. Sumamos los pares y le llamaremos S_p.
   5. Sumamos S_p y S_i y a esta suma le calculamos el módulo o resto de 10
   6. Por último, el resultado obtenido en el paso anterior, se lo restamos a 10 obteniendo el dígito de verificación.

Lo vemos en un ejemplo. Tarjeta de crédito con número 416881884444712X y X es el número de verificación.

1. 1. 1. Multiplicamos por 2 de izquierda a derecha los dígitos impares. 4×2=8, 6×2=12, 8×2=16, 8×2=16, 4×2=8, 4×2=8, 7×2=14, 2×2=4 obteniendo la lista (8, 12, 16, 16, 8, 8, 14, 4)
      2. Reducimos los mayores de 9 calculando el módulo de 9. Para los que no lo recuerden, el módulo de 9 es el resto obtenido al dividir un número entre otro, por ejemplo 20 mod 9 = 2 porque como D=d.c+r 20=9×2+2, así que a los números mayores de 9 les calculamos el módulo de 9 quedando la lista (8, 12 mod 9, 16 mod 9, 16 mod 9, 8, 8, 14 mod 9, 2) = (8, 3, 7, 7, 8, 8, 5, 4)
      3. Calculamos S_i=8+3+7+7+8+5+4=50
      4. Sobre los dígitos pares (1, 8, 1, 8, 4, 4, 1) Calculamos S_i=1+8+1+8+4+4+1=27
      5. Sumamos ambas sumas y le calculamos el módulo de 10. (50+27)=77. 77 mod 10 = 7.
      6. Por último le restamos a 10 el resultado del módulo X=10-7=3 quedando el número final de la tarjeta 4168818844447123.

De este modo cuando realizamos un pago y nos equivocamos al introducir el número de la tarjeta, la aplicación nos avisa de que el número no es un número válido de tarjeta.
Su cálculo es muy sencillo y como muestra de ello he aquí una sencilla función para su cálculo bajo el lenguaje Kotlin del que actualmente estoy enamorado.

fun main (args:Array) {
    val number= "416881884444712"
    val luhn= checkDigitLuhn(number)
    println("El código de verificación es $luhn")
    println("El número final es $number$luhn")
}

fun checkDigitLuhn(numbers:String): Int {
    val list = numbers.map{ e-> e.toString().toInt()}
    return 10 - ((list.filterIndexed { index, i -> index % 2 == 0 }
        .map { (it*2) % 9 }.sum() + 
        list.filterIndexed { index, i -> index % 2 ==1 }.sum()) % 10)
}

daría como resultado…

El código de verificación es 3
El número final es 4168818844447113