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.
Erstelle eine Gleichung, in der jede dieser Zahlen genau einmal vorkommt und das Ergebnis 24 ist.
Dabei können beliebig oft die Rechenoperationen Addieren, Subtrahieren, Multiplizieren und Dividieren, sowie beliebige Klammersetzung verwendet werden.

 

 

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")