CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

| Download
Views: 43
Image: ubuntu2204
Kernel: Python 3 (system-wide)

Rockbands Rätsel mittels OR-Tools lösen

Man soll die 26 Buchstaben des Alphabets den Werten von 1 bis 16 derartig zuordnen, sodass eine Reihe von Nebenbedingungen erfüllt sind. zB soll A+C+D+C=45A + C + D + C = 45 gelten. Anschließend ergibt sich ein Lösungswort aus der zurückübersetzen Kombination von einigen Zahlen.

https://developers.google.com/optimization

from IPython.display import Image Image("rockbands.jpg")
Image in a Jupyter notebook
from string import ascii_uppercase ascii_uppercase
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
from ortools.sat.python import cp_model model = cp_model.CpModel() # Definition aller Buchstaben, als Integer von 1 bis 26 letters = [model.NewIntVar(1, len(ascii_uppercase), l) for l in ascii_uppercase] # Alle müssen unterschiedlich sein – so eine Nebenbedingung ist speziell bei SAT Solvern möglich model.AddAllDifferent(letters) # Wir speichern jede Buchstaben-Variable global ab for char, var in zip(ascii_uppercase, letters): globals()[char] = var
# Beispielsweise F
F(1..26)

Nebenbedingungen

# Summe der Variablen nach Buchstaben + ein print zur Kontrolle def band(chars, s): varsum = sum([globals()[c] for c in chars if c in ascii_uppercase]) model.Add(varsum == s) print(f"{varsum} == {s}")
# Alle Buchstaben zusammen kennen wir auch band(ascii_uppercase, sum(range(1, len(ascii_uppercase) + 1)))
(((((((((((((((((((((((((A + B) + C) + D) + E) + F) + G) + H) + I) + J) + K) + L) + M) + N) + O) + P) + Q) + R) + S) + T) + U) + V) + W) + X) + Y) + Z) == 351
# Das würde auch gehen, aber wir verwenden die band-Funktion model.Add(A + C + D + C == 45)
<ortools.sat.python.cp_model.Constraint at 0x7fe4a376fa90>
band('BEATLES', 52) band('COLDPLAY', 62) band('DEEP PURPLE', 27) band('DIRE STRAITS', 82) band('EAGLES', 29) band('GENESIS', 47) band('JETHRO TULL', 97) band('LED ZEPPELIN', 55) band('LYNYRD SKYNYRD', 126) band('METALLICA', 87) band('NIRVANA', 75) band('OASIS', 43) band('PINK FLOYD', 92) band('ROLLING STONES', 103) band('STEPPENWOLF', 91) band('STYX', 60) band('URIAH HEEP', 78) band('VAN HALEN', 88)
((((((B + E) + A) + T) + L) + E) + S) == 52 (((((((C + O) + L) + D) + P) + L) + A) + Y) == 62 (((((((((D + E) + E) + P) + P) + U) + R) + P) + L) + E) == 27 ((((((((((D + I) + R) + E) + S) + T) + R) + A) + I) + T) + S) == 82 (((((E + A) + G) + L) + E) + S) == 29 ((((((G + E) + N) + E) + S) + I) + S) == 47 (((((((((J + E) + T) + H) + R) + O) + T) + U) + L) + L) == 97 ((((((((((L + E) + D) + Z) + E) + P) + P) + E) + L) + I) + N) == 55 ((((((((((((L + Y) + N) + Y) + R) + D) + S) + K) + Y) + N) + Y) + R) + D) == 126 ((((((((M + E) + T) + A) + L) + L) + I) + C) + A) == 87 ((((((N + I) + R) + V) + A) + N) + A) == 75 ((((O + A) + S) + I) + S) == 43 ((((((((P + I) + N) + K) + F) + L) + O) + Y) + D) == 92 ((((((((((((R + O) + L) + L) + I) + N) + G) + S) + T) + O) + N) + E) + S) == 103 ((((((((((S + T) + E) + P) + P) + E) + N) + W) + O) + L) + F) == 91 (((S + T) + Y) + X) == 60 ((((((((U + R) + I) + A) + H) + H) + E) + E) + P) == 78 (((((((V + A) + N) + H) + A) + L) + E) + N) == 88

Lösen

Status 4 ist "optimal", 3 wäre "infeasible"

solver = cp_model.CpSolver() status = solver.Solve(model) status
4
# Kontrolle def check(chars): vals = [solver.Value(globals()[c]) for c in chars if c in ascii_uppercase] return sum(vals)
assert check("ACDC") == 45 assert check('BEATLES') == 52 assert check("STEPPENWOLF") == 91 assert check("ROLLING STONES") == 103 assert check("OASIS") == 43 assert check("VAN HALEN") == 88

Lösung

Für die Lösung übersetzen wir die Zahlen wieder zurück zu den Buchstaben. Dafür machen wir uns ein dictionary von den Lösungswert jedes Buchstabens zu dem Buchstaben (also das Invertierte!) ...

mapping = {solver.Value(globals()[ascii_uppercase[i]]) : ascii_uppercase[i] for i in range(len(ascii_uppercase))} mapping
{8: 'A', 19: 'B', 16: 'C', 5: 'D', 1: 'E', 17: 'F', 9: 'G', 23: 'H', 10: 'I', 20: 'J', 18: 'K', 3: 'L', 25: 'M', 12: 'N', 11: 'O', 2: 'P', 24: 'Q', 4: 'R', 7: 'S', 13: 'T', 6: 'U', 21: 'V', 22: 'W', 26: 'X', 14: 'Y', 15: 'Z'}
# bzw. der Reihe nach {i: mapping[i] for i in sorted(mapping)}
{1: 'E', 2: 'P', 3: 'L', 4: 'R', 5: 'D', 6: 'U', 7: 'S', 8: 'A', 9: 'G', 10: 'I', 11: 'O', 12: 'N', 13: 'T', 14: 'Y', 15: 'Z', 16: 'C', 17: 'F', 18: 'K', 19: 'B', 20: 'J', 21: 'V', 22: 'W', 23: 'H', 24: 'Q', 25: 'M', 26: 'X'}

... und übersetzen die Zahlen

for i in [4, 11, 26, 14, ' ', 25, 6, 7, 10, 16]: if type(i) == str: print(i, end='') else: print(mapping[i], end='')
ROXY MUSIC