CodeStory en java : Scalaskel et la calculette

Cet article fait suite à l'article Ma participation à CodeStory en java : Intro.
Le but de cet article va être de vous parler de deux étapes du concours CodeStory : Scalaskel et la Calculette en vous présentant mon implémentation en Java.

Scalaskel

Voici l'énoncé tel que nous l'avons reçu par POST :

L’échoppe de monade sur Scalaskel.

Sur la planète Scalaskel, une planète en marge de la galaxie, aux confins de l’univers, la monnaie se compte en cents, comme chez nous. 100 cents font un groDessimal. Le groDessimal est la monnaie standard utilisable partout sur toutes les planètes de l’univers connu. C’est un peu compliqué à manipuler, mais si on ne s’en sert pas y’a toujours des erreurs d’arrondis incroyables quand on les soustrait ou on les divise, c’est idiot, mais c’est comme ça. Sur Scalaskel, on utilise rarement des groDessimaux, on utilise des pièces plus petites : Le Foo vaut 1 cent, le Bar vaut 7 cents, le Qix vaut 11 cents et le Baz vaut 21 cents.

Vous tenez une échoppe de monade et autres variables méta-syntaxiques sur Scalaskel. Pour faire face à l’afflux de touristes étrangers avec les poches remplies de groDessimaux vous avez besoin d’écrire un programme qui pour toute somme de 1 à 100 cents, vous donnera toutes les décompositions possibles en pièces de Foo, Bar, Qix ou Baz.

Par exemple, 1 cent ne peut se décomposer qu’en une seule pièce Foo. Par contre 7 cents peuvent se décomposer soit en 7 pièces Foo, soit en 1 pièce Bar.

Serveur Web :

Votre serveur doit répondre aux requêtes http GET de la forme http://serveur/scalaskel/change/X, X étant une valeur en cents de 1 à 100 cents.

La réponse attendue est un json de la forme :

[{“foo”: w, “bar”: x, “qix”: y, “baz”: z}, …]

Exemples Pour http://serveur/scalaskel/change/1 il faut répondre :

[ {“foo”: 1} ]

Pour http://serveur/scalaskel/change/7 il faut répondre :

[ {“foo”: 7}, {“bar”: 1} ]

L’ordre des valeurs dans le tableau json, ainsi que le formatage n’a pas d’importance à partir du moment où c’est du json valide, il s’entend.

Bon courage !

Première chose à mettre en place, le test unitaire (et oui, même si on est pressé, le TDD c'est bien) :

import com.meterware.httpunit.WebConversation;
import com.meterware.httpunit.WebResponse;

import static org.junit.Assert.assertEquals;

public class ScalaskelTest extends WebServerTestUtil {

    @Test
    public void should_answer_to_1cent() throws Exception {
        WebConversation wc = new WebConversation();
        WebResponse response = wc.getResponse(getURL() + "/scalaskel/change/1");
        assertEquals(200, response.getResponseCode());
        assertEquals("[{\"foo\":1}]", response.getText());
    }

    @Test
    public void should_answer_to_7cent() throws Exception {
        WebConversation wc = new WebConversation();
        WebResponse response = wc.getResponse(getURL() + "/scalaskel/change/7");
        assertEquals(200, response.getResponseCode());
        assertEquals("[{\"foo\":7},{\"bar\":1}]", response.getText());
    }

    @Test
    public void should_answer_to_11cent() throws Exception {
        WebConversation wc = new WebConversation();
        WebResponse response = wc.getResponse(getURL() + "/scalaskel/change/11");
        assertEquals(200, response.getResponseCode());
        assertEquals("[{\"foo\":11},{\"foo\":4,\"bar\":1},{\"qix\":1}]", response.getText());
    }

    @Test
    public void should_answer_to_21cent() throws Exception {
        WebConversation wc = new WebConversation();
        WebResponse response = wc.getResponse(getURL() + "/scalaskel/change/21");
        assertEquals(200, response.getResponseCode());
        assertEquals("[{\"foo\":21},{\"foo\":14,\"bar\":1},{\"foo\":10,\"qix\":1},{\"foo\":7,\"bar\":2},{\"foo\":3,\"bar\":1,\"qix\":1},{\"bar\":3},{\"baz\":1}]", response.getText());
    }
}

Rien d'extraordinaire dans ce test, il contient seulement les cas basiques (en même temps, le calcul à la main est assez chiant comme ça).

Si vous avez lu l'article précédent, vous savez que mon code en l'état ne gère pas les requêtes par path du type "/scalaskel/change/1", commençons donc par là. Dans la même idée que le "QueryHandler" présenté dans l'article précendent, j'ai d'abord créé un "PathHandler" :

import fr.ybonnel.codestory.WebServerResponse;
import javax.servlet.http.HttpServletRequest;

public abstract class AbstractPathHandler {
    public abstract WebServerResponse getResponse(HttpServletRequest request, String payLoad, String... params) throws Exception;
}

La "request" sert à récupérer deux choses : la méthode (GET/POST) et le path. Le payload est utile pour les énoncés et jajascript (données envoyées en POST). Et pour finir les params sont le résultat de l'application d'un pattern que nous verrons ensuite.

Tout comme pour les Query, j'ai mis en place un enum relativement proche, mis à part qu'il n'a pas de méthodes abstraites. Cet enum gère de manière générique le routage avec la méthode et un pattern. Voici le code complet de cet enum :

import fr.ybonnel.codestory.WebServerResponse;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public enum PathType {

    INSERT_ENONCE(new InsertEnonceHandler(), "/enonce/(\\d+)", "POST"),
    GET_ENONCES(new GetEnoncesHandler(), "/enonce(/)*", "GET"),
    SCALASKEL_CHANGES(new ChangeScalaskelHandler(), "/scalaskel/change/(\\d+)", "GET"),
    JAJASCRIPT(new OptimizeJajascriptHandler(), "/jajascript/optimize.*", "POST");

    private AbstractPathHandler handler;

    private Pattern pathPattern;
    private String method;

    PathType(AbstractPathHandler handler, String pathPattern, String method) {
        this.handler = handler;
        this.pathPattern = Pattern.compile(pathPattern);
        this.method = method;
    }


    public Matcher isThisPath(String method, String path) {
        if (this.method.equals(method)) {
            return pathPattern.matcher(path);
        } else {
            return null;
        }
    }

    public static WebServerResponse getResponse(HttpServletRequest request, String payLoad) throws Exception {
        for (PathType onePath : values()) {
            Matcher isThisPath = onePath.isThisPath(request.getMethod(), request.getPathInfo());
            if (isThisPath != null && isThisPath.matches()) {
                return onePath.handler.getResponse(request, payLoad, extractParameters(isThisPath));
            }
        }
        return new WebServerResponse(HttpServletResponse.SC_NOT_FOUND, "This path is unknown");
    }

    private static String[] extractParameters(Matcher thisPath) {
        String[] params = new String[thisPath.groupCount()];
        for (int groupIndex = 1; groupIndex <= thisPath.groupCount(); groupIndex++) {
            params[groupIndex - 1] = thisPath.group(groupIndex);
        }
        return params;
    }
}

Maintenant que nous avons vu la tuyauterie, passons à l'algo de Scalaskel en lui-même. Au niveau modèle, j'ai deux classes, une représentant une solution (Change), et un enum représentant les pièces :

import com.fasterxml.jackson.annotation.JsonProperty;

public class Change {
    @JsonProperty
    private Integer foo;
    @JsonProperty
    private Integer bar;
    @JsonProperty
    private Integer qix;
    @JsonProperty
    private Integer baz;

    public Change(Change change) {
        if (change != null) {
            foo = change.foo;
            bar = change.bar;
            qix = change.qix;
            baz = change.baz;
        }
    }

    public void pay(Coin coin) {
        switch (coin) {
            case FOO:
                foo = foo == null ? 1 : foo + 1;
                break;
            case BAR:
                bar = bar == null ? 1 : bar + 1;
                break;
            case QIX:
                qix = qix == null ? 1 : qix + 1;
                break;
            case BAZ:
                baz = baz == null ? 1 : baz + 1;
                break;
        }
    }
}

import java.util.List;

import static com.google.common.collect.Lists.newArrayList;

public enum Coin {
    FOO(1),
    BAR(7),
    QIX(11),
    BAZ(21);

    private int value;

    Coin(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public boolean canPay(int cents) {
        return cents >= value;
    }

    private static class ListHolder {
        private static final List<Coin> valuesAsLists = newArrayList(values());
    }

    public static List<Coin> valuesAsLists() {
        return ListHolder.valuesAsLists;
    }
}

La classe Change contient des annotations pour la sérialisation Json avec Jackson, elle contient également un constructeur par copie servant dans l'algo, ainsi qu'une méthode pay, permettant d'ajouter une pièce à une solution. Quand à la classe Coin, elle contient une méthode "canPay" permettant de savoir si on peut ajouter la pièce pour un nombre de cents restant. Les listes sont là pour pouvoir utiliser la méthode Collections2.filter de Guava.

Et pour finir, voici la classe principale : le service permettant de faire le calcul.

import com.google.common.base.Predicate;
import com.google.common.collect.Collections2;
import com.google.common.collect.Lists;

import java.util.List;

public enum ScalaskelChangeService {
    INSTANCE;

    public static ScalaskelChangeService getInstance() {
        return INSTANCE;
    }

    public List<Change> calculateChanges(int cents) {
        return completeChanges(cents, null, null);
    }

    private List<Change> completeChanges(int cents, Change currentChange, Coin lastCoin) {
        // Stop condition of recursivity
        if (cents == 0) {
            return Lists.newArrayList(currentChange);
        }
        List<Change> changes = Lists.newArrayList();
        for (Coin coin : Collections2.filter(
                Coin.valuesAsLists(),
                new FilterCoins(lastCoin, cents))) {
            Change change = new Change(currentChange);
            change.pay(coin);
            changes.addAll(completeChanges(cents - coin.getValue(), change, coin));
        }
        return changes;
    }

    /**
     * Filter coins with this rule :
     * coin is keeped only if :
     * <ul>
     * <li>its value is bigger or equals thant lastCoin</li>
     * <li>we can pay with the coin.</li>
     * </ul>
     */
    private static class FilterCoins implements Predicate {

        private int minValue;
        private int centsToPay;

        private FilterCoins(Coin lastCoin, int centsToPay) {
            minValue = lastCoin == null ? 0 : lastCoin.getValue();
            this.centsToPay = centsToPay;
        }

        @Override
        public boolean apply(Coin input) {
            return minValue <= input.getValue() && input.canPay(centsToPay);
        }
    }
}

Cette classe est un enum pour le côté singleton. La classe FilterCoins permet de filtrer les pièces utilisables en fonction de la dernière pièce utilisée ainsi que le nombre de cents restant à payer. Pour l'algo, il s'agit d'un algo récursif relativement bourrin. Il est sûr que si les performances avaient été un critère, j'aurais sûrement modifié l'algo. J'espère que mon code est suffisamment clair pour ne pas avoir à l'expliquer d'avantage.

La dernière partie que nous n'avons pas vu est le "PathHandler" permettant de lier le service au WebServer :

import com.fasterxml.jackson.annotation.JsonInclude;
import com.fasterxml.jackson.core.JsonProcessingException;
import com.fasterxml.jackson.databind.ObjectMapper;
import fr.ybonnel.codestory.WebServerResponse;
import fr.ybonnel.codestory.path.scalaskel.Change;
import fr.ybonnel.codestory.path.scalaskel.ScalaskelChangeService;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.util.List;

public class ChangeScalaskelHandler extends AbstractPathHandler {

    private ObjectMapper objectMapper = new ObjectMapper().setSerializationInclusion(JsonInclude.Include.NON_NULL);

    private boolean wrongParams(int centsToPay) {
        return centsToPay <= 0 || centsToPay > 100;
    }

    @Override
    public WebServerResponse getResponse(HttpServletRequest request, String payLoad, String... params) throws JsonProcessingException {
        int centsToPay = Integer.parseInt(params[0]);
        if (wrongParams(centsToPay)) {
            return new WebServerResponse(HttpServletResponse.SC_FORBIDDEN, "Wrong parameters");
        }

        List<Change> changes = ScalaskelChangeService.getInstance().calculateChanges(centsToPay);
        return new WebServerResponse(HttpServletResponse.SC_OK, objectMapper.writeValueAsString(changes));
    }
}

Dans cette classe, vous pouvez voir une petite protection afin d'éviter de faire tomber le serveur en demandant le change de 1.000.000 de cents. On peut également y voir la sérialisation Json avec Jackson, mais rien de sorcier non plus.

La calculette

Pour cet exercice, pas d'énoncé, la première requête reçue fut : "/?q=1+1" à laquelle on se doute qu'il faut répondre "2". Je ne vais pas vous détailler toutes les étapes par lesquelles je suis passé pour arriver au bout. Voici la liste des requêtes reçues (dans l'ordre) :

• 1+1
• 2+2
• 3+3
• 4+4
• 5+5
• 6+6
• 7+7
• 8+8
• 9+9
• 1*1
• 2*2
• 3*3
• 4*4
• 5*5
• 6*6
• 7*7
• 8*8
• 9*9
• 1+2*2
• (1+2)*2
• (1+2+3+4+5+6+7+8+9+10)*2
• (1+2)/2
• ((1+2)+3+4+(5+6+7)+(8+9+10)*3)/2*5
• 1,5*4
• ((1,1+2)+3,14+4+(5+6+7)+(8+9+10)*4267387833344334647677634)/2*553344300034334349999000
• ((1,1+2)+3,14+4+(5+6+7)+(8+9+10)*4267387833344334647677634)/2*553344300034334349999000/31878018903828899277492024491376690701584023926880
• (-1)+(1)
• 1,0000000000000000000000000000000000000000000000001*1,0000000000000000000000000000000000000000000000001

Cette liste vous permet sans doute de voir par quelles étapes je suis passé :

• Gestion des sommes
• Gestion des multiplication
• Gestion des priorités
• Gestion des parenthèses
• Gestion des divisions
• Gestion des décimaux
• Gestion des grands nombres
• Gestion des nombres négatifs
• Gestion des nombres de décimales élevés

Pour la première version de mon code, j'ai tout fait à la main à grand coup de Pattern, voici le résultat final :

import com.google.common.base.Throwables;
import fr.ybonnel.codestory.query.calculate.Operator;
import fr.ybonnel.codestory.query.calculate.SearchParanthesis;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.text.NumberFormat;
import java.text.ParseException;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class CalculateQueryHandler extends AbstractQueryHandler {

    private static final String NOMBRE = "\\-?\\d+\\.?\\d*";
    private static final String PATTERN_DIVIDE = "(" + NOMBRE + ")/(" + NOMBRE + ")";
    private static final String PATTERN_MULTIPLY = "(" + NOMBRE + ")\\*(" + NOMBRE + ")";
    private static final String PATTERN_ADD = "(" + NOMBRE + ")\\+(" + NOMBRE + ")";

    // operators list by priority.
    private List operators = new ArrayList() {{
        // operator divide.
        add(new Operator(PATTERN_DIVIDE) {
            @Override
            public BigDecimal operate(BigDecimal a, BigDecimal b) {
                try {
                    return a.divide(b);
                } catch (ArithmeticException exception) {
                    return a.divide(b, 1000, RoundingMode.HALF_UP);
                }
            }
        });
        // Operator Multiply.
        add(new Operator(PATTERN_MULTIPLY) {
            @Override
            public BigDecimal operate(BigDecimal a, BigDecimal b) {
                return a.multiply(b);
            }
        });
        // Operator Add.
        add(new Operator(PATTERN_ADD) {
            @Override
            public BigDecimal operate(BigDecimal a, BigDecimal b) {
                return a.add(b);
            }
        });
    }};

    private Pattern patternParenthesis = Pattern.compile("\\((.*)\\)");
    private NumberFormat format = new DecimalFormat("#0.#", new DecimalFormatSymbols(Locale.FRANCE));

    public CalculateQueryHandler() {
        format.setMaximumFractionDigits(500);
    }

    @Override
    public String getResponse(String query) {
        String result = null;
        try {
            result = calculateWithParenthesis(query.replace(' ', '+').replace(',', '.'));
        } catch (ParseException e) {
            Throwables.propagate(e);
        }

        try {
            BigDecimal retour = new BigDecimal(result);
            return format.format(retour);
        } catch (NumberFormatException numberFormatException) {
            numberFormatException.printStackTrace();
            return null;
        }
    }

    private String calculateWithParenthesis(String calculateQuery) throws ParseException {
        Matcher matcherParenthsis = patternParenthesis.matcher(calculateQuery);

        while (matcherParenthsis.find()) {
            SearchParanthesis searchParanthesis = new SearchParanthesis(calculateQuery).invoke();
            int start = searchParanthesis.getStart();
            int end = searchParanthesis.getEnd();

            // Calculate the content of parenthesis.
            String queryBetweenParenthesis = calculateQuery.substring(start + 1, end - 1);
            String result = calculateWithoutParenthesis(queryBetweenParenthesis);

            // Replace the parenthesis group with result.
            calculateQuery = calculateQuery.substring(0, start) + result + calculateQuery.substring(end);
            matcherParenthsis = patternParenthesis.matcher(calculateQuery);
        }

        calculateQuery = calculateWithoutParenthesis(calculateQuery);
        return calculateQuery;
    }

    private String calculateWithoutParenthesis(String calculateQuery) throws ParseException {

        for (Operator operator : operators) {
            Matcher matcher = operator.matcher(calculateQuery);

            while (matcher.find()) {
                BigDecimal a = new BigDecimal(matcher.group(1));
                BigDecimal b = new BigDecimal(matcher.group(2));
                BigDecimal result = operator.operate(a, b);

                // Replace sur operation in string by result.
                calculateQuery = calculateQuery.substring(0, matcher.start()) + result.toString() + calculateQuery.substring(matcher.end());

                matcher = operator.matcher(calculateQuery);
            }
        }

        return calculateQuery;
    }
}

Je vous l'accorde, le code est relativement complexe, mais je suis assez fier d'avoir pondu une calculette à la main.

Devant tout ce code, j'ai décidé de simplifier tout ça grâce à groovy, vous allez voir le code est grandement simplifié :

import groovy.lang.GroovyShell;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.text.NumberFormat;
import java.util.Locale;

public class CalculateQueryHandler extends AbstractQueryHandler {
    private NumberFormat format = new DecimalFormat("#0.#", new DecimalFormatSymbols(Locale.FRANCE));
    private GroovyShell shell = new GroovyShell();

    public CalculateQueryHandler() {
        format.setMaximumFractionDigits(500);
    }

    @Override
    public String getResponse(String query) {
        Object object = shell.evaluate("return " + query.replace(' ', '+').replace(',', '.'));
        return formatGroovyReturn(object);
    }

    private String formatGroovyReturn(Object object) {
        try {
            return format.format(object);
        } catch (NumberFormatException numberFormatException) {
            numberFormatException.printStackTrace();
            return null;
        }
    }
}

Et voilà, merci groovy, finalement pas besoin de réinventer la roue...

Cet article est le deuxième d'une série de trois articles dont le dernier est sans doute le plus intéressant : Jajascript et les performance. Afin de vous donner un avant-goût, vous pouvez regarder l'article sur le blog Code Story : Location d’astronef sur Jajascript.