Voilà ce que je pensais de cette question allait être, avant de la lire entièrement.

Un groupe de golfeurs de code entre dans la pizzeria The Nineteenth Bite et commande une pizza. Il se présente sous une forme irrégulière, faite de carrés unitaires. Votre tâche consiste à les aider à le couper en tranches identiques. Autrement dit, les tranches doivent avoir exactement la même forme et la même taille; ils peuvent être tournés mais pas retournés / mis en miroir. Par exemple, si ce sont des pièces Tetris, elles doivent être du même type, vous ne pouvez pas utiliser à la fois une pièce L et une pièce J.

Contribution

Vous recevrez le nombre de personnes dans le groupe sur la première ligne (toujours un entier de 2 à 10 inclus), suivi d'une matrice rectangulaire de caractères `` (espace) et '#', représentant la pizza. Tous les caractères «#» sont connectés par leurs bords. Le nombre de caractères «#» est garanti être un multiple du nombre de personnes.

Production

Vous devez imprimer la même matrice, chaque caractère '#' étant remplacé par un chiffre de 0 à n-1 (n étant le nombre de personnes). Chaque chiffre doit marquer une tranche. La forme de tranche doit être connectée à travers les bords carrés. La numérotation des tranches n'a pas besoin d'être dans un ordre particulier. S'il existe plusieurs façons de couper la pizza, l'une d'entre elles est acceptable.
S'il n'est pas possible de couper la pizza comme requis, vous devez imprimer la chaîne "Pas de pizza pour vous!" au lieu.

Notation

C'est le golf de code. Votre score sera le nombre d'octets dans le programme. Les personnages seront comptés via leur encodage UTF-8. Le score le plus bas l'emporte.

Exemples

Contribution:

3
 #  
### 
####
   #

Production:

 0  
100 
1122
   2

Contribution:

4
###
# #
###

Production:

001
2 1
233

Contribution:

2
#    #
######

Production:

No pizza for you!

Contribution:

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

Production:

    0  
   1000
  21110
 32221 
43332  
4443   
  4    

Contribution:

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

Production:

   0   
 1000  
111203 
  12233
  2233 

Exigences

• Vous devez écrire un programme complet qui lit à partir de l'entrée standard et écrit sur la sortie standard.
• Le programme doit être exécutable sous Linux en utilisant un logiciel disponible gratuitement.
• Votre programme devrait terminer chacun des exemples ci-dessus en moins d'une minute sur un ordinateur moderne.
• Pas de failles standard.

Code PHP, 1808 971 octets

Implémentation rapide et sale en PHP. D'abord force brute toutes les formes de tranche possibles, ensuite force brute toutes les positions et orientations des tranches.

Usage: cat pizza.txt | php pizza.php

Edit: réduction de la taille du code de plus de 45% en réécrivant l'algorithme en utilisant la récursivité plutôt que les boucles imbriquées. Cependant, cela mange de la mémoire (et des pizzas ;-)). Les pizzas plus grandes que 8x8 manqueront probablement de mémoire. La variante de boucle imbriquée peut facilement gérer n'importe quelle taille, mais est deux fois la taille du code.

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

Code non golfé et documenté

Ci-dessous se trouve le code original documenté. Pour garder ma raison, j'ai travaillé avec le code source complet et j'ai écrit un script de minifieur simple pour supprimer les instructions comme assert()et error_reporting(), supprimer les crochets inutiles, renommer les variables, les fonctions et les constantes pour générer le code joué ci-dessus.

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