Inilah yang saya pikir akan menjadi pertanyaan ini, sebelum saya sepenuhnya membacanya.

Sekelompok pegolf kode masuk ke The Nineteenth Bite Pizzeria dan memesan pizza. Itu datang dalam bentuk yang tidak teratur, terbuat dari kotak unit. Tugas Anda adalah membantu mereka memotongnya menjadi irisan yang identik. Artinya, irisan harus memiliki bentuk dan ukuran yang sama persis; mereka dapat diputar tetapi tidak terbalik / dicerminkan. Misalnya, jika mereka adalah potongan Tetris, mereka harus jenis yang sama, Anda tidak dapat menggunakan potongan L dan sepotong J.

Memasukkan

Anda akan diberi jumlah orang dalam grup di baris pertama (selalu bilangan bulat dari 2 hingga 10, inklusif), diikuti oleh matriks persegi karakter '' (spasi) dan '#', yang mewakili pizza. Semua karakter '#' terhubung melalui tepinya. Jumlah karakter '#' dijamin kelipatan dari jumlah orang.

Keluaran

Anda harus mencetak matriks yang sama, dengan setiap karakter '#' diganti dengan angka dari 0 hingga n-1 (n menjadi jumlah orang). Setiap digit harus menandai irisan. Bentuk irisan harus terhubung melalui tepi persegi. Penomoran irisan tidak perlu dalam urutan tertentu. Jika ada banyak cara untuk memotong pizza, salah satunya dapat diterima.
Jika tidak mungkin memotong pizza seperti yang diperlukan, Anda harus mencetak string "Tidak ada pizza untuk Anda!" sebagai gantinya.

Mencetak gol

Ini kode golf. Skor Anda akan menjadi jumlah byte dalam program. Karakter akan dihitung melalui pengkodean UTF-8 mereka. Skor terendah menang.

Contohnya

Memasukkan:

3
 #  
### 
####
   #

Keluaran:

 0  
100 
1122
   2

Memasukkan:

4
###
# #
###

Keluaran:

001
2 1
233

Memasukkan:

2
#    #
######

Keluaran:

No pizza for you!

Memasukkan:

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

Keluaran:

    0  
   1000
  21110
 32221 
43332  
4443   
  4    

Memasukkan:

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

Keluaran:

   0   
 1000  
111203 
  12233
  2233 

Persyaratan

• Anda harus menulis program lengkap yang membaca dari input standar dan menulis ke output standar.
• Program harus dapat dijalankan di Linux menggunakan perangkat lunak yang tersedia secara bebas.
• Program Anda harus menyelesaikan masing-masing contoh di atas dalam waktu kurang dari 1 menit pada komputer modern.
• Tidak ada celah standar.

Kode PHP, 1808 971 byte

Implementasi cepat dan kotor di PHP. Brute-force pertama semua bentuk slice yang mungkin, selanjutnya brute-force semua posisi dan orientasi irisan.

Pemakaian: cat pizza.txt | php pizza.php

Sunting: mengurangi ukuran kode lebih dari 45% dengan algoritma rewring menggunakan rekursi daripada loop bersarang. Namun, ini memakan memori (dan pizza ;-)). Pizza yang lebih besar dari 8x8 mungkin akan kehabisan memori. Varian loop bersarang dapat dengan mudah menangani ukuran apa pun, tetapi dua kali ukuran kode.

<?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);}

Kode tidak terdokumentasi dan terdokumentasi

Di bawah ini adalah kode asli yang didokumentasikan. Untuk menjaga kewarasan saya, saya bekerja dengan kode sumber lengkap, dan menulis skrip minifier sederhana untuk menghapus pernyataan seperti assert()dan error_reporting(), menghapus tanda kurung yang tidak perlu, mengganti nama variabel, fungsi dan konstanta untuk menghasilkan kode golf di atas.

<?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) ;
      }
   }
}