24
\$\begingroup\$

One of my kid's favorite toys is a set like this. Actually its one of my favorite toys - I've been playing with it and its been giving me some PPCG challenge ideas. Here's one:

Write a program or function that takes an ASCII line drawing as input and decides whether or not it folds into a cube.

Input

Input will consist of exactly one hexomino built from squares like this:

+-+
| |
+-+

For example a valid input heximino is:

+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
  | |
  +-+

Output

  • A truthy value if the hexomino can be folded into a cube, or
  • A falsey value otherwise.

To save us a bit of work, wikipedia has nice graphics of:

  • All 35 hexominoes:

  • All 11 hexominoes that fold into cubes:

Notes

  • Input hexominoes may have any rotation or reflection, not just those shown in the images above
  • Input hexominoes may have leading spaces, but will be correctly aligned with respect to themselves
  • Input hexominoes may have trailing space at the end of lines and trailing newlines at the end of input
\$\endgroup\$
  • 1
    \$\begingroup\$ Can you explain why there is an image-processing tag here ? Neither the question, nor the answer will have to do any kind of image processing to solve the challenge. \$\endgroup\$ – Optimizer May 10 '15 at 11:32
  • \$\begingroup\$ Clarification about leading/trailing space: are unnecessary leading/trailing spaces on each row and unnecessary newlines allowed in input ? Should I be able to manage a 1000+ chars input? \$\endgroup\$ – edc65 May 10 '15 at 13:08
  • \$\begingroup\$ @edc65 yes you should expect the unnecessary white space you describe. 1000 chars max input size seems reasonable - I'll edit that in \$\endgroup\$ – Digital Trauma May 10 '15 at 16:46
  • \$\begingroup\$ Hmm. I wonder how many cube hexominoes can be squeezed, juxtaposed, on a printed page? \$\endgroup\$ – luser droog Nov 18 '15 at 6:43
7
\$\begingroup\$

PMA/Snails, 130

.!(z\ |o{c..!(z\ }3){w=(..!(z\ )|b..!(z\ )o{..!(z\ }2|c{..!(z\ }1,2w..!(z\ )|w{..!(z\ }1,2c..!(z\ }4o..!(z\ )(..!(z\ )|n..!(z\ )`2

or more "readably",

?
.!(z\  | o{c..!(z\ }3  )
{w =( ..!(z\ ) | b ..!(z\ ) o {..!(z\ }2  | c {..!(z\ }1,2w..!(z\ ) | w {..!(z\ }1,2c..!(z\  }4
o  ..!(z\ ) ( ..!(z\ ) | n ..!(z\ ) `2

Unusually, a problem came along that can be handled by the limited amount of features implemented so far. The !(z\ ) pattern determines that the current position is at the space in the middle of a square using a negative assertion that there is a space in some "octilinear" direction. The general idea is to check for a pattern that places a square at each of the 5 necessary locations relative to the square that the match starts on. Also, it needs to check that it is not in a 2x2 block of squares. Before the program would work, I had to fix a bug with the parsing of parentheses.

If the hexomino does not map a cube, 0 is printed. If it does, some positive integer is printed (number of matches).

I adapted this polyomino generator to create all possible test cases:

n=input()
r=range
T=lambda P:set(p-min(p.real for p in P)-min(p.imag for p in P)*1j for p in P)
A=[]
for i in r(1<<18):
 P=[k%3+k/3*1j for k in r(18)if i>>k&1]
 C=set(P[:1])
 for x in P:[any(p+1j**k in C for k in r(4))and C.add(p)for p in P]
 P=T(P)
 if not(C^P or P in A or len(P)-n):
  #for y in r(4):print''.join(' *'[y+x*1j in P] for x in r(6))
  o = [ [' ']*13 for _ in r(9)]
  for y in r(4):
   for x in r(6):
    if y+x*1j in P: X=2*x;Y=2*y; o[Y][X]=o[Y+2][X]=o[Y][X+2]=o[Y+2][X+2]='+'; o[Y][X+1]=o[Y+2][X+1]='-';o[Y+1][X+2]=o[Y+1][X]='|'
  print '\n'.join(map(''.join,o))
  A+=[T([p*1j**k for p in P])for k in r(4)]
\$\endgroup\$
  • \$\begingroup\$ hahahahahahahah more "readably" \$\endgroup\$ – Optimizer May 10 '15 at 10:12
5
\$\begingroup\$

Ruby, 173 148 145 143 bytes

h=->b,c{[c.count(c.max),c.count(c.min),3].max*2<b.max-b.min}
->s{x=[];y=[];i=j=0
s.bytes{|e|e==43&&x<<i|y<<j;i=e<32?0*j+=1:i+1}
h[x,y]||h[y,x]}

Latest change: /2 on right side of < replaced by *2on left side. Allows elimination of one set of()

Explanation

The code is in two parts: a main unnamed function that does the parsing, and an auxiliary unnamed function assigned to the variable h that does the checking.

The main function scans bytewise through the string, adding the x and y coordinates i,j of all + symbols found to x[] and y[]. It then calls h twice. The first time it assumes the hexomino is horizontal (x[] contains the lengths and y[] the widths) and the second time it assumes it is vertical.

The function h takes the lengthwise coordinates in array b then the widthwise coordinates in array c. It calculates the length (in squares) by the expression (b.max.b.min)/2. If this is less than or equal to 3, the hexomino should be evaluated in the other direction so h returns false.

Inspection of the hexominos will show that if the length is 4, those hexominos that will fold into a cube have no more than 2 squares (3 + symbols) in the first and last row. Most of the squares are concentrated on the middle row, which will become the equator of the cube. This condition turns out to be necessary and sufficient for a hexomino of length 4 that will fold into a cube.

There is only one hexomino of length 5 that will fold into a cube. It has 3 squares (4 + symbols) in its first and last rows. All other hexominos of length 5 have 5 or more + symbols in either the first or last row.

There is only one hexomino of length 6. It has 7 + symbols on each row.

Putting all this together, it is sufficient to check that the length of the hexomino is greater than 3, and the number of + symbols on the first and last rows (whichever is higher) is less than the length.

Ungolfed in test program

#checking function as explained in text
h=->b,c{[c.count(c.max),c.count(c.min),3].max<(b.max-b.min)/2}

#main function for parsing
f=->s{
  x=[]                 #separate assignments required, 
  y=[]                 #otherwise we get 2 pointers to the same array
  i=j=0                #start coordinates 0,0
  s.bytes{|e|          #scan string bytewise
    e==43&&x<<i|y<<j     #if byte is a + symbol (ascii 43) add the coordinates to arrays x and y
    i=e<32?0*j+=1:i+1    #if byte is before ascii 32 assume newline, increment j and zero i. Otherwise increment i
  }
  h[x,y]||h[y,x]       #call h twice, with x and y in each possible order
}



#VALID INPUTS
puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
| |
+-+"]

puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
  | |
  +-+"]

puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
    | |
    +-+"]
puts f["
+-+
| |
+-+-+-+
| | | |
+-+-+-+-+
    | | |
    +-+-+"]

puts f["
+-+
| |
+-+-+-+-+
| | | | |
+-+-+-+-+
      | |
      +-+"]

puts f["
    +-+
    | |
+-+-+-+-+
| | | | |
+-+-+-+-+
    | |
    +-+"]
puts f["
    +-+
    | |
+-+-+-+
| | | |
+-+-+-+-+
    | | |
    +-+-+"]


puts f["
  +-+
  | |
+-+-+-+-+
| | | | |
+-+-+-+-+
    | |
    +-+"]
puts f["
  +-+
  | |
+-+-+-+
| | | |
+-+-+-+-+
    | | |
    +-+-+"]  
puts f["
+-+-+
| | |
+-+-+-+
  | | |
  +-+-+-+
    | | |
    +-+-+"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+-+-+
      | | | |
      +-+-+-+
"]


#INVALID INPUTS

puts f["
  +-+-+-+
  | | | |
  +-+-+-+
  | | | |
  +-+-+-+
"]


puts f["
  +-+-+-+-+-+-+
  | | | | | | |
  +-+-+-+-+-+-+

"]


puts f["
  +-+-+
  | | |
  +-+-+
  | |
  +-+
  | |
  +-+
  | |
  +-+
  | |
  +-+
"]

puts f["
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
    | |
    +-+
"]

puts f["
      +-+
      | |
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
"]

puts f["
  +-+-+-+-+
  | | | | |
  +-+-+-+-+-+
        | | |
        +-+-+"]

puts f["
  +-+-+-+-+
  | | | | |
  +-+-+-+-+
      | | |
      +-+-+
"] 


puts f["
  +-+-+-+-+
  | | | | |
  +-+-+-+-+
  | | | |
  +-+ +-+
"]

puts f["
 +-+   +-+
 | |   | |
 +-+-+-+-+
 | | | | |
 +-+-+-+-+
"]

puts f["
   +-+-+
   | | |
 +-+-+-+-+
 | | | | |
 +-+-+-+-+
"]

puts f["
  +-+
  | |
  +-+
  | |
  +-+-+-+-+
  | | | | |
  +-+-+-+-+
"]

puts f["
  +-+
  | |
  +-+-+-+
  | | | |
  +-+-+-+
  | |
  +-+
  | |
  +-+
"]

puts f["
  +-+
  | |
+-+-+-+
| | | |
+-+-+-+
| |
+-+
| |
+-+"]

puts f["
  +-+-+
  | | |
  +-+-+
  | |
  +-+-+
  | | |
  +-+-+
    | |
    +-+
"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+-+
    | | | |
    +-+-+-+
"]

puts f["
  +-+-+-+
  | | | |
  +-+-+-+
      | |
      +-+-+
      | | |
      +-+-+
"]


puts f["
  +-+-+-+
  | | | |
  +-+-+-+-+
      | | |
      +-+-+
        | |
        +-+
"]
\$\endgroup\$
  • \$\begingroup\$ pentonimo → hexonimo in your text? \$\endgroup\$ – Paŭlo Ebermann Nov 17 '15 at 21:49
3
\$\begingroup\$

JavaScript (ES6), 443 431

Edit bug fix, problem during input parse, removing blank columns

F=t=>(a=b=c=d=e=f=g=h=0,M=Math.min,
t=t.split('\n').filter(r=>r.trim()>''),
t=t.map(r=>r.slice(M(...t.map(r=>r.search(/\S/))))),
t.map((r,i)=>i&1&&[...r].map((_,j)=>j&1&&r[j-1]==r[j+1]&t[i-1][j]==t[i+1][j]&r[j-1]=='|'
&&(y=i>>1,x=j>>1,z=y*5,w=x*5,a|=1<<(z+x),e|=1<<(w+y),b|=1<<(4+z-x),f|=1<<(4+w-y),c|=1<<(20-z+x),g|=1<<(20-w+y),d|=1<<(24-z-x),h|=1<<(24-w-y)
))),~[1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056].indexOf(M(a,b,c,d,e,f,g,h)))

That's very long, and even longer as parsing input is a big part of the task.

What I do is verifyng if the given input is one of the 11 foldable hexominoes.

Each foldable hexomino can be mapped to some 5x5 bitmap (up to 8 different, with simmetry and rotations). Taken the bitmaps as 25bit number, I have found the min values for the 11 noted hexominoes, using the following code (with very simple input format)

h=[ // Foldable hexominoes
'o\noooo\no', ' o\noooo\n o', // pink
'o\noooo\n   o', ' o\noooo\n  o', 'ooo\n  ooo', 'oo\n oo\n  oo', //blue
'o\noooo\n o', 'o\noooo\n  o', 'oo\n ooo\n o', 'oo\n ooo\n  o', 'o\nooo\n  oo' // gray
]
n=[]
h.forEach(t=>(
  a=[],
  t.split('\n')
    .map((r,y)=>[...r]
      .map((s,x)=>s>' '&&(
         a[0]|=1<<(y*5+x),a[1]|=1<<(x*5+y),  
         a[2]|=1<<(y*5+4-x),a[3]|=1<<(x*5+4-y),  
         a[4]|=1<<(20-y*5+x),a[5]|=1<<(20-x*5+y),  
         a[6]|=1<<(24-y*5-x),a[7]|=1<<(24-x*5-y))
     )
  ),
n.push(Math.min(...a))
))

That gives [1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056]

So, given the input string, I have to do the same to find the min bitmap, then return true if this number is present in my precalc list.

// Not so golfed 

F=t=>(  
  a=b=c=d=e=f=g=h=0,M=Math.min,
  t=t.split('\n').filter(r=>r.trim()>''), // remove blank lines
  t=t.map(r=>r.slice(M(...t.map(r=>r.search(/\S/))))), // remove blank colums to the left
  t.map((r,i)=>i&1&&[...r] // only odd rows
   .map((_,j)=>j&1&& // only odd columns
      r[j-1]==r[j+1]&t[i-1][j]==t[i+1][j]&r[j-1]=='|' // found a cell
         &&(y=i>>1,x=j>>1,z=y*5,w=x*5, // find bitmaps for 8 rotations/simmetries
            a|=1<<(z+x),e|=1<<(w+y),  
            b|=1<<(4+z-x),f|=1<<(4+w-y),  
            c|=1<<(20-z+x),g|=1<<(20-w+y),  
            d|=1<<(24-z-x),h|=1<<(24-w-y)  
    ))),
   ~[1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056].indexOf(Math.min(a,b,c,d,e,f,g,h)) // look for min
)

Run snippet to test in Firefox

F=t=>(a=b=c=d=e=f=g=h=0,M=Math.min,
t=t.split('\n').filter(r=>r.trim()>''),
t=t.map(r=>r.slice(M(...t.map(r=>r.search(/\S/))))),
t.map((r,i)=>i&1&&[...r]
.map((_,j)=>j&1&&r[j-1]==r[j+1]&t[i-1][j]==t[i+1][j]&r[j-1]=='|'
&&(y=i>>1,x=j>>1,z=y*5,w=x*5,
a|=1<<(z+x),e|=1<<(w+y),b|=1<<(4+z-x),f|=1<<(4+w-y),c|=1<<(20-z+x),g|=1<<(20-w+y),d|=1<<(24-z-x),h|=1<<(24-w-y)
))),~[1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056].indexOf(M(a,b,c,d,e,f,g,h)))

s=[...'      \n      \n      \n  2   \n      \n      '],o=7,l=5,k={},t=0

out=[[],[]]

Test=s=>k[s]?0 // filter duplicates, but allow same shape in different position
  :k[s]=(
  p=Array(13).fill(0).map(x=>Array(13).fill(' ')), // build string to test in long format
  s.map((v,i)=>(x=2*(i%7),y=2*(i/7|0),-v&&(
    p[y][x]=p[y][x+2]=p[y+2][x]=p[y+2][x+2]='+',
    p[y][x+1]=p[y+2][x+1]='-',
    p[y+1][x]=p[y+1][x+2]='|'  
  ))),
  s=p.map(r=>r.join('')).join('\n'),
  ok=F(s), // test
  
  out[!ok|0].push('\n'+s+-ok),
  1
)

Fill=(z,p)=>(
  s[p]=2,
  z>l?Test(s):s.forEach((v,i)=>v==' '&(s[i+o]==2|s[i-o]==2|s[i-1]==2|s[i+1]==2)?Fill(z+1,i):0),
  s[p]=' '
)
             
Fill(1,s.indexOf('2')) 

OV.innerHTML=out[0].join('\n')
OI.innerHTML=out[1].join('\n')
pre { 
  overflow: auto;
  font-size: 9px;
  height: 500px; 
  display: block; 
  border: 1px solid #888;
  padding: 6px 20px;
  line-height: 6px;
}
Verify all hexominoes possible in a 6x6 grid (Better full page) <br>
<table><tr>
  <th>VALID</th><th>INVALID</th>
</tr><tr>
  <td><pre id=OV></pre></td>
  <td><pre id=OI></pre></td>
</tr></table>

\$\endgroup\$
  • \$\begingroup\$ Forgive me if I am missing something, but couldn't you the ,\nt=t from the end of the second line/the beginning of the third line? \$\endgroup\$ – Conor O'Brien Nov 19 '15 at 16:22
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ reviewing six months later, the parsing code could be made 10...15 bytes shorter. As is, I need the assignment to t in line 2 and the again in line 3 because in line 3 it's used to find the number of blank chars to cut at left side. \$\endgroup\$ – edc65 Nov 19 '15 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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