Gra wideo Minecraft polega na umieszczaniu i usuwaniu różnego rodzaju bloków w siatce liczb całkowitych 3D, która tworzy świat wirtualny. Każdy punkt sieci może zawierać dokładnie jeden blok lub być pusty ( oficjalnie blok „ powietrzny ”). W tym wyzwaniu zajmiemy się tylko jedną poziomą płaszczyzną 2D świata 3D i jednym rodzajem bloku: skrzyniami .

Skrzynie pozwalają graczom przechowywać przedmioty. Kiedy dwie skrzynie są prostopadle przylegające do tej samej płaszczyzny poziomej, ich tekstury łączą się i tworzy się podwójna skrzynia o podwójnej pojemności. Nie można zrobić nic większego niż podwójna skrzynia; nie ma potrójnych skrzyń ani poczwórnych skrzyń.

Blok skrzyni można umieścić w pustym kracie tylko wtedy, gdy wszystkie cztery sąsiadujące ze sobą prostopadle punkty są puste lub jeśli dokładnie jeden zawiera blok skrzyni, który nie jest już częścią podwójnej skrzyni. Te zasady rozmieszczania zapewniają, że bloki skrzyń łączące się w podwójne skrzynie nigdy nie będą dwuznaczne.

Załóżmy na przykład, że .jest to puste miejsce i Cskrzynia: (Liczby są również pustym miejscem i służą wyłącznie do identyfikacji).

.......C..
.1.C2.C3..
........5C
.CC4..CC..
..........

• Skrzynię można umieścić w miejscu 1, ponieważ jej 4 sąsiadów jest pustych.
• Skrzynię można umieścić w miejscu 2, ponieważ sąsiednia skrzynia nie jest (jeszcze) częścią podwójnej skrzyni.
• Skrzyni nie można umieścić w miejscu 3, ponieważ istniałaby dwuznaczność co do sposobu tworzenia podwójnej skrzyni.
• Skrzyni nie można umieścić w miejscu 4, ponieważ sąsiednia skrzynia jest już częścią podwójnej skrzyni.
• Skrzynia może zostać umieszczona w miejscu 5. Podwójna skrzynia sąsiadująca po przekątnej niczego nie wpływa.

Zakładając, że obszar poza siatką jest pusty, zmiana każdej .na siatce na pozycję, *jeśli można tam umieścić skrzynię, powoduje:

******.C**
***C**C.**
*..***..*C
.CC.*.CC.*
*..***..**

*Oczywiście nie wszystkie pola mogą być jednocześnie zajęte przez skrzynie, ale jeśli masz tylko jedną skrzynię, można ją umieścić w dowolnej z nich.

Wyzwanie

Napisz program lub funkcję, która pobiera a .i Cgrid, i zmienia każdy .na a, *jeśli można tam umieścić skrzynię, drukując lub zwracając wynikową siatkę.

• Dane wejściowe mogą pochodzić ze standardowego wejścia lub pliku lub jako argument ciągu funkcji.

• Możesz założyć, że dane wejściowe są dobrze uformowane - tj. Idealnie prostokątna siatka tekstu, o szerokości i wysokości co najmniej 1 znaku, zawierająca tylko .i CMożesz opcjonalnie założyć, że po ostatnim wierszu znajduje się znak nowej linii (i może być jedna na wyjściu ).

• Możesz założyć, że rozmieszczenie skrzyń na wejściu jest zgodne z powyższymi zasadami. Nigdy nie będzie dwuznaczności, które skrzynie tworzą podwójne skrzynie.

• W razie potrzeby można użyć dowolnych trzech odrębnych druku ASCII znaków w miejsce ., Ci *. Nie możesz używać czegoś innego zamiast nowych linii.

• Wszystkie skrzynie są normalnymi skrzyniami. Nie uwięzione skrzynie lub skrzynie końcowe .

Punktacja

Zgłoszenie z najmniejszą liczbą bajtów wygrywa.

^{W przypadku wyzwania związanego z Minecraft, które jest nieco trudniejsze, spróbuj Nether Portal Detection .}

CJam, 82 76 66 62 58 54 bajtów

qN/::~4{[8_]f/[9_]f*z{[{1$8-g)+}*]W%}%}*{_8<\2<8?}f%N*

Format wejściowy oczekuje 0dla komórki powietrznej i 8komórki piersiowej. Dane wyjściowe zawierają 1dla wszystkich komórek, które można umieścić za pomocą skrzyni.

AKTUALIZACJA : Naprawiono błąd. Zwiększony o 3 bajty :( grał w golfa dalej :). 4 bajty zapisane dzięki @ Sp3000

Przykładowe dane wejściowe:

0000000800
0008008000
0000000008
0880008808
0000000000

Wynik:

1111110811
1110018010
1008800108
0880088008
1008800110

Chyba już skończyłem grać w golfa ...

Wyjaśnienie

qN/::~                   "This part converts the input into array of integer array";
qN/                      "Split input on new line";
   ::~                   "Parse each character in each row as integer";

4{[8_]f/[9_]f*z{[{1$8-g)+}*]W%}%}*

4{   ...z{       W%}%}*  "Run the logic 4 times, first, columns in correct order, then,";
                         "columns in reverse order, then for rows";
  [8_]f/[9_]f*           "Convert adjacent chests represented by two 8 into two 9";
                         "This happens for all the rows in the columns iterations and";
                         "for all the columns in the rows iterations";
  {               }%     "For each row/column";
   [{        }*]         "Reduce and wrap it back in the array";
     :I8-                "Store the second number in I, remove 8 from it";
         g               "Do signum. Now we have -1 for < 8 number, 0 for 8 and 1 for > 8";
          )+I            "Increment to get 0, 1 & 2. Add it to first number and put I back";

{_8<\2<8?}f%N*           "This part converts the output from previous iterations";
                         "to 3 character based final output and prints it";
{        }f%             "Map each row using the code block";
 _8<   8?                "If the value is greater than 7, make it 8, else:";
    \2<                  "If the value is greater than 1, make it 0, else 1";
            N*           "Join the arrays using new line";

Wypróbuj online tutaj

.NET Regex ( Retina ), 434 416 310 + 1 = 311 bajtów

Po ostatnim wyzwaniu, na które odpowiedziałem w wyrażeniu regularnym (Wyzwanie Nether Portal, z którym łączy się to wyzwanie), w końcu postanowiłem napisać narzędzie wiersza polecenia, które działa jako interpreter wyrażeń regularnych w stylu .NET, dzięki czemu mogę odpowiadać na pytania z wyrażeniami regularnymi bez rzucania wyzwania, że ​​nie są one samodzielnym językiem. Nazwałem to Retina.

Teraz to wyzwanie nie nadaje się zbyt dobrze do przedłożenia wyrażenia regularnego, ale musiałem teraz użyć Retiny. ;) (Plus, Sp3000 wezwał mnie do zrobienia tego na czacie.) Oto więc:

Plik Regex

m`(?<=(?=.(.)*).*)(?<=((?<=(?<2>C|C(?(1)!)(\n|(?<-1>.))*)?)C(?=(?<2>C|(\n|(?<-1>.))*(?(1)!)C)?)(()(?(6)!)|(?<=^(?(7)!)(?<-7>.)*C).*\n(.)*()(?(8)!)))?){2}_(?=(?<2>((?(10)!)()|(?(11)!)()(.)*\n.*(?=C(?<-12>.)*(?(12)!)$))(?<=(?<2>C|C(?(1)!)(\n|(?<-1>.))*)?)C(?=(?<2>C|(\n|(?<-1>.))*(?(1)!)C)?))?){2}(?<-2>)?(?(2)!)

Plik zastępczy

*

Plik wyrażeń regularnych to głównie wyrażenia regularne, z wyjątkiem tego, że `pozwala umieścić w pliku kilka opcji, w tym przypadku po prostu tryb wielowierszowy. Po otrzymaniu dwóch plików Retina automatycznie przyjmuje tryb zamiany wszystkich plików. Te dwa pliki definiują program, który odczytuje dane wejściowe ze STDIN i drukuje wynik do STDOUT.

Możesz go również przetestować na RegexHero i RegexStorm . Wyrażenie regularne działa zarówno z końcowym znakiem nowej linii, jak i bez niego, i używa _zamiast .. (Najwyraźniej RegexStorm czasami ma problemy, jeśli nie ma końcowego nowego wiersza, ale RegexHero wydaje się dobrze obsługiwać oba przypadki).

W wyrażeniu regularnym występuje straszna ilość duplikacji i mam kilka pomysłów na znaczne skrócenie go ... Spróbuję później, a następnie dodam wyjaśnienie. Tymczasem daj mi znać, czy możesz znaleźć jakieś dane wejściowe, które dają zły wynik.

J, 75 73 bajtów

((,.|.)0 _1 0 1)(+:@](LF,@:,.~'*.C'{~>.)(2=f)+.[f]*f=.[:+/|.!.0)'C'&=;._2

Używa formatu w pytaniu, używając odpowiednio ./ */ Cdla spacji / powierzchni użytkowej / skrzyni.

Edycja: naprawia mały błąd (przypadkowo użyłem torusa zamiast poprawnie traktować otoczenie jako pustą przestrzeń).

Wyjaśnienie

## Preparation
              'C'&=;._2  NB. Map ./C to 0/1, turn into matrix
((,.|.)0 _1 0 1)         NB. Compute offsets to shift into each direction
                         NB. (i.e. [[_1 0], [1 0], [0 _1], [0 1]] in any order)


## "Part B"
(2=f)+.[f]*f=.[:+/|.!.0  NB. This part computes a matrix that is 1 for cells that
                         NB. cannot contain a chest:
              [:+/|.!.0  NB. Sum of shifts: shift in each of the four cardinal
                         NB. directions (using the array above) and then sum up.
           f=.           NB. Define this function as `f`; we'll use it some more.
         ]*              NB. Multiply by the "is chest" matrix: this isolates
                         NB. double-chests.
       [f                NB. Sum of shifts--1 for double-chest neighbours.
(2=f)                    NB. Isolate cells with two neighbouring chest.
     +.                  NB. Boolean or--either two neighbouring chests or next
                         NB. to a double-chest.

## Wrap up the result
(+:@] (fmt >.) PartB)    NB. Maximum of the array from the above and twice the "is
 +:@]      >.  PartB     NB. chest" matrix--this is 0,1,2 for '*', '.' or chest,
                         NB. respectively.

## Output formatting
LF,@:,.~'*.C'{~          NB. Format output...
        '*.C'{~          NB. Map 0,1,2 to '*.C' by using the value as index
LF   ,.~                 NB. Append line feed at end of each line
  ,@:                    NB. Ravel into one line

C 193

2 niepotrzebne nowe znaki dla jasności. Zmiany w odniesieniu do nieoznakowanego kodu obejmują: znaki jako kody ascii zamiast literałów znaków; przegrupowanie v = 0, strlen i strchr w celu zapisania znaków (strchr jest najbrzydszy, ponieważ oznacza, że ​​obliczenia, które w innym przypadku zostałyby wykonane tylko raz, są wykonywane 5 razy na komórkę!)

Funkcje C nie przyjmują ciągów jako argumentów ani nie zwracają ich jako wartości, więc najlepsze, co mogę zrobić, to: qwskaźnik do ciągu wejściowego. Funkcja modyfikuje ciąg, a gdy funkcja zwróci, wynik znajduje się w oryginalnym ciągu.

g(char*q){int v,j,w,l;
int f(p,d){int s=0,i=w=strchr(q,10)-q+1,r;for(;w/i;i-=i-1?w-1:2)r=p+i,r>-1&r<l&&q[r]==67&&++s&&d&&f(r,0);v|=s>d;}
for(j=l=strlen(q);j--;f(j,1),46-q[j]||v||(q[j]=42))v=0;}

Podsumowując zasady:

pusty kwadrat (który nie zawiera C ani nowej linii) może zostać przekonwertowany, jeśli ma maksymalnie 1 sąsiada z C

... I ten sąsiad nie ma sąsiadów z C.

Funkcja g zawiera funkcję f, która powraca od głębokości 1 do głębokości 0. Przy tylko 2 poziomach rekurencji wystarczy proste f(r,0)wywołanie rekurencyjne, nie ma takiej potrzeby f(r,d-1)!

Nieskluczony kod w programie testowym

Wejściowy ciąg testowy jest zakodowany na stałe. getsi scanfnie zaakceptuje ciągu wejściowego z nowymi liniami; kroją go na kawałki przy każdej nowej linii.

char n[]=".......C..\n...C..C...\n.........C\n.CC...CC..\n..........";

g(char*q){

  int v,j,w,l;

  int f(p,d){                    //p=cell to be checked,d=recursion depth
    int s=0,i=w,r;               //sum of C's found so far=0, i=width
    for(;w/i;i-=i-1?w-1:2)       //For i in   w,1,-1,-w   = down,right,left,up
      r=p+i,                     //r=cell adjacent to p
      r>-1&r<l&&q[r]=='C'&&++s   //If r not out of bounds and equal to C, increment s...
        &&d&&f(r,0);             //...and if recursion depth not yet at zero, try again one level deeper. 
    v|=s>d;                      //If the local s exceeds d, set global v to true to indicate invalid.
  }

  w=strchr(q,10)-q+1;            //width equals index of first newline + 1                   
  l=strlen(q);                   //length of whole string;
  for(j=l;j--;)                  //for l-1 .. 0 
    v=0,                         //clear v
    f(j,1),                      //and scan to see if it should be set
    '.'-q[j]||v||(q[j]='*');     //if the character is a '.' and v is not invalid, change to '*'
}

main(){
  g(n);
  puts(n);
}

Dane wyjściowe oparte na przykładzie pytania

******.C**
***C**C.**
*..***..*C
.CC.*.CC.*
*..***..**

JavaScript (ES6) 124 129

Używanie znaków 0 (*), 6 (C), 7 (.)

F=s=>[for(c of(d=[o=~s.search('\n'),-o,1,i=-1],s))
   d.map(j=>t-=s[i+j]==6&&~d.some(k=>s[i+j+k]==6),t=i++)|c<7|t>i&&c
].join('')

Nie golfił i wyjaśnił

F=s=>
{
  o=~s.search('\n') // offset to prev row (~ is shorter than +1 and sign does not matter)
  d=[o,-o,1,-1] // array of offset to 4 neighbors
  i=-1
  result = '' // in golfed code, use array comprehension to build the result into an array, then join it
  for (c of s) // scan each char
  {
    t = i++ // set a starting value in t and increment current position in i
    d.forEach(j => // for each near cell, offset in j
    {         
      if (s[i+j]==6) // if cell contains a Chest, must increment t
      {  
        // In golfed code "~some(...)" will be -1(false) or -2(true), using decrement instead of increment
        if (d.some(k=>s[i+j+k]==6)) // look for another Cheast in the neighbor's neighbors
        {
          // more than one chest, position invalid
          t += 2
        }
        else
        {
          t += 1
        }
      }
    })
    if (c < 7 // current cell is not blank
        || t > i) // or t incremented more than once, position invalid
    {
       result += c // curent cell value, unchanged
    }
    else
    {
       result += 0 // mark a valid position 
    }
  }
  return result
}

Przetestuj w konsoli Firefox / FireBug

a='\
7777777677\n\
7776776777\n\
7777777776\n\
7667776677\n\
7777777777\n';

console.log(F(a))

Wynik

0000007600
0006006700
0770007706
7667076670
0770007700

Perl, 66

Dopasowanie wyrażeń regularnych do klatki piersiowej zakończyło się na dłuższą metę, więc tym razem nie konkurowano z CJam.

#!perl -p0
/.
/;$"=".{@-}";s%0%s/\G0/2/r!~/2((.$")?2(.$")?|2$"|$"2)2/s*1%eg

Używa 0 i 2 dla pustych i skrzynek na wejściu, 1 do zaznaczenia miejsc na wyjściu.

Wypróbuj tutaj .

Python 2 - 281 bajtów

f=lambda x,y:sum(m[y][x-1:x+2])+m[y-1][x]+m[y+1][x]
m=[];o=''
try:
 while 1:m+=[map(int,'0%s0'%raw_input())]
except:a=len(m[0]);l=len(m);m+=[[0]*a]
for y in range(l*2):
 for x in range(1,a-1):
    if y<l:m[y][x]*=f(x,y)
    else:o+=`2if m[y-l][x]else +(f(x,y-l)<5)`
 if y>=l:print o;o=''

(Wiersze 8 i 9 są oznaczone pojedynczym znakiem tabulacji, który SE konwertuje na 4 spacje. Każda linia w tym programie ma 0 lub 1 bajt wiodących białych znaków).

Wkład: 0brak skrzyni, 2skrzynia
Ouput: 0brak skrzyni, 2istniejąca skrzynia, 1ewentualna nowa skrzynia

Boże, to jest okropne. Muszę poważnie zrezygnować z praktyki. Rzuciłem każdą sztuczką, którą znam, i wyszło ... no cóż, wyszło jako 281 bajtów, tracąc każdą odpowiedź oprócz tej w wyrażeniu regularnym , haha. Naprawdę czuję, że grałem w golfa całkiem dobrze, więc zgaduję, że mój algorytm był po prostu mniej niż idealny.

Nie golfowany:

def f(x,y):
    """Given x,y coords of the board, return the sum of that point and all
    adjacent points.
    """
    return (sum(board[y][x-1:x+2]) # (x-1,y) + (x,y) + (x+1,y)
            + board[y-1][x]
            + board[y+1][x])
board=[]
output=''
try:
    while True:
        row = '0%s0' % raw_input() # line from stdin with a leading and trailing 0
        board.append(map(int, row)) # convert to list of ints
except:
    pass # exception is thrown when stdin is empty

board_width = len(board[0])
board_height = len(board)

board.append([0]*board_width) # new row of all 0s

for y in xrange(board_height*2):
    # board_height multiplied by 2 so we can use this loop to simulate two
    for x in xrange(1,board_width-1):
        if y < board_height: # "first loop"
            board[y][x] *= f(x,y) # multiply everything on the board by itself + sum
                                  # of neighbours
                                  # empty cells (0) stay 0 no matter what
                                  # lone chests (2 surrounded by 0) become 2*2==4
                                  # double chests (2 touching another 2) are weird:
                                  # - one chest becomes 2*(2+2)==8
                                  # - the other chest becomes 2*(2+8)==20
        else: # "second loop"
            if board[y - board_height][x] != 0:
                output += '2' # anything not equal to 0 is an existing chest
            else:
                valid = f(x, y - board_height) < 5 # if the sum of neighbours > 4, the
                                                   # current cell is either beside a
                                                   # double chest or more than one
                                                   # single chest
                output += '01'[valid]
    if y >= board_height: # only print during the "second loop"
        print output
        output=''