Logik-Rätsel mit Hilfe von Python lösen

[noisefloor]

Hallo,

der Titel ist Programm

Der Rätsel ist hier: http://www.rattenburg.de/geo/GC2CEFV/ Es sollen alle Signale grün sein. Klickt man auf ein Signal, ändert sich dessen Status (rot -> grün bzw. umgekehrt) - und der Status aller verbunden Signale auch.

Zugegebener Massen bin ich gerade völlig ideenlos, was eine elegante Lösung angeht Ich habe einen Brute Force Ansatz, der aber nicht zum Erfolg führt (und ausserdem auch mit pypy ziemlich lange läuft. Die Stellwerk-Klasse liegt im Pastebin, die "Arbeit" erledigt dieser Code:

Code: Alles auswählen

from itertools import permutations, product
from stellwerk import Stellwerk

#combis = permutations(Stellwerk.STATIONEN)
combis = product(Stellwerk.STATIONEN, repeat=len(Stellwerk.STATIONEN))

for combi in combis:
    if not len(set(combi)) < 6 and not (combi[0]==combi[1]==combi[2]):
        stellwerk = Stellwerk()
        for station in combi:
            stellwerk.status_wechsel(station)
            if stellwerk.alle_true():
                print('moegliche Folge: {}'.format(combi))

ANGEBLICH ist das Ergebnis mit ~10 Schritten lösbar -deshalb steht `repeat` oben auch auf 12 (also `en(Stellwerk.STATIONEN)`)

Ich gehe auch davon aus, dass diese Art von Problem eine allgemeine Namen hat - ich habe aber keine Idee, wie der ist, um in diese Richtung weiter recherchieren zu können ("Stellwerksproblem" ist es jedenfalls nicht ).

Input und Denkanstöße sind also willkommen

Gruß, noisefloor

[BlackJack]

@noisefloor: Ich weiss nicht ob's elegant ist, aber ich habe das Problem als Graphenproblem formuliert. Es gibt 12 Signale die jeweils zwei Zustände einnehmen können, also insgesamt 4096 Möglichkeiten. Das sind die Knoten und wenn man die durchnummeriert, kann man die Bits als eben diese Signale auffassen. Kanten gibt's dann zwischen Knoten wo man von einem Zustand durch schalten eines Signals zum anderen Zustand kommen kann. Die Kante hat das Signal als Beschriftung. Und dann sucht man über den üblichen Algorithmus einen kürzesten Weg vom Ausgangsknoten 4095 zum Endknoten 0 (oder umgekehrt) und die Kantenbeschriftungen geben die Signale wieder die man schalten muss.

Das geht in 6 Schritten und mein C64 hat ca. 10 Sekunden gebraucht die zu finden. Mit einem in C geschriebenen Programm.

[stefanbunde]

hiho

also etwas anderes, als per bruteforce würde mir jetzt auch nicht einfallen.
hab mal eben was zusammengezimmert. in 10 sekunden schaffe ich das mit python nicht, aber ich würde sagen, mehr als 15 sekunden waren das nicht

auf 6 schritte komme ich dabei auch wobei man dazu sagen muss, dass es dabei extrem viele lösungen gibt.
mein script gibt dir sämtliche lösungswege (für bis zu 8 schritten) aus

Code: Alles auswählen

from itertools import product


class Stellwerk(object):
    def __init__(self, name):
        self.name = name
        self.related_to = []
        self.status = False

    def add_relation(self, stellwerke):
        self.related_to.extend(stellwerke)

    def toggle(self):
        self.status = not self.status
        for related in self.related_to:
            related.status = not related.status


names = ["ob", "kr", "du", "es", "do", "mg", "d", "w", "ha", "ac", "k", "si"]
stellwerke = {name: Stellwerk(name) for name in names}

stellwerke["ob"].add_relation([stellwerke["du"], stellwerke["es"], stellwerke["do"]])
stellwerke["kr"].add_relation([stellwerke["mg"], stellwerke["d"], stellwerke["du"]])
stellwerke["du"].add_relation([stellwerke["ob"], stellwerke["kr"], stellwerke["es"], stellwerke["d"]])
stellwerke["es"].add_relation([stellwerke["ob"], stellwerke["du"], stellwerke["do"], stellwerke["ha"]])
stellwerke["do"].add_relation([stellwerke["ob"], stellwerke["es"], stellwerke["ha"]])
stellwerke["mg"].add_relation([stellwerke["kr"], stellwerke["d"], stellwerke["ac"]])
stellwerke["d"].add_relation([stellwerke["kr"], stellwerke["du"], stellwerke["mg"], stellwerke["w"], stellwerke["k"]])
stellwerke["w"].add_relation([stellwerke["d"], stellwerke["ha"], stellwerke["k"]])
stellwerke["ha"].add_relation([stellwerke["es"], stellwerke["do"], stellwerke["w"], stellwerke["si"]])
stellwerke["ac"].add_relation([stellwerke["mg"], stellwerke["k"]])
stellwerke["k"].add_relation([stellwerke["d"], stellwerke["w"], stellwerke["ac"], stellwerke["si"]])
stellwerke["si"].add_relation([stellwerke["ha"], stellwerke["k"]])


def check_all():
    return all([stellwerk.status for stellwerk in stellwerke.values()])

def reset():
    for stellwerk in stellwerke.values():
        stellwerk.status = False

def print_all_status(toggled):
    return "%6s | %s" % (toggled.name, " | ".join(["%6s" % str(stellwerk.status)
                                                   for stellwerk in stellwerke.values()]))


for i in range(0, 8):
    for count, combi in enumerate(product(names, repeat=i)):
        out = ["toggle | %s" % " | ".join(["%6s" % name for name in names])]

        for item in combi:
            stellwerk = stellwerke[item]
            stellwerk.toggle()
            out.append(print_all_status(stellwerk))

            if check_all():
                for line in out:
                    print line
                print
        reset()

[noisefloor]

Hallo,

@BlackJack: Danke für die Info

Dein Lösungsweg deckt sich mit dem, was ich so geahnt habe. Besonders, dass es einen Lösungsweg gibt, der nicht stundenlang rechnet. Werde mir das die Tage nochmal anschauen und sehen, wie man das in Python umsetzt. Das Stichwort "Graphenproblem" war das, was mir fehlte

@stefanbude: Danke für den Code Wirkt auf den ersten Blick meinem ähnlich, nur etwas eleganter - und funktionierend. Probiere ich später mal.

Gruß, noisefloor

[kodela]

Hallo,

diese Lösung hat nichts mit Python zu tun:

- Klicke auf jedes der drei Signale mit einem Buchstaben in beliebiger Reihenfolge.
- Klicke auf jedes der drei jetzt noch nicht gesetzten Signale in beliebiger Reihenfolge.

@stefanbunde:
Dein Script erzeugt extrem viele, aber wesentlich mehr gleiche als unterschiedliche Lösungen.

MfG, kodel

[BlackJack]

Was die Anzahl der Unterschiedlichen Lösungen angeht kann man auch festlegen was ”unterschiedlich” eigentlich bedeutet. Da das Schalten von einem Signal sozusagen eine XOR-Verknüpfung nach sich zieht, ist die Reihenfolge in der man die Signale einer Lösung schaltet, egal. Man könnte also sagen das A, B, C und A, C, B die gleiche Lösung wäre.

[noisefloor]

Hallo,

- Klicke auf jedes der drei Signale mit einem Buchstaben in beliebiger Reihenfolge.
- Klicke auf jedes der drei jetzt noch nicht gesetzten Signale in beliebiger Reihenfolge.

Das stimmt. Beeindruckend einfach Wusstest du das, weil du das Rätsel kennst oder ist da noch irgendeine Logik hinter, die ich gerade nicht erkenne?

Gruß, noisefloor

[kodela]

Hallo noisefloor,

nein, weder das eine noch das andere ist der Fall. Das Programm von stefanbunde hat mich drauf gebracht, als mir die unzähligen meist selben Lösungen aufgefallen sind und deshalb habe ich mir diese Lösungen einmal genauer angesehen. Da klingelte bei mir plötzlich etwas.

Dieses Programm habe ich mir ausgesucht, da ich seit drei Wochen dabei bin, Python kennen zu lernen und da sind funktionierende Beispiele ein gutes Studienobjekt. Allerdings hatte ich Pech. Ich schreibe und debugge meine Testobjekte unter Netbeans und da muss in dem Modul für die Python-Plattform ein Bug sein, denn er zeigt mir für die Zeile 20 folgenden Fehler an:

Code: Alles auswählen

no viable alternative at input 'for'
mismatched input 'for' expecting RCURLY
mismatched input 'for' expecting RCURLY
mismatched input 'name' expecting NEWLINE
mismatched input '}' expecting NEWLINE
Assign expression to a variable

Im Debugg-Modus ließ sich das Programm allerdings ausführen. Dabei sah die Ausgabe wesentlich übersichtlicher aus, als in der Konsole, in der das Programm normal lief.

Ich baute auch noch einen Zähler ein und das Programm hörte überhaupt nicht mehr zu arbeiten auf. Bei etwa 7500 Lösungen habe ich es dann abgewürgt.

@stefanbunde:

Netbeans zeigt mir die Zuweisung zu 'names' noch als zur Stellwerk-Klasse gehörig an, was auf Grund der nicht mehr vorhandenen Einrückung ja nicht der Fall ist. Der nächste Block beginnt dann mit der Definition von 'stellwerke'. Dem Blockmarker am linken Rand fehlt allerdings der obere Schließen-Marker. Hast Du mit so etwa Erfahrung?

MfG, kodela

[BlackJack]

@kodela: Netbeans kommt anscheinen nicht mit allem klar was Python so an Syntax bietet. Das in Zeile 20 ist eine „dict comprehension“ die es seit Python 2.7 gibt. Vielleicht gibt's da ja ein Update für die Python-Unterstützung in Netbeans? Ansonsten scheint das ja nicht so geeignet zu sein.

[kodela]

Hallo @BlackJack,

ja, die Reihenfolge spielt überhaupt keine Rolle.

Man kann sogar sagen, die Lösung ist D, K, W, OB, ES, DO == D, K, W, OB, DO, ES == D, K, W, ES, OB, DO ... DO, ES, OB, W, K, D

Besser gesagt, jede beliebige Kombination dieser sechs Signale. Das sind 720 verschiedene Lösungswege, aber nur eine Lösung. So zumindest kann man das sehen.

MfG, kodela

[stefanbunde]

also ich muss zugeben, dass ich mir die lösungen nicht im detail angeguckt habe.
zwei, drei lösungen habe ich validiert, damit war die sache für mich gegessen

dass das script ewig läuft ist mir auch aufgefallen.
da hab ich aber auch noch nicht nachgeschaut, ob das daran liegt, dass es so viele mögliche lösungen gibt.


@kodela: mit netbeans hab ich nie gearbeitet, da hab ich null erfahrungen mit. ich entwickle mit vim oder pycharm. dieses script ist im vim entstanden


dass man erst die drei einbuchstabigen stellwerke stellen muss und dann die drei noch roten, das ist eine entdeckung unseres verstandes. es wurde aber nach dem python-way gefragt. dass python so ein ergebnis liefert grenz an künstliche intelligenz

[kodela]

@stefanbunde:

Danke für die Auskunft!

dass man erst die drei einbuchstabigen stellwerke stellen muss und dann die drei noch roten, das ist eine entdeckung unseres verstandes. es wurde aber nach dem python-way gefragt. dass python so ein ergebnis liefert grenz an künstliche intelligenz

Nicht nur, denn man muss eben nicht erst die drei einbuchstabigen Signale setzen. BlackJack hat richtig erkannt, dass wir es hier mit einer XOR Verknüpfung zu tu haben und die Reihenfolge der sechs Lösungs-Signale überhaupt keine Rolle spielt.

Das Programm erkennt aber sehr schnell, welche der sechs Signale relevant sind. Bei allen gefunden Lösungen sind nur diese sechs Signale eingebunden.

MfG, kodela

[BlackJack]

@stefanbunde: Das kann man sich ja leicht ausrechnen warum das so lange dauert. Für die minimale Anzahl der Schritte probierst Du 12⁶ = 2.985.984 Kombinationen durch. Bei sieben Schritten dann 12⁷ = 35.831.808 Kombinationen. Und das dauert dann wahrscheinlich eine Weile.

[kodela]

Hallo,

ich habe mich noch einmal mit dem Problem beschäftigt und folgendes Programm erstellt:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random

# Bezeichnungen der Signale
b = ['D', 'K', 'HA', 'ES', 'DU', 'W', 'MG', 'DO', 'KR', 'OB', 'SI', 'AC']

# Liste mit den Knoten
k = [[0, 1, 4, 5, 6, 8],      # 0 = D  <   
     [1, 0, 5, 10, 11],       # 1 = K  <
     [2, 3, 5, 7, 10],        # 2 = HA
     [3, 2, 4, 7, 9],         # 3 = ES <
     [4, 0, 3, 8, 9],         # 4 = DU
     [5, 0, 1, 2],            # 5 = W  <
     [6, 0, 8, 11],           # 6 = MG
     [7, 2, 3, 9],            # 7 = DO <
     [8, 0, 4, 6],            # 8 = KR
     [9, 3, 4, 7],            # 9 = OB <
     [10, 1, 2],              # 10 = SI
     [11, 1, 6]]              # 11 = AC 
          
d = 0
geloest = False

while not geloest:
    # Liste mit den Knoten zufällig sortieren
    random.shuffle(k)
    # Liste für den Status der Signale mit False initialisieren
    signale = 12 * [0]
    # Durchlaufzähler
    d += 1
    # nur die ersten sechs Knoten (Signale) berücksichtigen
        for n in range(0, 6, 1):
        # Knoten einschließlich aller Nachbarn umschalten
        for m in k[n]:
            signale[m] = ~signale[m]
        # prüfen ob alle Signale gesetzt sind
        if 0 not in signale:
            geloest = True
            print 'Durchläufe:\n', d
            print '\nSignalliste:\n', signale
            print '\nAusgewertete Knoten:\n', k[:6]
            print '\nFolgende Signale müssen umgestellt werden (Reihenfolge beliebig):\n',\
                b[k[0][0]]+' '+b[k[1][0]]+' '+b[k[2][0]]+' '+b[k[3][0]]+' '+b[k[4][0]]+' '+b[k[5][0]]
            break
    if geloest: break

Im Prinzip habe ich mit zwei Listen gearbeitet, einer mit allen Knoten (Signale) mit den Indizien für die eigene Position und die aller Nachbarn. In der zweiten wird für alle Signale eines Knotens der Status umgeschaltet.

Vor jedem Durchlauf wird die Liste mit den Knoten in eine zufällige Reihenfolge gebracht und die Liste für den Status der Signale für alle Signale auf "nicht gestellt" (0) gesetzt.

Danach werden die ersten sechs Knoten ausgewertet. Sind nach einer solchen Auswertung alle Signale gesetzt, wird der Durchlauf abgebrochen und das Ergebnis angezeigt.

Ich habe die über das Programm von stefanbunde gewonnenen Erkenntnisse, dass es genau sechs "Lösungswerte" gibt, deren Reihenfolge beliebig ist, als Faktum unterstellt. Wüsste man dies nicht, müsste man zum Beispiel mit einem Durchlauf von fünf Knoten beginnen und, falls damit nach einer bestimmten Anzahl von Durchläufen keine Lösung gefunden wird, die Anzahl der zu berücksichtigen Knoten schrittweise erhöhen.

Durch folgende Ergänzung lässt sich das sehr leicht realisieren:

Vor der while-Schleife einfügen: p = 5

In der Schleife ab Zeile 33 den Code so verändern:

Code: Alles auswählen

    if d % 5000 == 0:
        p += 1
    # nur die ersten p Knoten (Signale) berücksichtigen
    for n in range(0, p, 1):

MfG, kodela

[kodela]

Hallo,

eine Frage habe ich noch:

Gehört die if-Abfrage am Ende (Zeile 47) nicht eine Tab-Position weiter nach rechts? Es funktioniert bei beiden Positionen.

MfG, kodela

[Sirius3]

@kodela: die if-Abfrage gehört ganz weg, dafür hast Du doch die while-Schleife. Wobei das geloest komplett weg kann, weil Du die Schleife per break verläßt.

[BlackJack]

Hier ist das C-Programm das ich auf dem C64 laufen gelassen habe:

[Codebox=c file=Unbenannt.c]#include <stdint.h>
#include <stdio.h>

#define SIGNAL_COUNT 12
#define NODE_COUNT (1 << SIGNAL_COUNT)
#define NO_NODE 0xffff

enum {OB, KR, DU, ES, DO, MG, D, W, HA, AC, K, SI, NO_SIGNAL, START};

char *SIGNAL_NAMES[] = {
"OB", "KR", "DU", "ES", "DO", "MG", "D", "W", "HA", "AC", "K", "SI"
};

uint16_t SWITCHES[] = {
1 << OB | 1 << DU | 1 << ES | 1 << DO,
1 << KR | 1 << DU | 1 << MG | 1 << D,
1 << DU | 1 << OB | 1 << KR | 1 << ES | 1 << D,
1 << ES | 1 << OB | 1 << DU | 1 << DO | 1 << HA,
1 << DO | 1 << OB | 1 << ES | 1 << HA,
1 << MG | 1 << KR | 1 << D | 1 << AC,
1 << D | 1 << KR | 1 << DU | 1 << MG | 1 << W | 1 << K,
1 << W | 1 << D | 1 << HA | 1 << K,
1 << HA | 1 << ES | 1 << DO | 1 << W | 1 << SI,
1 << AC | 1 << MG | 1 << K,
1 << K | 1 << D | 1 << W | 1 << AC | 1 << SI,
1 << SI | 1 << HA | 1 << K,
};

typedef struct
{
uint8_t via_signal;
uint16_t next_id;
} Node;

Node graph[NODE_COUNT];


int main(void)
{
uint16_t node_id, next_node_id;
uint16_t first_node_id, last_node_id;
uint8_t signal_id;

for (node_id = 0; node_id < NODE_COUNT; ++node_id) {
graph[node_id].via_signal = NO_SIGNAL;
graph[node_id].next_id = NO_NODE;
}

first_node_id = last_node_id = NODE_COUNT - 1;
graph[first_node_id].via_signal = START;

for (;;) {
node_id = first_node_id;
first_node_id = graph[first_node_id].next_id;
if (first_node_id == NO_NODE) {
last_node_id = NO_NODE;
}

if (node_id == 0) break;

for (signal_id = 0; signal_id < SIGNAL_COUNT; ++signal_id) {
next_node_id = node_id ^ SWITCHES[signal_id];
if (graph[next_node_id].via_signal == NO_SIGNAL) {
graph[next_node_id].via_signal = signal_id;
if (last_node_id == NO_NODE) {
first_node_id = last_node_id = next_node_id;
} else {
graph[last_node_id].next_id = next_node_id;
last_node_id = next_node_id;
}
}
}
}

while ((signal_id = graph[node_id].via_signal) != START) {
printf("%s ", SIGNAL_NAMES[signal_id]);
node_id = node_id ^ SWITCHES[signal_id];
}
putchar('\n');

return 0;
}[/Codebox]

[kodela]

@Sirius3:

Danke für den Hinweis zur überflüssigen if-Abfrage. Allerdings kann ich geloest nicht ganz weg lassen, denn das break bezieht sich ja nur auf die Schleife for n in range(0, 6, 1): Damit komme ich aber nicht aus der while-Schleife heraus. Oder sehe ich da etwas falsch?

MfG, kodela

[kodela]

Hallo,

ich habe mich noch etwas mit der Frage von noisefloor befasst und mein weiter oben dazu bereits gepostete Programm überarbeitet, denn es gefiel mir nicht, dass ich von der unbewiesenen Voraussetzung ausgegangen bin, nur mit sechs Signalen wäre die Aufgabe zu lösen.

Mein erster Programmvorschlag hat nach dem Zufallsprinzip jeweils sechs Knoten ausgewählt und geprüft, ob über sie die Lösung zu erreichen ist. Das hat recht gut funktioniert, aber das Zufallsprinzip bei der Lösung einer solchen Aufgabe hat mir auch nicht gefallen. Ich entschloss mich daher, systematisch alle möglichen Kombinationen durchzuprüfen. Wie ich feststellen konnte, sind das gar nicht so viele, wenn die Reihenfolge der Signalumschaltungen keine Rolle spielt. Es gibt nur 4094 verschiedene Kombinationen. Berücksichtigt man Ober- und Untergrenze nicht, also eine Lösung mit zwölf beziehungsweise einer Umschaltung, dann sind es 4070 Kombinationen für die Umschaltungen.

Hier das Programm, welches diese 4070 Kombinationen prüft und dabei die einzige Lösungsmöglichkeit findet:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-
    
from time import *
import itertools

t1 = clock()

# Liste mit den Knoten
k = [[0,  'D', 1<<0|1<<1|1<<4|1<<5|1<<6|1<<8],
    [1,   'K', 1<<1|1<<0|1<<5|1<<10|1<<11],
    [2,  'HA', 1<<2|1<<3|1<<5|1<<7|1<<10],
    [3,  'ES', 1<<3|1<<2|1<<4|1<<7|1<<9], 
    [4,  'DU', 1<<4|1<<0|1<<3|1<<8|1<<9],
    [5,   'W', 1<<5|1<<0|1<<1|1<<2],
    [6,  'MG', 1<<6|1<<0|1<<8|1<<11],
    [7,  'DO', 1<<7|1<<2|1<<3|1<<9],
    [8,  'KR', 1<<8|1<<0|1<<4|1<<6],
    [9,  'OB', 1<<9|1<<3|1<<4|1<<7],
    [10, 'SI', 1<<10|1<<1|1<<2],
    [11, 'AC', 1<<11|1<<1|1<<6]]

# Bitmaske für alle Signale wenn gesetzt
alle = 1<<0|1<<1|1<<2|1<<3|1<<4|1<<5|1<<6|1<<7|1<<8|1<<9|1<<10|1<<11
sa = 12                                     # Anzahl der Signale
d = 0                                       # Zähler für Durchläufe
# alle Kombinationen von zwei bis elf der zwölf Signale prüfen
for vers in range(2, 11):
    # 
    for j in itertools.combinations(range(sa), vers):
        d += 1                          # Durchlaufzähler inkrementieren
        sstat = 0                       # Status für alle Signle zurückstzen

        # Knoten einschließlich aller Nachbarn umschalten
        for i in j:                     # nächsten Knoten der Kombination
            m = k[i]                    # in m übernehmen und
            sstat = sstat ^ m[2]        # in Statuszeile umschalten
        # prüfen ob alle Signale gesetzt sind
        if sstat == alle:
            geloest = True
            print 'Durchläufe:', d
            print '\nWenn alle Signale die gleiche Stellung ' + \
                'haben\nund folgende Signale umgestellt ' +\
                'werden (Reihenfolge beliebig),\n'
            for n in j:
                print ('  ->  ' + k[n][1])
            print '\nhaben alle Signale die selbe invertierte Stellung, ' +\
                'sie sind entweder alle offen oder geschlossen.'
print '\nDurchläufe:', d                    
t2 = clock()
td = t2 - t1          
print '\nRechenzeit: '+str(td)+' Sek.'

Und so sieht die Ausgabe aus:

Code: Alles auswählen

Durchläufe: 1685

Wenn alle Signale die gleiche Stellung haben
und folgende Signale umgestellt werden (Reihenfolge beliebig),

  ->  D
  ->  K
  ->  ES
  ->  W
  ->  DO
  ->  OB

haben alle Signale die selbe invertierte Stellung, sie sind entweder alle offen oder geschlossen.

Durchläufe: 4070

Rechenzeit: 0.0204042692577 Sek.

Mit dem 1685. Durchlauf wird die Lösung gefunden. Danach werden noch alle weiteren Kombinationen, insgesamt 4070, geprüft.

Den Tipp für Iterieren der Schleifen mit den jeweils benötigten Indizien für die zu prüfenden Knoten habe ich hier im Forum bekommen. Auch hier noch einmal ein Danke dafür.

Die kritischen Spezialisten in diesem Forum bitte ich, zu berücksichtigen, dass ich Python erst seit knapp vier Wochen kenne. Für Hinweise, wie man das eine oder andere verbessern kann, wäre ich dankbar.

MfG, kodela

[googol]

Sorry, dass ich eine untreue Tomate bin, aber dieses Problem ruft nach:
Prolog.