Rossie
Rear Admiral
- Registriert
- Dez. 2010
- Beiträge
- 5.158
Endless Storm schrieb:
Wenn man das Design richtig hinbekommt, sollte es nicht schwierig sein, solche Änderungen einzupflegen. Das ist im Berufsleben ein wichtiges Kriterium bei der Entwicklung: Code sollte wartbar sein.
Ich musste eine kleine Änderung vornehmen, um auf das richtige Ergebnis zu kommen. Vor der Berechnung wird jetzt geprüft, ob nicht zwei Werte gleich sind. Zwei Minuten Arbeit
Code:
/**
* Tests whether this input is valid.
*
* @return {@code true} if this input is valid.
*/
public boolean isValid()
{
return new HashSet<Long>(mappings.values()).size() == letters.length;
}Aber dabei ist mir dann aufgefallen, dass der Code noch nicht ganz zu Ende gedacht war. Die Hauptklasse besteht jetzt nur noch aus:
Code:
@SuppressWarnings("boxing")
public class Puzzle
{
/**
* Main program entry point.
*
* @param rArgs the command-line arguments.
*/
public static void main(String[] rArgs)
{
Collection<Solution> result = new PuzzleSolver().solve("H E S + T H E = B E S T");
System.out.printf("Found %d solutions%n", result.size());
for (Solution solution : result)
{
System.out.println("-----------------");
System.out.println(solution);
}
}
}PuzzleCalculatur habe ich mit dem PuzzleSolver verschmolzen. Hier sieht man wie das Visitor-Pattern Verwendung findet, um das Ergebnis der Rechenaufgabe zu ermitteln. Wenn man sich den Code genau anschaut, stellt man fest, dann auch bereits Subtraktion, Multiplikation und Division (weitgehend) unterstützt werden. Führt natürlich von der ursprünglichen Aufgabenstellung weg.
Code:
@SuppressWarnings("boxing")
public class PuzzleSolver
{
private Memory memory;
private ParseTree tree;
/** Creates a new PuzzleSolver object. */
public PuzzleSolver()
{
super();
}
/**
* Calculates all valid solutions for the given symbol puzzle.
*
* @param rPuzzle the puzzle.
*
* @return the solutions.
*/
public Collection<Solution> solve(String rPuzzle)
{
tree = parse(rPuzzle);
memory = new Memory(getLetters(tree));
Collection<Solution> result = new ArrayList<Solution>();
for (long number = 1, count = memory.getCombinations(); number < count;
number++)
{
memory.update(number);
if (performCalculation(tree).isValid())
{
result.add(new Solution(memory.getMappings(),
memory.toString(tree)));
}
}
return result;
}
private PuzzleParser createParser(String rInput)
{
return new PuzzleParser(new CommonTokenStream(
new PuzzleLexer(new ANTLRInputStream(rInput))));
}
private String[] getLetters(ParseTree rTree)
{
return new LetterVisitor().getLetters(rTree);
}
private ParseTree parse(String rInput)
{
return createParser(rInput).parse();
}
private Result performCalculation(ParseTree rTree)
{
return Result.valueOf((new Calculator().visit(rTree) == 0));
}
private class Calculator
extends PuzzleBaseVisitor<Integer>
{
@Override
public Integer visit(ParseTree rTree)
{
return !memory.isValid() ? 1 : super.visit(rTree);
}
@Override
public Integer visitAddSub(AddSubContext rContext)
{
int lhs = visit(rContext.expr(0));
int rhs = visit(rContext.expr(1));
return (rContext.op.getType() == PuzzleParser.ADD) ? (lhs + rhs)
: (lhs - rhs);
}
@Override
public Integer visitAssign(AssignContext rContext)
{
int lhs = visit(rContext.expr());
int rhs = visit(rContext.operand());
return (lhs == rhs) ? 0 : 1;
}
@Override
public Integer visitMulDiv(MulDivContext rContext)
{
int lhs = visit(rContext.expr(0));
int rhs = visit(rContext.expr(1));
return (rContext.op.getType() == PuzzleParser.MUL) ? (lhs * rhs)
: (lhs / rhs);
}
@Override
public Integer visitOperand(OperandContext rContext)
{
StringBuilder buf = new StringBuilder(5);
// an operand consists of one or more letters, each letter is mapped
// to an integer
for (ParseTree node : rContext.children)
{
buf.append(memory.getValue(node.getText()));
}
return Integer.valueOf(buf.toString());
}
@Override
public Integer visitParse(ParseContext rContext)
{
return super.visit(rContext.stat());
}
}
}Endless Storm schrieb:
Dein Code ist etwa 50 x schneller (7 ms vs. 350 ms auf meinem Rechner mit Java 6), wobei das nur für einen Durchlauf gilt und die Systemausgabe beinhaltet. Das Parsen kostet natürlich Zeit. Und auch bei der Berechnung werden jede Menge Objekte erstellt. Dafür ist der Code aber auf viel mehr Probleme anwendbar und besser wartbar. Es wäre z.B. trivial die Berechnung zu parallelisieren, wobei man dabei immer noch um Größenordnungen langsamer wäre, als die Original-Lösung. Aber das erscheint hier nicht sonderlich wichtig.
Endless Storm schrieb:
Das ist das Schöne am Programmieren. Es gibt viele Wege zum Ziel. Es gibt Menschen, die Programmieren als Kunst ansehen und sich an der Eleganz einer Lösung erfreuen. Kommt natürlich auch auf die Sprache an.
Endless Storm schrieb:
Vielleicht kommst Du im Berufsleben nie mit einem solchen Problem in Berührung
Aber wenn, ist ANTLR sicherlich ein Tool, dem man Beachtung schenken sollte. Bis dahin wird es sicherlich auch nicht nur eine Java-Version geben. Im Studium werden Dir Parser-Generatoren aber sicher noch mal begegnen.
