43
\$\begingroup\$

The aim of this task is to identify, clean up, and mark out all the faces in any given 'image'.

What's in a face?

A face will be a ZxZ square where Z is an odd integer greater than 1. The top left and right corners and the centre will be 'O' characters, and the bottom line will be a '\' and a '/' surrounding enough '_' characters to fill the rest of the line. Examples:

a 3x3 face:

O O
 O
\_/

a 5x5 face:

O   O

  O

\___/

a 7x7 face:

O     O


   O


\_____/

etc.

Input

Input will be on STDIN and will consist of a number of equal length strings of characters.

Output

Output should be the input with all recognizable faces cleared (i.e. all characters except the eyes, nose and mouth shoud be removed from within the face's bounds) and boxed (surrounded by +, -, and | characters). Where two or more faces overlap both should be cleared and boxed but priority should be given to the larger face (it should be placed on top); if both faces are the same size, the priority is left to the discretion of the implementer. If the input has no faces, output should be the same as input.

Some examples

Input:

*******
*******
**O*O**
***O***
**\_/**
*******
*******

Output:

*******
*+---+*
*|O O|*
*| O |*
*|\_/|*
*+---+*
*******

Input (incomplete face):

*******
*******
**O*O**
*******
**\_/**
*******
*******

Output:

*******
*******
**O*O**
*******
**\_/**
*******
*******

Input (nested faces):

*******
*O***O*
**O*O**
***O***
**\_/**
*\___/*
*******

Output:

+-----+
|O   O|
|     |
|  O  |
|     |
|\___/|
+-----+

Input (multiple faces):

~{$FJ*TBNFU*YBVEXGY%
FOCO$&N|>ZX}X_PZ<>}+
X$OOPN ^%£)LBU{JJKY%
@\_/$£!SXJ*)KM>>?VKH
SDY%£ILO(+{O:HO(UR$W
XVBFTER^&INLNLO*(&P:
>?LKPO)UJO$£^&L:}~{&
~@?}{)JKOINLM@~}P>OU
:@<L::@\___/GER%^*BI
@{PO{_):<>KNUYT*&G&^

Output:

+---+*TBNFU*YBVEXGY%
|O O|&N|>ZX}X_PZ<>}+
| O |N ^%£)LBU{JJKY%
|\_/|£+-----+M>>?VKH
+---+I|O   O|HO(UR$W
XVBFTE|     |LO*(&P:
>?LKPO|  O  |&L:}~{&
~@?}{)|     |@~}P>OU
:@<L::|\___/|ER%^*BI
@{PO{_+-----+YT*&G&^

Input (near boundary):

~{$FJ*TBNFU*YBVEXGY%
OCO$&N|>ZX}X_PZ<>}+^
$OOPN ^%£)LBU{JJKY%{
\_/$£!SXJ*)KM>>?VKHU
SDY%£ILO(+{8:HO(UR$W
XVBFTER^&INLNLO*(&P:
>?LKPO)UJ^$£^&L:}~{&
~@?}{)JKOINLM@~}P>OU
:@<L::@BJYT*GER%^*BI
@{PO{_):<>KNUYT*&G&^

Output:

---+J*TBNFU*YBVEXGY%
O O|&N|>ZX}X_PZ<>}+^
 O |N ^%£)LBU{JJKY%{
\_/|£!SXJ*)KM>>?VKHU
---+£ILO(+{8:HO(UR$W
XVBFTER^&INLNLO*(&P:
>?LKPO)UJ^$£^&L:}~{&
~@?}{)JKOINLM@~}P>OU
:@<L::@BJYT*GER%^*BI
@{PO{_):<>KNUYT*&G&^

Input (overlapping faces):

~{$FJ*TBNFU*YBVEXGY%
FXC£$&N|>ZX}X_PZ<>}+
X$*OPN O%£)LBO{JJKY%
@:U%$£!SXJ*)KM>>?VKH
SDY%£OLO(+{P:HO(UR$W
XVBFTER^&IOLNLO*(&P:
>?L\___/JR$£^&L:}~{&
~@?}{)JKOINLM@~}P>OU
:@<L::@\_____/R%^*BI
@{PO{_):<>KNUYT*&G&^

Output:

~{$FJ*TBNFU*YBVEXGY%
FX+---+-------+Z<>}+
X$|O  |O     O|JJKY%
@:|   |       |>?VKH
SD|  O|       |(UR$W
XV|   |   O   |*(&P:
>?|\__|       |:}~{&
~@+---|       |}P>OU
:@<L::|\_____/|%^*BI
@{PO{_+-------+*&G&^
\$\endgroup\$
  • \$\begingroup\$ What about conjoined faces (e.g. where an O doubles as a left eye and right eye)? Should those be treated as overlapping? \$\endgroup\$ – Joey Adams Jul 8 '11 at 21:01
  • \$\begingroup\$ @Joey Adams: that happens in the last example. \$\endgroup\$ – Lowjacker Jul 8 '11 at 21:44
  • \$\begingroup\$ @Joey Adams @Lowjacker Yes, just like the last example. \$\endgroup\$ – Gareth Jul 8 '11 at 22:28
  • \$\begingroup\$ I find the 3x3 face realistic and the 7x7 face derp. Just my opinion. Sad that I haven't got time to gain bountiez... :) \$\endgroup\$ – tomsmeding Mar 23 '14 at 21:36
  • 2
    \$\begingroup\$ @tomsmeding If you find the 3x3 face realistic I'd hate to see the people you associate with. :-\ \$\endgroup\$ – Gareth Mar 23 '14 at 21:45
19
\$\begingroup\$

Ruby, 304 298 295 characters

I=$<.read
q=(O=I*s=1).size
k=??+O=~/$/
o=->m,n{n.chars{|c|(m+=1)*(m%k)>0&&m<q&&O[m-1]=c}}
q.times{f=[[?\\+?_*s+?/,k*s+=1],[?O,0],[?O,s],[?O,(s+=1)/2*(1+k)]]
q.times{|x|f.all?{|a,b|I[x+b,a.size]==a}&&(o[x+k*s-1,o[x-k-1,?++?-*s+?+]]
s.times{|a|o[x+k*a-1,?|+' '*s+?|]}
f.map{|a,b|o[x+b,a]})}}
$><<O

Lower right is preferred on overlap if faces are of identical size. E.g. for the input

O.OO.O
.O..O.
\_/\_/
O.OO.O
.O..O.
\_/\_/

it recognizes all four faces and yields

O |O O
 O| O
--+---
O |O O
 O| O
\_|\_/

Edit 1: As Lowjacker proposed we can replace the index with a regex match (-3 chars). Moreover the +1 can be compensated by an additional dummy char before the matching which saves another char (-2 for the +1, +3 for dummy char, -2 because brackets are no more necessary). Two more since we can write the range also without brackets.

Edit 2: Another two characters saved by replacing both if with && and another one removing the range completely.

\$\endgroup\$
  • \$\begingroup\$ You can use (O=~/$/) instead of O.index($/) on the third line (saves 3 characters). \$\endgroup\$ – Lowjacker Jul 10 '11 at 15:31
  • \$\begingroup\$ @Lowjacker Thank you. I could even save one more with your trick (see my edit). \$\endgroup\$ – Howard Jul 10 '11 at 16:01
  • \$\begingroup\$ I think you can also save 2 characters by replacing the if statements with &&. \$\endgroup\$ – Lowjacker Jul 10 '11 at 16:48
3
+450
\$\begingroup\$

Python - 1199 941

I found the problem pretty interesting, so I solved in Python. Here's the compressed code.

#!/usr/bin/env python
import fileinput,sys
m=[[c for c in l if c!='\n'] for l in fileinput.input()]
X=len(m[0])
Y=len(m)
t=[]
for n in range(3,min(X,Y)+1,2):
  for x in range(X-n+1):
    for y in range(Y-n+1):
      if m[y][x]=='O' and m[y][x+n-1]=='O' and m[y+(n//2)][x+(n//2)]=='O' and m[y+n-1][x]=='\\' and m[y+n-1][x+n-1]=='/' and "".join(m[y+n-1][x+1:x+n-1])=='_'*(n-2):
        t.append((x,y,n))
for x,y,n in t:
  def a(v,h,c):
    w=x+h; z=y+v;
    if z>=0 and z<len(m):
      if w>=0 and w<len(m[y]):
        m[z][w]=c
  for v in range(n):
    for h in range(n): 
      a(v,h,' ')
  a(0,0,'O')
  a(0,n-1,'O')
  a(n/2,n/2,'O')
  a(n-1,0,'\\')
  a(n-1,n-1,'/')
  for w in range(1,n-1):
    a(n-1,w,'_')
  for v in [-1,n]:
    for h in range(n):
      a(v,h,'-')
  for h in [-1,n]:
    for v in range(n):
      a(v,h,'|')
  a(-1,-1,'+')
  a(-1,n,'+')
  a(n,-1,'+')
  a(n,n,'+')
for l in m:
  for c in l:
    sys.stdout.write(c)
  print

Here's the more readable code :

#!/usr/bin/env python

import fileinput, sys

matrix = [[c for c in l if c != '\n'] for l in fileinput.input()]

max_X = len(matrix[0])
max_Y = len(matrix)

tuples = []
for n in range(3, min(max_X, max_Y)+1, 2):
  for x in range(max_X-n+1):
    for y in range(max_Y-n+1):
      # if is_face(matrix, x, y, n):
      if matrix[y][x] == 'O' and matrix[y][x+n-1] == 'O' and matrix[y+(n//2)][x+(n//2)] == 'O' and matrix[y+n-1][x] == '\\' and matrix[y+n-1][x+n-1] == '/' and "".join(matrix[y+n-1][x+1:x+n-1]) == '_'*(n-2) :
        tuples.append((x, y, n))

for x,y,n in tuples:
  # blank_and_border(matrix,x,y,n)
  def assign(dy, dx, c):
    xx = x + dx; yy = y + dy;
    if yy >= 0 and yy < len(matrix) :
      if xx >= 0 and xx < len(matrix[y]) :
        matrix[yy][xx] = c

  # blank
  for dy in range(n):
    for dx in range(n): 
      assign(dy, dx, ' ')

  # face
  assign(0, 0, 'O')
  assign(0, n-1, 'O')
  assign(n/2, n/2, 'O')
  assign(n-1, 0, '\\')
  assign(n-1, n-1, '/')
  for w in range(1,n-1):
    assign(n-1, w, '_')

  # border
  for dy in [-1,n]:
    for dx in range(n):
      assign(dy, dx, '-')

  for dx in [-1,n]:
    for dy in range(n):
      assign(dy, dx, '|')

  assign(-1, -1, '+')
  assign(-1,  n, '+')
  assign( n, -1, '+')
  assign( n,  n, '+')

for l in matrix:
  for c in l:
    sys.stdout.write(c)
  print
\$\endgroup\$
  • 2
    \$\begingroup\$ Please do add your golfed version above this version in your answer. This is a code-golf question and you risk getting down votes if you haven't at least tried to golf it. You can leave your readable version here too. \$\endgroup\$ – Gareth Mar 28 '14 at 23:24
  • 1
    \$\begingroup\$ Right on, @Gareth. I often write solutions in Java, which is not terribly golf-friendly, but I always take the time to golf my solution, both for the exercise (it's fun thinking of ways to trim characters and reduce overall length) and to satisfy the spirit of code-golf (which is getting your solution as concise as possible). So, looking forward to seeing your golfed solution, sgauria! \$\endgroup\$ – ProgrammerDan Mar 29 '14 at 3:05
  • \$\begingroup\$ Thanks Gareth & @ProgrammerDan ! That's good advice - I am pretty new on codegolf. I have added my golfed solution above in addition to the longer solution. \$\endgroup\$ – sgauria Mar 29 '14 at 20:10

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.