Hallo.
Ich hab mich gerade mal an die aufgaben des BwInf Wettbewerbes gesetzt.
Die Aufgabe mit der ich Angefangen habe dreht sich um alphametiken.
(Ich will hier natürlich nichts was mir in dem Wettbewerb weiterhilft lesen, also nicht das ich was dagegen hätte, aber gerade
fair wäre das ja nicht.)
Jedenfalls hab ich ein Programm geschrieben, welches in der Lage ist Alphametiken zu lösen…
naja, „lösen“, denn ich bruteforce einfach alle Zahlen und schaue ob expressionValue == result ist.
Das ganze dauert bei dem klassischen Beispiel „SEND + MORE = MONEY“ … naja… ziemlich lange, da allein die schleife
von 0 - 1*10^8 läuft.
Ich würde mir Vorschläge wünschen… wie man das ein bisschen effizienter machen könnte…
Eigentlich fällt mir nichts ein was man von der herangehensweise ändern könnte, aber wenn
das bruteforcen totaler schwachsinn ist, sagt es mir bitte 
Das Programm bis jetzt:
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Alphametic {
private String rawContent;
private ArrayList<Expression> addends;
private Expression result;
public Alphametic(String content){
addends = new ArrayList<>();
content = content.replaceAll(" ", "");
this.rawContent = content;
String equation[] = content.split("=");
String term = equation[0];
Expression e[] = Expression.parseTerm(term);
for(Expression ex : e){
addends.add(ex);
}
result = Expression.parseValue(equation[1]);
}
public String getOnlyLetterContent(){
return rawContent.replaceAll("[^A-Z]", "");
}
public int genExpressionValue(HashMap<Character, Integer> setting){
int value = 0;
for(Expression e : addends){
value += e.genValue(setting);
}
return value;
}
public int genResultValue(HashMap<Character, Integer> setting){
return result.genValue(setting);
}
public static class Expression {
private String content;
private boolean negative;
private Expression(String content, boolean negative){
this.content = content;
this.negative = negative;
}
public static Expression[] parseTerm(String term){
String addends[] = Utils.removeEmptyFields(term.split("[+\\-/\\*]"));
String operands = term.replaceAll("[^+\\-/\\*]", "");
if(operands.length() < addends.length) operands = "+" + operands;
Expression expressions[] = new Expression[addends.length];
for(int i = 0; i < addends.length; i++){
boolean negative = false;
if(operands.charAt(i) == '-') negative = true;
expressions** = new Expression(addends**, negative);
}
return expressions;
}
public static Expression parseValue(String value){
return parseTerm(value)[0];
}
public int genValue(HashMap<Character, Integer> setting){
StringBuilder builder = new StringBuilder();
if(negative) builder.append("-");
for(int i = 0; i < content.length(); i++){
builder.append(setting.get(content.charAt(i)));
}
return Integer.valueOf(builder.toString());
}
}
public static class Utils {
public static String[] removeEmptyFields(String[] strings){
int matches = 0;
for(String s : strings) if(s.equals("")) matches++;
String result[] = new String[strings.length - matches];
int index = 0;
for(int i = 0; i < result.length; i++){
for(String s2 = strings[index]; (s2 = strings[index]).equals(""); index++){}
result** = strings[index++];
}
return result;
}
public static void printField(Object o[]){
for(Object obj : o){
System.out.print("[" + obj + "] ");
}
System.out.println();
}
}
public static void main(String[] args){
testAlphametic(createTestAlphametic());
}
private static void testAlphametic(Alphametic a){
ArrayList<HashMap<Character, Integer>> settings = createTestSetting(a);
for(HashMap<Character, Integer> setting : settings){
int expressionValue = a.genExpressionValue(setting), resultValue = a.genResultValue(setting);
if(expressionValue == resultValue){
System.out.print("possible setting found! " + setting.toString() + "
");
}
}
}
private static ArrayList<HashMap<Character, Integer>> createTestSetting(Alphametic a){
ArrayList<HashMap<Character, Integer>> settings = new ArrayList<HashMap<Character, Integer>>();
Set<Character> charSet = getAlphameticCharSet(a);
NumberFormat format = NumberFormat.getInstance();
int charCount = charSet.size();
format.setMinimumIntegerDigits(charCount);
format.setGroupingUsed(false);
System.out.println(Math.pow(10, charCount));
for(int i = 0; i < Math.pow(10, charCount); i++){
String s = String.valueOf(format.format(i));
HashMap<Character, Integer> setting = new HashMap<>();
Iterator<Character> charSetIterator = charSet.iterator();
int index = 0;
while(charSetIterator.hasNext()){
char currentChar = charSetIterator.next();
int currentInt = Integer.valueOf(s.substring(index, index + 1));
setting.put(currentChar, currentInt);
index++;
}
settings.add(setting);
}
return settings;
}
private static Set<Character> getAlphameticCharSet(Alphametic a){
char chars[] = a.getOnlyLetterContent().toCharArray();
Set<Character> charSet = new HashSet<>();
for(char c : chars) charSet.add(c);
return charSet;
}
private static Alphametic createTestAlphametic(){
return new Alphametic("SEND + MORE = MONEY");
}
}
*** Edit ***
Ein bisschen nachdenken, und mir kam der Gedanke ob man nicht
anhand bestimmter bedigungen bestimmte kombination ausschließen könnte…
aber welche könnten das sein? und würde es das nicht nur noch langsamer machen?
*** Edit ***
Eventuell könnte ich ja vllt auch das ganze in mehreren Threads laufen lassen.
Aber wenn die Cpu nun nur einen Kern oder so hat, dann bringt das ja auch nichts…
*** Edit ***
Nach noch genauerem hinschauen und zeitmessen fällt auch auf,
das die eigentlichen Zeitbomben erzeugung der objekte in der for
sind… aber das kann man ja beim besten willen nicht schneller machen…
