Это то, что я думал, что этот вопрос будет, прежде чем я полностью прочитал его.

Группа игроков в гольф с кодами заходит в пиццерию «Девятнадцатый укус» и заказывает пиццу. Он имеет неправильную форму и состоит из единичных квадратов. Ваша задача - помочь им нарезать его на одинаковые кусочки. То есть ломтики должны иметь одинаковую форму и размер; они могут вращаться, но не переворачиваться / отражаться. Например, если это фигуры тетриса, они должны быть одного типа, вы не можете использовать как фигуру L, так и фигуру J.

вход

Вам будет указано количество человек в группе в первой строке (всегда целое число от 2 до 10 включительно), за которым следует прямоугольная матрица символов '' (пробел) и "#", представляющих пиццу. Все символы «#» связаны через свои края. Количество символов «#» гарантированно будет кратным количеству людей.

Выход

Вы должны напечатать ту же матрицу, где каждый символ «#» заменяется цифрой от 0 до n-1 (n - количество человек). Каждая цифра должна отмечать срез. Форма среза должна быть соединена через квадратные края. Нумерация срезов не должна быть в каком-то определенном порядке. Если есть несколько способов нарезки пиццы, любой из них приемлем.
Если вы не можете разрезать пиццу так, как требуется, вы должны напечатать строку «Нет пиццы для вас!» вместо.

счет

Это код гольф. Ваша оценка будет количество байтов в программе. Символы будут учитываться в кодировке UTF-8. Самый низкий балл побеждает.

Примеры

Входные данные:

3
 #  
### 
####
   #

Выход:

 0  
100 
1122
   2

Входные данные:

4
###
# #
###

Выход:

001
2 1
233

Входные данные:

2
#    #
######

Выход:

No pizza for you!

Входные данные:

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

Выход:

    0  
   1000
  21110
 32221 
43332  
4443   
  4    

Входные данные:

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

Выход:

   0   
 1000  
111203 
  12233
  2233 

Требования

• Вы должны написать полную программу, которая читает из стандартного ввода и записывает в стандартный вывод.
• Программа должна быть запущена в Linux с использованием свободно доступного программного обеспечения.
• Ваша программа должна завершить каждый из приведенных выше примеров менее чем за 1 минуту на современном компьютере.
• Нет стандартных лазеек.

Код PHP, 1808 971 байт

Быстрая и грязная реализация в PHP. Сначала перебор всех возможных форм срезов, затем перебор всех положений и ориентаций срезов.

Использование: cat pizza.txt | php pizza.php

Редактирование: уменьшил размер кода более чем на 45%, переписав алгоритм с использованием рекурсии, а не вложенных циклов. Тем не менее, это ест память (и пиццу ;-)). Пицца больше 8х8, вероятно, не хватит памяти. Вариант с вложенным циклом может легко обрабатывать любой размер, но в два раза больше размера кода.

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

Незакрытый документированный код

Ниже приведен документированный, оригинальный код. Чтобы сохранить здравомыслие, я работал с полным исходным кодом и написал простой скрипт-минификатор, чтобы убрать такие выражения, как assert()и error_reporting(), удалить ненужные скобки, переименовать переменные, функции и константы, чтобы сгенерировать вышеприведенный код.

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