Prüfen Sie, ob drei Buchstaben einen „Godel-Escher-Bach-Würfel“ bilden können.

29

Diese Frage ist vom Cover des Buches "Godel, Escher, Bach" inspiriert:

Die Herausforderung besteht darin, eine Funktion zu schreiben, die angibt, ob drei gegebene Buchstaben eine 3D-Skulptur erzeugen können, die von drei Seiten gelesen werden kann.

In dieser Übung können Sie nur 26 5px * 5px-Bitmaps verwenden:

Oder binär (von A bis Z):

01110  11110  01111  11110  11111  11111  11111  10001  11111  11111  10001  10000  10001  10001  01110  11110  01110  11110  01111  11111  10001  10001  10001  10001  10001  11111
10001  10001  10000  10001  10000  10000  10000  10001  00100  00100  10010  10000  11011  11001  10001  10001  10001  10001  10000  00100  10001  10001  10001  01010  01010  00010
10001  11110  10000  10001  11100  11110  10011  11111  00100  00100  11100  10000  10101  10101  10001  10001  10001  11111  01110  00100  10001  01010  10001  00100  00100  00100
11111  10001  10000  10001  10000  10000  10001  10001  00100  10100  10010  10000  10001  10011  10001  11110  10011  10010  00001  00100  10001  01010  10101  01010  00100  01000
10001  11110  01111  11110  11111  10000  11111  10001  11111  11100  10001  11111  10001  10001  01110  10000  01111  10001  11110  00100  01110  00100  01010  10001  00100  11111

Die Skulptur besteht aus drei Buchstaben in der folgenden Reihenfolge:

  • beschriften sie eine auf die spitze,
  • Buchstabe zwei auf der linken Seite
  • Buchstabe drei rechts
  • Der untere Teil des ersten Buchstabens ist an den oberen Teil des zweiten Buchstabens gebunden.

Beispiel:

Ihre Funktion akzeptiert möglicherweise drei Großbuchstaben (drei Zeichen oder drei Zeichenfolgen aus einem Buchstaben) als Eingabe und gibt einen Booleschen Wert (true / false oder 0/1) aus, der angibt, ob die entsprechende Skulptur vorhanden sein kann.

Beispiel:

f("B","E","G") // true  (because if you "sculpt out" B on top + E on the left + G on the right, and watch the three sides of the sculpture, you'll see exactly B, E and G as they are defined)
f("B","G","E") // false (because if you "sculpt out" B on top + G on the left + E on the right, and watch the three sides of the sculpture, you won't see a complete G and a complete E. Their shapes bother each other)

NB: Sie können true zurückgeben, auch wenn die Skulptur "fliegende Pixel" enthält (Würfel oder eine Gruppe von Würfeln, die an nichts gebunden sind).

Es gelten Standardlücken.

Genauer gesagt, Sie können keine externen Eingaben neben den drei Buchstaben verwenden und die 17576 möglichen Antworten in Ihrem Quellcode nicht fest codieren

Kürzeste Antwort in Zeichen in einer Sprache gewinnt!

Habe Spaß :)

xem
quelle
Ja, es ist das MU-Puzzle, das mich dazu gebracht hat, das Buch zu entdecken, und es ist das Cover des Buches, das mich dazu gebracht hat, über diese Herausforderung nachzudenken. Gibt es ein Problem? War das ein Teil Ihrer 18-Loch-Sache?
14.
2
Es wäre eine gute Option gewesen, Loch 1 zu ersetzen.;) ... Egal, wenn irgendetwas meine Schuld ist, dass ich nicht früher etwas auf die Beine gestellt habe. Es ist eine wirklich anständige Herausforderung, +1!
Martin Ender,
Können wir die Daten, die die Buchstabenformen definieren, aus einer externen Datei abrufen oder muss dies auch in der Quelle enthalten sein?
CaesiumLifeJacket
Ihr binäres B hat 0 in der oberen linken Ecke, nicht 1.
Calvins Hobbys

Antworten:

13

Mathematica 423

Ich habe einen Abschnitt namens "So funktioniert das Blockieren" hinzugefügt.

Ungolfed

(* Die Binärdaten des Alphabets werden als einzelne Zeichenfolge in gespeichert s. varsImportiert sie und konvertiert sie in ein Array.)

vars=IntegerDigits[#,10,5]&/@Transpose[ImportString[s,"Table"]];
get[char_]:=(ToCharacterCode[char]-64)[[1]];
cube=Flatten[Table[{i,j,k},{i,5},{j,5},{k,5}],2];

(* character slice along axis *)
slice[char_,layer_,axis_,bit_]:=Insert[(Reverse@#),layer,axis]&/@Position[Reverse@vars[[get[char]]],bit]

(* cuboid assembly  *)
charBlocks[{char_,axis_,bit_}]:=Flatten[Table[slice[char,k,axis,bit],{k,5}],1]

(* letters are those whose HOLES should be sculped out of the full cube *)
sculpturePoints[letters_(*{char_,axis_,bit_}*)]:=Complement[cube,Union[Join@@(charBlocks/@letters(*{char,axis,bit}*))]];

collapse[letters_(*{char_,axis_,bit_}*),axis_]:=Union[Reverse/@(Delete[#,axis]&/@sculpturePoints[letters(*{char,axis,bit}*)])](*/.{x_,y_}\[RuleDelayed] {6-x,y}*)

vQ[l_]:=collapse[l,3]==collapse[{l[[1]]},3]\[And]collapse[l,2]==collapse[{l[[2]]},2]\[And]collapse[l,1]==collapse[{l[[3]]},1]

validQ@l_:= vQ[{{l[[1]],3,0},{l[[2]],2,0},{l[[3]],1,0}}]


perspective[letts_,view_:1]:=
Graphics3D[{AbsolutePointSize[10],Cuboid/@sculpturePoints[letts]},
ImageSize-> 120,
ViewPoint-> Switch[view,1,{0,0,\[Infinity]},2,{0,-\[Infinity],0},3,{\[Infinity],0,0},4,Top,5,Front,6,Right,True,{0,0,\[Infinity]}],
PlotLabel-> Switch[view,1,"top orthogonal view",2,"front orthogonal view",3,"right orthogonal view",4,"top close-up view",5,"front close-up view",6,"right close-up view"],
ImagePadding->10]

Beispiel

Ist der Würfel {"B", "G", "E"}gültig? (Werden die drei Buchstaben richtig auf die Wände projizieren?)

validQ[{"B", "G", "E"}]

Falsch

Abbildungen

Die folgenden Abbildungen zeigen, wie BGE gerendert wird. Die obere Figurenreihe nimmt orthogonale Perspektiven ein, als ob der Betrachter in unendlichen Abständen vom Würfel positioniert wäre. Die untere Reihe zeigt, wie die Blöcke aus der Nähe aussehen würden. Die 3D-Figuren können manuell gedreht werden, um genau zu prüfen, wo die einzelnen Einheitswürfel positioniert sind.

Ein Problem tritt mit dem Buchstaben "G" auf. Es gibt nichts, was die Serife mit dem Rest des Briefes verbindet.

pts = {{"B", 3, 0}, {"G", 2, 0}, {"E", 1, 0}}
GraphicsGrid@Partition[Table[perspective[pts, view], {view, 1, 6}], 3]

bge


BEG sollte jedoch gut funktionieren.

 validQ[{"B", "E", "G"}]

Wahr

pts2 = {{"B", 3, 0}, {"E", 2, 0}, {"G", 1, 0}}
GraphicsGrid@Partition[Table[perspective[pts2, view], {view, 1, 6}], 3]

bitten


Wie funktioniert das Blockieren?

Bitte entschuldigen Sie, wenn dies offensichtlich erscheint, aber vielleicht möchten einige Leute visualisieren, wie Buchstaben sich gegenseitig stören und ihre 3D-Pixel aufheben.

Lassen Sie uns im BGE-Cube-Rendering verfolgen, was mit dem Buchstaben G geschieht.

Wir werden dem Voxel (3D-Pixel oder Einheitswürfel) unten besondere Aufmerksamkeit schenken . Das ist das Pixel, das im BGE-Würfel verschwindet. Dies ist das Pixel, das Zeile 4, Spalte 5 im Bit-Array und im entsprechenden Array-Diagramm entspricht.

blockieren 1


In der xy-Ebene entspricht das Pixel der grauen Scheibe am Punkt (5,2). Da wir aber in 3D arbeiten werden, müssen wir die 5 Positionen in der Welle von (5,1,2) bis (5,5,2) berücksichtigen. Wenn eines dieser Pixel die Bildhauerei durch die Buchstaben B und E überlebt, können wir das interessierende Pixel in der 3D-Projektion an der Wand sehen.

blockieren 2


Buchstaben stören, wenn Pixel aus dem durchgehenden Block entfernt werden. Links stellt der schwarze Pfeil das Herausschneiden von Pixeln dar, das dem Bit unten rechts entspricht. es hat den Wert 0 für den Buchstaben B. Durch Herausschnitzen wird das Pixel bei (5,1,2) sowie die direkt darüber und darunter liegenden Pixel entfernt. Es müssen noch vier Pixel berücksichtigt werden.

blockieren 3

Wie der rechte Bereich zeigt, formt der Buchstabe E die verbleibenden interessierenden Pixel (5,2,2) (5,3,2), (5,4,2) und (5,5,2) aus. (Dies ist auf die Tatsache zurückzuführen, dass der Buchstabe E in der vierten Zeile von Spalte 2 bis Spalte 5 Bits gleich 0 enthält.) Infolgedessen verbleibt kein einziges Pixel unter denjenigen, die benötigt wurden, um die Schattierung an Punkt (5) sicherzustellen , 2) an der gegenüberliegenden Wand (für den Buchstaben G). Stattdessen erscheint ein heller Fleck, der einem Loch im Buchstaben G entspricht! Der Würfel BGE ist nicht gut, weil er G falsch darstellt.

Golf 423 Zeichen

Die Funktion hatte hdieselbe Funktion wie validQim unGolfed-Code. Die Rendering-Funktion perspectiveist nicht enthalten, da sie nicht zur Herausforderung beiträgt und von ihr nicht benötigt wird.

x=Reverse;q=Flatten;
g@c_:=(ToCharacterCode[c]-64)[[1]];
r[{c_,a_,b_}]:=q[Table[Insert[(x@#),k,a]&/@Position[x@(IntegerDigits[#,10,5]&/@
Transpose[ImportString[s,"Table"]])[[g[c]]],b],{k,5}],1]
p@l_:=Complement[q[Table[{i,j,k},{i,5},{j,5},{k,5}],2],Union[Join@@(r/@l)]];
w[l_,a_]:=Union[x/@(Delete[#,a]&/@p[l])]
v@l_:=w[l,3]==w[{l[[1]]},3]\[And]w[l,2]==w[{l[[2]]},2]\[And]w[l,1]==w[{l[[3]]},1]

h@l_:= v[{{l[[1]],3,0},{l[[2]],2,0},{l[[3]],1,0}}]
DavidC
quelle
Woah, diese 3D-Ansichten sind sehr ordentlich! Sind Sie sicher, dass der letzte Codeblock "UnGolfed" ist? Es scheint mir Golf zu spielen. :)
Xem
Du hast Recht. Der letzte Block ist Golf. Ich habe die Überschrift korrigiert. Eine coole Sache an den 3D-Ansichten ist, dass sie interaktiv sind: Drehen und Zoomen können mit der Maus durchgeführt werden.
DavidC
Übrigens, nach meiner Zählung gibt es 564 gültige Würfel unter den 15600 möglichen Permutationen.
DavidC
Das ist eine nette Information. Wie lange haben Sie gebraucht, um das zu berechnen? auch 26 * 26 * 26 = 17576, nicht 15600. Oder vermisse ich etwas?
XEM
Ich habe Permutationen verwendet, keine Tupel. dh keine wiederholten Buchstaben. 26 * 25 * 24 = 15600. Es dauerte 21 Sekunden, um die 564 Fälle zu finden.
DavidC
12

Prolog, 440 , 414

:- encoding(utf8).
i(I) :- between(0,4,I).
h(T,L,R,X,Y,Z) :- i(X),i(Y),i(Z),I is 4-X,c(T,Z,I),c(L,Z,Y),c(R,X,Y).
f(T,L,R) :- forall((i(U),i(V),I is 4-V),((\+c(T,U,V);h(T,L,R,I,Y,U)),(\+c(L,U,V);h(T,L,R,X,V,U)),(\+c(R,U,V);h(T,L,R,U,V,Z)))).
c(C,X,Y) :- char_code(C,N),i(X),i(Y),Z is X+5*Y+25*(N-65),I is floor(Z/15),O is (Z mod 15),string_code(I,"䙎㹟䘑߯硁䙏縑ԁࠟя摟䠑䠑ᐑ粤Ⴟ䔅┉ё籁垑䙑曓䗱㩑䙏㡏晑䘞䕟㡞縐Ⴄ䙄㩑⩑䒪噑⩊䕤ᅱ粤ࢨ?",V),1 is (V-32)>>O/\1.

Das Programm heißt so:

?- f('B','E','G').
true.
?- f('B','G','E').
false.

Prologschien eine gute Wahl zu sein, da es einfach ist, das Problem in der Logik erster Ordnung darzustellen. Auch Prologbietet starke Funktionalität für diese Art von Problem zu lösen.

Da der Code jedoch Golf ist, sollte ich eine Erklärung hinzufügen.

Leicht golfene Version

:- encoding(utf8).
i(I) :- between(0,4,I).
t(C,X,Z) :- I is 4-X,c(C,Z,I).
l(C,Y,Z) :- c(C,Z,Y).
r(C,X,Y) :- c(C,X,Y).
h(T,L,R,X,Y,Z) :- i(X),i(Y),i(Z),t(T,X,Z),l(L,Y,Z),r(R,X,Y).
u(T,L,R) :- forall((i(U),i(V),I is 4-V,c(T,U,V)),h(T,L,R,I,Y,U)).
v(T,L,R) :- forall((i(U),i(V),c(L,U,V)),h(T,L,R,X,V,U)).
w(T,L,R) :- forall((i(U),i(V),c(R,U,V)),h(T,L,R,U,V,Z)).
f(T,L,R) :- u(T,L,R),v(T,L,R),w(T,L,R).
c(C,X,Y) :- char_code(C,N),i(X),i(Y),Z is X+5*Y+25*(N-65),I is floor(Z/15),O is (Z mod 15),string_code(I,"䙎㹟䘑߯硁䙏縑ԁࠟя摟䠑䠑ᐑ粤Ⴟ䔅┉ё籁垑䙑曓䗱㩑䙏㡏晑䘞䕟㡞縐Ⴄ䙄㩑⩑䒪噑⩊䕤ᅱ粤ࢨ?",V),1 is (V-32)>>O/\1.

Die Koordinaten, die den Pixeln auf jeder Seite der Würfel entsprechen, können leicht in ein 3D-Koordinatensystem umgewandelt werden. I verwenden T, Lund Rfür die oben (1), links (2) und die rechte (3) Seite. uund vwerden für die Koordinaten in den Bildern verwendet:

  • T :(u,v) -> (4-v, ?, u)
  • L :(u,v) -> (?, v, u)
  • R :(u,v) -> (u, v, ?)

Die Ergebnisse für jedes aktive (dh schwarze) Pixel werden zu einer Reihe von "3D-Pixeln" kombiniert, die aktiviert werden können, ohne das Aussehen des Objekts von dieser Seite aus zu verändern. Der Schnittpunkt der Sätze für jede Seite sind alle 3D-Pixel, die aktiviert werden können, ohne dass Pixel hinzugefügt werden müssen, die die Ansicht behindern würden (dh wenn Sie von mindestens einer Seite aus sehen, würde sich ein Pixel befinden, das nicht vorhanden sein sollte).

Es muss nur noch für jede Seite überprüft werden, ob sich in der Kreuzung ein Pixel befindet, das die Ansicht blockiert, sofern dies erforderlich ist.

Dies führt zu den Prädikaten im Programm:

  • f : führt die Endkontrolle durch; Nimmt die Buchstaben oben, links und rechts
  • u , v und w : Überprüft, ob für jedes Pixel, das auf der Seite aktiv ist, ein 3D-Pixel in der Schnittmenge vorhanden ist, das die Ansicht blockiert
  • h : Überprüft, ob ein Pixel in der Kreuzung vorhanden ist
  • t , l , r : Prüft, ob ein 3D-Pixel von oben, links und rechts blockiert werden kann.
  • c : Überprüft das Pixel im Bild eines Buchstabens. Die Zeichenfolge darin sieht vielleicht etwas seltsam aus, aber es ist nur eine kompakte Art, die Bilddaten zu speichern. Es ist einfach eine Zeichenfolge mit den folgenden Werten (Hex-Notation):

    [464e,3e5f,4611,7ef,7841,464f,7e11,501,81f,44f,645f,4811,4811,1411,7ca4,10bf,4505,2509,451,7c41,5791,4651,66d3,45f1,3a51,464f,384f,6651,461e,455f,385e,7e10,10a4,4644,3a51,2a51,44aa,5651,2a4a,4564,1171,7ca4,8a8,3f]
    

    Jedes dieser Zeichen speichert die Daten für 3 Pixelzeilen in Buchstabenbildern (= 15 Pixel). Die Pixel werden auch neu angeordnet, damit die Daten an einem Ort gespeichert und nicht wie die Daten des OP auf mehrere Zeilen aufgeteilt werden.

Mathematische Formulierung

Formel

Eingabedaten

Formel

Umwandlung von Pixel in einem Zeichen in eine Menge von 3D-Pixeln, die die Ansicht für dieses Pixel verdecken

Formel

Formel

Formel

Pixel, die sicher hinzugefügt werden können (ohne die Ansicht an der falschen Stelle zu beeinträchtigen)

Formel

Überprüft für jede Seite, ob die Pixel, die blockiert werden müssen, sicher blockiert werden können

Formel

Formel

Formel

Scheckkombination für jede Seite

Formel

Fabian
quelle
1
Ich ... äh ... was? Ich finde das unverständlich. (+1)
siehe auch
Heilig ... ich gehe ins Bett ...
BrunoJ
Beeindruckend! Vielen Dank für diese Antwort
xem
1
Nett. Übrigens denke ich, dass der Prozess mit einem festen kubischen Block beginnt. (Sie denken anscheinend, dass Sie Pixel hinzufügen, wo vorher keine waren.) Jeder Buchstabe entfernt einige 3D-Pixel aus diesem Block. Interferenz entsteht also, wenn ein benachbarter Buchstabe Pixel entfernt, die ein Buchstabe "behalten" wollte. Die Interferenz rührt eher von "fehlenden Pixeln" als von zusätzlichen Pixeln her.
DavidC
9

J - 223 197 191 char

Eine Funktion, die eine Drei-Zeichen-Liste als Argument verwendet.

(_5#:\".'1b',"#:'fiiifalllvhhhheehhhvhhllvgkkkvnlhhvv444vhhvhhggvhjha44v1111vv848vv248vehhheciiivfjhhedmkkvilll9ggvggu111uo616ou121uha4ahg878ghpljh')((-:0<+/"1,+/"2,:+/)*`(*"1/)/)@:{~_65+3&u:

Dieser Golf beruht in hohem Maße auf einer leistungsstarken Funktion von J namens Rank , mit der wir die Operationen "Sculpt-Out" und "Watch-Side-Of" fast kostenlos ausführen können. Um es ein wenig zu vereinfachen, bezieht sich der Rang auf die Dimensionalität eines Substantivs oder der natürlichen Argumente eines Verbs.

J hat mehrdimensionale Arrays, und es ist offensichtlich, dass ein 3D-Array beispielsweise als einzelnes 3D-Array oder als Liste von Matrizen oder als 2D-Array von Vektoren oder als 3D-Array von Skalaren interpretiert werden kann. So kann jede Operation in J ihre Anwendung so steuern, dass sie über das Argument verteilt wird. Rang 0 bedeutet, dass sie auf die Skalare angewendet werden, Rang 1 bedeutet, dass sie auf die Vektoren angewendet werden und so weiter.

   1 + 2 + 3 + 4  NB. add these things together
10
   +/ 1 2 3 4     NB. sum the list by adding its items together
10
   i. 3 4         NB. 2D array, with shape 3-by-4
0 1  2  3
4 5  6  7
8 9 10 11
   +/"2 i. 3 4    NB. add the items of the matrix together
12 15 18 21
   0 1 2 3 + 4 5 6 7 + 8 9 10 11    NB. equivalent
12 15 18 21
   +/"1 i. 3 4    NB. now sum each vector!
6 22 38
   +/"0 i. 3 4    NB. now sum each scalar!
0 1  2  3
4 5  6  7
8 9 10 11

Dies wird sehr effektiv, wenn Sie dyadische Funktionen (mit zwei Argumenten) einführen. Wenn die Formen der beiden Argumente (nach Berücksichtigung des Rangs) akzeptabel sind, führt J eine implizite Schleife durch:

   10 + 1             NB. scalar addition
11
   10 20 30 + 4 5 6   NB. vector addition, pointwise
14 25 36
   10 + 4 5 6         NB. looping! 
14 15 16
   10 20 + 4 5 6      NB. shapes do not agree...
|length error
|   10 20    +4 5 6

Wenn alle Ihre Formen zufriedenstellend sind und Sie den Rang selbst festlegen können, gibt es viele Möglichkeiten, Argumente zu kombinieren. Hier zeigen wir einige Möglichkeiten, wie Sie eine 2D-Matrix und ein 3D-Array multiplizieren können.

   n =: i. 5 5
   n
 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
   <"2 n *"2 (5 5 5 $ 1)  NB. multiply by 2-cells
+--------------+--------------+--------------+--------------+--------------+
| 0  1  2  3  4| 0  1  2  3  4| 0  1  2  3  4| 0  1  2  3  4| 0  1  2  3  4|
| 5  6  7  8  9| 5  6  7  8  9| 5  6  7  8  9| 5  6  7  8  9| 5  6  7  8  9|
|10 11 12 13 14|10 11 12 13 14|10 11 12 13 14|10 11 12 13 14|10 11 12 13 14|
|15 16 17 18 19|15 16 17 18 19|15 16 17 18 19|15 16 17 18 19|15 16 17 18 19|
|20 21 22 23 24|20 21 22 23 24|20 21 22 23 24|20 21 22 23 24|20 21 22 23 24|
+--------------+--------------+--------------+--------------+--------------+
   <"2 n *"1 (5 5 5 $ 1)  NB. multiply by vectors
+---------+---------+--------------+--------------+--------------+
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
+---------+---------+--------------+--------------+--------------+
   <"2 n *"0 (5 5 5 $ 1)  NB. multiply by scalars
+---------+---------+--------------+--------------+--------------+
|0 0 0 0 0|5 5 5 5 5|10 10 10 10 10|15 15 15 15 15|20 20 20 20 20|
|1 1 1 1 1|6 6 6 6 6|11 11 11 11 11|16 16 16 16 16|21 21 21 21 21|
|2 2 2 2 2|7 7 7 7 7|12 12 12 12 12|17 17 17 17 17|22 22 22 22 22|
|3 3 3 3 3|8 8 8 8 8|13 13 13 13 13|18 18 18 18 18|23 23 23 23 23|
|4 4 4 4 4|9 9 9 9 9|14 14 14 14 14|19 19 19 19 19|24 24 24 24 24|
+---------+---------+--------------+--------------+--------------+

Sie werden feststellen, dass dies nicht in die Buchstaben in der gewünschten Ausrichtung eingraviert, sondern nur eingeschrieben wird, was für die Ranglogik praktisch ist. Wenn wir die Buchstaben nicht umkehren oder drehen, bevor wir sie anwenden, funktioniert es nicht richtig. Das Korrigieren solcher Dinge würde jedoch wertvolle Zeichen in Anspruch nehmen. Stattdessen werden wir die Buchstaben so codieren, dass, wenn J sie auf natürliche Weise einschneidet, sich einige Dreifachgesichter in den richtigen Ausrichtungen und relativen Positionen befinden. Es stellt sich heraus, dass die kürzeste Lösung darin besteht, alle Briefbögen um eine Vierteldrehung gegen den Uhrzeigersinn zu drehen. Unter Berücksichtigung der dritten Dimension von J zur Darstellung der Achse von vorne nach hinten zeigt das grobe Diagramm unten, warum dieses Schema funktioniert.

Visualisierung des Würfels Abbildung A: Die drei Seiten des Würfels, in den J schnitzt. Abbildung B: Die drei Seiten, auf denen die Buchstaben wie in der Frage dargestellt ausgerichtet sind.

Diese Wahl bei der Codierung spart 12 Zeichen gegenüber der vorherigen Methode und macht das Ganze ordentlicher. Der eigentliche Golfspieler erschafft den Würfel aus "1und "2schnitzt mit etwas Funky-Logik, aufgrund einer nicht zusammenhängenden Optimierung.

Dann müssen wir die Gesichter überprüfen. Da wir den Block als 1 und 0 kodieren, können wir entlang jeder Achse in der Art und Weise zusammenzufassen nur wollen wir (das sind die +/"1, +/"2und +/Bits), passen Sie auf booleans ( 0<), und sie dann auf die ursprüngliche 90 ° alle direkt vergleichen - umgedrehte Buchstaben.

Das Komprimierungsschema codiert jede 5px-Zeile jedes Buchstabens als die Basis 32-Darstellung einer Binärzahl. Durch Ausnutzen einer Reihe syntaktischer Zucker und Überladungen von Operatoren ".'1b',"#:ist dies der kürzeste Weg, um die Liste der Zeichen in Basis-36-Zahlen umzuwandeln. Nun, technisch gesehen, Basis 32, aber J denkt, es ist unärgerlich, also wer zählt?

Verbrauch ist unten. Beachten Sie, dass Strings Zeichen-Arrays in J sind, sodass eine Liste 'A','B','C'mit drei Elementen 'ABC'kurz geschrieben werden kann . Auch Boolesche Werte sind 1/0.

   NB. can be used inline...
   (_5#:\".'1b',"#:'fiiifalllvhhhheehhhvhhllvgkkkvnlhhvv444vhhvhhggvhjha44v1111vv848vv248vehhheciiivfjhhedmkkvilll9ggvggu111uo616ou121uha4ahg878ghpljh')((-:0<+/"1,+/"2,:+/)*`(*"1/)/)@:{~_65+3&u:'BEG'
1
   NB. or assigned to a name
   geb=:(_5#:\".'1b',"#:'fiiifalllvhhhheehhhvhhllvgkkkvnlhhvv444vhhvhhggvhjha44v1111vv848vv248vehhheciiivfjhhedmkkvilll9ggvggu111uo616ou121uha4ahg878ghpljh')((-:0<+/"1,+/"2,:+/)*`(*"1/)/)@:{~_65+3&u:
   geb 'BGE'
0
algorithmshark
quelle
4

Python, 687 682 671

import itertools as t,bz2
s=range(5)
c=dict([(i,1)for i in t.product(*3*[s])])
z=dict([(chr(i+65),[map(int,bz2.decompress('QlpoOTFBWSZTWXndUmsAATjYAGAQQABgADABGkAlPJU0GACEkjwP0TQlK9lxsG7aomrsbpyyosGdpR6HFVZM8bntihQctsSiOLrWKHHuO7ueAyiR6zRgxbMOLU2IQyhAEAdIJYB0ITlZwUqUlAzEylBsw41g9JyLx6RdFFDQEVJMBTQUcoH0DEPQ8hBhXBIYkXDmCF6E/F3JFOFCQed1Saw='.decode('base64')).split('\n')[j].split()[i])for j in s])for i in range(26)])
def m(a,g):
 for e in c:c[e]&=g[e[a]][e[a-2]]
def f(a):
 g=map(list,[[0]*5]*5)
 for e in c:g[e[a]][e[a-2]]|=c[e]
 return g
r=lambda g:map(list,zip(*g)[::-1])
def v(T,L,R):T,L,R=r(r(z[T])),r(z[L]),z[R];m(1,T);m(2,L);m(0,R);return(T,L,R)==(f(1),f(2),f(0))

Rufen Sie an mit v:

v('B','E','G') => True
v('B','G','E') => False

Alles unten ist von meiner vorherigen ungolfed Version, die hilfreiche Zeichenfunktionen enthält. Fühlen Sie sich frei, es als Ausgangspunkt zu verwenden.

import string as s
import itertools as t

az = """01110  11110  01111  11110  11111  11111  11111  10001  11111  11111  10001  10000  10001  10001  01110  11110  01110  11110  01111  11111  10001  10001  10001  10001  10001  11111
10001  10001  10000  10001  10000  10000  10000  10001  00100  00100  10010  10000  11011  11001  10001  10001  10001  10001  10000  00100  10001  10001  10001  01010  01010  00010
10001  11110  10000  10001  11100  11110  10011  11111  00100  00100  11100  10000  10101  10101  10001  10001  10001  11111  01110  00100  10001  01010  10001  00100  00100  00100
11111  10001  10000  10001  10000  10000  10001  10001  00100  10100  10010  10000  10001  10011  10001  11110  10011  10010  00001  00100  10001  01010  10101  01010  00100  01000
10001  11110  01111  11110  11111  10000  11111  10001  11111  11100  10001  11111  10001  10001  01110  10000  01111  10001  11110  00100  01110  00100  01010  10001  00100  11111""".split('\n')

dim = range(len(az))
az = dict([(c, [map(int, az[j].split()[i]) for j in dim]) for i, c in enumerate(s.uppercase)])
cube = dict([(i, 1) for i in t.product(*3*[dim])])

def mask(axis, grid):
    for c in cube:
        if not grid[c[axis]][c[axis - 2]]:
            cube[c] = 0

def face(axis):
    grid = [[0 for j in dim] for i in dim]
    for c in cube:
        if cube[c]:
            grid[c[axis]][c[axis - 2]] = 1
    return grid

def rot(grid):
    return map(list, zip(*grid)[::-1])

def draw(grid, filled='X', empty=' '):
    s = ''
    for y in dim:
        for x in dim:
            s += filled if grid[y][x] else empty
        s += '\n'
    print s

def drawAll():
    print 'TOP:\n'
    draw(rot(rot(face(1))))
    print 'LEFT:\n'
    draw(rot(rot(rot(face(2)))))
    print 'RIGHT:\n'
    draw(face(0))

def valid(top, left, right):
    top, left, right = rot(rot(az[top])), rot(az[left]), az[right]
    mask(1, top)
    mask(2, left)
    mask(0, right)
    return top == face(1)and left == face(2) and right == face(0)

letters = 'BEG'

if valid(*letters):
    print letters, 'is valid.\n'
else:
    print letters, 'is not valid!\n'

drawAll()

Rufen Sie validan, um es auszuführen:

valid('B', 'E', 'G') #returns True
valid('B', 'G', 'E') #returns False

Im Moment ist der Code eingerichtet, um die Gültigkeit B E Gder resultierenden Gesichter zu testen und auszudrucken:

BEG is valid.

TOP:

XXXX 
X   X
XXXX 
X   X
XXXX 

LEFT:

XXXXX
X    
XXX  
X    
XXXXX

RIGHT:

XXXXX
X    
X  XX
X   X
XXXXX

Wenn B G Ewir es ausführen, können wir sehen, dass das G falsch ist:

BGE is not valid!

TOP:

XXXX 
X   X
XXXX 
X   X
XXXX 

LEFT:

XXXXX
X    
X  XX
X    
XXXXX

RIGHT:

XXXXX
X    
XXX  
X    
XXXXX
Calvins Hobbys
quelle
Wow, gute Arbeit! +1 für drawAll und die Vollständigkeit der Antwort. +1 für die Verwendung eines so kurzen Algorithmus. <3 it
xem
@xem Danke! Ich habe endlich Golf gespielt. Obwohl ich nicht herausfinden konnte, wie man bz2 dazu bringt, Unicode-Zeichen zu dekomprimieren.
Calvins Hobbys
+1. Gute Antwort. Hoffe, dass mehr Leute Golfplätze, die aus kleineren Golfplätzen bestehen, positiv bewerten, denn das kostet wirklich Mühe.
Vectorized
1
g=[[0 for j in s]for i in s]kann auf gekürzt werden g=map(list,[[0]*5]*5). Sie können auch Einrücken Blöcke vermeiden , wenn sie eine einzelne Anweisung sind: if c[e]:g[e[a]][e[a-2]]=1.
Bakuriu
@ Bakuriu und Bitpwner, danke für die Vorschläge und Änderungen :)
Calvin Hobbies
1

Python 3 + Numpy, 327C

from numpy import*
B=hstack([ord(x)>>i&1for x in'옮弟ჹ羂옱쏷)ជ࿂︹缘龌ℿ쓥剴ℌᾄ起츱ꎚㆋឺ௣옮忬⧼ﯠႄ挒⺌ꕆ豈ꪱ袨冊䈑∾Ϣ'for i in range(16)])[:-6].reshape(26,5,5)
T=transpose
def f(*X):
 A=ones((5,5,5));F=list(zip([A,T(A,(1,0,2)),T(fliplr(A),(2,0,1))],[B[ord(x)-65]for x in X]))
 for r,f in F:r[array([f]*5)==0]=0
 return all([all(r.sum(0)>=f)for r,f in F])

Diese Golflösung benötigt eine externe Bibliothek, Numpy, die sehr beliebt ist, daher denke ich, dass es in Ordnung ist, sie zu verwenden.

Die Unicode-Zeichenfolge besteht aus 41 Zeichen, während in der Prolog-Antwort von @ fabian das Gleiche gilt: 44.

Das interessanteste hier ist, dass die Indizierung von Numpy-Array. In a[ix], ixkann als eine Boolesche Array mit der gleichen Form sein a. Es ist das gleiche wie zu sagen a[i, j, k] where ix[i, j, k] == True.

Ungolfed Version

import numpy as np
table = '옮弟ჹ羂옱쏷)ជ࿂︹缘龌ℿ쓥剴ℌᾄ起츱ꎚㆋឺ௣옮忬⧼ﯠႄ挒⺌ꕆ豈ꪱ袨冊䈑∾Ϣ'

def expand_bits(x):
    return [ord(x) >> i & 1 for i in range(16)]

# B.shape = (26, 5, 5), B[i] is the letter image matrix of the i(th) char
B = np.hstack([expand_bits(x) for x in table])[:-6].reshape(26, 5, 5)

def f(*chars):
    """
    cube:    ----------   axis:           
            /         /|      --------->2  
           /   1     / |     /|            
          /         /  |    / |            
         /         /   |   /  |            
        |---------|  3 |  v   |           
        |         |    /  1   |           
        |    2    |   /       v          
        |         |  /        0         
        |         | /                  
        -----------
    """
    cube = np.ones((5, 5, 5))
    cube_views = [
        cube,
        cube.transpose((1, 0, 2)),  # rotate to make face 2 as face 1
        np.fliplr(cube).transpose(2, 0, 1),  # rotate to make face 3 as face 1
    ]
    faces = [B[ord(char) - ord('A')] for char in chars]
    # mark all white pixels as 0 in cube
    for cube_view, face in zip(cube_views, faces):
        # extrude face to create extractor
        extractor = np.array([face] * 5)
        cube_view[extractor == 0] = 0

    return np.all([
        # cube_view.sum(0): sum along the first axis
        np.all(cube_view.sum(0) >= face)
        for cube_view, face in zip(cube_views, faces)
    ])

Skript zum Komprimieren der Tabelle

import numpy as np

def make_chars():
    s = """
01110  11110  01111  11110  11111  11111  11111  10001  11111  11111  10001  10000  10001  10001  01110  11110  01110  11110  01111  11111  10001  10001  10001  10001  10001  11111
10001  10001  10000  10001  10000  10000  10000  10001  00100  00100  10010  10000  11011  11001  10001  10001  10001  10001  10000  00100  10001  10001  10001  01010  01010  00010
10001  11110  10000  10001  11100  11110  10011  11111  00100  00100  11100  10000  10101  10101  10001  10001  10001  11111  01110  00100  10001  01010  10001  00100  00100  00100
11111  10001  10000  10001  10000  10000  10001  10001  00100  10100  10010  10000  10001  10011  10001  11110  10011  10010  00001  00100  10001  01010  10101  01010  00100  01000
10001  11110  01111  11110  11111  10000  11111  10001  11111  11100  10001  11111  10001  10001  01110  10000  01111  10001  11110  00100  01110  00100  01010  10001  00100  11111
""".strip().split('\n')
    bits = np.zeros((26, 5, 5), dtype=np.bool)
    for c_id in range(26):
        for i in range(5):
            for j in range(5):
                bits[c_id, i, j] = s[i][j + c_id * 7] == '1'
    bits = np.hstack([bits.flat, [0] * 7])
    bytes_ = bytearray()
    for i in range(0, len(bits) - 8, 8):
        x = 0
        for j in range(8):
            x |= bits[i + j] << j
        bytes_.append(x)
    chars = bytes_.decode('utf16')
    return chars
Strahl
quelle