Data structure - arithmetic expressions

Question

I recently received the following challenge in college, but I’m having a hard time

The challenge is:

Identify how a subset of numbers from 1 to 1000 can be written using arithmetic expressions that have only the following elements:

5, 7, (, ), +, - and *.

For example, below are represented the expressions for the numbers from 30 to 35. It is important to note that the expressions should be as short as possible, because it would be too simple to find only the expression equivalent to 1 and then sum it as many times as necessary to obtain a number. The number of parentheses should also be as small as possible. The complication degree of a number is the amount of times 5 and 7 should be used in the expression that corresponds to the number. Thus, 30 has the degree of complication 3, and 31 has the degree of complication 5. Expressions should be mounted with the minimum degree of complication possible.

Examples:

30 = 5 * 7 - 5
31 = 7 - ( 5 * 5 ) + 7 * 7
32 = 7 + 5 * 5
33 = 5 * 7 + 5 - 7
34 = 7 + 5 * 5 - ( 5 - 7 )
35 = 5 * 7

So far I’m trying this way, but I can not reach the result I hope, is not generating error, but the output result is far from what asks the exercise

package ex5e7;

//import static java.lang.Math.pow;
import javax.swing.JOptionPane;

public class Expressoes {

    String[] expressoes = new String[1000];
    boolean[] preenchidos = new boolean[1000];

    public void preenchidos(boolean preencher) {
        if (preencher) {
            for (int i = 0; i < 1000; i++) {
                preenchidos[i] = false;
            }
        } else {
            String pre = "";
            for (int i = 0; i < 1000; i++) {
                if (preenchidos[i]) {
                    pre += i + "\n";
                }
            }
            JOptionPane.showMessageDialog(null, pre);
        }
    }

    public void multiplos() {
        int resultado = 5;
        boolean mil = false;
        expressoes[resultado] = "5 = 5";
        preenchidos[resultado] = true;
        while (!mil) {
            resultado *= 5;
            if (resultado <= 1000) {
                expressoes[resultado] = resultado + " = " + expressoes[resultado / 5].substring(expressoes[resultado / 5].indexOf("=") + 2) + "*5";
                preenchidos[resultado] = true;
            } else {
                mil = true;
            }
        }
        resultado = 7;
        mil = false;
        expressoes[resultado] = "7 = 7";
        preenchidos[resultado] = true;
        while (!mil) {
            resultado *= 7;
            if (resultado <= 1000) {
                expressoes[resultado] = resultado + " = " + expressoes[resultado / 7].substring(expressoes[resultado / 7].indexOf("=") + 2) + "*7";
                preenchidos[resultado] = true;
            } else {
                mil = true;
            }
        }
    }

    public void somas() {
        int resultado = 10;
        boolean mil = false;
        expressoes[resultado] = "10 = 5+5";
        preenchidos[resultado] = true;
        /*while (!mil) {
            resultado += 5;
            if (resultado <= 1000) {
                expressoes[resultado] = resultado + " = " + expressoes[resultado - 5].substring(expressoes[resultado - 5].indexOf("=") + 2) + "+5";
                preenchidos[resultado] = true;
            } else {
                mil = true;
            }
        }*/
    }

    public void mulCincoSete() {
        boolean mil = false;
        int n1 = 125, n2 = 7;
        expressoes[n1 * n2] = "875 = 7*5*5*5";
        preenchidos[n1 * n2] = true;
        while (!mil) {            
            for (int i = n1 - 1; i > 0; i--) {
                if (preenchidos[i]) {
                    n1 = Integer.parseInt(expressoes[i].substring(0, expressoes[i].indexOf("=") - 1));
                }
            }
            if (n1 * n2 <= 1000) {

            } else {
                mil = true;
            }
        }
    }

    /*public int[] multiplos(int num, int tamanho) {
        int[] multiplos = new int[tamanho];
        for (int i = 0; i < tamanho; i++) {
            multiplos[i] = num * tamanho;
        }
        return multiplos;
    }

    public int[] soma(int tamanho) {
        int[] resultados = new int[(int) pow(2, tamanho)];
        int[] num = {5, 7};
        int k = 0;
        for (int i = 0; i < pow(2, tamanho); i++) {
            resultados[i] = 0;
        }
        for (int i = 0; i < pow(2, tamanho); i++) {
            for (int j = 0; j <= 1; j++) {
                resultados[i] += num[j];
            }
        }
        return resultados;
    }*/
}

Answer 1

I did it. The result is a monstrous thing.

The code below is divided into several parts:

• Lexical analysis - Divides a numerical expression into a sequence of tokens. A token may be either a number consisting of a sequence of 5s and 7s or one of the symbols +, -, *, /, ( or ).

• Syntactic trees - Represented by the functional interface Operacao and by the methods that return such a lot. Responsible for interpreting syntactically well-formed expressions. Can generate an error in case of division by zero or non-integer division.

• Parsing - Discover the structure of a given expression. Parsing is based on a context-free language and the analyser is recursive descendant LL-1 with the following grammar:

  • additive (initial symbol) multiplicative (cont_additive)*
  • cont_aditivo (+ | -) multiplicative
  • unary multiplicative (multiplicative counter)*
  • multiplicative count (* | /) unary
  • unary (+ | -) parentheses
  • parentheses ( additive ) | number

• String generation of random expressions - Converts a number to a string of symbols consisting of 5, 7, +, -, *, /, ( and ).

• Evaluation of the number of parentheses and the degree of complication of the strings.

• Expression optimizer - find the best expression that generates the desired number:

  • Searches for an increasing number of characters, starting at 1 and going up to 12 and generating by brute force all strings sequences with the symbols mentioned in the corresponding size. It only looks for a larger string if it has not found any smaller string that fits.

  • The strings that serve are those that can be compiled and interpreted without generating lexical, syntactic or interpretation errors and that the result of the evaluation is equal to the number sought.

  • When finding a string with a certain size, keep looking for a better one with the same size. If the new string has the same size and fewer parentheses than the previous one or has the same size and number of parentheses but less complication, test it when compiling and interpreting.

The program tries to optimize all numbers from 0 to 100. The statement says it is up to 1000, but as this business runs on the basis of brute force, then it takes him to finish and I had no bag to wait until he solve the 1000. Syntactic parser code could also be better and a little more organized, but that should be good enough.

Here’s the code:

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.LinkedHashMap;

/**
 * @author Victor Williams Stafusa da Silva
 */
public class Expressoes {

    private static class ExpressaoMalformadaException extends Exception {}

    private static class AvaliacaoExpressaoException extends Exception {}

    // Árvore sintática e interpretação:

    @FunctionalInterface
    private interface Operacao {
        public int calcular() throws AvaliacaoExpressaoException;
    }

    private static Operacao soma(Operacao a, Operacao b) {
        return () -> a.calcular() + b.calcular();
    }

    private static Operacao sub(Operacao a, Operacao b) {
        return () -> a.calcular() - b.calcular();
    }

    private static Operacao mult(Operacao a, Operacao b) {
        return () -> a.calcular() * b.calcular();
    }

    private static Operacao div(Operacao a, Operacao b) {
        return () -> {
            int ac = a.calcular();
            int bc = b.calcular();
            if (bc == 0 || ac % bc != 0) throw new AvaliacaoExpressaoException();
            return ac / bc;
        };
    }

    private static Operacao op(String simbolo, Operacao a, Operacao b) {
        switch (simbolo) {
            case "+": return soma(a, b);
            case "-": return sub(a, b);
            case "*": return mult(a, b);
            case "/": return div(a, b);
            default: throw new AssertionError();
        }
    }

    private static Operacao simples(int i) {
        return () -> i;
    }

    // Análise léxica:

    private static List<String> tokenize(String expressao)
            throws ExpressaoMalformadaException
    {
        List<String> tokens = new ArrayList<>(expressao.length());
        StringBuilder proximoToken = new StringBuilder(expressao.length());
        for (int i = 0; i < expressao.length(); i++) {
            char c = expressao.charAt(i);
            if ("()+-*/".indexOf(c) != -1) {
                if (proximoToken.length() != 0) {
                    tokens.add(proximoToken.toString());
                    proximoToken = new StringBuilder(expressao.length() - i);
                }
                tokens.add(String.valueOf(c));
            } else if ("57".indexOf(c) != -1) {
                proximoToken.append(c);
            } else {
                throw new ExpressaoMalformadaException();
            }
        }
        if (proximoToken.length() != 0) tokens.add(proximoToken.toString());
        return tokens;
    }

    // Análise sintática:

    private static class Subexpressao {
        private final Operacao op;
        private final List<String> resto;

        public Subexpressao(Operacao op, List<String> resto) {
            this.op = op;
            this.resto = resto;
        }
    }

    private static class Continuacao {
        private final String simbolo;
        private final Operacao op;
        private final List<String> resto;

        public Continuacao(String simbolo, Operacao op, List<String> resto) {
            this.simbolo = simbolo;
            this.op = op;
            this.resto = resto;
        }
    }

    private static class Simbolo {
        private final String op;
        private final List<String> resto;

        public Simbolo(String op, List<String> resto) {
            this.op = op;
            this.resto = resto;
        }
    }

    private static Subexpressao parseAditivo(List<String> tokens) {
        Subexpressao a = parseMultiplicativo(tokens);
        if (a == null) return null;

        List<String> resto = a.resto;
        List<Continuacao> outros = new ArrayList<>();
        while (true) {
            Continuacao proximo = parseContinuacaoAditivo(resto);
            if (proximo == null) break;
            outros.add(proximo);
            resto = proximo.resto;
        }

        for (Continuacao c : outros) {
            a = new Subexpressao(op(c.simbolo, a.op, c.op), c.resto);
        }
        return a;
    }

    private static Continuacao parseContinuacaoAditivo(List<String> tokens) {
        Simbolo sinal = parseTerminal("+", tokens);
        if (sinal == null) sinal = parseTerminal("-", tokens);
        if (sinal == null) return null;

        Subexpressao b = parseMultiplicativo(sinal.resto);
        if (b == null) return null;

        return new Continuacao(sinal.op, b.op, b.resto);
    }

    private static Subexpressao parseMultiplicativo(List<String> tokens) {
        Subexpressao a = parseUnario(tokens);
        if (a == null) return null;

        List<String> resto = a.resto;
        List<Continuacao> outros = new ArrayList<>();
        while (true) {
            Continuacao proximo = parseContinuacaoMultiplicativo(resto);
            if (proximo == null) break;
            outros.add(proximo);
            resto = proximo.resto;
        }

        for (Continuacao c : outros) {
            a = new Subexpressao(op(c.simbolo, a.op, c.op), c.resto);
        }
        return a;
    }

    private static Continuacao parseContinuacaoMultiplicativo(List<String> tokens) {
        Simbolo sinal = parseTerminal("*", tokens);
        if (sinal == null) sinal = parseTerminal("/", tokens);
        if (sinal == null) return null;

        Subexpressao b = parseUnario(sinal.resto);
        if (b == null) return null;

        return new Continuacao(sinal.op, b.op, b.resto);
    }

    private static Subexpressao parseUnario(List<String> tokens) {
        Simbolo sinal = parseTerminal("+", tokens);
        if (sinal == null) sinal = parseTerminal("-", tokens);
        if (sinal == null) return parseParenteses(tokens);

        Subexpressao v = parseParenteses(sinal.resto);
        if (v == null) return null;

        return new Subexpressao(op(sinal.op, simples(0), v.op), v.resto);
    }

    private static Subexpressao parseParenteses(List<String> tokens) {
        Simbolo abre = parseTerminal("(", tokens);
        if (abre == null) return parseNum(tokens);

        Subexpressao dentro = parseAditivo(abre.resto);
        if (dentro == null) return null;

        Simbolo fecha = parseTerminal(")", dentro.resto);
        if (fecha == null) return null;

        return new Subexpressao(dentro.op, fecha.resto);
    }

    private static Subexpressao parseNum(List<String> tokens) {
        if (tokens.isEmpty()) return null;
        String first = tokens.get(0);
        int t;
        try {
            t = Integer.parseInt(first);
        } catch (NumberFormatException e) {
            return null;
        }
        return new Subexpressao(simples(t), tokens.subList(1, tokens.size()));
    }

    private static Simbolo parseTerminal(String s, List<String> tokens) {
        if (tokens.isEmpty()) return null;
        String first = tokens.get(0);
        if (!s.equals(first)) return null;
        return new Simbolo(s, tokens.subList(1, tokens.size()));
    }

    private static Subexpressao analiseSintatica(List<String> tokens)
            throws ExpressaoMalformadaException
    {
        Subexpressao raiz = parseAditivo(tokens);
        if (raiz == null) throw new ExpressaoMalformadaException();
        if (!raiz.resto.isEmpty()) throw new ExpressaoMalformadaException();
        return raiz;
    }

    // Interpretador:

    private static int interpretar(String expressao)
            throws ExpressaoMalformadaException, AvaliacaoExpressaoException
    {
        return analiseSintatica(tokenize(expressao)).op.calcular();
    }

    // Gerador de expressões:

    private static final String SIMBOLOS = "57()+-*/";
    private static final int TAMANHO_SIMBOLOS = SIMBOLOS.length();

    private static String gerarExpressao(int chute, int tamanho) {
        char[] c = new char[tamanho];
        for (int i = 0; i < tamanho; i++) {
            int r = chute % TAMANHO_SIMBOLOS;
            c[i] = SIMBOLOS.charAt(r);
            chute /= TAMANHO_SIMBOLOS;
        }
        return new String(c);
    }

    private static int complicacao(String x) {
        int comp = 0;
        for (char c : x.toCharArray()) {
            if (c == '5' || c == '7') comp++;
        }
        return comp;
    }

    private static int contaPar(String x) {
        int comp = 0;
        for (char c : x.toCharArray()) {
            if (c == '(' || c == ')') comp++;
        }
        return comp;
    }

    private static int pow(int base, int expoente) {
        return expoente == 0 ? 1 : base * pow(base, expoente - 1);
    }

    // Otimizador de expressões:

    private static String acharMelhorString(int valor) {
        String melhor = "";
        int menosComplicado = 999999;
        int menosParenteses = 999999;
        int menor = melhor.length();
        for (int tamanho = 1; tamanho < 12; tamanho++) {
            boolean achou = false;
            int max = pow(TAMANHO_SIMBOLOS, tamanho);
            for (int i = 0; i < max; i++) {
                String g = gerarExpressao(i, tamanho);

                int par = contaPar(g);
                if (par > menosParenteses) continue;

                int complicado = complicacao(g);
                if (par == menosParenteses && complicado >= menosComplicado) continue;

                try {
                    if (valor == interpretar(g)) {
                        melhor = g;
                        menosComplicado = complicado;
                        menosParenteses = par;
                        System.out.println("Achei: " + valor + " = " + g);
                    }
                } catch (ExpressaoMalformadaException | AvaliacaoExpressaoException e) {
                    // Ignora e continua.
                }
            }
            if (!melhor.isEmpty()) return melhor;
        }
        return "";
    }

    private static Map<Integer, String> tabelar(int min, int max) {
        Map<Integer, String> tabela = new LinkedHashMap<>(max - min + 1);
        for (int i = min; i <= max; i++) {
            tabela.put(i, acharMelhorString(i));
        }
        return tabela;
    }

    public static void main(String[] args) {
        Map<Integer, String> tabela = tabelar(0, 100);
        for (Map.Entry<Integer,String> entry : tabela.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

The way out is like this:

Achei: 0 = 5-5
Achei: 1 = 5/5
Achei: 2 = 7-5
Achei: 3 = 5-7+5
Achei: 4 = 5-5/5
Achei: 5 = 5
Achei: 6 = 5/5+5
Achei: 7 = 7
Achei: 8 = 7+5/5
Achei: 9 = 7+7-5
Achei: 10 = 5+5
Achei: 11 = 55/5
Achei: 12 = 7+5
Achei: 13 = 75-7-55
Achei: 13 = 7+5/5+5
Achei: 14 = 7+7
Achei: 15 = 75/5
Achei: 16 = 55/5+5
Achei: 17 = 7+5+5
Achei: 18 = 75-57
Achei: 18 = 5*5-7
Achei: 19 = 7+7+5
Achei: 20 = 75-55
Achei: 20 = 5*5-5
Achei: 21 = 7+7+7
Achei: 22 = 77-55
Achei: 23 = 5-57+75
Achei: 23 = 5*5-7+5
Achei: 24 = 7+7+5+5
Achei: 25 = 5*5
Achei: 26 = 75-7*7
Achei: 27 = 7+75-55
Achei: 27 = 7+5*5-5
Achei: 28 = 7*5-7
Achei: 29 = 7+77-55
Achei: 30 = 5*5+5
Achei: 31 = 775/5/5
Achei: 32 = 7+5*5
Achei: 33 = 7*5-7+5
Achei: 34 = 7*5-5/5
Achei: 35 = 7*5
Achei: 36 = 5/5+7*5
Achei: 37 = 7+5*5+5
Achei: 38 = 55-7-5-5
Achei: 39 = 7*7-5-5
Achei: 40 = 7*5+5
Achei: 41 = 55-7-7
Achei: 42 = 7+7*5
Achei: 43 = 55-7-5
Achei: 44 = 7*7-5
Achei: 45 = 55-5-5
Achei: 46 = 57-55/5
Achei: 47 = 57-5-5
Achei: 48 = 55-7
Achei: 49 = 7*7
Achei: 50 = 55-5
Achei: 51 = 7*7+7-5
Achei: 52 = 57-5
Achei: 53 = 5-7+55
Achei: 54 = 7*7+5
Achei: 55 = 55
Achei: 56 = 7*7+7
Achei: 57 = 57
Achei: 58 = 57+5/5
Achei: 59 = 7+57-5
Achei: 60 = 5+55
Achei: 61 = 75-7-7
Achei: 62 = 7+55
Achei: 63 = 75-7-5
Achei: 64 = 7+57
Achei: 65 = 5+5+55
Achei: 66 = 55/5+55
Achei: 67 = 7+5+55
Achei: 68 = 75-7
Achei: 69 = 7+7+55
Achei: 70 = 75-5
Achei: 71 = 7+7+57
Achei: 72 = 77-5
Achei: 73 = 5-7+75
Achei: 74 = 75-5/5
Achei: 75 = 75
Achei: 76 = 5/5+75
Achei: 77 = 77
Achei: 78 = 77+5/5
Achei: 79 = 7+77-5
Achei: 80 = 5+75
Achei: 81 = 5/5+5+75
Achei: 82 = 7+75
Achei: 83 = 7*5-7+55
Achei: 84 = 7+77
Achei: 85 = 5+5+75
Achei: 86 = 55/5+75
Achei: 87 = 7+5+75
Achei: 88 = 77+55/5
Achei: 89 = 7+7+75
Achei: 90 = 7*5+55
Achei: 91 = 7+7+77
Achei: 92 = 57+7*5
Achei: 93 = 75-57+75
Achei: 93 = 5*5-7+75
Achei: 94 = 7+7+5+75
Achei: 95 = 7*5+5+55
Achei: 96 = 755/5-55
Achei: 96 = 7+7+7+75
Achei: 97 = 7+7*5+55
Achei: 98 = 7*7+7*7
Achei: 99 = 7*7-5+55
Achei: 100 = 5*5+75
0: 5-5
1: 5/5
2: 7-5
3: 5-7+5
4: 5-5/5
5: 5
6: 5/5+5
7: 7
8: 7+5/5
9: 7+7-5
10: 5+5
11: 55/5
12: 7+5
13: 7+5/5+5
14: 7+7
15: 75/5
16: 55/5+5
17: 7+5+5
18: 5*5-7
19: 7+7+5
20: 5*5-5
21: 7+7+7
22: 77-55
23: 5*5-7+5
24: 7+7+5+5
25: 5*5
26: 75-7*7
27: 7+5*5-5
28: 7*5-7
29: 7+77-55
30: 5*5+5
31: 775/5/5
32: 7+5*5
33: 7*5-7+5
34: 7*5-5/5
35: 7*5
36: 5/5+7*5
37: 7+5*5+5
38: 55-7-5-5
39: 7*7-5-5
40: 7*5+5
41: 55-7-7
42: 7+7*5
43: 55-7-5
44: 7*7-5
45: 55-5-5
46: 57-55/5
47: 57-5-5
48: 55-7
49: 7*7
50: 55-5
51: 7*7+7-5
52: 57-5
53: 5-7+55
54: 7*7+5
55: 55
56: 7*7+7
57: 57
58: 57+5/5
59: 7+57-5
60: 5+55
61: 75-7-7
62: 7+55
63: 75-7-5
64: 7+57
65: 5+5+55
66: 55/5+55
67: 7+5+55
68: 75-7
69: 7+7+55
70: 75-5
71: 7+7+57
72: 77-5
73: 5-7+75
74: 75-5/5
75: 75
76: 5/5+75
77: 77
78: 77+5/5
79: 7+77-5
80: 5+75
81: 5/5+5+75
82: 7+75
83: 7*5-7+55
84: 7+77
85: 5+5+75
86: 55/5+75
87: 7+5+75
88: 77+55/5
89: 7+7+75
90: 7*5+55
91: 7+7+77
92: 57+7*5
93: 5*5-7+75
94: 7+7+5+75
95: 7*5+5+55
96: 7+7+7+75
97: 7+7*5+55
98: 7*7+7*7
99: 7*7-5+55
100: 5*5+75

These lines that start with "I found" are to see what he’s doing. Interesting that you can see the optimizer working, as in this example below where an expression was found for the 18 with 5 characters and complication degree 4, but when searching for a better expression, one with a complication degree 3 was found later:

Achei: 18 = 75-57
Achei: 18 = 5*5-7

Interestingly, none of the expressions generated up to 100 use parentheses (they are expensive because each pair of parentheses leaves the expressions longer in 2 characters). Even your example gives this:

31 = 7 - ( 5 * 5 ) + 7 * 7

But the show thought so:

31 = 775 / 5 / 5

And in this case there, the degree of complication is equal, but the expression size and the number of parentheses is lower.