Code Kata: parchís

Con el code kata de esta semana intentaremos mejorar nuestras dotes de modelado orientado a objetos y diseño.

Imagen de Santi Oliveri

Nuestro objetivo será modelar utilizando el paradigma orientado a objetos (o alguna aproximación si se utilizan otros paradigmas) para modelar el juego del parchís. Este juego de orígenes lejanos y orientales ha dado lugar muchísimas variantes (parchisi, ludo, por parejas) y la idiosincracia española ha contribuido a crear variantes por nuestra tendencia a inventarnos normas ad-hoc favorables a nuestra causa. Para evitar discusiones a continuación se incluye el parchís normalizado para exlabos (release candidade 1). Proximamente se enviará al W3C para su estandarización.

Parchis para exlabos RC1

Definiciones previas:

Jugador

Cada uno de los participantes. En una partida existen de 2 a cuatro y cada uno de ellos utiliza un color direfente

Color

Hay cuatro colores, por orden: amarillo, azul, rojo y verde

Ficha

Cada jugador tiene 4 fichas de su color ocupando alguna casilla.

Casilla

Cada uno de los lugares en los que pueden estar las fichas en el tablero. Hay 68 casillas comunes y 8 en la escalera de cada jugador (recta final coloreada). Las casillas tienen una capacidad máxima de, en general 2 fichas. Aunque parezca obvio, de la 68 se pasa a la 1.

Casa

Posición inicial de las fichas que no están en juego para cada jugador, lo que viene siendo el limbo. Capacidad: 4 fichas.

Escalera

Las últimas ocho casillas del camino exclusivas para cada jugador.

Seguro

Casillas especiales en las que no se capturan fichas. Hay 12: 5, 12, 17, 22, 29, 39, 46, 51, 58, 63, 68.

Salida

Seguro con el color de un jugador y punto de entrada de sus fichas desde su casa al ponerse en juego con un 5.

Meta

Última casilla de cada escalera. Capacidad: 4 fichas.

Puente

Dos fichas del mismo color en la misma casilla. Impiden el paso a cualquier ficha. (Tomad esto literalmente.)

Captura

Cuando se mueve una ficha a una casilla ya ocupada por una ficha de otro jugador esta es capturada. La ficha vuelve a su casa y el jugador cuenta 20 (si procede)

Turno

Lo que viene siendo un turno, avanzando en sentido anti-horario

Movimiento

Trasladar cualquier ficha que no esté ni en casa ni en la meta hasta el número de casillas por delante que se esté contando si la casilla de destino no está llena y no hay que atravesar puentes.

También se considera mover una ficha desde casa a la salida cuando se tiene una tirada de 5.

Inicio del juego. Al comenzar, cada jugador tendrá cuatro fichas en su casa. El que saque una tirada preliminar mayor disfrutará del primer turno. En caso de empate se vuelve a tirar.

Turno de un jugador.

Se tira el dado, si se saca...

• 5. Si quedan fichas en casa y la salida no está llena, se pone en juego una ficha. Si no, se mueve contándose 5 y en siguiente turno será para el siguiente jugador (amarillo -> azul -> rojo -> azul -> amarillo -> ... imaginad el ciclo del rey león).
• 6.
  • Primer y segundo turnos consecutivos. Contarse 6 (7 si no quedan fichas en casa) y el siguiente turno será del mismo jugador.
  • Tercer turno consecutivo. La última ficha movida vuelve a la casa a no ser que se encuentre en la escalera y termina el turno.
• Resto de tiradas. Se cuentan las casillas correspondientes a la tirada.

Mover una ficha. Si se está contando 6 o 7 y alguno de los movimientos posibles (ver definición) puede romper un puente se debe romper un puente (nobleza obliga). En otro caso se elige cualquier movimiento posible o no se mueve si no existe ninguno.

Si existe captura, se vuelve a mover una ficha, contándose 20 esta vez.

Si se alcanza la meta, se vuelve a mover una ficha, contándose 10.

Fin del juego. Si todas las fichas de un jugador llegan a su meta ha ganado y finaliza la partida. En teoría se podría continuar hasta que ganasen n-1 jugadores, pero no tiene ningún interes.

Parchis Kata

El objetivo es modelar el juego descrito en las normas anteriores pero no de cualquier forma. Es necesario:

• Poder representar mediante un objeto cada estado del juego. No es necesario representar la tirada inicial que decide que jugador comienza.
• La interfaz debe ser lo más natural y sucinta posible. Debe ser posible recuperar la información necesaria para representar el estado del juego y también para ejecutar los movimientos de los jugadores.
• En concreto, se debe prestar especial atención a las diferentes acciones que un jugador pueda elegir. Se tienen que poder listar como objetos antes de decidirse por uno de ellos.

El kata se puede ejercitar hasta diferentes niveles de detalle:

• Representación inicial mediante UML o cajitas en una servilleta
• Interfaces concretas para los diferentes objetos
• Implementación de los métodos (y sus pruebas de unidad para comprobar que se cumplen las normas)

Esto es todo por el momento, disfrutad!

Cuatro cuatros code kata: show me the code!

El viernes pasado hubo un éxito en cuanto a seguimiento del code kata con gente implementando el problema en Java, Python, JavaScript y Haskell. Sin embargo, la mayoría se quedó en el punto 5, con la búsqueda de expresiones para un determinado valor.

Muchos os estaréis preguntando cómo se puede resolver ese punto (show me the money, esto, the code!). Los impacientes pueden descargar mi solución en Java.

Los primeros puntos se resuelven creando una pequeña jerarquía de clases o una interfaz y dos clases que la implementen:

• Clase abstracta/interfaz Exp. Declara los métodos getValue(), count4() y, puede servir más adelante para incluir el método estático findExp.

  public abstract class Exp {
  
      public abstract int getValue() throws ValueError;
  
      public abstract int count4();
  
      protected abstract String toString(int priority);
  
  
      public static Exp findExp(int target) {
          ...
      }
  }
  

• Clase Num. Muy simple, basta con contar los dígitos y almacenar un entero.

  public class Num extends Exp {
  
      public Num(int num) {
          assert all4(num);
          this.num = num;
      }
  
      @Override
      public int getValue() {
          return this.num;
      }
  
      @Override
      public String toString() {
          return Integer.toString(this.num);
      }
  
      @Override
      public int count4() {
          return Integer.toString(num).length();
      }
  
      public static boolean all4(int num) {
          while (num > 10) {
              int lastDigit = num % 10;
              if (lastDigit != 4) {
                  return false;
              }
  
              num = num / 10;
          }
  
          return num == 4;
      }
  
      private final int num;
  
      @Override
      protected String toString(int priority) {
          return this.toString();
      }
  }
  

• Clase Op. Se basa en tres atributos, un caracter para determinar el operador concreto y dos enlaces a las sub-expresiones (left y right). Para los operadores unarios se utiliza sólo uno de los enlaces.

  import java.util.HashMap;
  import java.util.Map;
  
  /**
   *
   * @author sortega
   */
  public class Op extends Exp {
  
      public Op(char operator, Exp left, Exp right) {
          assert left != null;
          assert right != null;
          assert "+-*/".contains("" + operator);
          this.left = left;
          this.right = right;
          this.op = operator;
      }
  
      public Op(char operator, Exp child) {
          assert child != null;
          assert "!V".contains("" + operator);
          this.left = child;
          this.right = null;
          this.op = operator;
      }
  
      @Override
      public int getValue() {
          int leftValue = this.left.getValue();
  
          if (this.isBinary()) {
              int rightValue = this.right.getValue();
  
              switch (this.op) {
                  case '+':
                      return leftValue + rightValue;
  
                  case '-':
                      return leftValue - rightValue;
  
                  case '*':
                      return leftValue * rightValue;
  
                  case '/':
                      if (leftValue % rightValue != 0) {
                          throw new ValueError();
                      }
                      return leftValue / rightValue;
  
                  default:
                      throw new IllegalStateException();
              }
              
          } else {
              switch (this.op) {
                  case '!':
                      return fact(leftValue);
  
                  case 'V':
                      int square = (int) Math.sqrt(leftValue);
                      if (square * square == leftValue) {
                          return square;
                      } else {
                          throw new ValueError();
                      }
  
                  default:
                      throw new IllegalStateException();
              }
          }
      }
  
      @Override
      public String toString() {
          if (this.isBinary()) {
              return this.left.toString(this.getOpPriority()) + this.op +
                  this.right.toString(this.getOpPriority());
          } else {
              String operand = this.left.toString(this.getOpPriority());
              switch (this.op) {
                  case '!':
                      return operand + '!';
  
                  case 'V':
                      return 'V' + operand;
  
                  default:
                      throw new IllegalStateException();
              }
          }
      }
  
      @Override
      public int count4() {
          return this.left.count4() +
                  (this.isBinary() ? this.right.count4() : 0);
      }
  
      private static final Map OPERATOR_PRIORITIES =
              new HashMap() {{
                  put('!', 1); put('V', 1);
                  put('*', 2); put('/', 2);
                  put('+', 3); put('-', 3);
              }};
      
      private final char op;
      private final Exp left;
      private final Exp right;
  
  
      private int fact(int n) {
          int fact = 1;
          for (int i = 0; i < n; i++) {
              fact *= n;
          }
          return fact;
      }
  
      private boolean isBinary() {
          return this.right != null;
      }
  
      private int getOpPriority() {
          return OPERATOR_PRIORITIES.get(this.op);
      }
  
      @Override
      protected String toString(int priority) {
          if (this.getOpPriority() > priority) {
              return "(" + this.toString() + ")";
          } else {
              return this.toString();
          }
      }
  }
  

En cuanto al método findExp, lo primero que debe venirnos a la mente es el backtracking como forma de construir el árbol con la expresión deseada. Sin embargo, cuanto más inteligente sea la forma de generar los nodos que se prueban, más eficiente será el proceso. En la solución propuesta se realiza de la siguiente forma (pseudocódigo):

• Buscar expresión para el número N -> Buscar expresión para el número N con 4 cuatros.
• Buscar expresión para un número N con R cuatros
• Es N igual a R cuatros? -> Devolver new Num(N)
• Por cada número concebible usando de 1 a R cuatros
• Por cada operador binario. Es posible encontrar una expresión (llamada recursiva con N y R - los cuatros usados) resultante de aplicar el operador inverso? En cristiano, si es posible encontrar N - operando entonces devolver new Op('+', operando, sub-expresión encontrada)
• Hacer algo parecido con los operadores unarios

Si tienes una solución mejor o una explicación inteligible de este método, mándala y actualizamos el post. Mientras tanto, podemos usar el código para aclarar esta explicación:

public static Exp findExp(int target) {
        return findExp(4, target);
    }


    private static Exp findExp(int rem4, int target) {
        Exp result;

        result = findNum(rem4, target);
        if (result != null) {
            return result;
        }

        int operand = 0;
        for (int i = 1; i <= rem4; i++) {
            operand = 10 * operand + 4;

            // Unary operators
            if (rem4 == i) {
                result = new Op('!', new Num(operand));
                if (result.getValue() == target) {
                    return result;
                }

                result = new Op('V', new Num(operand));
                try {
                    if (result.getValue() == target) {
                        return result;
                    }
                } catch (ValueError ex) {
                }
            }

            // Binary operators

            int rightTarget, leftTarget;
            Exp rightExp, leftExp;

            rightTarget = target - operand;
            rightExp = findExp(rem4 - i, rightTarget);
            if (rightExp != null) {
                return new Op('+', new Num(operand), rightExp);
            }

            rightTarget = operand - target;
            rightExp = findExp(rem4 - i, rightTarget);
            if (rightExp != null) {
                return new Op('-', new Num(operand), rightExp);
            }
            leftTarget = target + operand;
            leftExp = findExp(rem4 - i, leftTarget);
            if (rightExp != null) {
                return new Op('-', leftExp, new Num(operand));
            }

            if (target % operand == 0) {
                rightTarget = target / operand;
                rightExp = findExp(rem4 - i, rightTarget);
                if (rightExp != null) {
                    return new Op('*', new Num(operand), rightExp);
                }
            }

            if (target != 0 && operand % target == 0) {
                rightTarget = operand / target;
                rightExp = findExp(rem4 - i, rightTarget);
                if (rightExp != null) {
                    return new Op('/', new Num(operand), rightExp);
                }
            }
            leftTarget = target * operand;
            leftExp = findExp(rem4 - i, leftTarget);
            if (rightExp != null) {
                return new Op('/', leftExp, new Num(operand));
            }

        }

        return null;
    }

    private static Num findNum(int rem4, int target) {
        if (Num.all4(target)) {
            Num num = new Num(target);
            if (num.count4() == rem4) {
                return num;
            }
        }
        return null;
    }

Seguid esforzándoos!

Cuatro cuatros code kata

De vez en cuando propondremos un code kata, esperamos que los viernes. Se trata de utilizar el lenguaje de programación preferido y practicar.

El de hoy ha sido inspirado por un post de kriptópolis sobre el juego del cuatro:

¿Es posible expresar todos los dígitos del 1 al 20 utilizando cuatro cuatros y operadores matemáticos sencillos (suma, resta, producto, cociente, paréntesis y raíz cuadrada)? Sí... a excepción del 19, que requiere además el punto decimal y/o el signo factorial (!). De hecho, añadiendo estos dos operadores y otro que indique infinitas cifras periódicas (p. ej: ´.4 = 0.4444...) es posible llegar al 112.

La idea, retocada para nuestro propósito consiste en utilizar sólo aritmética entera (no vamos a contemplar números reales ni racionales) y buscar expresiones que contengan exactamente cuatro dígitos 4 y un número arbitrario de operadores +, -, *, / y paréntesis.

De esta forma, una expresión válida para el conseguir el número 8 es "4+4+4-4", y "44-4*4" o "44-(4*4)" para conseguir 28.

Cuatro cuatros kata

1. Construir expresiones. Se tiene que poder crear expresiones de forma sencilla, ejemplo en Java para "(44-(4*4))".

   Exp exp = new Op('-', new Num(44), new Op('*', new Num(4), new Num(4)));
   

2. Imprimir expresiones. Se tiene que poder imprimir las expresiones de forma inteligible.

   assertEquals("(44-(4*4)", exp.toString());
   

3. Comprobar el número de cuatros.

   assertEquals(4, exp.count4());
   

4. Calcular el valor de la expresión con un método getValue. La división debe ser entera 5 / 4 dará una excepción (por ejemplo ValueError)
5. Buscar una expresión para un número dado, por ejemplo el 28.

   Exp exp = Exp.findExpression(28);
   assertEquals(4, exp.count4());
   assertEquals(28, exp.getValue());
   

6. Hacerse un método que busque expresiones para los números del -256 al 256 y cuente las expresiones encontradas (y las encontradas pero que no cumplan las condiciones ;). ¿Cuántas soluciones encuentras?
7. Repetir añadiendo el operador raíz cuadrada (también entera, vale para 4, pero no para -4 ni para 8) y factorial. Los símbolos serán ! y V.

   Exp exp = new Op('!', new Op('V', new Num(4)));
   assertEquals("!(V(4))", exp.toString());
   assertEquals(2, exp.getValue());
   

   ¿Cuántas expresiones más encuentras? ¿Cuánto tiempo tarda?
8. Para nota, encontrar las expresiones con el menor número de operadores...

Esto es todo, espero que os guste y ver soluciones ingeniosas

Porra: Cuándo nos intervienen los alemanes?

Tras la noticia sobre la intervención de Grecia, todos nos preguntamos cual es el siguiente cerdo al que le va a llegar el San Martín (PIGS: Portugal, Italy, Greece, and last but not least, Spain).

Convocamos a los labos y exlabos y otros especímenes a opinar en esta porra-encuesta sin ánimo de lucro.

Grecia ya ha caído, seguramente seamos los siguientes. ¿Conseguirá Zapatero presidir la institución que intervenga su propio país? Todo es posible.

No se vosotros, pero de momento nadie propone que terminemos el año con honor.

Un saludo

URL Extender

Yo no se a vosotros, pero a mí las URLs me gustan largas. El caso es que necesitábamos extender una URL añadiendo elementos al path de la misma en Python y resulta ser muy fácil gracias al módulo urlparse:

def url_extend(url, extra_path_parts):
     (scheme, netloc, path, params, query, fragment) = urlparse(url)
     path = '/'.join(path.split('/') + extra_path_parts) + ('/')
     return urlunparse([scheme, netloc, path, params, query, fragment])

Un ejemplo de uso:

print url_extend('http://exlabos.blogspot.com/exto/si?hola=true', ['extra', 'path'])
>> 'http://exlabos.blogspot.com/exto/si/extra/path/?hola=true'

BTW, un saludo a todos los labos y exlabos.

It Works!

Hola a todos, Este es un mensaje para advertiros a todos de que hay un proyecto en marcha mediante el cual se pretende contar las vivencias y andaduras de los miembros (y ya no tan miembros) del labo. En este blog se pretende explicar cualquier cosa que nos suceda y qué consideremos al menos interesante y qué creamos que debería saber todo el mundo. De este modo trataremos de evitar situaciones como: "Te acuerdas de... eh! que a mi no me habéis contado eso!" o las típicas situaciones de "No he encontrado una solución para mi problema" o como cuando encuentras a alguien que tiene el mismo problema pero lo soluciona sin contarlo.

No perderé la oportunidad de decir que esto será algo parecido a un "ceiling-cat" y para quien quiera uno en casa tan solo tiene que coger está plantilla de papel y fabricarse el suyo propio.

Un saludo a todos o como dirían mis compañeros, think that you!