Vor kurzem stellte unser Kollege Tobias ein Matherätsel vor, welches er sogleich mit dem Cubeware Importer löste. Die ausführliche Lösung findet ihr hier, aber das Rätsel sei an dieser Stelle noch einmal rekapituliert:
|
Man hat die Zahlen 1, 3, 4, 6 zur Verfügung.
|
Die grundsätzliche Idee hinter dem Lösungsansatz wurde dort bereits genau ausgeführt, doch Tobias stellte sich nach der schönen Cubeware-Lösung dann doch bald die Frage: muss das nicht auch mit T-SQL gehen? Schließlich machen wir doch den ganzen Tag nichts anderes…
Und natürlich geht das! Wie sich herausstellt sogar deutlich schneller, denn statt knapp 6 Minuten läuft diese Lösung keine zwei Sekunden. Fairerweise sei allerdings gesagt, dass beide Lösungen nicht bis zum Letzten durchoptimiert wurden, denn ab und an lieben wir es einfach quick & dirty!
Hier nun also die komplette Lösung mit T-SQL:
DECLARE @Klammern TABLE
(
[klammer] [VARCHAR](1) NULL
)
DECLARE @Operationen TABLE
(
[operation] [CHAR](1) NULL
)
DECLARE @Zahlen TABLE
(
[zahl] [CHAR](3) NULL
)
INSERT @Klammern
([klammer])
VALUES ('('),
(')'),
('')
INSERT @Operationen
([operation])
VALUES ('+'),
('-'),
('*'),
('/')
INSERT @Zahlen
([zahl])
VALUES ('1.0'),
('3.0'),
('4.0'),
('6.0')
DECLARE @Formel TABLE
(
[formel] VARCHAR(255)
)
INSERT INTO @Formel
(formel)
SELECT
Concat(k1.klammer, z1.zahl, k2.klammer, o1.operation, k3.klammer, z2.zahl, k4.klammer, o2.operation, k5.klammer, z3.zahl, k6.klammer, o3.operation, k7.klammer, z4.zahl, k8.klammer)
FROM @Klammern k1
CROSS JOIN @Zahlen z1
CROSS JOIN @Klammern k2
CROSS JOIN @Operationen o1
CROSS JOIN @Klammern k3
CROSS JOIN @Zahlen z2
CROSS JOIN @Klammern k4
CROSS JOIN @Operationen o2
CROSS JOIN @Klammern k5
CROSS JOIN @Zahlen z3
CROSS JOIN @Klammern k6
CROSS JOIN @Operationen o3
CROSS JOIN @Klammern k7
CROSS JOIN @Zahlen z4
CROSS JOIN @Klammern k8
WHERE
-- unsinnige Klammern ausschließen
k1.klammer <> ')'
AND k2.klammer <> '('
AND k3.klammer <> ')'
AND k4.klammer <> '('
AND k5.klammer <> ')'
AND k6.klammer <> '('
AND k7.klammer <> ')'
AND k8.klammer <> '('
AND NOT ( k1.klammer = '('
AND k2.klammer = ')' )
AND NOT ( k3.klammer = '('
AND k4.klammer = ')' )
AND NOT ( k5.klammer = '('
AND k6.klammer = ')' )
AND NOT ( k7.klammer = '('
AND k8.klammer = ')' )
AND k2.klammer <> CASE
WHEN k1.klammer = '' THEN ')'
ELSE NULL
END
AND
-- Zahlen dürfen nur einmal vorkommen
z1.zahl <> z2.zahl
AND z1.zahl <> z3.zahl
AND z1.zahl <> z4.zahl
AND z2.zahl <> z3.zahl
AND z2.zahl <> z4.zahl
AND z3.zahl <> z4.zahl
DECLARE @Gleichung VARCHAR(255)
DECLARE @Ergebnis FLOAT
DECLARE db_cursor CURSOR FOR
SELECT 'SELECT @Ergebnis = ' + formel
FROM @Formel
WHERE
-- Anzahl der geöffneten Klammern muss dieselbe sein wie die der geschlossenen
( Len(formel) - Len(Replace(formel, ')', '')) ) = ( Len(formel) -
Len(Replace(formel, '(', '')) )
AND
-- Es darf nicht eine geschlossene vor der ersten geöffneten Klammer kommen
Patindex('%)%', formel) > Patindex('%(%', formel)
OPEN db_cursor
FETCH next FROM db_cursor INTO @Gleichung;
WHILE @@FETCH_STATUS = 0
BEGIN
BEGIN try
EXEC Sp_executesql
@Gleichung,
'@Ergebnis float OUTPUT',
@Ergebnis output
IF @Ergebnis = 24
BEGIN
PRINT Replace(@Gleichung, 'SELECT @Ergebnis = ', '')
END
END try
BEGIN catch
END catch
FETCH next FROM db_cursor INTO @Gleichung
END
CLOSE db_cursor
DEALLOCATE db_cursor Was haben wir hier genau gemacht? Zunächst einmal definieren wir drei Tabellenvariablen für die Klammern, Zahlen, und Rechenoperationen. Nun setzen wir aus diesen die (wiederum in einer Tabellenvariablen gespeicherte) Formel zusammen. Da wir in der Theorie alle Kombinationen testen müssen, verwenden wir für jede benötigte Stelle der Formel einen Cross Join mit der Tabelle des an dieser Stelle benötigten Elementes. Nun haben wir alle Formeln, die man aus den vorgegebenen Klammern, Rechenoperationen und Zahlen bilden kann. Das sind eine Menge! Und nun ja, mit dieser Menge ist der SQL Server per se erst einmal ein wenig überfordert, weshalb wir sie in bester quick&dirty-Manier einschränken und alles ausschließen, was uns mit kurzem Nachdenken in den Kopf kommt: unsinnige Klammern(-Kombinationen), gleiche Zahlen (das Rätsel sagt ja explizit, dass jede Zahl nur einmal vorkommen darf). Schließlich muss man nun wirklich nicht prüfen, ob )1(-3*)4(+)6( eine Lösung für das Rätsel ist. Mit der Menge geht der SQL Server dann schon deutlich besser gelaunt an die Arbeit, wir müssen also zum Glück nicht noch komplexeren Unsinn ausschließen.
Aber wie prüfen wir jetzt jede der übrig gebliebenen Formeln darauf, ob sie sinnvoll sind und vor allem zum gewünschten Ergebnis führen? Nun, wer hätte gedacht, dass wir den guten alten Cursor mal in einem Blog verwenden…
Wir iterieren mit Hilfe eines Cursors über jede der eben ermittelten Formeln, schließen dabei nochmal ein wenig offensichtlichen Unsinn aus, und machen daraus ein dynamisches SELECT-Statement, welches das Ergebnis in eine Variable speichert. Dieses Statement lassen wir anschließend per sp_executesql ausführen (nachdem wir uns bei der richtigen Syntax einmal die Finger verknotet haben). Natürlich benötigen wir hierfür einen TRY-CATCH-Block, da trotz unserer Bemühungen immer noch Formeln enthalten sind, die die Mathematik so gar nicht mag. Und da wir letztlich alle Lösungen, die nicht 24 sind, komplett uninteressant finden, lassen wir per print-Kommando lediglich die Gewinnerzeilen ausgeben – was, wie die Leser des ersten Beitrags wissen, lediglich eine einzige ist:
Puh, ein Blogbeitrag mit dynamischem T-SQL, Cursor, einem guten Dutzend Cross Joins und TRY-CATCH, was fehlt da noch… Richtig, eine Python-Lösung, die vom Kollegen Timo Klerx über LinkedIn eingereicht wurde. Da der Autor dieses Beitrags in aller Bescheidenheit zugeben muss, dass er dazu nicht viel sagen kann, sie aber auch nicht vorenthalten wollte, hier in all ihrer Schönheit.
Hier nun also die komplette Lösung mit Python:
__author__ = "Rob Knight, Gavin Huttley, and Peter Maxwell"
__version__ = "0.0.1"
__email__ = "tklex@paiqo.com"
__status__ = "Alpha"
from operator import add, sub, mul, truediv
from itertools import permutations, product
def compute(numbers, operators):
if len(numbers) == 1:
return [numbers[0]]
else:
res = []
try:
lefts = [operators[0](numbers[0], x)
for x in compute(numbers[1:], operators[1:])]
res.extend(lefts)
except ZeroDivisionError:
pass
try:
middle_idx = len(numbers) // 2
operator_idx = len(operators) // 2
middles = [operators[operator_idx](left, right) for left, right
in product(compute(numbers[:middle_idx], operators[:operator_idx]), compute(numbers[middle_idx:], operators[operator_idx:]))]
res.extend(middles)
except ZeroDivisionError:
pass
try:
rights = [operators[-1](x, numbers[-1])
for x in compute(numbers[:-1], operators[:-1])]
res.extend(rights)
except ZeroDivisionError:
pass
return res
operators = [add, sub, mul, truediv]
operands = [1, 3, 4, 6]
perms = permutations(operands)
ops_candidates = product(operators, repeat=len(operands)-1)
desired_result = 24
i = 0
for perm, ops in product(perms, ops_candidates):
res = compute(perm, ops)
if desired_result in res:
print(f"Found the desired result {desired_result}.")
ops_names = [op.__name__ for op in ops]
print(
f"The result can be achieved with the following set of operators: {ops_names}.")
break
i += len(res)
print(f"Tried {i} combinations")