Thema: No. #999
- Mein neunhundertneunundneunzigster Beitrag - :
Weil es es ein guter Brauch ist, Jubiläen zu begehen, gedenke ich,
das mit etwas Ausführlicherem als gewöhnlich zu tun.
Es ist dies ein Geschenk an sometimes, aber auch für alle diejenigen
gedacht, die es eventuell sonst noch intressieren möge.
sometimes hatte vor einiger Zeit die Frage nach einem _Lösungsprogramm_
für rubiks cube gestellt - das ist dieser bunte Würfel, der, hat man
(gemeint ist der Normalmensch) ihn einmal so richtig verdreht, auf
ewige Zeiten bunt verdreht bleiben wird - sich also mithin beharrlich
weigert, jemals wieder in seine Anfangskonstellation zurückzukehren.
Mein Sohn Henry hat mir zu Weihnachten so ein Ding geschenkt, und aus
dem Beipackzettel jennes erfuhr ich, daß dessen eigner geistiger Vater
rund einen Monat brauchte, um das Monstrum zu bezwingen - und Rubik
himself ist immerhin gestandner Mathematiker.
Allerdings möchte ich keine ausführliche Lösung liefern, sondern
einen brauchbaren Ansatz zu einer solchen - es wär' sonst gar zu witzlos.
Worum es im folgenden geht, ist _nicht_ der Originalwürfel mit einer
Kantenlänge von drei (Teilwürfeln), sondern das abgespeckte Modell
mit einer Kantenlänge von zwo, wobei das ein wesentlicher Schritt in die
richtche Richtung ist, alldieweil _jeder_ Würfel nunmal acht Ecken hat.
Auch wird der Würfel nicht im geringsten vollständig gelöst werden, und
schon gar nicht systematisch (respective auf dem kürzest möglichen Weg),
sondern nur der erste Schritt wird gezeigt werden, und auch der lediglich
grob zufällig.
Die Gründe hierfür sind quasi mehrdimensional:
Zunächst und -allererst sollte mein 999zigster Beitrag gefälligst ein
script enthalten, das 99 Zeilen hat - das ist auch ein Grund, warum
ich mögliche elegantere Formulierungen mir schlicht verboten habe,
sonst wär's kürzer ausgefallen.
Sodann soll dieser Beitrag auch dazu dienen, Leuten, die davon bisher
nicht so beleckt waren, Lust auf PYTHON zu machen, und ein wenig davon
zu zeigen - deshalb finden sich auch verschiedene Arten, etwas in dieser
Sprache zu formulieren, wiewohl es uU. nicht die schnellsten oder
kürzest möglichen sind (weder in der Ausführung, noch in der Formulierung,
wobei beide Dinge mitnichten deckungsgleich sind). Ein weiterer Grund für die
Beschränkung auf die Teilaufgabe: die Darstellung des vollständigen Würfels
erschwert das Verständnis unnötigerweise, ohne wesentlich zu einem solchen
beizutragen.
Doch nach all diesen einführenden Einschränkungen in medias res:
Ersteinmal, so noch nicht geschehn, sollte man sich Python besorgen -
ein wenig rumclicken in http://www.python.org/ erledigt das.
Sodann auch numarray - Vorgehn desselbigengleichen, bissel einlesen
tut nicht weh und schadet bestimmt nicht.
Das Vorgehn:
Dem Programm muß zuerst ein 'real-world'-Würfel mitgeteilt werden,
also ein Würfel, der aus etwelchen Verdrehungen aus dem Original
entstanden ist. Das vorliegende Programm prüft nicht auf _unmögliche_
Würfel (ganz einfach, um den Ball flach zu halten).
(Obwohl: mit der angenehmen Ausnahme-Behandlung in python wäre das
auch kein Problem, es tät' aber den hier gesetzten Rahmen sprengen.)
Dieses Mitteilen geschieht, indem ins array I die einzelnen Teilwürfel
als jeweilige Farbbestandteile eingetragen werden, und zwar dergestalt (Kleist),
daß:
die vordere linke obere Ecke I[0] ist, die vordere rechte obere Ecke I[1], die
vordere linke untere Ecke I[2], die vordere rechte untere Ecke I[3], die hintere
linke obere Ecke I[4], usw. bis hintere rechte untere Ecke I[7], wobei immer
zuerst der Farbanteil in X-Richtung eingetragen wird, dann der in
Y-Richtung, und last, but very not least, der in Z-Richtung.
z
/
I[4]-----------I[5]
/ /
/ /
/ /
/ /
I[0]-----------I[1]-x
| |
| |
| |
| |
| |
I[2]-----------I[3]
|
y
Eine mögliche Ausgangsstellung eines nichtverdrehten Würfels wäre demgemäß:
I = [ ['orange', 'red', 'blue'] ,
['green', 'red', 'blue'] ,
['orange', 'white', 'blue'] ,
['green', 'white', 'blue'] ,
['orange', 'red', 'purple'] ,
['green', 'red', 'purple'] ,
['orange', 'white', 'purple'] ,
['green', 'white', 'purple'] ]
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Ein möglicher Dreier-Würfel (bereits verdreht) würde beispielsweise so notiert:
I = [ ['orange', 'red', 'blue'], [0, 'purple', 'red'], ['orange', 'white', 'blue'],
['orange', 0, 'purple'] , [0, 0, 'orange'], ['white', 0, 'green'],
['white', 'purple', 'green'], [0, 'orange', 'red'], ['blue', 'red', 'green'],
['red', 'green', 0], [0, 'blue', 0], ['white', 'orange', 0],
['red', 0, 0], [0, 0, 0], ['white', 0, 0],
['white', 'blue', 0], [0, 'purple', 0], ['red', 'blue', 0],
['orange', 'red', 'purple'], [0, 'purple', 'white'], ['green', 'red', 'purple'],
['orange', 0, 'blue'], [0, 0, 'green'], ['green', 0, 'purple'],
['white', 'blue', 'green'7], [0, 'blue', 'green'], ['purple', 'white', 'orange']]
- bitte gans schnell wieder vergessen - denn darum geht's hier, wie gesagt, _nicht_. -
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Schritt 1: Sammle alle Teilwürfel, die Eckwürfel sind, d.h.: alle Teilwürfel, die in jeder Richtung
eine Farbe haben - es gibt nämlich bei allen Würfel der Kantenlänge <=3 immer genau einen Teilwürfel
mit einer einzigartigen Farbkombination - soll heißen: die Eckwürfel insgesamt zeigen alle möglichen
Farben des jeweiligen Würfels:
[eI.append(i) for i in I if 0 not in i]
Man könnte das auch absolut anders formulieren (zB. naheliegenderweise abhängig von der Kantenlänge),
aber das ist ein Beispiel-script, das auch etwas von Möglichkeiten von Python zeigen soll.
In diesem Fall (dem Zweier-Würfel) sind natürlich sämtliche Teilwürfel auch Ecken......
Schritt 2: Ordne die Farben einander zu (zwei in jeder Dimension: x, y, und z):
x0, y0, z0 = eI[0]
xn, yn, zn = [[[i for i in j if i!=k[0] and i!=k[1]]
for j in eI[1:] if k[0] in j and k[1] in j][0][0]
for k in ((y0, z0), (x0, z0), (x0, y0))]
Bereits ab hier kann ein möglicher Algorithmus optimiert werden: indem er nämlich
nach bereits vollständigen Farbflächen sucht, und in Abhängigkeit davon den
Anfangs-Teilwürfel (I[0]) wählt.
Schritt 3: Pack alle Farben in ein array:
F = [0, x0, y0, z0, xn, yn, zn]
Schritt 4 : Bilde aus diesen Farben den Ausgangswürfel (den es wiederherzustellen gilt):
V = [ [x0,y0,z0], [xn,y0,z0],
[x0,yn,z0], [xn,yn,z0],
[x0,y0,zn], [xn,y0,zn],
[x0,yn,zn], [xn,yn,zn] ]
Schritt 5: Erstelle der Ordnung halber eine Arbeitskopie des Ausgangsarrays I:
W = deepcopy(I)
Schritt 6: Wandle zur internen Bearbeitung alle Farbnamenstrings in Zahlen
(das braucht's - numarray heißt nicht umsonst so) - und wandle die
array-shapes in etwas zum Berechnen Brauchbares um:
def Z(z):
for i in z:
for j in i:
if j in F : i[i.index(j)] = F.index(j)
[Z(i) for i in (V, W)]
V, W = [transpose(i, axes = (0,1)) for i in (V, W)]
[i.setshape(2,2,2,3) for i in (V, W)]
Schritt 7: Mal kurz Verschnaufen, um'n paar Abkürzungen zu notieren:
def C(c): return concatenate(c)
def S(s0, s1, s2): return swapaxes(s0, s1, s2)
Schritt 8: Keine Athempause, Geschichte wird gemacht, es geht voran...:
bilde die drehbaren Schichten des Würfels - davon gibt es in
jeder Dimension genau Kantenlänge Stück:
sX, sY, sZ = S(S(W, 0,2), 1,2), S(S(W, 0,1), 1,2), transpose(W, axes = (0,1,2,3))
Schritt 9: Eine function zum Drehen der jeweiligen Farbanteile um die
betreffenden Achsen (siehe argument qqq in def Q(q, qq, qqq)):
def D(a, s = 0):
if s==0 : a[0], a[1], a[2] = a[0], a[2], a[1]
if s==1 : a[0], a[1], a[2] = a[2], a[1], a[0]
if s==2 : a[0], a[1], a[2] = a[1], a[0], a[2]
return a
Mir schwant irgendwie nebulös, daß hier ein gewiefter Mathe-Hai vermittels
geeigneter Matrizen-Manipulation was Schöneres machen könnte, aber mein armer,
alter Kopf.......
Schritt 10: Eine function, die die Schichten dreht, in Abhängigkeit vom zugeordneten
Operator - siehe array Op (und Operatoren gibt es natürlich pro Schicht
zwo - vorwärts und rückwärts (siehe argument qq in def Q(q, qq, qqq)):
def Q(q, qq, qqq = 0):
if qq == 0 : a, b = 0, 1
else: a, b = 1, 0
q = C((C((D(q[a][b], qqq), D(q[b][b], qqq))), C((D(q[a][a], qqq), D(q[b][a], qqq)))))
q.setshape(2,2,3)
return q
Schritt 11: function def E(e, ee = None), die den Klumbadaradadsch ausführt:
def E(e, ee = None):
exec(Op[e])
if ee: print Op[e][:5], Op[e][16],
--------------------------------------------------------------------------------------------------
Ende, Gelände.......
Nochemol dat Janze im Zusammenhang:
from numarray import *
from copy import deepcopy
import random
###########################################################
I = [ ['orange', 'blue', 'white'], # ein irgendwie verdrehter Würfel...
['green', 'red', 'blue'],
['orange', 'purple', 'white'],
['green', 'white', 'blue'],
['orange', 'blue', 'red'],
['green', 'red', 'purple'],
['orange', 'purple', 'red'],
['green', 'white', 'purple'] ]
###########################################################
ln = 'n----------------n'
eI = []
[eI.append(i) for i in I if 0 not in i]
x0, y0, z0 = eI[0]
xn, yn, zn = [[[i for i in j if i!=k[0] and i!=k[1]]
for j in eI[1:] if k[0] in j and k[1] in j][0][0]
for k in ((y0, z0), (x0, z0), (x0, y0))]
F = [0, x0, y0, z0, xn, yn, zn]
V = [ [x0,y0,z0], [xn,y0,z0],
[x0,yn,z0], [xn,yn,z0],
[x0,y0,zn], [xn,y0,zn],
[x0,yn,zn], [xn,yn,zn] ]
W = deepcopy(I)
def OUT(o):
OT = [[[[],[]],[[],[]]],[[[],[]],[[],[]]]]
for i in range(len(o)):
for j in range(len(o[i])):
for k in range(len(o[i][j])):
OT[i][j][k] = [F[o[i][j][k][0]], F[o[i][j][k][1]], F[o[i][j][k][2]]]
return OT
def T():
global TMP
TMP = deepcopy(W)
def Z(z):
for i in z:
for j in i:
if j in F : i[i.index(j)] = F.index(j)
[Z(i) for i in (V, W)]
V, W = [transpose(i, axes = (0,1)) for i in (V, W)]
[i.setshape(2,2,2,3) for i in (V, W)]
def C(c): return concatenate(c)
def S(s0, s1, s2): return swapaxes(s0, s1, s2)
sX, sY, sZ = S(S(W, 0,2), 1,2), S(S(W, 0,1), 1,2), transpose(W, axes = (0,1,2,3))
def D(a, s = 0):
if s==0 : a[0], a[1], a[2] = a[0], a[2], a[1]
if s==1 : a[0], a[1], a[2] = a[2], a[1], a[0]
if s==2 : a[0], a[1], a[2] = a[1], a[0], a[2]
return a
def Q(q, qq, qqq = 0):
if qq == 0 : a, b = 0, 1
else: a, b = 1, 0
q = C((C((D(q[a][b], qqq), D(q[b][b], qqq))), C((D(q[a][a], qqq), D(q[b][a], qqq)))))
q.setshape(2,2,3)
return q
Op = ['sX[0] = Q(sX[0],0)', 'sX[0] = Q(sX[0],1)', 'sX[1] = Q(sX[1],0)', 'sX[1] = Q(sX[1],1)',
'sY[0] = Q(sY[0],0,1)', 'sY[0] = Q(sY[0],1,1)', 'sY[1] = Q(sY[1],0,1)', 'sY[1] = Q(sY[1],1,1)',
'sZ[0] = Q(sZ[0],0,2)', 'sZ[0] = Q(sZ[0],1,2)', 'sZ[1] = Q(sZ[1],0,2)', 'sZ[1] = Q(sZ[1],1,2)' ]
def E(e, ee = None):
exec(Op[e])
if ee: print Op[e][:5], Op[e][16],
###########################################################
print V, ln, W, ln
def R():
while V[0][0][1] != W[0][0][1]:
E(random.choice((2,6,10)), 1) # random.choice((2,6,10)) wählt die Operatoren, die nicht die x0, y0, z0-Schichten
print W[0][0][1] # bewegen, zufällig aus, und zwar bloß in eine Richtung
else:
print ln, V[0][0][0],' => ', OUT(V)[0][0][0],' || ', V[0][0][1],' => ', OUT(V)[0][0][1], ln
for i in OUT(W):
for j in i:
print j
print ln, 'done'
R()
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Drei Dinge wurden bisher nicht erwähnt: def T(), def OUT(o), und der letzte Abschnitt.
def T() zur Bildung einer zwischenzeitlichen Sicherungskopie wird bei der Entwicklung
eines Algorithmus gute Dienste leisten, und def OUT(o) ist eine Möglichkeit, zum Schluß
die interne Zahlendarstellung wieder in Farbnamen zurückzuwandeln.
Der letze Abschnitt wird ordnungsgemäß nun auch zuletzt beschrieben.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Zuguterletzt: Entwickle einen Algorithmus:
Bisher wurde lediglich die Arbeitsbedingung geschaffen und bereitgestellt.
Allerdings, meines Erachtens sind diese 99 schlappen Zeilchen ein guter
Anfang. Die Operatoren sind vorhanden - E() - der Rest ist aweng
Gehirnschmalz. Ein möglicher Lösungsweg für den Würfel mit der Kantenlänge
zwei (id est: die Ecken des Würfels mit der Kantenlänge drei - oder vier, oder neunundsechzig -):
Nimm einen willkürlich gewählten (hier: den mit der Eingabe ins array I
vorgegebenen ersten) Anfangs-Teilwürfel (W[0][0][0] == V[0][0][0]), ermittle sodann
W[0][0][1] == V[0][0][1] unter Ausschluß der Operatoren auf den Achsen x0, y0, z0
(also: ohne den Anfangswürfel - W[0][0][0] - in der vorderen linken oberen Ecke zu bewegen),
ermittle sodann W[0][1][0] == V[0][1][0] und W[0][1][1] == V[0][1][1], ohne W[0][0][0]
oder W[0][0][1] zu bewegen, ermittele zum Schluß W[1][0][0] , W[1][0][1] ,
W[1][1][0] und W[1][1][1] allein durch Drehung der z1-Achse (der letzten verbliebenen,
die frei beweglich ist).
Wenn nicht alle Teil-Eckwürfel übereinstimmen (also V != W) gehe zurück, und verdrehe den
Anfangs-Würfel möglichst geschickt - and do it again, Sam.......
Hier wird def T(), also die Zwischenspeicherung, wichtig.
Zwei Dinge sind dabei bedenkenswert:
1.) jeder Teilwürfel kann an jeder Ecke erscheinen, und das in jeder möglichen
Verdrehung der Farben um die Achsen.
2.) Sind alle Schichten frei beweglich, benötigt es _höchstens_ 3 Drehungen, um
einen Teilwürfel in jeder möglichen Verdrehung an eine beliebige andere Ecke zu bringen,
ebenfalls in jeder möglichen Verdrehung.
def R() macht nun nichts anderes, als den zweiten Teilwürfel rein zufällig zu finden (while W[0][0][1] != V[0][0][1]),
und bei Erfolg Laut zu geben - eine mögliche Ausgabe ist zB.:
[[[[1 2 3]
[4 2 3]]
[[1 5 3]
[4 5 3]]]
[[[1 2 6]
[4 2 6]]
[[1 5 6]
[4 5 6]]]]
----------------
[[[[1 2 3]
[4 6 2]]
[[1 5 3]
[4 3 2]]]
[[[1 2 6]
[4 6 5]]
[[1 5 6]
[4 3 5]]]]
----------------
sX[1] 0 [4 2 3]
----------------
[1 2 3] => ['orange', 'blue', 'white'] || [4 2 3] => ['green', 'blue', 'white']
----------------
[['orange', 'blue', 'white'], ['green', 'blue', 'white']]
[['orange', 'purple', 'white'], ['green', 'purple', 'white']]
[['orange', 'blue', 'red'], ['green', 'blue', 'red']]
[['orange', 'purple', 'red'], ['green', 'purple', 'red']]
----------------
done
Weil aber R() in der Tat ein kleiner Anarchist ist, könnte es zB. auch vermelden:
[[[[1 2 3]
[4 2 3]]
[[1 5 3]
[4 5 3]]]
[[[1 2 6]
[4 2 6]]
[[1 5 6]
[4 5 6]]]]
----------------
[[[[1 2 3]
[4 6 2]]
[[1 5 3]
[4 3 2]]]
[[[1 2 6]
[4 6 5]]
[[1 5 6]
[4 3 5]]]]
----------------
sZ[1] 0 [4 6 2]
sY[1] 0 [4 6 2]
sZ[1] 0 [4 6 2]
sX[1] 0 [3 1 5]
sX[1] 0 [1 6 5]
sY[1] 0 [1 6 5]
sX[1] 0 [2 6 1]
sZ[1] 0 [2 6 1]
sZ[1] 0 [2 6 1]
sX[1] 0 [4 2 3]
----------------
[1 2 3] => ['orange', 'blue', 'white'] || [4 2 3] => ['green', 'blue', 'white']
----------------
[['orange', 'blue', 'white'], ['green', 'blue', 'white']]
[['purple', 'red', 'green'], ['green', 'purple', 'white']]
[['white', 'orange', 'purple'], ['blue', 'orange', 'red']]
[['orange', 'purple', 'red'], ['blue', 'green', 'red']]
----------------
done
Das dauert zwar bloß einen Sekundenbruchteil, ist allerdings absolut falsch (in den Augen
des lösungsbegierigen Menschen).
Aber vermittels geschickterer Nutzung von E() lassen sich eine solche oder längere (ungewollte)
Erfolgsmeldungen durchaus vermeiden. Weil ich Dir (@ sometimes, wahlweise geneigter Leser, geneigte
Leserin) aber nicht den Spaß an der Erkundung von Python und der Beschäftigung mit rubiks cube
von vornherein rauben möchte,
verbleibe ich mit delphinischem gruß
matho
postscriptum 1:
Um ein Gefühl für die Sache zu bekommen, kann man den unverdrehten Würfel ins array I eintragen:
I = [ ['orange', 'red', 'blue'] ,
['green', 'red', 'blue'] ,
['orange', 'white', 'blue'] ,
['green', 'white', 'blue'] ,
['orange', 'red', 'purple'] ,
['green', 'red', 'purple'] ,
['orange', 'white', 'purple'] ,
['green', 'white', 'purple'] ]
und im letzten Absatz die beiden Zeilen:
print V, ln, W, ln
und
R()
mit einer kleinen Raute versehen:
#print V, ln, W, ln
#R()
Sodann lasse man sich zB. die obere sY-Schicht anzeigen - einfach folgende code-Zeilen an das script anhängen:
print sY[0]
und führe eine Drehung dieser Schicht aus:
E(4)
Dann lasse man sich wieder diese Schicht anzeigen:
print ln, sY[0]
Diese Zeilen:
print W, ln, sY[0], ln
E(4)
print W, ln, sY[0], ln
E(5)
print W, ln, sY[0], ln
geben den Würfel und die obere sY-Schicht aus, drehen einmal, geben die Änderung aus,
drehen wieder zurück, und zeigen das Endergebnis, nämlich wieder den Ausgangswürfel
sowie die obere sY-Schicht in Ausgangsstellung.
postscriptum 2:
Beinah hätt' ich's vergessen - ein paar Buchempfehlungen:
Python für kids
Gregor Lingl
mitp-Verlag
ISBN: 3-8266-0951-4
Python Cookbook
Edited by Alex Martelli & David Ascher
O'Reilly
ISBN: 0-596-00167-3
Python and Tkinter Programming
John E. Grayson
Manning Publications Co.
ISBN: 1-884777-81-3
Python Programming Patterns
Thomas W. Christopher
Prentice Hall PTR
ISBN: 0-13-040956-1
Python Web Programming
Steve Holden with David Beazley
New Riders
ISBN: 0-7357-1090-2
Jetzt lerne ich Python
Ivan van Laningham
Markt+Technik Verlag
ISBN 3-8272-5843-X
Dieses letzte Buch ist zwar (in der mir vorliegenden Fassung - Ausgabe von 2000)
ziemlich veraltet und eh - nun ja, ausgeklinkt - dafür aber absolut liebenswert.
