Coding Solution

CGX Formatter – solution CodinGame en Java

Difficileparsingrecursive descentstring manipulationpretty printingMis à jour le
Réponse courte

On concatène toutes les lignes d'entrée, puis on parse le texte récursivement en trois sortes d'éléments : primitives, paires clé-valeur et blocs entre parenthèses, en sautant espaces et tabulations partout sauf dans les chaînes entre quotes. On réaffiche ensuite l'arbre avec chaque élément de bloc sur sa propre ligne, indenté de quatre espaces supplémentaires, et un ';' après chaque élément sauf le dernier. Le parcours est linéaire en la longueur du texte, à un facteur profondeur près dans cette implémentation.

L'énoncé

CGX est un petit format de données, un peu comme JSON. Une primitive est un nombre, true, false, null ou une chaîne entre quotes simples. Un bloc est une liste d'éléments entre parenthèses, séparés par des points-virgules. Une clé-valeur est une chaîne entre quotes, un signe égal et soit une primitive, soit un bloc.

On reçoit le texte CGX réparti sur N lignes avec un espacement quelconque et il faut l'afficher dans la mise en forme canonique : parenthèses seules sur leur ligne, chaque élément de bloc sur une ligne distincte indentée de 4 espaces par niveau, aucun espace hors des chaînes, et la valeur bloc d'une clé-valeur affichée sur la ligne qui suit la clé et son '='.

La démarche, étape par étape

  1. Joindre les lignesLes retours à la ligne n'ont aucun sens hors des chaînes, donc on concatène les N lignes en une seule chaîne et on garde un unique curseur qui avance au fil du parsing.
  2. Sauter les blancs, mais pas dans les chaînesAvant de lire chaque jeton, on saute les espaces et les tabulations. À l'intérieur d'une chaîne entre quotes, on copie chaque caractère tel quel, y compris espaces, parenthèses, points-virgules et signes égal.
  3. Déterminer le type d'élément'(' ouvre un bloc. Une quote ouvre soit une chaîne simple, soit une clé : on lit jusqu'à la quote fermante, on saute les blancs et on regarde si le caractère suivant est '='. Tout le reste est un nombre ou un mot-clé (true, false, null) lu jusqu'à un délimiteur.
  4. Parser les blocs récursivementUn bloc lit des éléments jusqu'à ')', en consommant les séparateurs ';'. Chaque élément est parsé par la même fonction, donc les blocs imbriqués et les clés-valeurs dont la valeur est un bloc sont gérés sans effort supplémentaire.
  5. Afficher avec un niveau d'indentationOn affiche '(' et ')' seuls sur leur ligne au niveau courant, les enfants au niveau + 4, un ';' après chaque enfant sauf le dernier, et pour une clé-valeur dont la valeur est un bloc, la clé et '=' sur une ligne puis le bloc sur la suivante, au même niveau.

Complexité

TempsO(L·D)
MémoireO(L)

L est la longueur du texte et D la profondeur d'imbrication. Cette implémentation formate chaque enfant en chaîne puis le réindente avec replace(), donc le texte profond est copié une fois par niveau ; transmettre le niveau d'indentation pendant l'affichage ramène le tout à O(L).

Code de la solution

CGX Formatter – Java

Chaque type d'élément est une sous-classe d'une classe abstraite Element avec read() et toFormattedCGX(), un bel exemple de polymorphisme. La vérification isKeyValue() regarde au-delà de la quote fermante et des espaces ou tabulations éventuels pour trouver un '=' avant de considérer une chaîne comme une clé.

import java.util.*;
import java.io.*;
import java.math.*;

/** This class represents an element, which can be read from CGX content
 * and printed as a well formatted String
 */
abstract class Element {

    /** modifies the representation of an element, indenting it by 'indentLevel' spaces */
    public static String indent(String toIndent, int indentLevel) {
        // Creates the indentation block
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++)
            sb.append(" ");
        String indentation = sb.toString();

        // Adds it in front of each line 
        return indentation+toIndent.replace("\n", "\n"+indentation);
    }

    /** returns an int describing the type of the element beginning by content[offset]
     * type 1 : block    type 2 : primitive type    type 3 : key value
     * type 0 : none of the 3, probably a tabulation or a space
     */
    public static int type(String content, int offset) {
        if (isBlock(content, offset))
            return 1;
        else if (isKeyValue(content, offset))
            return 3;
        else if (isPrimitive(content, offset))
            return 2;
        else
            return 0;
    }

    /** reads next element of content and return new offset
     * for each type, should work only if content[offset] is really
     * the beginning of the given type.
     */
    abstract int read(String content, int offset);

    /** returns a representation of the element, following the formatting
     * rules given in the puzzle
     */
    abstract String toFormattedCGX();


    // private functions used to identify each type

    /** returns true if and only if next Element in content is a Block */
    private static boolean isBlock(String content, int offset) {
        return content.charAt(offset) == '(';
    }

    /** returns true if next Element in content is a Primitive type
     * be careful, also returns true if it is a KeyValue, so check with isKeyValue
     * returns false if it is not a Primitive or KeyValue
     */
    private static boolean isPrimitive(String content, int offset) {
        return Character.isDigit(content.charAt(offset)) ||
        content.regionMatches(offset, "true", 0, 4) ||
        content.regionMatches(offset, "false", 0, 5) ||
        content.regionMatches(offset, "null", 0, 4) ||
        content.charAt(offset) == '\'';
    }

    /** returns true if and only if next Element in content is a KeyValue */
    private static boolean isKeyValue(String content, int offset) {
        if (content.charAt(offset) != '\'')
            return false;
        else {
            while (content.charAt(++offset) != '\'');
            ++offset;
            while (offset < content.length() && 
                   (content.charAt(offset) == ' ' || content.charAt(offset) == '\t'))
                ++offset;
            return (offset < content.length() && content.charAt(offset) == '=');
        }
    }
}

class Block extends Element {
    private ArrayList<Element> elements;
    private static final int INDENT_LEVEL = 4;

    public Block() {
        elements = new ArrayList<Element>();
    }

    public int read(String content, int offset) {
        // skips opening parenthesis
        offset++;
        // read each item :
        while (content.charAt(offset) != ')') {
            // skips optionnal ' ', tabulations and ';'
            while (content.charAt(offset) == ' ' || 
                   content.charAt(offset) == '\t' || 
                   content.charAt(offset) == ';')
                offset++;

            // if there is at least one item left
            if (content.charAt(offset) != ')') {
                Element nextElement = null;
                switch (Element.type(content, offset)) {
                    case 1 :
                        nextElement = new Block();
                        break;
                    case 2 :
                        nextElement = new Primitive();
                        break;
                    case 3 :
                        nextElement = new KeyValue();
                        break;
                }
                offset = nextElement.read(content, offset);
                elements.add(nextElement);
            }
        }
        // skip closing parenthesis and return new offset
        return ++offset;
    }

    public String toFormattedCGX() {
        StringBuilder result = new StringBuilder();
        result.append("(\n");
        
        if (elements.size() > 0) {
            for (Element e : elements) {
                result.append(indent(e.toFormattedCGX(), INDENT_LEVEL));
                result.append(";\n");
            }
            // remove last ';' and add closing parenthesis
            result.deleteCharAt(result.length()-2);
        }

        result.append(")");
        return result.toString();
    }
} 

class Primitive extends Element {

    /** string representing the primitive :
     * true, false, null, a number, a string (with quotes)*/
    private String value;

    public Primitive() {}

    public int read(String content, int offset) {
        /* sets i so that content[offset+i] is the 1st char after the primitive
           using the fact that for a string it follows ', for a number it is the  
           is 1st non digital char, and for others it is the first non lower case */ 
        int i = 0;
        
        if (content.charAt(offset) == '\'') {
            ++i;
            while (offset+i < content.length() && content.charAt(offset+i) != '\'')
                ++i;
            ++i;
        } 
        else if (Character.isDigit(content.charAt(offset)))
            while (offset+i < content.length() && Character.isDigit(content.charAt(offset+i)))
                i++;
        else
            while (offset+i < content.length() && Character.isLowerCase(content.charAt(offset+i)))
                i++;

        value = content.substring(offset, offset+i);
        return offset+i;
    }

    public String toFormattedCGX() {
        return value;
    }
}

class KeyValue extends Element {
    // key, stored as a Primitive string
    private Primitive key;
    // value, which can be a block or a Primitive
    private Element value;

    public KeyValue() {
        key = new Primitive();
    }

    public int read(String content, int offset) {
        offset = key.read(content, offset);
        // skips '=', and optionnal spaces
        while (Element.type(content, offset) == 0)
            offset++;
        switch (Element.type(content, offset)) {
            case 1 :
                value = new Block();
                break;
            case 2 :
                value = new Primitive();
                break;
        }
        offset = value.read(content, offset);
        return offset;
    }

    public String toFormattedCGX() {
        StringBuilder result = new StringBuilder();
        result.append(key.toFormattedCGX());
        result.append("=");
        if (value instanceof Block)
            result.append("\n");
        result.append(value.toFormattedCGX());
        return result.toString();
    }
}

class Solution {

    private static String content;
    private static int offset = 0;
    
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);

        // Reading CGX content
        int N = in.nextInt();
        in.nextLine();
        StringBuilder CGXlines = new StringBuilder(); 
        for (int i = 0; i < N; i++) 
            CGXlines.append(in.nextLine());
        content = CGXlines.toString();
        // For each element, reads it, formats it and prints it
        while (offset < content.length()) {
            Element nextElement = null;
            switch (Element.type(content, offset)) {
                case 1 :
                    nextElement = new Block();
                    break;
                case 2 :
                    nextElement = new Primitive();
                    break;
                case 3 :
                    nextElement = new KeyValue();
                    break;
            }
            if (nextElement == null)
                offset++;
            else {
                offset = nextElement.read(content, offset);
                System.out.println(nextElement.toFormattedCGX());
            }
        }   
    }
}
            

Erreurs fréquentes

Pour aller plus loin

On n'a en réalité pas besoin d'arbre. Un formateur en une seule passe fonctionne : on parcourt les caractères avec un compteur d'indentation ; sur '(' on émet un retour à la ligne si nécessaire, on affiche '(' au niveau courant et on l'augmente ; sur ')' on le diminue et on affiche ')' seul sur sa ligne ; sur ';' on affiche ';' et un retour à la ligne ; sur '=' on affiche '=' et, si le prochain caractère significatif est '(', on passe à une nouvelle ligne ; on copie les chaînes telles quelles et on supprime les blancs ailleurs. La difficulté de cette version en flux est de savoir quand un retour à la ligne est dû avant un jeton, et c'est pourquoi la plupart des gens trouvent la version récursive avec arbre plus facile à faire juste. Un bon test maison consiste à repasser votre sortie dans votre propre formateur : un formateur correct est idempotent, donc la seconde passe doit reproduire exactement son entrée.

Questions fréquentes

Peut-il y avoir plusieurs éléments de premier niveau ?

L'entrée contient normalement un seul élément de premier niveau, mais une boucle qui continue à parser jusqu'à la fin du texte, comme le fait ce code, en gère plusieurs sans effort supplémentaire.

Les nombres négatifs ou décimaux sont-ils possibles ?

Dans les tests, le format n'utilise que des suites de chiffres pour les nombres. Pour être défensif, on peut lire un nombre comme tout ce qui précède le prochain délimiteur (blanc, ';', ')' ou '=').

Pourquoi mes tests passent mais pas les validateurs ?

Dans presque tous les cas, ce sont les tabulations : les validateurs contiennent des caractères de tabulation autour des jetons. Il faut les gérer partout où l'on saute les espaces.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome