16
\$\begingroup\$

This is what I thought this question was going to be, before I fully read it.

A group of code golfers walk into The Nineteenth Bite Pizzeria and order a pizza. It comes in an irregular shape, made of unit squares. Your task is to help them cut it into identical slices. That is, the slices must have the exact same shape and size; they can be rotated but not flipped/mirrored. For example, if they are Tetris pieces, they must be the same kind, you can't use both an L piece and a J piece.

Input

You will be given the number of people in the group on the first line (always an integer from 2 to 10, inclusive), followed by a rectangular matrix of ' ' (space) and '#' characters, representing the pizza. All the '#' characters are connected through their edges. The number of '#' characters is guaranteed to be a multiple of the number of people.

Output

You should print the same matrix, with each '#' character replaced with a digit from 0 to n-1 (n being the number of people). Each digit should mark a slice. The slice shape must be connected through the square edges. The slice numbering doesn't need to be in any particular order. If there are multiple ways of cutting the pizza, any of them is acceptable.
If it's not possible to cut the pizza as required, you should print the string "No pizza for you!" instead.

Scoring

This is code golf. Your score will be the number of bytes in the program. Characters will be counted through their UTF-8 encoding. Lowest score wins.

Examples

Input:

3
 #  
### 
####
   #

Output:

 0  
100 
1122
   2

Input:

4
###
# #
###

Output:

001
2 1
233

Input:

2
#    #
######

Output:

No pizza for you!

Input:

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

Output:

    0  
   1000
  21110
 32221 
43332  
4443   
  4    

Input:

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

Output:

   0   
 1000  
111203 
  12233
  2233 

Requirements

  • You should write a full program that reads from the standard input and writes to the standard output.
  • The program must be runnable in Linux using freely available software.
  • Your program should finish each of the above examples in less than 1 minute on a modern computer.
  • No standard loopholes.
\$\endgroup\$
3
  • 3
    \$\begingroup\$ The Nineteenth Bite :^) \$\endgroup\$ Sep 9, 2015 at 20:30
  • \$\begingroup\$ @FryAmTheEggman © Calvin's Hobbies \$\endgroup\$ Sep 9, 2015 at 20:45
  • \$\begingroup\$ Bonus for regex solutions. \$\endgroup\$
    – flawr
    Sep 10, 2015 at 9:59

1 Answer 1

3
\$\begingroup\$

PHP code, 1808 971 bytes

Quick and dirty implementation in PHP. First brute-force all possible slice shapes, next brute-force all positions and orientations of the slices.

Usage: cat pizza.txt | php pizza.php

Edit: reduced code size by more than 45% by rewring algorithm using recursion rather than nested loops. However, this eats memory (and pizza's ;-)). Pizza's larger than 8x8 will probably run out of memory. The nested loop variant can easily handle any size, but is twice the code size.

<?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, documented code

Below is the documented, original code. To keep my sanity, I worked with the full source code, and wrote a simple minifier script to strip statements like assert() and error_reporting(), remove unnecessary brackets, rename variables, functions and constants to generate the golfed code above.

<?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) ;
      }
   }
}
\$\endgroup\$
6
  • \$\begingroup\$ I'm getting "PHP Fatal error: Cannot redeclare _() in pizza.php on line 1" \$\endgroup\$ Sep 13, 2015 at 14:03
  • \$\begingroup\$ @aditsu: there is only one function _() in the golfed version. Did you accidently copy-paste the code twice? \$\endgroup\$ Sep 17, 2015 at 7:30
  • \$\begingroup\$ The file size is 972 so I don't think the code could fit twice. The ungolfed code seems to work btw :) \$\endgroup\$ Sep 17, 2015 at 8:57
  • \$\begingroup\$ I noticed you have define('_',98), doesn't that conflict with function _? I don't know php so I can't tell... \$\endgroup\$ Sep 17, 2015 at 9:01
  • \$\begingroup\$ @aditsu: The golfed code works fine on my Mac with PHP 5.4.43, but it appears _() is an alias for gettext() on other platforms. Changed minifier to avoid _() altogether. \$\endgroup\$ Sep 17, 2015 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.