35
\$\begingroup\$

This question is inspired by the cover of the book "Godel, Escher, Bach":

The challenge here is to write a function that tells if three given letters can produce a 3D sculpture that can be read from three sides.

For this exercise, the only letters you can use are 26 5px * 5px bitmaps:

Or in binary (A to 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

The sculpture is formed by three letters in the following order:

  • letter one on top,
  • letter two on the left
  • letter three on the right
  • the bottom of letter one is bound to the top of the letter two.

Example:

Your function may accept as input three uppercase letters (three chars or three strings of one letter), and output a boolean (true/false or 0/1) telling if the corresponding sculpture can exist.

Example:

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: you may return true even if the sculpture contains "flying pixels" (cubes or group of cubes that are attached to nothing).

Standard loopholes apply.

More precisely, you can't use external input besides the three letters, and you can't hardcode the 17576 possible answers in your source code

Shortest answer in characters in any language wins!

Have fun :)

\$\endgroup\$
11
  • 12
    \$\begingroup\$ You guys gotta be kidding me. \$\endgroup\$ Jul 14, 2014 at 20:21
  • \$\begingroup\$ Yep, it's the MU puzzle that made me discover the book, and it's the cover of the book that made me think of this challenge. Is there a problem? Was this a part of your 18 holes thing? \$\endgroup\$
    – xem
    Jul 14, 2014 at 20:30
  • 2
    \$\begingroup\$ It would have been a good option to replace hole 1. ;) ... Never mind, if anything it's my fault for not getting something up sooner. It's a really decent challenge, +1! \$\endgroup\$ Jul 14, 2014 at 21:00
  • \$\begingroup\$ Can we retrieve the data defining the shapes of letters from an external file, or does that need to be included in the source as well? \$\endgroup\$ Jul 14, 2014 at 23:09
  • \$\begingroup\$ Your binary B has 0 in the top left corner, not 1. \$\endgroup\$ Jul 15, 2014 at 4:11

6 Answers 6

16
\$\begingroup\$

Mathematica 423

I added a section called "How blocking works".

Ungolfed

(*The binary data of the alphabet are stored as a single string in s. vars imports it and converts it into an 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]

Example

Is the cube {"B", "G", "E"} valid? (i.e. Will the three letters project correctly onto the walls?)

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

False

Illustrations

The figures below show how BGE is rendered. The upper row of figures takes orthogonal perspectives, as if the viewer were positioned at infinite distances from the cube. The lower row shows how the blocks would look from close up. The 3D figures can be manually rotated to inspect precisely where the individual unit cubes are positioned.

A problem occurs with the letter "G". There is nothing connecting the serif to the rest of the letter.

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

bge


BEG, however, should work fine.

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

True

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

beg


How Does Blocking Work?

Please excuse me if this seems obvious, but perhaps some folks will want to visualize how how letters interfere with each other, canceling their 3D pixels.

Let's follow what happens to the letter G, in the BGE cube rendering.

We'll be paying special attention to the voxel (3D pixel or unit cube) below. That is the pixel that disappears in the BGE cube. It is the pixel corresponding to Row 4, Column 5 in the bit array and in the corresponding array plot.

blocking 1


In the x y plane, the pixel corresponds to the gray disk at point (5,2). But because we're going to work in 3D, we need to consider the 5 positions in the shaft from (5,1,2) to (5,5,2). If any of those pixels survives sculpting by the letters B and E, we'll be able to see the pixel of interest in the 3D projection on the wall.

blocking 2


Letters interfere when pixels are removed from the solid block. In the left, the black arrow represents the carving out of pixels, corresponding to the bit at the bottom right; it has the value 0 for the letter B. Carving out removes the pixel at (5,1,2), along with those directly above and below it. Four pixels remain to be accounted for.

blocking 3

But as the right pane shows, the letter E sculpts out the remaining pixels of interest, (5,2,2) (5,3,2), (5,4,2) and (5,5,2). (This is due to the fact that the letter E has bits equal to 0 in the fourth row, from column 2 through column 5.) As a result, not a single pixel remains among those that were needed to ensure shade at point (5,2) on the far wall (for the letter G). Instead, there will be a bright spot corresponding to a hole in the letter G! The cube BGE is no good because it incorrectly renders G.

Golfed 423 chars

The function h served the same role as validQ in the unGolfed code. The rendering function, perspective, is not included because it does not contribute to, and is not required by, the challenge.

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}}]
\$\endgroup\$
5
  • \$\begingroup\$ Woah, those 3D views are very neat! Are you sure the last code block is "UnGolfed"? It seems golfed to me. :) \$\endgroup\$
    – xem
    Jul 19, 2014 at 9:41
  • \$\begingroup\$ You are correct. The final block is golfed. I corrected the heading. One cool thing about the 3D views is that they are interactive: rotation and zooming can be done by mouse. \$\endgroup\$
    – DavidC
    Jul 19, 2014 at 9:46
  • \$\begingroup\$ BTW, by my count, there are 564 valid cubes among the 15600 possible permutations. \$\endgroup\$
    – DavidC
    Jul 19, 2014 at 16:11
  • \$\begingroup\$ That's a nice information. How long did it take you to compute that? also, 26*26*26 = 17576, not 15600. Or am I missing something? \$\endgroup\$
    – xem
    Jul 19, 2014 at 17:43
  • \$\begingroup\$ I used permutations, not tuples; i.e. no repeated letters. 26 *25*24 =15600. It took 21 seconds to find the 564 cases. \$\endgroup\$
    – DavidC
    Jul 19, 2014 at 21:35
13
\$\begingroup\$

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.

The program is called like this:

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

Prolog seemed to be a good choice, since it's easy to represent the problem in first order logic. Also Prolog provides potent functionality for solving this kind of problem.

However, since the code is golfed, I guess I should add some explanation.

Mildly golfed 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.

The coordinates corresponding to the pixels on each side of the dice can be easily converted to a 3D coordinate system. I use T,L and R for top(1), left(2) and right(3) side. u and v are used for the coordinates in the images:

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

The results for each active (i.e. black) pixel are combined to a set of "3D-pixels" that can be acitvated without changing the look of the object from this side. The intersection of the sets for each side are all 3D-pixels, that can be activated without adding pixels, that would obstruct the view (i.e. looking from at least one side there would be a pixel that shouldn't be there).

All that remains is to check for each side, if there is a pixel in the intersection that blocks the view, where it's necessary.

This leads to the predicates in the program:

  • f: does the final check; takes the letters at the top, the left side and the right side
  • u, v and w: do the checks, if for every pixel active on the side there is a 3D-pixel in the intersection, that blocks the view
  • h: checks, for the existence of a pixel in the intersection
  • t,l,r: checks, if a 3D-pixel can be blocked from top, left and right side.
  • c: checks for the pixel in the image of a letter. The string in there may look a bit strange, but it's only a compact way to store the image data. It's simply a character sequence with the following values(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]
    

    Each of these characters stores the data for 3 pixel rows in letter image(s) (=15 pixel). The pixels are also reordered so that the data is stored at one location and not divided across multiple rows, like the data of the OP.

Mathematic formulation

formula

Input data

formula

Conversion from pixel in one char to set of 3D-pixels that obstruct the view for this pixel

formula

formula

formula

Pixels that can be added safely(without obstructing the view in the wrong place)

formula

Checks for each side, that the pixels that need to be obstructed can be obstructed safely

formula

formula

formula

Combinatin of checks for each side

formula

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I.. Uh.. What? I find this incomprehensible. (+1) \$\endgroup\$
    – seequ
    Jul 16, 2014 at 6:59
  • \$\begingroup\$ Holy... I'm going to bed... \$\endgroup\$
    – BrunoJ
    Jul 16, 2014 at 7:03
  • \$\begingroup\$ Impressive! Thanks for this answer \$\endgroup\$
    – xem
    Jul 16, 2014 at 10:13
  • 1
    \$\begingroup\$ Nice. btw, I think of the process as starting off with a solid cubic block. (You seem to think of it as adding pixels where none were before.) Each letter removes some 3D pixels from that block. So interference arises when a neighboring letter removes pixels that a letter "wanted to keep". The interference stems from "missing pixels" rather than extra pixels. \$\endgroup\$
    – DavidC
    Jul 19, 2014 at 9:53
10
\$\begingroup\$

J - 223 197 191 char

A function taking a three char list as argument.

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

This golf relies heavily on a powerful feature of J called rank, which gives us the "sculpt out" and "watch side of" operations almost for free. To oversimplify it a bit, rank refers to the dimensionality of a noun or of a verb's natural arguments.

J has multidimensional arrays, and it is obvious that, say, a 3D array can be interpreted as a single 3D array, or as a list of matrices, or a 2D array of vectors, or a 3D array of scalars. So every operation in J can have its application controlled w.r.t. how to be spread over the argument. Rank 0 means apply on the scalars, rank 1 means apply on the vectors, and so on.

   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

This becomes very powerful when you introduce dyadic (two-argument) functions, because if the shapes of the two arguments (after accounting for rank) are agreeable, J will do some implicit looping:

   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

When all your shapes are agreeable and you can specify the rank yourself, there are many ways to combine arguments. Here we show off some of the ways that you can multiply a 2D matrix and a 3D array.

   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|
+---------+---------+--------------+--------------+--------------+

You'll notice that this doesn't actually carve in the letters in the orientation the question asks for, it just writes them in however is convenient for rank logic. Unless we reverse or rotate the letters before we apply them, it won't work right. But correcting things like that would take up precious characters, so instead we'll encode the letters such that, when J carves them in naturally, some triple of faces will be in the correct orientations and relative positions. It turns out the shortest solution is to rotate all the letterforms a quarter-turn counterclockwise. Considering J's third dimension to represent the front-to-back axis, the crude diagram below shows why this scheme works.

visualization of cube Figure A: The three sides of the cube that J carves into. Figure B: The three sides which have the letters oriented like the question asks.

This choice in encoding saves 12 characters over the previous method, and makes the whole thing neater. The actual golf creates the cube out of the "1 and "2 carves with some funky logic, due to an unrelated optimization.

Then we have to check the faces. Since we encode the block as 1s and 0s, we can just sum along each axis in the way we want (these are the +/"1, +/"2, and +/ bits), adjust to booleans (0<), and then compare them all directly to the original 90°-turned-letters.

The compression scheme encodes each 5px row of each letter as the base 32 representation of a binary number. By exploiting a number of syntactic sugars and operator overloadings, ".'1b',"#: is the shortest way to turn the list of characters into base 36 numbers. Well, technically, base 32, but J thinks it's unary, so who's counting?

Usage is below. Note that strings are character arrays in J, so a three item list 'A','B','C' can be written 'ABC' for short. Also, booleans are 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
\$\endgroup\$
0
5
\$\begingroup\$

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))

Call with v:

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

Everything below is from my previous ungolfed version which includes helpful drawing functions. Feel free to use it as a jumping off point.

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()

Call valid to run it:

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

Right now the code is setup to test the validity of B E G and print out the resulting faces:

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

Running it on B G E we can see that the G is incorrect:

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
\$\endgroup\$
8
  • \$\begingroup\$ wow, good job! +1 for drawAll and the completeness of the answer. +1 for using such a short algorithm. <3 it \$\endgroup\$
    – xem
    Jul 15, 2014 at 6:26
  • \$\begingroup\$ @xem Thanks! I finally golfed it. Though I couldn't figure out how to get bz2 to decompress unicode characters. \$\endgroup\$ Jul 15, 2014 at 9:55
  • \$\begingroup\$ +1. Nice answer. Hope more people will upvote golfs that comprise of smaller golfs, like this, cuz it really takes effort. \$\endgroup\$
    – Vectorized
    Jul 15, 2014 at 10:47
  • 1
    \$\begingroup\$ g=[[0 for j in s]for i in s] can be shortened to g=map(list,[[0]*5]*5). Also you can avoid indenting blocks if they are a single statement: if c[e]:g[e[a]][e[a-2]]=1. \$\endgroup\$
    – Bakuriu
    Jul 15, 2014 at 11:04
  • \$\begingroup\$ @Bakuriu and bitpwner, thanks for the suggestions and edits :) \$\endgroup\$ Jul 15, 2014 at 11:19
3
+200
\$\begingroup\$

APL (Dyalog Unicode), 150 bytes

x y z←(⎕A⍳⍞)⌷¨⊂26 5 5⍴(8⍴2)⊤⎕AV⍳'5∘⍉⍉c∨wÌþ∩⍀ýFó  â⍒⍪┤ÌÙÍ⊃?>áóU│yEå≥∧+├Û└KEÐ┐⌹;⍉ùigë/⋄⍪,ËwÙ4○$⊣7×c⍺þS¢|⍋îÜ⍀â:b⌷Î'
(x,y,z)≡(∨⌿,∨⌿⍤2,∨/)x×⍤2⊢z∘.×⍤1⊢y

Try it online!

A full program that takes three uppercase letters from stdin and prints 0 (false) or 1 (true) to stdout.

We already have an answer in J which has an excellent primer on multi-dimensional arrays and function rank. This answer uses the same concept. (Plus an obvious advantage that we can efficiently encode the binary arrays using the single-byte character encoding.)

How it works

⍝ Extract the three bit matrices
x y z←(⎕A⍳⍞)⌷¨⊂26 5 5⍴(8⍴2)⊤⎕AV⍳'5∘⍉⍉c∨wÌþ∩⍀ýFó  â⍒⍪┤ÌÙÍ⊃?>áóU│yEå≥∧+├Û└KEÐ┐⌹;⍉ùigë/⋄⍪,ËwÙ4○$⊣7×c⍺þS¢|⍋îÜ⍀â:b⌷Î'
                            ⎕AV⍳'...'  ⍝ Char value of each char w.r.t. the code page
                      (8⍴2)⊤  ⍝ Convert each number to 8 bits, making 8-row matrix
               26 5 5⍴  ⍝ Take the bits and form 26×5×5 brick
      (⎕A⍳⍞)⌷¨⊂  ⍝ Take 3-char input and extract the corresponding 5×5 matrices
x y z←  ⍝ Assign to three variables

(x,y,z)≡(∨⌿,∨⌿⍤2,∨/)x×⍤2⊢z∘.×⍤1⊢y
                         z∘.×⍤1⊢y  ⍝ Combine front and right faces
                                   ⍝ so that three dimensions are oriented naturally
                    x×⍤2⊢  ⍝ Combine the top face
        (∨⌿,∨⌿⍤2,∨/)  ⍝ Compute the top, front, and right views of the pixels
(x,y,z)≡  ⍝ Check if they all match the original faces
\$\endgroup\$
1
  • \$\begingroup\$ You might be able to pack the data even tighter, since this challenge is old enough to count in characters. \$\endgroup\$
    – Adám
    Jun 12, 2020 at 5:15
1
\$\begingroup\$

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])

This golf solution need an external library, numpy, which is quite popular so I think it's fine to use it.

The unicode string is in 41 chars, while the same thing in @fabian's prolog answer is 44.

The most interesting here is that the indexing of numpy array. In a[ix], ix can be an boolean array with the same shape as a. It's the same as saying 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)
    ])

Script to compress table

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.