Schneiden Sie eine Pizza in identische Scheiben

16

Dies ist, was ich diese Frage dachte würde, bevor ich sie vollständig gelesen habe.

Eine Gruppe von Code-Golfern betritt die The Nineteenth Bite Pizzeria und bestellt eine Pizza. Es kommt in einer unregelmäßigen Form, bestehend aus Quadraten. Ihre Aufgabe ist es, ihnen zu helfen, es in identische Scheiben zu schneiden. Das heißt, die Scheiben müssen exakt die gleiche Form und Größe haben. Sie können gedreht, aber nicht gespiegelt werden. Wenn es sich beispielsweise um Tetris-Teile handelt, muss es sich um die gleiche Art handeln. Sie können nicht sowohl ein L-Stück als auch ein J-Stück verwenden.

Eingang

In der ersten Zeile wird die Anzahl der Personen in der Gruppe angegeben (immer eine ganze Zahl von 2 bis einschließlich 10), gefolgt von einer rechteckigen Matrix aus '' (Leerzeichen) und '#' Zeichen, die die Pizza darstellen. Alle '#' Zeichen sind durch ihre Kanten verbunden. Die Anzahl der '#' Zeichen ist garantiert ein Vielfaches der Anzahl der Personen.

Ausgabe

Sie sollten dieselbe Matrix drucken, wobei jedes '#' Zeichen durch eine Ziffer von 0 bis n-1 ersetzt wird (n ist die Anzahl der Personen). Jede Ziffer sollte eine Scheibe markieren. Die Scheibenform muss durch die quadratischen Kanten verbunden werden. Die Slice-Nummerierung muss nicht in einer bestimmten Reihenfolge erfolgen. Wenn es mehrere Möglichkeiten zum Schneiden der Pizza gibt, ist jede davon akzeptabel.
Wenn es nicht möglich ist, die Pizza nach Bedarf zu schneiden, sollten Sie die Zeichenfolge "Keine Pizza für Sie!" Drucken. stattdessen.

Wertung

Das ist Code Golf. Ihre Punktzahl ist die Anzahl der Bytes im Programm. Zeichen werden durch ihre UTF-8-Codierung gezählt. Die niedrigste Punktzahl gewinnt.

Beispiele

Eingang:

3
 #  
### 
####
   #

Ausgabe:

 0  
100 
1122
   2

Eingang:

4
###
# #
###

Ausgabe:

001
2 1
233

Eingang:

2
#    #
######

Ausgabe:

No pizza for you!

Eingang:

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

Ausgabe:

    0  
   1000
  21110
 32221 
43332  
4443   
  4    

Eingang:

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

Ausgabe:

   0   
 1000  
111203 
  12233
  2233 

Bedarf

  • Sie sollten ein vollständiges Programm schreiben, das von der Standardeingabe liest und in die Standardausgabe schreibt.
  • Das Programm muss unter Linux mit frei verfügbarer Software lauffähig sein.
  • Ihr Programm sollte jedes der oben genannten Beispiele auf einem modernen Computer in weniger als 1 Minute beenden.
  • Keine Standardlücken.
aditsu
quelle
3
Der neunzehnte Biss : ^)
FryAmTheEggman
@FryAmTheEggman © Calvins Hobbys
aditsu
Bonus für Regex-Lösungen.
Fehler

Antworten:

3

PHP Code, 1808 971 Bytes

Schnelle und schmutzige Implementierung in PHP. Erstens alle möglichen Schnittformen brachial erzwingen, zweitens alle Positionen und Ausrichtungen der Schnitte brachial erzwingen.

Verwendung: cat pizza.txt | php pizza.php

Bearbeiten: Reduziert die Codegröße um mehr als 45%, indem der Algorithmus mithilfe von Rekursion und nicht mit verschachtelten Schleifen neu gestartet wird. Dies frisst jedoch Speicher (und Pizza ;-)). Pizza größer als 8x8 wird wahrscheinlich keinen Speicher mehr haben. Die Variante mit verschachtelten Schleifen kann problemlos mit jeder Größe umgehen, ist jedoch doppelt so groß wie der 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);}

Ungolfed, dokumentierter Code

Unten finden Sie den dokumentierten Originalcode. Um meinen Verstand zu wahren, habe ich mit dem vollständigen Quellcode gearbeitet und ein einfaches Minifier-Skript geschrieben, um Anweisungen wie assert()und zu error_reporting()entfernen, unnötige Klammern zu entfernen, Variablen, Funktionen und Konstanten umzubenennen und den oben genannten Code zu generieren.

<?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) ;
      }
   }
}
Jason Smith
quelle
Ich erhalte die Meldung "
Schwerwiegender
@aditsu: In der Golfversion gibt es nur eine Funktion _ (). Haben Sie den Code versehentlich zweimal kopiert und eingefügt?
Jason Smith
Die Dateigröße beträgt 972, daher glaube ich nicht, dass der Code zweimal passen könnte. Der ungolfed Code scheint übrigens zu funktionieren :)
aditsu
Mir ist aufgefallen, dass du das hast define('_',98), steht das nicht im Widerspruch function _? Ich kenne kein PHP, also kann ich nicht sagen ...
Aditsu
@aditsu: Der Golf-Code funktioniert auf meinem Mac mit PHP 5.4.43 einwandfrei, aber es scheint, dass _ () ein Alias ​​für gettext () auf anderen Plattformen ist. Minifier geändert, um _ () komplett zu vermeiden.
Jason Smith