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!