8
\$\begingroup\$

Challenge

Write a program which, given a 2-dimensional boolean array (equivalently, a monochromatic bitmap), outputs a series of polygons that describe the outline of the region that is “true” (1).

The input is provided as a sequence of '#' (hash), ' ' (space) and \n (newline) characters. Lines may differ in length, in which case the missing parts are assumed to be spaces. The output should be a (newline-separated) list of polygons, each polygon represented by a (comma-separated) list of coordinates.

Examples & Requirements

  1. The co-ordinates must be listed in clockwise order. Input:

    #
    

    Acceptable outputs include:

    (0,0), (1,0), (1,1), (0,1)
    
    (1,0), (1,1), (0,1), (0,0)
    
    (1,1), (0,1), (0,0), (1,0)
    
    (0,1), (0,0), (1,0), (1,1)
    
  2. Disjoint regions must return multiple polygons. Input:

    # #
    

    Example output (actual output must consist of two lines):

    (0,0), (1,0), (1,1), (0,1)
    (2,0), (3,0), (3,1), (2,1)
    
  3. Holes in a polygon must be listed as a separate polygon, but in anti-clockwise order. Input:

    ###
    # #
    ###
    

    Example output:

    (0,0), (3,0), (3,3), (0,3)
    (1,1), (1,2), (2,2), (2,1)
    
  4. You are free to choose whether diagonally adjacent vertices join up or not. Input:

    #
     #
    

    Example output:

    (0,0), (1,0), (1,1), (0,1)
    (1,1), (2,1), (2,2), (1,2)
    

    or

    (0,0), (1,0), (1,1), (2,1), (2,2), (1,2), (1,1), (0, 1)
    
  5. The lists of coordinates need not be optimally short. For example:

    ##
    

    Acceptable outputs:

    (0,0), (2,0), (2,1), (0,1)
    
    // Redundant coordinates along a straight line are acceptable
    (0,0), (1,0), (2,0), (2,1), (1,1), (0,1)
    
    // Duplicate start- and end-point are acceptable
    (0,0), (2,0), (2,1), (0,1), (0,0)
    

As usual, shortest program “wins”.

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you explain the corollary of point 5? I find it highly counterintuitive. \$\endgroup\$ – Peter Taylor Mar 8 '11 at 17:19
  • \$\begingroup\$ if you said that in a square AB over CD then BC are always connected and AD are always disconnected that would be consistent, but you seem to be saying (in effect) that the squares aren't really squares and their shapes change subtly when you convert a # to a space or vice versa. \$\endgroup\$ – Peter Taylor Mar 9 '11 at 8:06
  • \$\begingroup\$ I've added a couple of tags to help categorize this beast. [optimized-output] is intended to represent you condition "The lists of coordinates need not be optimally short", and I would be happy if someone could find a better expression for it. \$\endgroup\$ – dmckee --- ex-moderator kitten Mar 11 '11 at 19:25
  • \$\begingroup\$ I’ve relaxed the conditions a little, so whether diagonally-adjacent things join up or not is now optional. I’ve also deleted my comments defending the old requirements. \$\endgroup\$ – Timwi Dec 19 '15 at 21:58
3
\$\begingroup\$

Perl, 345 311 265 chars

s!.!$i{$x++}=$&eq'#'!ge,$x=$r+=64for<>;sub a{$d+=@_||3;$d%=4;$y=$x%64;$z=$x>>6;$c.=", ($y,$z)";}for$x(keys%i){if($c=!$v{$x}&$i{$x}&!$i{$x-1}){$i{($x+=(1,64)[$d^3])-(64,65,1)[$d]}?$i{$x-(65,1,0,64)[$d]}?a 1:($x-=(64,1)[$d]):a while$d||!$v{$x}++;print substr$c.$/,3}}

Limitations

Assumes that the input is no wider than 64 characters (but its height is in principle unbounded). This can be extended to 512 or 8192 or any other power of two by changing the relevant constants, making the code only slightly longer.

Slightly more readable version

Some credit goes to mob because the first line is my re-use of his idea in lasers. The rest is entirely my work.

# Read “%i”nput (this line is essentially mob’s idea, see above)
s!.! $i{$x++} = $& eq '#' !ge, $x = $r += 64 for <>;

# Subroutine to add a vertex to the current polygon and change the current “$d”irection
sub a
{
    $d += @_ || 3;
    $d %= 4;
    $y = $x % 64;
    $z = $x >> 6;
    $c .= ", ($y,$z)";
}

for $x (keys %i)
{
    # Go to the next “upward-pointing” edge that we haven’t already “%v”isited.
    if ($c = !$v{$x} & $i{$x} & !$i{$x-1})
    {
        # We’re going in the “$d”irection of 0=up, 1=left, 2=down, 3=right
        $i{($x += (1,64)[$d^3]) - (64,65,1)[$d]}
        ?  $i{$x - (65,1,0,64)[$d]}
           ?  a 1               # take a 90° turn to the left
           : ($x -= (64,1)[$d]) # move straight ahead
        : a                     # take a 90° turn to the right

        # Only stop if the current “$d”irection is “up” and we encounter a “%v”isited edge
        # (which necessarily is the one we started from)
        while $d || !$v{$x}++;

        # Remove “1, ” and output this polygon
        print substr $c.$/, 3
    }
}

Edits

  • (345 → 312) Realised there’s no need to update $x when taking a turn because the next iteration will already do it
  • (312 → 311) Change 1=down,2=left to 1=left,2=down and update $d via XOR instead of directly
  • (311 → 265) Remove repetition of the innermost expression and use arrays to parametrise it
\$\endgroup\$
2
\$\begingroup\$

Python, 607 characters

The code works by keeping a list of the boundaries discovered so far as it processes # symbols in input order. The boundaries are stored in a table E which maps edges (4-tuples of x_start,y_start,x_end,y_end) to a list of edges which form the boundary of a polygon. As we process each new #, it may be connected to a polygon above (p) or to its left (q). The code finds p and q using E and then merges the boundary of the current # (r) with p and q, if they exist. The case where p==q generates holes.

import sys
x=y=N=0
E={}
def P(L):
 if L:print ', '.join(map(lambda z:str(z[:2]),L))
while 1:
 r,a,b,c=[(x,y,x+1,y),(x+1,y,x+1,y+1),(x+1,y+1,x,y+1),(x,y+1,x,y)],(x+1,y,x,y),(x,y,x,y\
+1),sys.stdin.read(1)
 if not c:break
 p,q=E.get(a),E.get(b)
 if'#'==c:
  if p:
   i=p.index(a)
   if q:
    j=q.index(b)
    if p==q:
     if i<j:P(p[i+1:j]);p[i:j+1]=r[1:3]
     else:P(p[i+1:]+p[:j]);p[i:]=r[1:3];p[0:j+1]=[]
    else:p[i:i+1]=r[1:3]+q[j+1:]+q[:j]
   else:p[i:i+1]=r[1:]
  elif q:j=q.index(b);q[j:j+1]=r[:3];p=q
  else:p=r
  for e in p:E[e]=p
 x+=1
 if'\n'==c:y+=1;x=0
for L in E.values():
 if L:P(L);L[:]=[]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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