CGX Formatter – CodinGame solution in Java
Concatenate all input lines, then parse the text recursively into three kinds of elements: primitives, key-value pairs and parenthesised blocks, skipping spaces and tabs everywhere except inside quoted strings. Print the tree back with each block element on its own line, indented by four more spaces, with ';' after every element except the last.
The problem
CGX is a small data format, a bit like JSON. A primitive is a number, true, false, null or a string between single quotes. A block is a list of elements wrapped in parentheses and separated by semicolons. A key-value is a quoted string, an equals sign and either a primitive or a block.
You get the CGX text spread over N lines with arbitrary spacing and must print it in the canonical layout: parentheses on their own lines, each block element on a separate line indented by 4 spaces per level, no spaces outside strings, and a block value of a key-value printed on the line after the key and its '='.
Approach, step by step
- Join the linesLine breaks carry no meaning outside strings, so concatenate the N lines into one string and keep a single cursor that moves forward as you parse.
- Skip whitespace, but not in stringsBefore reading each token, skip spaces and tab characters. Inside a quoted string, copy every character verbatim, including spaces, parentheses, semicolons and equals signs.
- Decide the element type'(' starts a block. A quote starts either a plain string or a key: read to the closing quote, skip whitespace and check whether the next character is '='. Anything else is a number or a keyword (true, false, null) read until a delimiter.
- Parse blocks recursivelyA block reads elements until ')', consuming the ';' separators. Each element is parsed by the same function, so nested blocks and key-values whose value is a block come for free.
- Print with an indent levelPrint '(' and ')' on their own lines at the current indent, children at indent + 4, a ';' after every child except the last, and for a key-value with a block value print the key and '=' on one line and the block on the next at the same indent.
Complexity
O(L·D)O(L)L is the length of the text and D the nesting depth. This implementation formats each child to a string and then re-indents it with replace(), so deep text is copied once per level; passing the indent level down while printing makes it O(L).
Solution code
CGX Formatter – Java
Each element type is a subclass of an abstract Element with read() and toFormattedCGX(), a clean example of polymorphism. The isKeyValue() check looks past the closing quote and any spaces or tabs for an '=' before treating a string as a key.
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());
}
}
}
}
Common mistakes
- Ignoring tab charactersThe public tests only use spaces, but the hidden validators also contain tabs around parentheses, semicolons and '='. Treat '\t' exactly like a space or several validators fail for no visible reason.
- Trimming inside stringsA string such as 'a ; (b)' must be printed unchanged. Removing whitespace globally before parsing, or splitting on ';', breaks it.
- Wrong trailing semicolonOnly separators between elements are printed, so the last element of a block has no ';'. Building the list first and joining with ';\n' avoids an off-by-one.
- Empty blocks() must still print as '(' and ')' on two lines. Code that assumes at least one child often prints a lone ';' or crashes on the separator logic.
- Key-value with a block valueThe block does not go on the same line as the key: print the key and '=' first, then the block on the next line at the same indentation as the key.
Going further
You do not actually need a tree. A single-pass formatter works: walk the characters with an indent counter; on '(' emit a newline if needed, print '(' at the current indent and increase it; on ')' decrease it and print ')' on its own line; on ';' print ';' and a newline; on '=' print '=' and, if the next significant character is '(', move to a new line; copy strings verbatim and drop whitespace elsewhere. The tricky part of this streaming version is knowing when a newline is due before a token, which is why most people find the recursive tree version easier to get right. A good self-test is to run your output through your own formatter again: a correct formatter is idempotent, so the second pass must reproduce its input exactly.
FAQ
Can there be several top-level elements?
The input normally holds one top-level element, but a loop that keeps parsing until the end of the text, as this code does, handles several without extra effort.
Are negative or decimal numbers possible?
The format only uses digit sequences for numbers in the tests. If you want to be defensive, read a number as everything up to the next delimiter (whitespace, ';', ')' or '=').
Why do my tests pass but validators fail?
In almost every case it is tabs: the validators contain tab characters around tokens. Handle them wherever you skip spaces.