Gra

Ostatnio wiele czasu spędzam na wciągającej grze na mój telefon o nazwie Logic Dots, która zainspirowała mnie do napisania tego wyzwania. Łatwiej jest wyjaśnić zasady, jeśli pokażę ci ekran gry, więc oto zrzut ekranu nierozwiązanej i rozwiązanej układanki:

Tutaj są trzy główne rzeczy do zauważenia.

1. Plansza (siatka kwadratów 4x4 na środku)
2. Wymagane kształty (połączone kropki na drugim pasku od góry, pod partyturą i menu itp.), Które są wszystkimi liniami lub aprzez 1 prostokąty
3. Liczby nad wierszami i kolumnami, które wskazują, ile kropek musi znajdować się w kolumnie, dla rozwiązania

Celem gry jest dopasowanie wymaganych kształtów do siatki. Możesz obracać kształty, ale nie mogą one wchodzić po przekątnej.

W rozwiązaniu zauważ, że wszystkie kształty są tworzone dokładnie raz (ponieważ są tylko w wymaganych kształtach raz), aw tym przypadku wszystkie są poziome, ale mogą być również pionowe. Różowe wypełnione kwadraty oznaczają kwadraty nieużywane.

Oto większa i nieco bardziej skomplikowana siatka:

Zauważ, że w nierozwiązanej układance jest już wypełnionych kilka kwadratów. Szare kwadraty oznaczają zablokowane kwadraty, na których NIE MOŻESZ umieścić kropki. Kropki z ogonami informują, że kropka znajduje się w tym miejscu i łączy się z co najmniej jedną kropką w kierunku ogona, ale nie w żadnym innym kierunku (w tym w przeciwnym kierunku).

Notacja

W dalszej części tego posta będę odwoływał się do tablicy za pomocą następujących symboli:

• <,>, ^, v - Oznacza wcześniej umieszczoną kropkę z ogonem rozciągającym się w kierunku punktu
• * - Oznacza kropkę. Jeśli podano go na nierozwiązanej siatce (dane wejściowe), jest to indywidualny kształt. Jeśli na wyjściu, to jest podłączony do kropek wokół niego.
• # - Oznacza zablokowany kwadrat siatki (gdzie nie można umieścić kropki)
• -, | (łącznik i kreska) - oznacza kropkę z prawym i lewym ogonem oraz kropkę z odpowiednio górnym i dolnym ogonem
• ** (znak spacji) - ** Oznacza puste miejsce

Korzystając z tych symboli, ten drugi przykładowy przypadek (nierozwiązany) można przedstawić następująco:

 <    



    # 
 ^ #

Rozwiązanie można przedstawić jako:

*< * *
   *  
     *
 *   *
 * *#*
 ^ # *

Pamiętaj, że żadne dwa kształty nie mogą dotykać poziomo, pionowo ani po przekątnej , więc następujący przypadek jest nieprawidłowy:

 *** 
**   
  ** 

Wyzwanie

Twoim wyzwaniem jest rozwiązanie zagadki logicznej z kropkami, od 4x4 do 9x9 włącznie. Otrzymasz cztery linie wejściowe, a następnie planszę. Linie będą następujące:

• 1. linia, Kształty - kształty do znalezienia, każdy podany w formie sizexquantity(np. 3x2Dla dwóch kształtów o długości trzy) i oddzielone spacją. Przykładowa linia:3x1 2x1 1x1
• Drugi wiersz, kolumny - Oddzielona spacjami lista wymaganej liczby kropek dla każdej kolumny. Przykładowa linia:1 1 2 2
• Trzecia linia, wiersze - Oddzielona spacjami lista wymaganej liczby kropek dla każdego wiersza. Przykładowa linia:3 0 3 0
• 4. linia, rozmiar tablicy - jedna liczba całkowita, rozmiar tablicy, B

Tablica jest następnie podawana i jest Bliniami wejściowymi reprezentującymi tablicę przy użyciu wspomnianej wyżej notacji. Na przykład pełne dane wejściowe dla drugiego przykładu są następujące:

4x1 3x1 2x2 1x2
1 4 0 3 0 5
4 1 1 2 3 2
6
 <    



    # 
 ^ #  

Twój program wyświetli następnie rozwiązaną tablicę w tym samym zapisie. Dopasowane dane wyjściowe dla powyższego wejścia są następujące:

** * *
   *  
     *
 *   *
 * *#*
 * # *

Pamiętaj, że plansza może mieć wiele rozwiązań. W takim przypadku po prostu wypisz jedno prawidłowe rozwiązanie. Ponadto twój program musi wypisać prawidłowe rozwiązanie w ciągu 10 sekund na rozsądnym komputerze stacjonarnym dla skomplikowanej siatki 10x10.

To jest kod golfowy, więc wygrywa najmniej bajtów.

Przypadki testowe

Wejście 1

3x2 1x4
2 2 3 1 2
4 0 3 0 3
5


    #
  #  
    *

Wyjście 1

*** *

 ***#
  #  
* * *

Wejście 2

3x1 1x6
2 0 4 0 3
3 1 2 1 2
5
*    


   # 

Wyjście 2

* * *
  *  
  * *
*  # 
  * *

Wejście 3

5x1 4x1 2x1 1x2
1 2 3 3 2 2
0 5 0 4 0 4
6
#     
  -   


 #    
   <  

Wyjście 3

#     
 *****

 **** 
 #    
* ** *

Python 2: 766 739 696 663 633 bajtów

def f(B,S,o=0):
 if[]==S:print'\n'.join(B);exit()
 s=S[0]
 for i in r:
  for j in R(Z-s+1):
   if(B[i][j]in' '+'>v'[o])*(B[i][j+s-1]in' '+'<^'[o])*({' ','-|'[o]}>=set(B[i][j+1:j+s-1]))*all(B[x][y]in'# 'for x,y in [(x,y)for y in R(j-1,j+s+1)for x in i-1,i+1]+[(i,j-1),(i,j+s)]if 0<=x<Z>y>=0):q=B[:];q[i]=q[i][:j]+'*'*s+q[i][j+s:];q=(q,t(q))[o];any((t(q)+q)[k].count('*')>m[k]for k in R(Z+Z))or f(q,S[1:])
 o or f(t(B),S,1)
y=raw_input;S=[];s=str.split
for i in s(y()):u,v=map(int,s(i,'x'));S+=[u]*v
m=map(int,s(y())+s(y()));Z=input();R=range;r=R(Z);B=[y()for _ in r];J=''.join;t=lambda x:map(J,zip(*x))
f(B,S[:len(S)-J(B).count('*')])

Zobacz, jak działa online: Ideone.com (wersja online może być zbyt wolna dla dużych i trudnych sieci, offline powinna być w porządku)

Wejście odbywa się poprzez standardowe wejście, wystarczy skopiować i ominąć wiersze z OP (ale uważaj, wymiana stosu czasami usuwa spacje lub wiersze).

Kilka podstawowych pomysłów na ten kod: Używa funkcji rekurencyjnej f. fpróbuje umieścić jeden kształt na planszy. Dla każdej możliwej lokalizacji nazywa się ona zmodyfikowaną tablicą. Są w nim 3 pętle. ookreśla orientację (2 - pozioma, 3 - pionowa). Zawsze umieszcza kształt poziomo, dlatego na końcu o=2transponuje tablicę z funkcją t. ito wiersz i jwszystkie możliwe kolumny początkowe. Następnie odbywa się wiele kontroli, jeśli końce kształtu mają prawidłowe znaki, jeśli środek kształtu ma prawidłowe znaki i jeśli otoczenie jest puste.

JavaScript (ES6) 661 667 695 702 745 755 786 790 784 798

Prace w toku, można skrócić. Prawdopodobnie za wolno na złożonej siatce. Może nie.

Edytuj Trochę dłużej, dużo szybciej.
Edytuj 2 Poprawka błędu, sprawdzanie kolumn / wierszy. Nawiasem mówiąc, teraz jest szybciej

Główna jest funkcja M. Parametr w jest łańcuchem wieloliniowym ze wszystkimi danymi wejściowymi. Funkcja analizuje dane wejściowe i przygotowuje tablicę startową. Znaki <>^v|-*na planszy startowej są zamieniane na ,, każda z nich ,musi być zastąpiona *we właściwym rozwiązaniu.

Funkcja R próbuje rekurencyjnie umieszczać wszystkie kształty na planszy. Po umieszczeniu kształtu nazywa się on przekazywaniem krótszej listy kształtów i zmodyfikowanej planszy. Po umieszczeniu wszystkich kształtów rozwiązanie może nadal być niepoprawne, jeśli nie zostanie ,zastąpione przez *.

Test funkcji P, czy kształt można umieścić w danej pozycji i orientacji. Sprawdza wszystkie costrains (wewnątrz tablicy, bez nakładania się, bez dotyku, poprawna liczba wierszy i kolumn)

M=w=>(
  [x,c,r,z]=w=w[S='split'](n='\n'),
  (b=[...w.slice(4).join(n)])
  .map((c,p)=>~(k='*<>-*^v|'.indexOf(c))&&[(q=k>3?z:1,0),k&1&&-q,k&2&&q].map(o=>b[p+o]=0),
    c=c[S](e=' '),r=r[S](e),w=z++,f='*',s='',x[S](e).map(v=>s+=v[0].repeat(v[2]))),
  R=(s,b,x=0,y=0,n=s[0],V=i=>b[i]>'#',
    P=(p,o,q,t,g,l,d=[...b])=>{
        if(l<z-n&!V(p+o*l-o)&!V(p+o*l+o*n))
        {
          for(i=-1;v=d[p],++i<w;p+=o,t-=v==f)
            if(i>=l&i-n<l)
              for(v!=e&v!=0|[q,w,~z].some(w=>V(p+w)|V(p-w))?t=0:d[p]=f,j=o*i,u=k=0;
                  ++k<z;(u+=d[j]==f)>g[i]?t=0:j+=q);
          return t>=n&&d.join('')
        }
    })=>{
    if(b){
      if(!n)return~b.search(0)?0:b;
      for(s=s.slice(1);y<w||(y=0,++x<w);++y)
        if(h=R(s,P(y*z,1,z,r[y],c,x))||n>1&&R(s,P(x,z,1,c[x],r,y)))return h
    }
  })(s,b)

Testuj w konsoli FireFox / FireBug

;['3x2 1x4\n2 2 3 1 2\n4 0 3 0 3\n5\n     \n     \n    #\n  #  \n    *\n'
,'3x1 1x6\n2 0 4 0 3\n3 1 2 1 2\n5\n*    \n     \n     \n   # \n     \n'
,'5x1 4x1 2x1 1x2\n1 2 3 3 2 2\n0 5 0 4 0 4\n6\n#     \n  -   \n      \n      \n #    \n   <  \n'
,'4x1 3x1 2x2 1x2\n1 4 0 3 0 5\n4 1 1 2 3 2\n6\n <    \n      \n      \n      \n    # \n ^ #  \n']
.forEach(x=>console.log(x,M(x).replace(/ /g,'`'))) // space replaced with ` for clarity

Wyjście (całkowity czas wykonania <1 s)

3x2 1x4
2 2 3 1 2
4 0 3 0 3
5


    #
  #  
    *

***`*
`````
`***#
``#``
*`*`*

3x1 1x6
2 0 4 0 3
3 1 2 1 2
5
*    


   # 


*`*`*
``*``
``*`*
*``#`
``*`*

5x1 4x1 2x1 1x2
1 2 3 3 2 2
0 5 0 4 0 4
6
#     
  -   


 #    
   <  

#`````
`*****
``````
`****`
`#````
*`**`*

4x1 3x1 2x2 1x2
1 4 0 3 0 5
4 1 1 2 3 2
6
 <    



    # 
 ^ #  

**`*`*
```*``
`````*
`*```*
`*`*#*
`*`#`*