Contraseñas y entropía

Contraseñas y entropía

Hoy un amigo nos ha enviado un mensaje al grupo de la Promoción para ver que opinábamos al respecto de la siguiente imagen

IMG-20200902-WA0018.jpg

y yo que la he visto, instantáneamente me he acordado del cálculo necesario para rellenar esta tabla.

Lo primero de todo se debe calcular la entropía. La entropía de una contraseña es calculo matemático que representa un indicador de como se encuentra esta contraseña sobre una población, si incluimos en nuestra contraseña mayúsculas, minúsculas, números y símbolos, la entropía de nuestra contraseña será mayor puesto que la población de carcateres usados es mucho mayor, en este caso, unos 94 (26 minúsculas, 26 mayúsculas, 10 números y 32 símbolos). La fórmula es la siguiente:

entropia.png

o lo que es lo mismo, es el logaritmo en base de 2 de la cantidad de elementos de la población por la longitud de la cadena. Si efectuamos el cálculo inverso, 2 elevado a la entropía debe ser igual a la población elevada al número de caracteres de  nuestra contraseña, que esto serían el número máximo de operaciones necesarias para intentar reventar nuestra password por fuerza bruta.

Si nuestra contraseña usa solo las minúsculas, su “pool” sería de 26 y por tanto la contraseña tendría una entropía baja y fácil de descubrir.

Si hay alguien que quiera comprobar la fuerza de su contraseña online puede hacerlo desde Kaspersky
Bien, pero lo que a mi me importa es como sabemos, con código. En la clase le he incluido una penalización si nuestra contraseña se encuentra entre las más conocidas.

En C#

    /*
************************************************************************************************************************************************
    * © JOAQUIN MARTINEZ RUS 2020
    * Archivo:         PasswordEntropy.cs
    * Descripción:     Clase que calcula la entropia y el tiempo en descifrar por fuerza bruta de de una contraseña
    * Historial:
    *                  1. Joaquin Martínez Rus - 02 sep 2020. Creación
    *
    * Comentarios:
    *
    *
    ****************************************************************/
    public class PasswordEntropy
    {
        public PasswordEntropy(string password)
        {
            Password = password;

        }

        public string Password { get; set; }
        public double Entropy => GetEntropy();
        public string EntropyToString => GetTimeByEntropy(Entropy);

        private double GetEntropy()
        {
            //Pools
            double pool = 0;

            // Numbers
            pool += Password.Any(k => char.IsDigit(k)) ? 10 : 0;
            // Lower 26
            pool += Password.Any(k => char.IsLower(k)) ? 26 : 0;
            // Upper 26
            pool += Password.Any(k => char.IsUpper(k)) ? 26 : 0;
            // Simbols 30
            pool += Password.Any(k => (char.IsSymbol(k) || char.IsPunctuation(k))) ? 32 : 0;

            if (pool == 0) return pool;
            // entropy = Lenght * log pool / log2
            var p = Math.Log(pool, 2);
            var entropy = Password.Length * Math.Log(pool, 2);

            // el uso de una contraseña famosa, indica una falta de seguridad absoluta
            // por lo que no se incluye como deducción de entropía, sino que se incluye en el
            // mismo cálculo de la entropía
            if (IsFamous(Password))
            {
                entropy = (int)Entropies.NoSecurity - 1; // Inexistencia de seguridad
            }
            return entropy;
        }

        private const double OPERATIONPERSECOND = 4*10E12;

        private bool IsFamous(string password)
        {
            var list = new List()
            {
                "1234",
                "2000",
                "12345",
                "111111",
                "123123",
                "123456",
                "654321",
                "696969",
                "1234567",
                "12345678",
                "abc123",
                "alejandra",
                "america",
                "baseball",
                "bonita",
                "daniel",
                "dragon",
                "estrella",
                "football",
                "harley",
                "iloveyou",
                "jennifer",
                "jesus",
                "jordan",
                "letmein",
                "mariposa",
                "master",
                "michael",
                "monkey",
                "mustang",
                "password",
                "pussy",
                "qwerty",
                "roberto",
                "sebastian",
                "shadow",
                "superman",
                "Tequiero"
            };
            return list.Contains(password);
        }

        public enum Entropies
        {
            Blank = 0,
            NoSecurity =10,
            TooWeak=20,
            VeryWeak=28,
            Weak=35,
            Medium=55,
            Strong=75,
            Stronger=127,
            OverTheTopStrong = 190
        }

        private string GetTimeByEntropy(double entropy)
        {
            if (entropy == 0) return string.Empty;
            string output = "";

            double value = Math.Pow(2, entropy) / OPERATIONPERSECOND;
            double ms = 0;
            double seconds = value;
            double minutes = seconds / 60;
            double hours = minutes / 60;
            double days = hours / 24;
            double months = days / 30;
            double years = months / 12;
            double centuries = years / 100;
            double millennium = centuries / 10;

            seconds = value;
            if (value == 0) return "";

            if (seconds  0 && seconds  59 && minutes  59 && hours  24 && days  30 && months  11 && years  99 && centuries  1000000)
            {
                output = "Tu contraseña puede ser descifrada en más de un millón de años!";
            }
            else
            {
                millennium = Math.Round(millennium, 1);
                output = $"Tu contraseña puede ser descifrada en {millennium}, {(millennium == 1 ? "milenio" : "milenios")}";
            }

            return output;
        }
    }

static void Main(string[] args)
        {
            var password = "x#Pr0m0cio_N";

            for (int i = 1; i <= password.Length; i++)
            {
                var pwd = new PasswordEntropy(password.Substring(0,i));
                Console.WriteLine($"Password: {pwd.Password}\n{pwd.EntropyToString}");
                Console.WriteLine("Press any key");
            }

            Console.ReadKey();
        }

el resultado iterando por la contraseña que he creado


Password: x
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#P
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr0
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr0m
Tu contraseña puede ser descifrada en 17, milisegundos
Press any key
Password: x#Pr0m0
Tu contraseña puede ser descifrada en 2, segundos
Press any key
Password: x#Pr0m0c
Tu contraseña puede ser descifrada en 3, minutos
Press any key
Password: x#Pr0m0ci
Tu contraseña puede ser descifrada en 4, horas
Press any key
Password: x#Pr0m0cio
Tu contraseña puede ser descifrada en 15,6, dias
Press any key
Password: x#Pr0m0cio_
Tu contraseña puede ser descifrada en 4,1, años
Press any key
Password: x#Pr0m0cio_N
Tu contraseña puede ser descifrada en 3,8, siglos
Press any key

y en Kotlin

class PasswordEntropy(val password: String) {

    init {

    }

    fun entropy(): Double {

        //Pools
        var pool = 0.0

        // Numbers
        pool += if (password.any { c -> c.isDigit() }) 10.0 else 0.0
        // Lower 26
        pool += if (password.any { c -> c.isLowerCase() }) 26.0 else 0.0
        // Upper 26
        pool += if (password.any { c -> c.isUpperCase() }) 26.0 else 0.0
        val (noSymbols, symbols) = password.partition { it.isLetter() || it.isDigit() }
        // Simbols 32
        pool += if (symbols.count()>0) 32.0 else 0.0
        if (pool == 0.0) return pool
        // entropy = Lenght * log pool / log2

        var entropy = password.length * log2(pool)

        // el uso de una contraseña famosa, indica una falta de seguridad absoluta
        // por lo que no se incluye como deducción de entropía, sino que se incluye en el
        // mismo cálculo de la entropía
        if (isFamous()) {
            entropy = 9.0 // Inexistencia de seguridad
        }
        return entropy
    }

    private fun isFamous(): Boolean{
        return listOf(
            "1234",
            "2000",
            "12345",
            "111111",
            "123123",
            "123456",
            "654321",
            "696969",
            "1234567",
            "12345678",
            "abc123",
            "alejandra",
            "america",
            "baseball",
            "bonita",
            "daniel",
            "dragon",
            "estrella",
            "football",
            "harley",
            "iloveyou",
            "jennifer",
            "jesus",
            "jordan",
            "letmein",
            "mariposa",
            "master",
            "michael",
            "monkey",
            "mustang",
            "password",
            "pussy",
            "qwerty",
            "roberto",
            "sebastian",
            "shadow",
            "superman",
            "Tequiero").contains(password)

    }
    private val OPERATION_PER_SECOND: Double = 4*10E12

    fun entropyToString(): String {
        val entropy = entropy()
        if (entropy == 0.0) return ""

        val value = 2.0.pow(entropy) / OPERATION_PER_SECOND
        var ms = 0
        var seconds = value
        val minutes = seconds / 60.0
        val hours = minutes / 60.0
        val days = hours / 24.0
        val months = days / 30.0
        val years = months / 12.0
        val centuries = years / 100.0
        val millennium = centuries / 10.0

        seconds = value
        if (value == 0.0) return ""

        return when {
            seconds  {
                ms = seconds.toInt() * 1000
                "Tu contraseña puede ser descifrada en $ms, ${if (ms == 1) "milisegundo" else "milisegundos"}"
            }
            seconds > 0 && seconds  "Tu contraseña puede ser descifrada en ${seconds.toInt()}, ${if (seconds.toInt() == 1) "segundo" else "segundos"}"
            seconds > 59 && minutes  "Tu contraseña puede ser descifrada en ${minutes.toInt()}, ${if (minutes.toInt() == 1) "minuto" else "minutos"}"
            minutes > 59 && hours  "Tu contraseña puede ser descifrada en ${hours.toInt()}, ${if (hours.toInt() == 1) "hora" else "horas"}"
            hours > 24 && days  "Tu contraseña puede ser descifrada en ${days.toInt()}, ${if (days.toInt() == 1) "dia" else "dias"}"
            days > 30 && months  "Tu contraseña puede ser descifrada en ${months.toInt()}, ${if (months.toInt() == 1) "mes" else "meses"}"
            months > 11 && years  "Tu contraseña puede ser descifrada en ${years.toInt()}, ${if (years.toInt() == 1) "año" else "años"}"
            years > 99 && centuries  "Tu contraseña puede ser descifrada en ${"%.1f".format(centuries)}, ${if (centuries == 1.0) "siglo" else "siglos"}"
            millennium > 1000000 -> "Tu contraseña puede ser descifrada en más de un millón de años!"
            else -> "Tu contraseña puede ser descifrada en ${millennium.toInt()}, ${if (millennium.toInt() == 1) "milenio" else "milenios"}"
        }
    }

}

fun main(){
    val password = "x#Pr0m0cio_N";

    for (i in (1..password.length)) {
        val pwd = PasswordEntropy(password.substring(0,i))
        println("Password: ${pwd.password}\n${pwd.entropyToString()}\n")

    }
}

el resultado para Kotlin


Password: x
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#P
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr0
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr0m
Tu contraseña puede ser descifrada en 17, milisegundos
Press any key
Password: x#Pr0m0
Tu contraseña puede ser descifrada en 2, segundos
Press any key
Password: x#Pr0m0c
Tu contraseña puede ser descifrada en 3, minutos
Press any key
Password: x#Pr0m0ci
Tu contraseña puede ser descifrada en 4, horas
Press any key
Password: x#Pr0m0cio
Tu contraseña puede ser descifrada en 15,6, dias
Press any key
Password: x#Pr0m0cio_
Tu contraseña puede ser descifrada en 4,1, años
Press any key
Password: x#Pr0m0cio_N
Tu contraseña puede ser descifrada en 3,8, siglos
Press any key

Saludos a la X Promoción del IPE 2!!!

Licencia Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional

Interface. Genetic Algorithm II

Interface. Genetic Algorithm II
En este post veremos como un algoritmo genético es capaz de ordenar un tablero de ajedrez. Es como si un niño de 2 años pusiera las piezas aleatoriamente en el tablero y el algoritmo se encargara de poner cada una en su sitio.

Crearemos una clase ChessPiece para cada figura de ajedrez y una clase ChessBoard que implementará la interfaz IMutable. Esto quiere decir que nuestro cromosoma es una lista de piezas de ajedrez y que el Fitness es del tipo doble.
Acto seguido, creamos el geneset o conjunto de genes que formarán el cromosoma donde incluiremos también la casilla vacía. Luego le daremos un valor a cada pieza y otro valor a cada casilla, cada vez que se acierte, el fitness se verá incrementado hasta el 100%.

class ChessBoard : IMutable {
    override val geneset = mutableListOf(
            ChessPiece("T",ChessPieceColor.BLACK,11),
            ChessPiece("C",ChessPieceColor.BLACK,13),
            ChessPiece("A",ChessPieceColor.BLACK,15),
            ChessPiece("D",ChessPieceColor.BLACK,16),
            ChessPiece("R",ChessPieceColor.BLACK,18),
            ChessPiece("A",ChessPieceColor.BLACK,15),
            ChessPiece("C",ChessPieceColor.BLACK,13),
            ChessPiece("T",ChessPieceColor.BLACK,11),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("T",ChessPieceColor.WHITE,10),
            ChessPiece("C",ChessPieceColor.WHITE,12),
            ChessPiece("A",ChessPieceColor.WHITE,14),
            ChessPiece("D",ChessPieceColor.WHITE,17),
            ChessPiece("R",ChessPieceColor.WHITE,19),
            ChessPiece("A",ChessPieceColor.WHITE,14),
            ChessPiece("C",ChessPieceColor.WHITE,12),
            ChessPiece("T",ChessPieceColor.WHITE,10),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5))

    init {

        geneset.addAll((1..32).map { ChessPiece("_",ChessPieceColor.EMPTY,0) })
    }

    override val target: Double = 64.0
    override var bestParent = createParent(0)
    override var bestFitness: Double = 0.0
    private val values = mutableListOf(11,13,15,16,18,15,13,11,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,5,5,5,5,5,5,5,10,12,14,17,19,14,12,10)

    override fun isSuccess(): Boolean = bestFitness == 1.0

    var result=""
    override fun start() {
        bestFitness = getFitness(bestParent)
        var childFitness: Double
        var child: MutableList
        //Display(bestParent, bestFitness)
        var attemps=0

        do {
            do {
                child = mutate(bestParent)
                childFitness = getFitness(child)

            } while (bestFitness > childFitness)

            bestFitness = childFitness
            bestParent = child
            result +=toShortString() + "\n\n\n"
            attemps ++
            println(toShortString() + "\n")
        } while (!isSuccess())
        println("Nº de intentos: $attemps")
    }

    override fun createParent(param: Any): MutableList {
        // llena el tablero con las 32 fichas piezas + 32 vacias
        return geneset.shuffled().toMutableList()
    }

    override fun getFitness(obj: MutableList): Double = obj.mapIndexed { index, chessPiece -> if (values[index] == chessPiece.value) 1.0 else 0.0  }.sum() / target

    override fun mutate(parent: MutableList): MutableList {
        val parentFitness: Double = getFitness(parent)
        var childFitness = 0.0
        var child = mutableListOf()

        do {
            child.clear()
            child.addAll(parent)

            val startIndex = Random.nextInt(bestParent.size)
            val endIndex = Random.nextInt(bestParent.size)
            val start = parent[startIndex]
            val end = parent[endIndex]
            child[startIndex] = end
            child[endIndex] = start
            childFitness = getFitness(child)

        }while (childFitness chessPiece.toString() + if ((index+1) % 8 ==0) "\n" else "\t" }
            .joinToString("")}\nFitness: $bestFitness"

    fun toShortString(): String ="${bestParent
                    .mapIndexed { index, chessPiece -> (if (chessPiece.value==0) " " else if (chessPiece.value == values[index]) (if (chessPiece.color==ChessPieceColor.WHITE) "○" else "●") else "#")+if ((index+1) % 8 == 0) "\n" else "" }
                    .joinToString("")
        }\nFitness: ${"%.3f".format(bestFitness)}"
    fun  foo(collection: MutableList){

    }
}

fun main(){
    val chessBoard = ChessBoard()
    chessBoard.start()
    println(chessBoard.bestParent)
}

Y este es el resultado del progreso de los cromosomas para 36 intentos
cromosomas.png

TN	CN	AN	DN	RN	AN	CN	TN
PN	PN	PN	PN	PN	PN	PN	PN
__	__	__	__	__	__	__	__
__	__	__	__	__	__	__	__
__	__	__	__	__	__	__	__
__	__	__	__	__	__	__	__
PB	PB	PB	PB	PB	PB	PB	PB
TB	CB	AB	DB	RB	AB	CB	TB

Fitness: 1.0

Y ahora implementaremos la interfaz con mi mejor amigo, C#

 public class ChessPiece
    {
        public ChessPiece(string name, Colors color, int value)
        {
            Name = name;
            ChessPieceColor = color;
            Value = value;
        }

        public string Name { get; set; }
        public int Value { get; set; }
        public Colors ChessPieceColor { get; set; }

        public enum Colors
        {
            Black,
            White,
            Empty
        }

        public string ColorToString => ValueToString(ChessPieceColor);

        public new string ToString => $"{Name}{ColorToString}";

        private string ValueToString(Colors color)
        {
            switch (color)
            {
                case Colors.Black:
                    return "N";
                case Colors.White:
                    return "B";
                case Colors.Empty:
                    return "_";
                default:
                    return "";
            }
        }

    }

    public class ChessBoard : IMutable
    {
        public ChessBoard()
        {
            Geneset = new List()
            {
                    new ChessPiece("T", ChessPiece.Colors.Black, 11),
                    new ChessPiece("C", ChessPiece.Colors.Black, 13),
                    new ChessPiece("A", ChessPiece.Colors.Black, 15),
                    new ChessPiece("D", ChessPiece.Colors.Black, 16),
                    new ChessPiece("R", ChessPiece.Colors.Black, 18),
                    new ChessPiece("A", ChessPiece.Colors.Black, 15),
                    new ChessPiece("C", ChessPiece.Colors.Black, 13),
                    new ChessPiece("T", ChessPiece.Colors.Black, 11),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("T", ChessPiece.Colors.White, 10),
                    new ChessPiece("C", ChessPiece.Colors.White, 12),
                    new ChessPiece("A", ChessPiece.Colors.White, 14),
                    new ChessPiece("D", ChessPiece.Colors.White, 17),
                    new ChessPiece("R", ChessPiece.Colors.White, 19),
                    new ChessPiece("A", ChessPiece.Colors.White, 14),
                    new ChessPiece("C", ChessPiece.Colors.White, 12),
                    new ChessPiece("T", ChessPiece.Colors.White, 10),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5)
            };

            Geneset.AddRange(Enumerable.Range(0, 32).ToList().Select(k => new ChessPiece("_", ChessPiece.Colors.Empty, 0)));           

        }

        public List Geneset { get; set; }
        public double Target { get; set; } = 64;
        public List BestParent { get; set; }
        public double BestFitness { get; set; }

        private Random rnd = new Random();
        private IList Values = new List() { 11, 13, 15, 16, 18, 15, 13, 11, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 10, 12, 14, 17, 19, 14, 12, 10 };
        private string result = "";

        public List CreateParent(object param) => Suffled(Geneset);

        public double GetFitness(List obj) => obj
            .Select((item, index) => new { Item = item, Index = index })
            .Select(k => k.Item.Value == Values[k.Index] ? 1.0 : 0.0)
            .Sum()/Target;

        public bool IsSuccess() => BestFitness == 1.0;

        public List Mutate(List parent)
        {

            var parentFitness = GetFitness(parent);
            var childFitness = 0.0;
            var child = new List();

            do
            {
                child.Clear();
                child.AddRange(parent);

                var startIndex = rnd.Next(BestParent.Count());
                var endIndex = rnd.Next(BestParent.Count());
                var start = parent[startIndex];
                var end = parent[endIndex];

                child.RemoveAt(startIndex);
                child.Insert(startIndex, end);
                child.RemoveAt(endIndex);
                child.Insert(endIndex, start);

                childFitness = GetFitness(child);
                //print(child);
            } while (childFitness k.Value)));
        }

        public void Start()

        {
            BestParent = CreateParent(null);
            BestFitness = GetFitness(BestParent);
            var childFitness = 0.0;
            var child = new List();

            var attemps = 0;
            do
            {
                do
                {
                    child = Mutate(BestParent);
                    childFitness = GetFitness(child);
                } while (BestFitness > childFitness);

                BestFitness = childFitness;
                BestParent = child;
                result += ToShortString + "\n\n\n";
                Console.WriteLine(result);
                attemps++;
            } while (!IsSuccess());

            Console.WriteLine(ToShortString + "\n");
            Console.WriteLine($"Nº intentos: {attemps}");
        }

        private List Suffled(List source) => source
            .Select(x => new { value = x, order = rnd.Next() })
            .OrderBy(x => x.order).Select(x => x.value).ToList();

        public new string ToString => $"{string.Join("",BestParent.Select((item, index) => new { Item = item, Index = index }).Select(k => k.Item.ToString + (((k.Index + 1) % 8 == 0) ? '\n' : ' '))) }";
        public string ToShortString => $"{string.Join("",BestParent.Select((item, index) => new { Item = item, Index = index }).Select(k => (k.Item.Value == 0 ? " " : (k.Item.Value == Values[k.Index]) ? (k.Item.ChessPieceColor == ChessPiece.Colors.White ? "O" : "■") : "#") + (((k.Index + 1) % 8 == 0) ? '\n' : ' '))) }";

    }
 class Program
    {
        static void Main(string[] args)
        {
            var chessboard = new ChessBoard();
            chessboard.Start();
            Console.WriteLine(chessboard.ToString);
            Console.WriteLine("Press any key...");
            Console.ReadKey();
        }
    }

Si quieres leer mi anterior post sobre la interface de algoritmos genéticos, aquí lo tienes.

Licencia Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

Interface. Genetic Algorithm I

Interface. Genetic Algorithm I

¿Cómo conseguir un objetivo por los mismos medios por los que una especie sobrevive? La respuesta es, mutando y cruzándo sus individuos para obtener ese objetivo.

Los algoritmos genéticos desde el punto de vista del desarrollo de software, tienen casi todos un patrón único y si tienen un patrón único atienden a una estructura común, por tanto es como cualquier interface, atienden siempre a la misma composición, de modo que ¿Por qué no generamos una interface que implemente este comportamiento? ¿Por qué crear una interface? Generamos una interface porque esperamos que cualquier clase que implemente esta interface haga lo mismo y la interface es el elemento adecuado. (¿he entrado en bucle? uhmmm). Para saber más acerca de interfaces, aquí tiene un artículo de Wakicode.

Bien, la verdad que he buscado y “requetebuscado” (que dicen en mi tierra) y no he visto nada parecido acerca de una interface de algoritmo genéticos.

Un algoritmo genético tiene los siguientes elementos:

  • Un conjunto de genes en los que se basan cada uno de objetos generados
  • Un patrón inicial o digamos un Adán o una Eva
  • Un candidato a ser el mejor de la especie
  • Un indicador métrico de aptitud del mejor de la especie

y efectua las siguientes tareas:

  • Inicia el algoritmo
  • Crea el patrón inicial
  • Obtiene la métrica de cualquier objeto de la especie. Función de Aptitud
  • Ejecuta un cruce entre individuos de la especie. Cruce
  • Ejecuta una mutación sobre un objeto. Mutación
  • Comprueba si se ha cumplido con el objetivo. Criterio de parada
  • Si no se ha conseguido el objetivo, volvemos a realizar la tarea
  • Obtención de la solucióndiagrama algoritmo genetico.png

Además un algoritmo genético no tiene porque realizar un cruce porque a lo mejor nuestro problema lo podemos solucionar mutando solamente sus genes sin realizar cruce. Cada algoritmo hay que estudiarlo

Dicho esto nos ponemos manos a la obra y vamos a desarrollar una interfaz que tenga estos elementos y que nos permita realizar estas acciones con diferentes tipos. En principio voy a crear una interface del tipo Mutable y luego heredaré de esta para crear una nueva Crossover  con funciones de cruce.

En Kotlin

/**
 * @author Joaquin Martinez Rus ©
 * @since 15AGO20
 * version 1.1
 */
interface IMutable
{
    val geneset: T
    val target: F
    var bestParent: T
    var bestFitness: F

    /**
     * Return true when target is reached
     * @return Boolean
     */
    fun isSuccess(): Boolean

    /**
     * Start algorithm
     * @sample
     * CreateParent
     * Mutate
     * GetFitness
     * Compare
     * IsSuccess
     */
    fun start()

    /**
     * Return a new parent object
     * @param Parameter of generation
     * @return Type T
     */
    fun createParent(param: Any): T

    /**
     * Get object fitness
     * @return F value
     */
    fun getFitness(obj: T): F

    /**
     * Return a mutation of a parent object
     * @param Parent element
     * @return type T mutated
     */
    fun mutate (parent: T): T
}

/**
 * @author Joaquin Martinez Rus ©
 * @since 15AGO20
 * version 1.1
 */
interface ICrossOver : IMutable
{
    /**
     * Return a crossover of two objects of same type
     * @param Parent element
     * @return type T crossed over
     */
    fun crossOver(father: T, mother: T): T
}

y en C#

/* ************************************************************************************************************************************************
    * © JOAQUIN MARTINEZ RUS 2020
    * Archivo:         Imutable.cs
    * Descripción:     Interface que implementa un algoritmo genético de mutación
    * Historial:
    *                  1. Joaquin Martínez Rus - 15 ago 2020. Creación
    *
    * Comentarios:
    *
    *
    **************************************************************************************************************************************************/
    public interface IMutable where F : IComparable
    {
        public T Geneset { get; set; }
        public F Target { get; set; }
        public T BestParent { get; set; }
        public F BestFitness { get; set; }

        ///
        /// Return true when target is reached
        /// 

        /// Boolean
        bool IsSuccess();

        ///
        ///  Start algorithm
        ///  Example
        ///  CreateParent
        ///  Mutate
        ///  Getfitness
        ///  Compare
        ///  IsSuccess
        /// 

        void Start();

        ///
        /// Return a new parent object
        /// 

        /// Parameter of generation
        /// Type T
        T CreateParent(object param);

        ///
        /// Get object fitness
        /// 

        /// Object from which the fitness is obtained
        /// F Value
        F GetFitness(T obj);

        ///
        /// Return a mutation of a parent object
        /// 

        /// Parent element
        /// T mutated
        T Mutate(T parent);

    }

    /* ************************************************************************************************************************************************
    * © JOAQUIN MARTINEZ RUS 2020
    * Archivo:         ICrossOver.cs
    * Descripción:     Interface que implementa un algoritmo genético de mutación y cruce
    * Historial:
    *                  1. Joaquin Martínez Rus - 15 ago 2020. Creación
    *
    * Comentarios:
    *
    *
    **************************************************************************************************************************************************/
    public interface ICrossOver : IMutable where F: IComparable
    {
        ///
        /// Return a crossover of two objects of same type
        /// 

        /// Fateher
        /// Mother
        /// type T crossed over
        T CrossOver(T father, T mother);

    }

Analicemos la interface.Lo primero. La interface es una interface genérica con dos tipos, T es el tipo del objeto del algoritmo y F es el tipo de la propiedad Fitness que obligatoriamente debe ser comparable. Este será el cromosoma.
Cuatro propiedades, un geneset o conjunto de genes, el objetivo que pretenderá alcanzar el algoritmo (target), un objeto genérico como mejor individuo de su especie (bestParent) y un indicador de aptitud del mejor de los individuos (bestFitness).
Luego tenemos 5 métodos, método start para iniciar el algoritmo, un método createParent que creará el primero de la especie al cual le he incluido un parámetro por si quisiéramos determinar alguna particularidad sobre él, un método mutate que mutará un objeto en otro, un método getFitness que obtiene la aptitud y por último otro método booleano que determina si el algoritmo ha cumplido su objetivo (isSuccess).La interface ICrossOver hereda de esta añadiéndole un método más llamado crossOver con dos parámetros o padre y madre del objeto resultante.Si ahora creamos una clase que implemente esta interface, nos aseguramos que como mínimo tendremos que desarrollar los elementos de la interface, más fácil imposible. ¿Dónde tenemos que estrujarnos el cerebro? en diseñar el tipo de cromosoma, el objetivo como debe alcanzarse o en como debe mutar. No es poco, pero si tienes poca experiencia con algoritmos genéticos, esta es tu interface.

En la práctica, vamos a generar un algoritmo sencillo que adivine una frase. Esto tan fácil como crear una clase que implemente IMutable y en nuestro IDE nos aparecerá en rojo indicándonos que algo mal. La mayoría de los IDE,s tiene un asistente, una bombilla, una herramienta, un algo que al pulsar sobre él nos indica que algo está pasando y este dirá “implement as constructor parameters”, seleccionamos las propiedades y et voilá, propiedades en la clase, pulsamos de nuevo y nos dirá implement members.

genetics01.jpg.png

Al pulsar, seleccionamos todos lo métodos y clase lista. Ahora el código

genetics02.png
Y aquí la clase con su código, esta solo mutará por tanto implementa IMutable, donde el algoritmo intentará adivinar unos preciosos versos de Mario Benedetti “Corazón coraza” con 334 caracteres.
El algoritmo creará una cadena aleatoria inicialmente e irá mutando hasta llegar al objetivo deseado.

class GuessString (override val target: Double, override val geneset: String) : IMutable{
    val guess = "Porque te tengo y no porque te pienso\n" +
            "porque la noche está de ojos abiertos\n" +
            "porque la noche pasa y digo amor\n" +
            "porque has venido a recoger tu imagen\n" +
            "y eres mejor que todas tus imágenes\n" +
            "porque eres linda desde el pie hasta el alma\n" +
            "porque eres buena desde el alma a mí\n" +
            "porque te escondes dulce en el orgullo\n" +
            "pequeña y dulce\n" +
            "corazón coraza"
    override var bestParent: String = createParent(guess.length)
    override var bestFitness: Double = getFitness(bestParent)
    private var attempts = 0

    init {
        start()
    }

    override fun start()
    {
        var childFitness: Double
        var child: String

        do {
            do {
                child = mutate(bestParent)
                childFitness = getFitness(child)
            } while (bestFitness >= childFitness)

            bestFitness = childFitness
            bestParent = child
            attempts ++
        } while (!isSuccess())
        println("Intentos: $attempts")
    }

    override fun isSuccess(): Boolean {
        val value = (bestFitness.toString().toDouble() / guess.length)
        return value >= target
    }

    override fun createParent(param: Any) : String {
        val genes = StringBuilder()
        val length = geneset.length
        (0 until param.toString().toInt()).forEach {
            genes.append(geneset[Random.nextInt(length)])
        }

        return genes.toString()
    }

    override fun getFitness(obj: String): Double = guess.mapIndexed { i, c -> if (c==obj[i]) 1.0 else 0.0}.sum()

    override fun mutate(parent: String): String {
        var index = 0
        val parentFitness: Double = getFitness(parent)
        var childFitness = 0.0

        var newGene: Char
        var alternate: Char
        var definitive: Char
        var indexGeneset: Int
        var child: String

        var length =  geneset.length

        do {
            index = Random.nextInt(parent.length)
            indexGeneset = Random.nextInt( length)

            newGene = geneset[indexGeneset]

            indexGeneset = Random.nextInt( length)
            alternate = geneset[indexGeneset]
            //definitivo
            definitive = if (newGene == parent[index]) alternate else newGene

            child = parent.replaceRange(index,index+1, definitive.toString())

            childFitness = getFitness(child)

        } while (parentFitness >= childFitness)

        return child
    }
}

fun main() {
val guess =GuessString(
        1.0,
        " áéíóúabcdefghijklmnñopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ,\n")
println(guess.bestParent)
}

Y el resultado

Intentos: 328
Porque te tengo y no porque te pienso
porque la noche está de ojos abiertos
porque la noche pasa y digo amor
porque has venido a recoger tu imagen
y eres mejor que todas tus imágenes
porque eres linda desde el pie hasta el alma
porque eres buena desde el alma a mí
porque te escondes dulce en el orgullo
pequeña y dulce
corazón coraza

Pues aquí tenéis mi interface para algoritmos genéticos.
En el próximo post, veremos un algoritmo genético que posicionará las piezas de ajedrez en su sitio.
Pd: En realidad, la clase de adivinar no es gran cosa, porque se podría haber conseguido por iteración, pero entonces no habriáis aprendido el algortimo genético. Entonces, espero que os haya servido. 😉
Podía haber elegido a Antonio Machado a Calderón de la Barca o a cualquier otro poeta o poema, pero, este me parece especialmente bello. Leedlo completo, es corto, tres estrofas.
Licencia Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

Interfaces

Interfaces

Cuando se empieza a programar, el uso de interfaces es un poco abstracto ya que no se le ve utilidad, pero las interfaces son de los más útiles. ¿Qué es una interface? es un contrato por el que una clase se ve obligada a cumplir en todos sus términos. Es decir, la interface contiene métodos y propiedades y cuando una clase implementa esta interface, la clase debe tener absolutamente todos los métodos y todas las propiedades que la interface le ha dicho.

Un objeto en la mayoría de los lenguajes, solo puede heredar de una clase, pero si puede implementar varias interfaces.

Un ejemplo. Quiero crear una colección de figuras de ajedrez; si quisiera ordenar la colección por valor y color en el que las negras valiesen más, al usar el método sort(), orderby() o el que sea, el objeto como mínimo deberá contener algún método que use ese método para ordenar sus elementos, compararlos y decidir cual va primero y cual después, ¿no?, pues yo lo que haría sería por ejemplo en Kotlin, es que la clase FiguraAjedrez implemente la interface Comparable (lo normal es que las interfaces, dependen del lenguaje comiencen por I, pero todas acaben con -able) que a su vez contiene un método compareTo.

Pues si la FiguraAjedrez tiene ese método, la colección cuando use el método sort encontrará el método compareTo donde nosotros escribiremos nuestro código, comparamos por el valor de la figura y le añadimos un extra por el color.

También, cuando pasamos como argumento una interface, nos estamos asegurando que el objeto que se pasa cumple con las expectativas. En C# si pasamos como argumento en un método un objeto del tipo IEnumerable, no estamos asegurando que el objeto que se pasa, tiene como mínimo un enumerador y que pude moverse por los elementos de la colección. O si le pasamos como argumento la interface IList, nos estamos asegurando que esta interface está heredando de ICollection, IEnumerable<T> e IEnumerable, de modo que puede moverse por sus elementos, puede borrar la colección, añadir, eliminar objetos, saber si tiene un objeto en la colección y hacer copias, todo esto. En Kotlin pasa algo parecido con la interface MutableList que hereda de las interfaces List y MutableCollection para hacer estas mismas acciones y algunas más.

        private static void Foo(IList collection)
        {
            // Do something
        }
         fun  foo(collection: MutableList){
            // Do something
         }

A continuación vamos ver un ejemplo de interface y de una clase que la implemente

interface IChessPiece: Comparable{
    fun doSomething()
    fun move()
    val isBlack: Boolean
    val value: Int
    val piece: String
}
class ChessPiece(override val piece: String, override val isBlack: Boolean, override val value: Int) : IChessPiece {
    override fun doSomething() {
        TODO("Not yet implemented")
    }

    override fun move() {
        TODO("Not yet implemented")
    }

    override fun compareTo(other: ChessPiece): Int {
        // Aqui incluimos el código de comparación
    }

}

fun foo(chessPiece: IChessPiece){

}

En el ejemplo, vemos que la interface IChessPiece implementa IComparable, así que podremos comparar objetos con otros del mismo tipo y luego le añadimos algunas propiedades y métodos, así que la clase ChessPiece obligatoriamente, debe tener cada uno de los métodos y propiedades establecidos en la interface.
En el método foo pasamos como argumento un objeto que implemente la interface, ASEGURANDO que va a hacer y va a tener lo que queremos que haga y que tenga. si mañana cambiamos el código de la clase o creamos una nueva con más funciones, lo que nos importa para que se entienda con el resto del código es que cumpla como mínimo con lo esperado.Usa las interfaces, sobre todo en los modelos y viewmodel, más tarde te alegraras enormemente.
Licencia Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

My Golden Class

My Golden Class

Repasando un problema de @diegorattaggi y #mathiratti sobre φ el número áureo, el cual intenté mediante artificios matemáticos aprovechando las propiedades de las potencias del número aúreo sin llegar a resolverlo, se me ocurrió hacerlo por fuerza bruta, es decir iterando cada uno de los términos hasta conseguir resultados. En vano, solo obtuve un resultado para m=7 y n=5 y además no podía prosperar en cuanto las cifras crecían en número de dígitos. (El problema es bello, pero para resolverlo matemáticamente.)

Luego me acordé de este otro problema y me propuse mejorar la clase que desarrollé para ejecutar la fuerza bruta del problema anterior.

Aprovechando que es una clase nueva, he eliminado cualquier rastro de fuerza bruta y le he incluido algunas mejoras como por ejemplo :

  1. Número infinito de decimales de φ
  2. Cálculo de potencias de φ en función de los elementos de la sucesión de Fibonacci, más rápido y más preciso
  3. Cálculo de raices cuadradas para el tipo BigDecimal, para obtener infinitos decimales de φ.
  4. Obtención de la sucesión de Fibonacci n, como no. (Hasta Fib (315.000) y creo que haciendo algunos ajustes en el compilador de Intellij, alguno más caerá). Le he incluido una versión secursiva y otra iterativa, la función recursiva es mucho más eficiente gracias a la palabra clave modificadora de función tailrec de kotlin,el cual al incluirlo delante de una función recursiva, el compilador la trata como si fuera iterativa convirtiendo la función en un ciclo rápido y muy eficiente, alucinante.
  5. Obtención de un elemento concreto de la sucesión

Y ahora estamos preparados para atacar el problema con software, aunque a mi me gusta más hacerlo con matemáticas. Lo primero la clase con Kotlin

import java.math.BigDecimal
import java.math.BigInteger
import java.math.RoundingMode

class Phi {
    var decimals = 10
    val  TWO= 2.toBigDecimal()
    val  FIVE= 5.toBigDecimal()
    val  SQRTFIVE= sqrt(FIVE)

    val value: BigDecimal
        get() = (BigDecimal.ONE + SQRTFIVE).divide(TWO, decimals, RoundingMode.HALF_DOWN)
    private val fibonacci = mutableListOf()

    init {
        fibonacci.clear()
    }

    private fun calculateFibonacci(n: Int) {
        fibonacci.clear()
        fibonacciRecursive(n.toBigDecimal())
    }

    private fun sqrt(value: BigDecimal, scale: Int=decimals): BigDecimal {
        var x0 = BigDecimal("0")
        var x1 = BigDecimal(kotlin.math.sqrt(value.toDouble()))
        while (x0 != x1) {
            x0 = x1
            x1 = value.divide(x0, scale, RoundingMode.HALF_UP)
            x1 = x1.add(x0)
            x1 = x1.divide(TWO, scale, RoundingMode.HALF_UP)
        }
        return x1
    }

    private tailrec fun fibonacciRecursive(n: BigDecimal, a: BigDecimal = BigDecimal.ZERO, b: BigDecimal = BigDecimal.ONE) {
        fibonacci.add(b)
        when (n) {
            BigDecimal.ZERO -> a
            BigDecimal.ONE -> b
            else -> fibonacciRecursive(n - BigDecimal.ONE, b, a.add(b))
        }
    }

    private fun checkSucession(n:Int) { if (fibonacci.size < n) calculateFibonacci(n)}

    fun fibonacciIterator(n: Int): BigDecimal{
        var l = BigDecimal.ONE
        var lm1 = BigDecimal.ONE
        for (i in 3..n){
            var tmp = l
            l += lm1
            lm1 = tmp
        }
        return l
    }

    fun pow(n: Int) : BigDecimal {
        checkSucession(n)
        return fibonacci[n - 1] * value + fibonacci[n - 2]
    }

    fun fibonacciExplicitItem(n: Int): BigInteger = (getPhi(decimals).pow(n) - (BigDecimal.ONE - value).pow(n)).divide(sqrt(FIVE), decimals, RoundingMode.HALF_DOWN).toBigInteger()

    fun fibonacciItem(n: Int): BigDecimal {
        checkSucession(n)
        return fibonacci[n-1]
    }


    fun fibonacci(n: Int): List {
        checkSucession(n)
        return fibonacci;
    }

    fun sumInverse(n: Int): BigDecimal{
        val pn = value.pow(n)
        return when (n % 2){
            0 -> pn.toBigInteger().toBigDecimal() + BigDecimal.ONE
            1 -> pn.toBigInteger().toBigDecimal()
            else -> BigDecimal.ZERO
        }
    }

    override fun toString(): String {
        return value.toString()
    }

    fun getPhi(decimals:Int): BigDecimal = (BigDecimal.ONE + sqrt(FIVE, decimals )).divide(TWO)

    fun getPhiToString(decimals:Int): String {
        val phi = getPhi(decimals).toString()
        val text : StringBuilder= StringBuilder()
        text.append("1.\n")
        val phi2 = phi.removePrefix("1.")
        phi2.forEachIndexed { index, c ->
            when {
                index % 100 == 0 && index > 0 -> text.append("\t$index:\n$c")
                index % 10 == 0  && index > 0 -> text.append(" $c")
                else -> text.append(c)
            }
        }
        text.append("\t$decimals:")
        return text.toString()
    }
}

Y para iniciar, vamos a ver como funciona

import java.math.BigDecimal
import kotlin.system.measureTimeMillis

fun main(args: Array){
val n = 100000
val power = 1500
val phi = Phi()

val t1 = measureTimeMillis { println("phi: ${phi.getPhi(100000)}") }
println("$n decimals of Phi. Duration: $t1")
val t2 = measureTimeMillis { "Fibonacci($n): ${phi.fibonacci(n)}" }
println("Fibonacci($n). Duration: $t2")
val t3 = measureTimeMillis { println("Fibonacci($n): ${phi.fibonacciItem(n)}") }
println("FibonacciItem($n). Duration: $t3")
val t4 = measureTimeMillis { println("Phi^$power: ${phi.pow(power)}") }
println("Phi^$power. Duration: $t4")
}
  1. Instancia de la clase
  2. Obtenemos el número φ con 100.000 decimales
  3. Obtenemos la sucesión de Fibonacci para n=100.000
  4. Obtenemos el elemento 100.000 de la sucesión de Fibonacci
  5. Elevamos φ a la potencia 1500

Resultado

Phi: 1.618033988... 100.000 decimals ...8836739749559326107
100000 decimals of Phi. Duration: 2601ms
Fibonacci(100000). Duration: 143044ms
Fibonacci(100000): 259740693472217 ... 20.900 digits ... 5699780289236362349895374653428746875
FibonacciItem(100000). Duration: 1ms
Phi^1500: 30301238166550805786929189390145575626423967452224056329446235918567465318942832927313669458439880439962733393211656583769182495024464042800878040985094292794417098116786924311826550387756605278028834211153418987752560366539982408518048936164775701203049457214716895381907861202507701229899701575192565697255980968.78939750000
Phi^1500. Duration: 1ms

Pues para el montón de dígitos, sin paralelismo y lo que conseguimos, Kotlin vuelve a conquistarme.

Para terminar resolvamos el segundo problema

val t1 = measureTimeMillis {
val phi3 = phi.pow(3)
val phi5 = phi.pow(5)
val phi6 = phi.pow(6)
val phi8 = phi.pow(8)

val result =
(phi3 + ((phi3 + ((phi3 + phi5) / (BigDecimal.ONE - phi8))) / (BigDecimal.ONE - ((phi6 + phi8) / (BigDecimal.ONE - phi8))))) /
(((phi6 + ((phi6 + phi8) / (BigDecimal.ONE - phi8))) / (BigDecimal.ONE - ((phi6 + phi8) / (BigDecimal.ONE - phi8)))) - BigDecimal.ONE)
println("Result: $result")
}
println("Result. Duration: $t1")

20200723_155641.jpg

El resultado rápido y preciso y sobretodo, bello en sí. Las matemáticas lo son.

Result: 1.00000000000
Result. Duration: 3ms

Saludos y gracias @diegorattaggi

Pd: El post de Arithmos sobre la cantidad de dígitos de los elementos de la sucesión de Fibonacci, está implementada con esta clase y con buena nota

Las imágenes han sido descargadas del perfil de @diegorattaggi.

Pi, Montecarlo y Kotlin

Pi, Montecarlo y Kotlin

Hace unos dias, escribí un artículo sobre el método Montecarlo para calcular la probabilidad de la posición final de un robot en una línea. Luego me acordé del clásico para calcular una aproximación de PI lanzando dardos y al final pensé, ¿que tal se defenderá Kotlin con coroutines en este ambiente?. Bien

fun main (args: Array){

    val averages = mutableListOf()
    val time = measureTimeMillis {
        (0..100000).forEach { _ ->
            runBlocking{
                averages.add(calculate())
            }
        }
        println("PI= ${averages.average()}")
    }
    println("time: $time")
}

fun calculate(): Double{
    val successful = mutableListOf()
    (0..500).forEach { _ ->
        GlobalScope.run {  successful.add((Random.nextDouble().pow(2) + Random.nextDouble().pow(2)) k }.toDouble() / successful.count().toDouble()
}

la verdad que las coroutines van de maravilla, consumen poco y superrápidas.

Funciones estadísticas

Funciones estadísticas

Vamos a ver las funciones estadísticas de varianza, desviación típica y coefeciente de variación con Kotlin. Partiremos de una lista de elementos Double y crearemos extensiones de la lista para calcularlas.

Varianza. La varianza tiene la siguiente formula.

quicklatex.com-d5166eaa9614351e91ec76dec4fc3faf_l3

o lo que es lo mismo

quicklatex.com-220898e23d5d0c3236780d6397b187a2_l3

Equivale al cuadrado de la desviación típica

fun List.variance(): Double {
    val n = this.count()
    val average = this.average()
    return this.map { (it - average).pow(2.0) / n}.sum()
}

Así que si la la desviación al cuadro es la varianza, podemos obtener la desviación obteniendo la raiz de la varianza.

fun List<Double>.stdDeviation() = sqrt(this.variance())

Por último el coeficiente de variación que es igual a la relación entre la desviación típica y el promedio.

cv.png

fun List<Double>.coefficientOfVariation() = stdDeviation() / this.average()

Obtenermos una muestra aleatoria y con pocas líneas de código el resultado:

val list = (0..10).map { n-> Random.nextDouble(5.0,10.0) }
println(list)
println("Average: ${list.average()}")
println("Variance: ${list.variance()}")
println("Std Deviation: ${list.stdDeviation()}")

 

[5.1126146370135555, 7.961926277327813, 6.030297997339725, 7.346200593709344, 6.977298121605789, 6.480337764164781, 9.12926821809771, 9.830048028655337, 7.107841652359342, 7.047870562367113, 8.943727133742051]
Average: 7.451584635125688
Variance: 1.8100002521711398
Std Deviation: 1.3453624984260337
Coefficient: 0.18054716738828816

#PIDay2020

#PIDay2020

 

Calculadora de números complejos en Kotlin

Calculadora de números complejos en Kotlin
I kt
Siempre me ha gustado C#, quero recordar cuando apareció Linq y las funciones lambda, operador Elvis, inicializadores de propiedades automáticas, la magia asincrónica, etc.. Java añadió a su código novedades, la guerra de “mi lenguaje es mejor” y… de un lenguaje de una empresa que casi nadie conocía, se va haciendo hueco hasta que Google alabando su velocidad de compilación, facilidad y simplicidad, lo nombra lenguaje oficial de Android allá por el 2017. En 2018, me da por investigar Kotlin, porque no seré el primero que ha aprendido un lenguaje que luego no ha pasado de cuartos y según avanzaba con Kotlin, más y más me gustaba, de hecho cada día me asombra y descubro alguna bondad que me aporta.Bueno, ya que he halagado, alabado, agasajado, piropeado y adulado a Kotlin, retomo una calculadora de números complejos en este lenguaje ya que la tengo en este blog en C# y Java y se ha alineado las mates y este lenguaje, así que no hay más remedio (le tocará a la calculadora IP, a matrices, a…).

Lo mejor de esta, su simplicidad en tan poco tiempo, seguro que si le dedicas un poco de tiempo, se puede simplificar más, pero esto lo dejo para vosotros. He aquí el código de una calculadora de números complejos para consola o para lo que queráis con Kotlin.


class Complex (var x: Double = 0.0, var y: Double = 0.0, val isDegrees: Boolean = false){

    var module: Double = 0.toDouble()
    var grades: Double = 0.toDouble()

    init {
        this.module = Math.sqrt(Math.pow(x, 2.0) + Math.pow(x, 2.0))
        this.grades = Math.atan2(y, x)
    }

    operator fun plus(complex: Complex):Complex = plusComplex(complex)
    operator fun minus(complex: Complex):Complex = substractComplex(complex)
    operator fun times(complex: Complex):Complex = multiplyComplex(complex)
    operator fun div(complex: Complex):Complex = divideComplex(complex)

    fun toVectorialString(): String ="(${toNumber(this.x, 2)}, ${toNumber(this.y, 2)})"

    override fun toString(): String ="${toNumber(this.x, 2)} ${if (this.y < 0) "" else  "+"} ${toNumber(this.y, 2)}i"

    fun toPolarString(): String {
        val angle = if (isDegrees) this.grades * 180 / Math.PI else this.grades
        val angleToString =
            "${(if (isDegrees) toNumber(angle, 1) else toNumber(angle, 3))} ${if (isDegrees) 'º' else " radians"}"
        return "${toNumber(this.module, 1)} )  $angleToString"
    }

    fun conjugate(complex: Complex = this): Complex = Complex(complex.x, -complex.y)

    fun opposite(complex: Complex = this): Complex = Complex(-complex.x, -complex.y)

    fun reverse(complex: Complex = this): Complex {
        return Complex(complex.x / denominator(), -complex.y / denominator())
    }

    fun equals(complex: Complex?): Boolean =complex != null && this.javaClass == complex.javaClass && this.x == complex.x && this.y == complex.y

    private fun denominator(complex: Complex=this) = Math.pow(complex.x, 2.0) + Math.pow(complex.y, 2.0)

    private fun plusComplex(complex: Complex): Complex {
        return Complex(this.x + complex.x, this.y + complex.y)
    }

    private fun substractComplex(complex: Complex): Complex = Complex(this.x - complex.x, this.y - complex.y)

    private fun multiplyComplex(complex: Complex): Complex {
        return Complex(
            this.x * complex.x - this.y * complex.y,
            this.x * complex.y + this.y * complex.x
        )
    }

    private fun divideComplex(complex: Complex): Complex = divideComplex(this, complex)

    private fun divideComplex(complex1: Complex, complex2: Complex): Complex {
        val xx = (complex1.x * complex2.x + complex1.y * complex2.y) / (Math.pow(
            complex2.x,
            2.0
        ) + Math.pow(complex2.y, 2.0))
        val yy = (complex1.y * complex2.x - complex1.x * complex2.y) / (Math.pow(
            complex2.x,
            2.0
        ) + Math.pow(complex2.y, 2.0))
        return Complex(xx, yy)
    }

    companion object {

        fun convertToBinomial(module: Double, argument: Double):Complex = convertPolarToBinomial(module, argument)

        fun convertPolarToBinomial(module: Double, argument: Double): Complex = Complex(abs(module) * cos(argument), -abs(module) * sin(argument))

        fun toNumber(number: Double, digits: Int): String {
            val fn = NumberFormat.getNumberInstance()
            fn.maximumFractionDigits = digits
            return fn.format(number)
        }
    }
}


y el resultado


fun main(args:Array){
    val c1 = Complex(3.0,4.0)
    val c2 = Complex(5.0,6.0)

    println(c1.toString())


    println(c2.toString())
    println(c1+c2)
    println(c1-c2)
    println(c1*c2)
    println(c1/c2)
    println(c1.reverse())
    println(c1.conjugate())

}

3 + 4i
5 + 6i
8 + 10i
-2  -2i
-9 + 38i
0,64 + 0,03i
0,12  -0,16i
3  -4i

PD: Kotlin es el lenguaje oficial de Android, pero también permite desarrollar aplicaciones de consola, de escritorio, WEB, etc., es multiplataforma, ya que corre bajo la JVM y puede ser compilado a JavaScript.

Señores de WordPress, ¿Cuando podré publicar lenguaje Kotlin en su editor?

Dead XOR Alive

Dead XOR Alive

En uno de mis blogs, en Arithmos, publiqué un post sobre una historia de carceleros y presos; minutos después de acabar el artículo, dije, ¿por qué no hago una app que lo muestre?, dicho y hecho, me puse y en una tarde desarrollada estaba.

Y ¿por qué digo esto? para demostrar lo fácil que es desarrollar una pequeña aplicación con C# y WPF.

Si leen el artículo, podrán observar que la aplicación solo muestra un tablero de ajedrez, con monedas en cada casilla con una cara o una cruz aleatoriamente, un cuadro mágico que es el elegido por el carcelero y un cuadro del tablero que debe calcular uno de los presos para que el siguiente convicto les salve de la muerte, este último cuadro no es otro que una operación XOR.

El modelo podría ser una clase Chessboard que alberga objetos del tipo CoinBox, las monedas que ya de camino le diremos que color tiene el cuadro donde se apoyan en el tablero.

    public class Chessboard
    {
        public List CoinsBox { get; set; }

        public Chessboard() : this(-1) { }

        public Chessboard(int headsCount)
        {
            CoinsBox = new List();
            FillChessboard(headsCount);
        }

        ///
        /// Rellena el tablero con cuadros y monedas aleaotorias con cara y cruz
        /// 

        /// Número de caras. si es -1, se genera aletoriamente
        void FillChessboard(int headsCount)
        {
            var random = new Random();

            headsCount = headsCount == -1 ? random.Next(64) : headsCount;

            // Llenar Lista con monedas con cruz
            Enumerable.Range(0, 64).ToList()
            .ForEach(n => CoinsBox.Add(new CoinBox(n, false, (n / 8) % 2 == 0 ? n % 2 == 0 : n % 2 != 0)));

            // Cambiar n monedas a cara
            Enumerable.Range(0, headsCount).ToList().ForEach(n => CoinsBox[random.Next(64)].IsHeads = true);

            // Cuadro mágico
            CoinsBox[random.Next(64)].IsMagicBox = true;

            // Cuadro que debe cambiar
            var changed= CoinsBox
                .Where(n => n.IsHeads).Aggregate(MagicBox.Index, (acum, n) => acum ^ n.Index, op => op);
            CoinsBox[changed].IsChangedBox = true;

        }

        public CoinBox MagicBox => CoinsBox.Where(n => n.IsMagicBox).FirstOrDefault();
        public CoinBox ChangedBox => CoinsBox.Where(n => n.IsChangedBox).FirstOrDefault();
        public int ParityChessboard => CoinsBox
                .Where(n => n.IsHeads).Aggregate(0, (acum, n) => acum ^ n.Index, op => op);

        public string ParityChessboardToString => $"La paridad del tablero es {ParityChessboard}";
        public string ResultToString => $"Si cambiamos la moneda {ChangedBox.Index}, la paridad del tablero será {MagicBox.Index} que es el cuadrado mágico!!!";
        public string MagicBoxToString => $"El cuadro mágico seleccionado por el carcelero es el número {MagicBox.Index}";
        public string ChangeBoxToString => $"La moneda que debe cambiar el convicto es la número {ChangedBox.Index}";
        public string ListaXORToString => $"La operación XOR de las monedas que tienen cara {string.Join(", ", CoinsBox.Where(k => k.IsHeads).Select(i => i.Index))} y el cuadro mágico {MagicBox.Index} da como resultado {ChangedBox.Index} o la operación XOR entre el cuadro mágico {MagicBox.Index} y la paridad del tablero {ParityChessboard} es {ChangedBox.Index}";
    }

    public class CoinBox
    {

        public CoinBox(int index, bool isHeads, bool isBlack)
        {
            Index = index;
            IsHeads = isHeads;
            IsBlack = isBlack;
        }

        public int Index { get; set; }

        public bool IsHeads { get; set; }

        public bool IsTails { get { return !IsHeads; } }

        public bool IsChangedBox { get; set; }

        public bool IsMagicBox { get; set; }

        public bool IsBlack { get; set; }
    }

Como algo particular, la asignación del color del cuadro mediante la operación (n / 8) % 2 == 0 ? n % 2 == 0 : n % 2 != 0) con la que con el índice del cuadro le decimos si el cuadro es negro o blanco o las expresiones lambda que calculan la operación XOR sobre una lista de elementos mediante la función lambda Aggregate, la cual le pasamos un parámetro acumulador inicial y posteriormente es usado elemento a elemento con la operación XOR.Para la vista, he creado un control definido por el usuario llamado Box, el cual contiene el Binding cambiando su aspecto según las propiedades del objeto CoinBox asociado a su Datacontext. Como podéis ver a continuación, creo converter para transformar valores booleanos en Visibility, Brush o Bitmap. (Si alguien los quiere los converter, los cuelgo)

<UserControl x:Class="DxorAlive.Box"
             xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
             xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
             xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
             xmlns:d="http://schemas.microsoft.com/expression/blend/2008" 
             xmlns:local="clr-namespace:DxorAlive"
             mc:Ignorable="d" 
             d:DesignHeight="43" d:DesignWidth="43" Margin="1">
    <UserControl.Resources>
        <local:BoolToVisibleConverter x:Key="b2tvc" Reverse="False"/>
        <local:ImageConverter x:Key="itc"/>
        <local:BoolToColorConverter x:Key="btcc"/>
    </UserControl.Resources>
    <Grid>

        <Rectangle Width="64" Height="64" Stroke="Gray" StrokeThickness="1" Fill="{Binding IsBlack, Converter={StaticResource btcc}}"/>
        <Rectangle Width="62" Height="62" Stroke="Red" StrokeThickness="2" Visibility="{Binding IsMagicBox, Converter={StaticResource b2tvc}}"/>
        <Rectangle Width="60" Height="60" Stroke="Orange" StrokeThickness="2" Visibility="{Binding IsChangedBox, Converter={StaticResource b2tvc}}"/>
        <Image Source="{Binding IsHeads, Converter={StaticResource itc}}" Height="48"/>
    </Grid>
</UserControl>

Ahora solo nos queda crear o con xml o desde la clase de la vista (runtime) una matriz de objetos cada uno con su datacontext. Yo lo he he desarrollado con código en vez de crear 64 cuadros del tipo Box. Llamamos al método FillChessboard y se genera un nuevo tablero.

        private void FillChessboard(int headsCount)
        {
            grid.Children.Clear();
            // Crear tablero
            var cb = new Chessboard(headsCount);

            //crear cuadros y monedas
            cb.CoinsBox.ForEach(n =>
            {
                var c = new Box();
                c.DataContext = n;
                var row = n.Index / 8;
                var col = n.Index % 8;
                Grid.SetRow(c, row);
                Grid.SetColumn(c, col+1);
                grid.Children.Add(c);
            });

            this.DataContext = cb;

        }

he aquí el resultado. Un saludo a tod@s

deadxoralive1.png
Os dejo el enlace del ejecutable

PD: Y como llevo una temporada enamorado de Kotlin, os paso código en este lenguaje para una app de consola. I ♥ kt

 
import kotlin.random.Random

fun main(args: Array) {
    val c= Chessboard(5)
    println(c)

}


class Chessboard(var headsCount: Int) {
    val coinsBox = mutableListOf()

    init {
        headsCount = if (headsCount == -1) Random.nextInt(64) else headsCount
        fillChessboard()
    }

    private fun fillChessboard() {
        // Rellenar de monedas
        (0..63).toList().forEach {
            coinsBox.add(CoinBox(it, false, if ((it / 8) % 2 == 0) (it % 2 == 0) else (it % 2 != 0)))
        }
        // Caras
        (0..headsCount!!).toList().forEach { coinsBox[Random.nextInt(64)].isHeads = true }
        // cuadro mágico
        val vMB = Random.nextInt(64)
        coinsBox[vMB].isMagicBox = true
        // moneda cambiante
        coinsBox[coinsBox.filter { i-> i.isHeads }.fold(vMB) { acc, opXOR -> acc.xor(opXOR.index) }].isChangedBox=true

    }

    override fun toString(): String {
        return "$magic\n$parityToString\n$changed\n$result\n$listaXOR\n$chessboard"
    }

    val magicBox = coinsBox.filter { n -> n.isMagicBox }.firstOrNull()
    val changedBox = coinsBox.filter { n -> n.isChangedBox }.firstOrNull()
    val parityChessBoard = coinsBox[coinsBox.filter { i-> i.isHeads }.fold(0) { acc, opXOR -> acc.xor(opXOR.index) }]

    val parityToString= "La paridad del tablero es ${parityChessBoard.index}"
    val result = "Si cambiamos la moneda ${changedBox?.index}, la paridad del tablero será ${magicBox?.index} que es el cuadrado mágico"
    val magic = "El cuadro seleccionado por el carcelero es el número ${magicBox?.index}"
    val changed = "La moneda que debe cambiar el convicto es la número ${changedBox?.index}"
    val listaXOR = "La operación XOR de las monedas que tienen cara ${coinsBox.filter { k-> k.isHeads }.joinToString(", "){it.index.toString()}} " +
            "y el cuadro mágico ${magicBox?.index} da como resultado ${changedBox?.index} " +
            "\no la operación XOR entre el cuadro mágico ${magicBox?.index} y la paridad del tablero ${parityChessBoard.index} es ${changedBox?.index}"
    val chessboard = coinsBox.joinToString("") {k-> "\t${k.index} ${if (k.isHeads) "H" else "T"} ${if ((k.index+1) % 8==0) "\n" else ""}"  }

}


data class CoinBox(
    val index: Int,
    var isHeads: Boolean,
    var isBlack: Boolean,
    var isChangedBox: Boolean = false,
    var isMagicBox: Boolean = false