Czy potrafisz złożyć hexomino w sześcian?

24

Jedną z ulubionych zabawek mojego dziecka jest taki zestaw . Właściwie to jedna z moich ulubionych zabawek - bawiłem się nią i dawałem mi pomysły na wyzwania PPCG. Tutaj jest jeden:

Napisz program lub funkcję, która pobiera rysunek linii ASCII jako dane wejściowe i decyduje, czy złoży się w kostkę.

Wkład

Dane wejściowe będą składały się z dokładnie jednego heksomina zbudowanego z kwadratów takich jak to:

+-+
| |
+-+

Na przykład poprawnym wejściem heximino jest:

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

Wydajność

  • Prawda, jeśli heksomino można złożyć w sześcian lub
  • W przeciwnym razie wartość falsey.

Aby zaoszczędzić nam trochę pracy, wikipedia ma ładną grafikę:

  • Wszystkie 35 heksominoes:

  • Wszystkie 11 heksomino, które składają się w kostkę:

Notatki

  • Heksomino wejściowe mogą mieć dowolny obrót lub odbicie, a nie tylko te pokazane na powyższych obrazach
  • Heksomino wejściowe mogą mieć spacje wiodące, ale zostaną odpowiednio wyrównane względem siebie
  • Heksomino wejściowe mogą mieć końcowe spacje na końcu linii i końcowe nowe linie na końcu wprowadzania
code-golf ascii-art kolmogorov-complexity geometry Cyfrowa trauma
źródło
1
Czy możesz wyjaśnić, dlaczego jest tu tag przetwarzania obrazu? Ani pytanie, ani odpowiedź nie będą wymagały przetwarzania obrazu w celu rozwiązania problemu.
Optymalizator
Wyjaśnienie dotyczące początkowych / końcowych spacji: czy niepotrzebne początkowe / końcowe spacje w każdym wierszu i niepotrzebne znaki nowej linii są dozwolone na wejściu? Czy powinienem być w stanie zarządzać danymi ponad 1000 znaków?
edc65
@ edc65 tak, należy się spodziewać niepotrzebnej białej przestrzeni, którą opisujesz. Maksymalny rozmiar wejściowy 1000 znaków wydaje się rozsądny - zedytuję to
Digital Trauma
Hmm Zastanawiam się, ile heksomino-kostek można wycisnąć, zestawić na wydrukowanej stronie?
luser droog

Odpowiedzi:

7

PMA / Ślimaki , 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

lub bardziej „czytelnie”,

?
.!(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

Niezwykle pojawił się problem, którym można zaradzić dzięki ograniczonej liczbie zaimplementowanych do tej pory funkcji. !(z\ )Wzór określa, że obecna sytuacja jest w przestrzeni w środku kwadratu przy użyciu twierdzenia negatywny, że istnieje przestrzeń w jakimś kierunku „octilinear”. Ogólnym pomysłem jest sprawdzenie wzoru, który umieszcza kwadrat w każdej z 5 niezbędnych lokalizacji w stosunku do kwadratu, od którego rozpoczyna się mecz. Musi także sprawdzić, czy nie ma go w bloku kwadratów 2x2. Zanim program zadziałał, musiałem naprawić błąd podczas analizowania nawiasów.

Jeśli hexomino nie mapuje sześcianu, 0jest drukowane. Jeśli tak, wypisywana jest dodatnia liczba całkowita (liczba dopasowań).

Zaadaptowałem ten generator poliomino, aby stworzyć wszystkie możliwe przypadki testowe:

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)]
feersum
źródło
hahahahahahahah bardziej „czytelnie”
Optymalizator
5

Rubinowy, 173 148 145 143 bajtów

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

Ostatnia zmiana: /2po prawej stronie< zastąpiona przez *2po lewej stronie. Umożliwia eliminację jednego zestawu()

Wyjaśnienie

Kod składa się z dwóch części: głównej nienazwanej funkcji wykonującej parsowanie oraz pomocniczej nienazwanej funkcji przypisanej do zmiennej h , która sprawdza.

Główna funkcja skanuje kolejno ciąg znaków, dodając współrzędne xiy i,jwszystkich +znalezionych symboli do x[]i y[]. Następnie dzwoni hdwukrotnie. Za pierwszym razem zakłada, że ​​heksomino jest w poziomie ( x[]zawiera długości iy[] szerokości), a po raz drugi zakłada, że ​​jest w pionie.

Funkcja hprzyjmuje współrzędne wzdłużne w tablicy, ba następnie współrzędne wzdłużne w tablicy c. Oblicza długość (w kwadratach) według wyrażenia (b.max.b.min)/2. Jeśli jest mniejsza lub równa 3, heksomino powinno być ocenione w innym kierunku, więc hpowraca false.

Inspekcja heksominów pokaże, że jeśli długość wynosi 4, te heksominosy, które złożą się w sześcian, mają nie więcej niż 2 kwadraty (3 +symbole) w pierwszym i ostatnim rzędzie . Większość kwadratów koncentruje się w środkowym rzędzie, który stanie się równikiem sześcianu. Ten warunek okazuje się konieczny i wystarczający dla heksomino o długości 4, które złoży się w sześcian.

Jest tylko jedno heksomino o długości 5, które złoży się w sześcian. Ma 3 kwadraty (4 +symbole) w pierwszym i ostatnim rzędzie. Wszystkie pozostałe heksominosy o długości 5 mają 5 lub więcej+ symboli w pierwszym lub ostatnim rzędzie.

Jest tylko jeden heksomino o długości 6. Ma 7 +symboli w każdym rzędzie.

Podsumowując, wystarczy sprawdzić, czy długość heksomina jest większa niż 3, a liczba +symboli w pierwszym i ostatnim rzędzie (w zależności od tego, która wartość jest większa) jest mniejsza niż długość.

Niegolfowany w programie testowym

#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["
  +-+-+-+
  | | | |
  +-+-+-+-+
      | | |
      +-+-+
        | |
        +-+
"]
Level River St
źródło
pentonimo → hexonimo w tekście?
Paŭlo Ebermann
3

JavaScript (ES6), 443 431

Edytuj poprawkę błędu, problem podczas analizy wejściowej, usuwanie pustych kolumn 

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

To bardzo długo, a nawet dłużej, ponieważ analizowanie danych wejściowych stanowi dużą część zadania.

To, co robię, to sprawdzanie, czy dane wejście jest jednym z 11 składanych heksomino.

Każde składane hexomino może być mapowane na jakąś bitmapę 5x5 (do 8 różnych, z symetrią i obrotami). Biorąc mapy bitowe jako liczbę 25-bitową, znalazłem wartości minimalne dla 11 odnotowanych heksominoes, używając następującego kodu (z bardzo prostym formatem wejściowym)

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

To daje [1505,2530,3024,4578,252,6552,2529,4577,2499,4547,7056]

Biorąc pod uwagę ciąg wejściowy, muszę zrobić to samo, aby znaleźć minimalną mapę bitową, a następnie zwrócić wartość true, jeśli ta liczba jest obecna na mojej liście precalc.

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

Uruchom fragment kodu, aby przetestować w przeglądarce Firefox

Pokaż fragment kodu

edc65
źródło
Wybacz mi, jeśli coś mi brakuje, ale czy nie mógłbyś ,\nt=tod końca drugiej linii / początku trzeciej linii?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ przeglądając sześć miesięcy później, kod parsowania może być skrócony o 10 ... 15 bajtów. W tej chwili potrzebuję przypisania do t w linii 2 i ponownie w linii 3, ponieważ w linii 3 służy do znalezienia liczby pustych znaków do wycięcia po lewej stronie.
edc65