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

[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.

[noisefloor]

Hallo,

das stimmt - die Idee hatte ich auch Nur ist mein Prolog so rudimentär, dass die Lösung mehrere Monate gedauert hätte

Gruß, noisefloor

[googol]

Hallo,

das stimmt - die Idee hatte ich auch Nur ist mein Prolog so rudimentär, dass die Lösung mehrere Monate gedauert hätte

Gruß, noisefloor

Ist das nicht mal nen Grund, 's wieder zu versuchen ?

Ich find Prolog in dieser Hinsicht immer wieder toll...
Niemals wieder 'n Sudoku mit der Hand lösen....
Niemals wieder Personalplanung mit Excel.

Und jetzt schau Dir doch mal den Python-Code an...
Hübscher als Prolog ist der auch nicht, nur dass man die Anzahl der Iterationen zählen kann. Geschenkt.
'Yes' und 'No' weckt bei mir Erinnungen.

Und ja: Ich zieh hier auch nur nen uralten Hasen ausm Hut.

[Hyperion]

@googol: Wo findet sich denn deine Prolog Lösung?

[googol]

@googol: Wo findet sich denn deine Prolog Lösung?

demnächst. Meine Zeit ist auch begrenzt und die Kunst ist nicht, den Hasen aus dem Hut zu ziehen, sondern ihn da herein zu bekommen. Aber:
"challenge accepted".