Tak myślałem, że to pytanie będzie, zanim w pełni je przeczytam.

Grupa golfistów wkracza do The Nineteenth Bite Pizzeria i zamawia pizzę. Ma nieregularny kształt, składa się z kwadratów jednostkowych. Twoim zadaniem jest pomóc im pokroić na identyczne plastry. Oznacza to, że plastry muszą mieć dokładnie ten sam kształt i rozmiar; mogą być obracane, ale nie odwracane / dublowane. Na przykład, jeśli są to elementy Tetris, muszą być tego samego rodzaju, nie można użyć zarówno elementu L, jak i J.

Wejście

W pierwszym wierszu zostanie podana liczba osób w grupie (zawsze liczba całkowita od 2 do 10 włącznie), a następnie prostokątna matryca znaków „” (spacja) i „#” reprezentujących pizzę. Wszystkie znaki „#” są połączone krawędziami. Gwarantowana liczba znaków „#” jest wielokrotnością liczby osób.

Wynik

Powinieneś wydrukować tę samą matrycę, a każdy znak „#” zastąpić cyfrą od 0 do n-1 (n oznacza liczbę osób). Każda cyfra powinna oznaczać plasterek. Kształt plastra należy połączyć kwadratowymi krawędziami. Numeracja plasterków nie musi być w żadnej określonej kolejności. Jeśli istnieje wiele sposobów krojenia pizzy, każdy z nich jest dopuszczalny.
Jeśli nie można pokroić pizzy zgodnie z wymaganiami, należy wydrukować ciąg „Brak pizzy dla Ciebie!” zamiast.

Punktacja

To jest kod golfowy. Twój wynik będzie liczbą bajtów w programie. Znaki będą liczone według ich kodowania UTF-8. Najniższy wynik wygrywa.

Przykłady

Wejście:

3
 #  
### 
####
   #

Wynik:

 0  
100 
1122
   2

Wejście:

4
###
# #
###

Wynik:

001
2 1
233

Wejście:

2
#    #
######

Wynik:

No pizza for you!

Wejście:

5
    #  
   ####
  #####
 ##### 
#####  
####   
  #    

Wynik:

    0  
   1000
  21110
 32221 
43332  
4443   
  4    

Wejście:

4
   #   
 ####  
###### 
  #####
  #### 

Wynik:

   0   
 1000  
111203 
  12233
  2233 

Wymagania

• Powinieneś napisać pełny program, który odczytuje ze standardowego wejścia i zapisuje na standardowe wyjście.
• Program musi być uruchamiany w systemie Linux przy użyciu ogólnodostępnego oprogramowania.
• Twój program powinien zakończyć każdy z powyższych przykładów w mniej niż 1 minutę na nowoczesnym komputerze.
• Brak standardowych luk.

Kod PHP, 1808 971 bajtów

Szybka i brudna implementacja w PHP. Najpierw brutalna siła wszystkich możliwych kształtów plastra, następnie brutalna siła wszystkich pozycji i orientacji plastrów.

Stosowanie: cat pizza.txt | php pizza.php

Edycja: zmniejszono rozmiar kodu o ponad 45% poprzez przewijanie algorytmu za pomocą rekurencji zamiast zagnieżdżonych pętli. To jednak zjada pamięć (i pizzę ;-)). Pizza większa niż 8x8 prawdopodobnie zabraknie pamięci. Wariant z zagnieżdżoną pętlą może z łatwością obsługiwać dowolny rozmiar, ale jest dwukrotnie większy niż kod.

<?php define('A',98);$n=fgets(STDIN);$d=array();$m=$u=str_pad('',A,'+');$s=0;while($g=fgets(STDIN)){$g=rtrim($g);assert(strlen($g)<=A-2);$s++;$m.='+'.str_pad(rtrim($g),A-2,' ').'+';for($l=0;$l<strlen($g);$l++)if($g[$l]=='#')$d[]=$s*A+$l+1;}$m.=$u;$r=count($d)/$n;x(reset($d),array(array()),0,0,0,0);die('No pizza for you!');function x($e,$c,$b,$a,$q,$t){global$r,$m,$d;$h=$a*A+$b;if(!in_array($e+$h,$d))return;if(in_array($h,$c[0]))return;$c[0][]=$h;$c[1][]=$b*A-$a;$c[2][]=-$a*A-$b;$c[3][]=-$b*A+$a;if(count($c[0])<$r)do{x($e,$c,$b+1,$a,$b,$a);x($e,$c,$b,$a+1,$b,$a);x($e,$c,$b-1,$a,$b,$a);x($e,$c,$b,$a-1,$b,$a);$v=($b!=$q||$a!=$t);$b=$q;$a=$t;}while($v);else w($c,$m,0,reset($d),0);}function w(&$p,$f,$o,$e,$i){global$n,$d;foreach($p[$i]as$h){$j=$e+$h;if(!isset($f[$j])||$f[$j]!='#')return;$f[$j]=chr(ord('0')+$o);}if(++$o==$n){for($k=A;$k<strlen($f)-A;$k++)if($k%A==A-1)echo PHP_EOL;else if($k%A)echo$f[$k];exit;}foreach($d as$j)for($i=0;$i<4;$i++)w($p,$f,$o,$j,$i);}

Niegolfowany, udokumentowany kod

Poniżej znajduje się udokumentowany, oryginalny kod. Aby zachować zdrowie psychiczne, pracowałem z pełnym kodem źródłowym i napisałem prosty skrypt minizera, aby usunąć instrukcje, takie jak assert()i error_reporting(), usunąć niepotrzebne nawiasy, zmienić nazwy zmiennych, funkcji i stałych, aby wygenerować powyższy kod.

<?php
error_reporting(E_ALL) ;

// Width of each line of pizza shape.
// Constant will be reduced to single character by minifier,
// so the extra cost of the define() will be gained back.
define('WIDTH', 98) ;

// Read number of slices
$nrSlices = fgets(STDIN) ;

// Read pizza shape definition and 
// convert to individual $positionList[]=$y*width+$x and
// linear (1D) $pizzaShape[$y*WIDTH+$x] with protective border around it.
//
// WARNING: assumes maximum pizza width of WIDTH-2 characters!
$positionList = array() ;
$pizzaShape = $headerFooter = str_pad('', WIDTH, '+') ;
$y = 0 ;
while ($line = fgets(STDIN))
{  $line = rtrim($line) ;
   assert(strlen($line) <= WIDTH-2) ;
   $y++ ;
   $pizzaShape .= '+'.str_pad(rtrim($line), WIDTH-2, ' ').'+' ;
   for ($x = 0 ; $x < strlen($line) ; $x++)
   {  if ($line[$x] == '#') $positionList[] = $y*WIDTH + $x+1 ;
   }
}
$pizzaShape .= $headerFooter ;

// Determine size of a slice
$sliceSize = count($positionList)/$nrSlices ;

// Build all possible slice shapes. All shapes start with their first part at 
// the top of the pizza, and "grow" new parts in all directions next to the 
// existing parts. This continues until the slice has the full size. This way
// we end up with all shapes that fit at the top of the pizza.
//
// The shape is defined as the offsets of the parts relative to the base 
// position at the top of the pizza. Offsets are defined as linear offsets in
// the 1-D $pizzaShape string.
//
// For efficiency, we keep track of all four possible rotations while building
// the slice shape.
//
growSlice(reset($positionList), array(array()), 0, 0, 0, 0) ;
die('No pizza for you!') ;

function growSlice($basePosition, $shapeDeltas, $dx, $dy, $prevDx, $prevDy)
{  global $sliceSize, $pizzaShape, $positionList ;

   // Check validity of new position
   // Abort if position is not part of pizza, or 
   // if position is already part of slice
   $delta = $dy*WIDTH + $dx ;
   if (!in_array($basePosition+$delta, $positionList)) return ;
   if (in_array($delta, $shapeDeltas[0])) return ;

   // Add all four rotations to shapeDeltas[]
   $shapeDeltas[0][] = $delta ;
   $shapeDeltas[1][] = $dx*WIDTH - $dy ;
   $shapeDeltas[2][] = -$dy*WIDTH - $dx ;
   $shapeDeltas[3][] = -$dx*WIDTH + $dy ;

   // Have we built a full slice shape?
   if (count($shapeDeltas[0]) < $sliceSize) 
   {  // Grow shape either at current position or at previous position
      do
      {  growSlice($basePosition, $shapeDeltas, $dx+1, $dy,   $dx, $dy) ;
         growSlice($basePosition, $shapeDeltas, $dx,   $dy+1, $dx, $dy) ;
         growSlice($basePosition, $shapeDeltas, $dx-1, $dy,   $dx, $dy) ;
         growSlice($basePosition, $shapeDeltas, $dx,   $dy-1, $dx, $dy) ;
         $retry = ($dx != $prevDx || $dy != $prevDy) ;
         $dx = $prevDx ;
         $dy = $prevDy ;
      } while ($retry) ;
   } else
   {  // Try to cover the entire pizza by translated and rotated instances of
      // the slice shape.
      fitSlice($shapeDeltas, $pizzaShape, 0, reset($positionList), 0) ;
   }
}

function fitSlice(&$shape, $pizza, $id, $basePosition, $rotation)
{  global $nrSlices, $positionList ;

   // Try to fit each part of the slice onto the pizza. If the part falls
   // outsize the pizza, or overlays another slice we reject this position
   // and rotation. If it fits, we mark the $pizza[] with the slice $id.
   foreach ($shape[$rotation] as $delta)
   {  $position = $basePosition + $delta ;
      if (!isset($pizza[$position]) || $pizza[$position] != '#') return ;
      $pizza[$position] = chr(ord('0')+$id) ;
   }

   // If $nrSlices slices have been fitted, we have found a valid solution!
   // In that case, we display the solution and quit.
   if (++$id == $nrSlices)
   {  for ($pos = WIDTH ; $pos < strlen($pizza)-WIDTH ; $pos++)
      {  if ($pos % WIDTH == WIDTH-1) echo PHP_EOL ;
         else if ($pos % WIDTH) echo $pizza[$pos] ;
      }
      exit ;
   }

   // The current slice did fit, but we have still more slices to fit.
   // Try all positions and rotations for the next slice.
   foreach ($positionList as $position)
   {  for ($rotation = 0 ; $rotation < 4 ; $rotation++)
      {  fitSlice($shape, $pizza, $id, $position, $rotation) ;
      }
   }
}