Effizientere Alphametik Lösung?

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 :smiley:

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…

Wie würdest du es denn mit Bleistift und Papier machen? Genau, von hinten (D,E,Y) eine mögliche Kombination raussuchen, für die (D+E) % 10 == Y gilt. Jetzt eine Belegung mit der vorletzten Stelle suchen, für die (ND + RE) % 100 == EY gilt, u.s.w.
Wenn du damit irgendwann nicht weiterkommst, einen Schritt zurück (wenn das nicht hilft auch mehrere) und eine andere Lösung probieren - also Backtracking.

Hm, inwiefern würde mir das denn Zeit ersparen?
Letzten Endes muss da doch genauso viel ausprobiert werden…

*** Edit ***

Außerdem soll das ganze ja auch mit mehreren summanden und auch mit den operatoren * und / laufen…
Bleibt mir da denn noch mehr als einfach ausprobieren?

In einer Vorlesung hatten wir sowas mal mit dem http://de.wikipedia.org/wiki/AC-3-Algorithmus gelöst (man kann es allgemein als CSP betrachten), das Begleitbuch gibt’s unter http://aima.cs.berkeley.edu/ und den Code vom AC3 direkt unter http://aima-java.googlecode.com/svn/trunk/aima-core/src/main/java/aima/core/search/csp/AC3Strategy.java - Praktischerweise gibt’s GENAU das richtige Kapitel von der second edition (http://aima.cs.berkeley.edu/2nd-ed/ ) auch als Vorschau: http://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf . Aber natürlich gibt’s auch andere Möglichkeiten, da ranzugehen (bin gerade ziemlich übermüdet, deswegen hab’ ich den geposteten Code noch nicht gelesen)

In dem du bestimmte Kombinationen früh ausschließt, weil du nicht auf die gesamten Zahlen schaust, sondern nur auf die “Hinterteile”. Wenn dann eine Belegung von D,E,R,N oder so nicht funktioniert, brauchst du die ganzen Kombinationen für die übrigen Buchstaben gar nicht erst zu versuchen. Oder anders ausgedrückt: Statt einer Liste mit “Vollbelegungen” arbeitest du einen Baum ab, wo du bestimmte Äste gar nicht weiterverfolgst.

Außerdem soll das ganze ja auch mit mehreren summanden und auch mit den operatoren * und / laufen…

Ist kein Problem, auch für mehrere Operanden und -, * und / funktioniert der “% 10”-Trick. Bei anderen Operatoren (etwa bitweisen) wäre das allerdings nicht der Fall.

Bei der Additionsaufgabe, könnte man so vorgehen, dass man das Gleichungssystem null setzt.

Send+More-Money = 0

Nun kann man sich die Buchstaben herausfischen und koeffizienten Bilden

S = 1000
E = 100
N = 10
D = 1
M = 1000
O = 100
R = 10
E = 1
M = -10000
O = -1000
N = -100
E = -10
Y = -1

Diese kann man nun zusammenfassen.
S = 1000
E = 91 (100 + 1 - 10)

etc.

Dann kann man hingehen und das ganze sortieren.
S = 1000
E = 91
R = 10
D = 1
Y = -1
N = -90
O = -900
M = -9000

Wenn man nun Zahlen für die Buchstaben einsetzt bekommt man ein Ergebnis. Gesucht ist eine Kombination die Null ergibt.

Die kleinste Zahl die Gebildet werden kann ist, wenn man für
S = 0
E = 1
R = 2
D = 4
// Wechsel von positiv zu negativ
Y = 6
N = 7
O = 8
M = 9

einsetzt. Die Grösste Zahl bekommt man in dem man das ganze umgekehrt angeht.

Als nächsten Schritt, würde ich mir die absoluten Werte der Koeffizienten holen und danach sortieren.

D = 1
Y = 1
R = 10
N = 90
E = 91
O = 900
S = 1000
M = 9000

Jetzt heisst es M (-) solange verringern, solange man noch im Negativen bereich bleibt.
Danach S (+) solange erhöhen, bis man immer noch im Negativen Bereich bleibt.
Danach O (-) wieder solange verringern, bis man immer noch im Negativen Bereich bleibt oder eben die Zahl genau getroffen hat.

So kann man sich dann an die Zahl herantasten.

Hallo,

ich bin neu hier im Forum und sitze auch gerade an der vom TE beschriebenen Aufgabe. Ich gehe gerade schon mal alles im Kopf durch, bis ich am Freitag mit der Aufgabe in der Schule weitermache. Dabei werde ich die Landei’sche Methode verwenden :D.

Beim Überlegen stellt sich mir aber eine Frage: Wie kann ich diese Methode verwenden, um eine mögliche zweite oder dritte Lösung zu finden? Es kann ja sein, dass das eingegebene Rätsel mehrere Lösungen hat.

Nicht abbrechen, wenn man die erste Lösung gefunden hat, sondern alle Lösungen in einer Liste sammeln.

Hey Leute, was genau ist der % 10 Trick? ich habe ein ähnliches problem, nur nicht vom Bwinf und finde aber bei Onkel Google nichts dazu…:rolleyes:

so wie es beschrieben ist:

das % 10 heißt nur dass mit der Wahl von D und E sich durch die letzte Ziffer der Rechnung die Belegung von Y ergibt

am Anfang hat man eh fast freie Auswahl, alles passt solange man zwei verschiedene Zahlen nimmt denn D ist ja ungleich E,
Y taucht sonst auch nicht weiter auf in diesem Beispiel, dessen Belegung primär nicht so wichtig,
wird dann aber doch wichtig als dass eine weitere Ziffer vergeben ist, nicht mehr für als nächstes N, R, E gewählt werden kann
usw.

also wenn D = 8 und E = 4 dann ist Y mit (D+E) % 10 == 2 ?

(Danke für die schnelle Antwort. (: )

ja allein schon in Hinsicht auf Alphametik, mit dem Lösungsweg hier hat das nur halb zu tun :wink:

der Vorschlag ist, mit D und E zu beginnen, 8 und 4 sind da eine von einigen möglichen Kombinationen,
dass sich daraus Y = 2 ergibt ist weder Trick, noch Java-Frage, noch Variante(n-Wahl) oder Entscheidung sondern schlichte logische Konsequenz :wink:

ja, klar wegen dem übertrag. so dumm bin ich dann doch nicht. (;
aber trotzdem danke für deine hilfe zum verständnis dieser ausdrucksweise. (;