31
\$\begingroup\$

Help, I've been diagnosed with prosopagnosia! This means I'm no longer able to recognise faces.... :(

Can you help me?

The challenge

You will be given an image as a matrix of regular ASCII characters separated by new line characters, and your task is to determine if it contains a face. Faces will look something like the following:

o.o
.7.
___

Of course, people all look different - the only features that virtually everyone has are two eyes, a nose, and a mouth. For this challenge, eyes will be a lower-case o, a nose will be a 7, and the mouth will be a line of underscores _. For this challenge, faces must have all of these features.

To be specific, a face must have two eyes in the same row of the matrix, with a nose centred horizontally between them somewhere between the rows with the eyes and the mouth, and a mouth at the bottom of the face that is a row of underscores that extends all the way from the column of one eye to the other. Since a face must have a horizontally-centred nose, all faces must be an odd number of characters wide. Please note: The nose does not have to be centred vertically so long as it is between the rows of the eyes and mouth (exclusive). No other features of the face matter so long as the face has only two eyes, one nose, and one mouth - the "fill" of the face can be anything but the characters o, 7, or _

The output format is flexible - all you must be able to do is distinguish whether the image from the input has a face. You may use any output values to represent whether an image has a face (e.g. 1 if it does, 0 if it does not)

Examples/Test Cases

...o.....o.
......7....
..._______.

^ contains a face

...o.....o.o.o
......7.....7.
..._______.___

^ contains a face (actually contains two but your program does not need to care about any additional faces)

o.o...o..o
o.7.7._.7.
.._____7__

^ does not contain a face

o.o...o..o
o...7...7.
.._____7__

^ contains a face (notice the two differences between this case and the one above)

o...o
.7...
_____

^ does not contain a face, as the nose is not centred horizontally

..o...o
.......
.......
.......
....7..
.______

^ contains a face formed by the last five columns

,/o[]8o
o198yH3
f_3j`~9
()**&#^
*#&^79%
2______

^ contains a face (the last five columns form a face just like in the previous example, except with different filler characters that make it less human-readable)

o..o.o..o.o...o..o.o.o..o...o.o.o.o.o
......7....o7......7......7......7...
..7...............___......7....___..
____.____.___._.._____.._____._______

^ contains a face (only the 3x3 face in the fifth-last through third-last columns is a face - all the other potential faces break one or more rules)

.....
.o.o.
..7..
.....
.___.

^ contains a face

o7o
...
___

^ does not contain a face

A few extra clarifications

-Faces will never be rotated

-The .'s in the test cases could be any regular ASCII characters other than the three special characters, they are periods just for better readability

-You can assume all matrices will be smaller than 100 x 100

Scoring

This is . Shortest code wins!

\$\endgroup\$
  • 3
    \$\begingroup\$ May we output a list of valid faces as truthy and an empty list as falsey? Or has the truthy/falsey output has to be consistent? \$\endgroup\$ – Kevin Cruijssen Jun 30 at 16:34
  • 2
    \$\begingroup\$ @KevinCruijssen since the output format is flexible, I'm going to allow this. So long as the program can tell the difference between a face and no face, then it's fine \$\endgroup\$ – Daniel H. Jun 30 at 16:36
  • 1
    \$\begingroup\$ @Noodle9 the characters next to the mouth can be anything, including mouth characters. There's an example of this in the sixth test case already \$\endgroup\$ – Daniel H. Jun 30 at 17:29
  • 2
    \$\begingroup\$ @Jonah the fill of the face means the characters inside the square of the face itself. Characters outside the face can be anything, which means yes, there could be special characters outside the face that are not part of any faces \$\endgroup\$ – Daniel H. Jul 1 at 2:48
  • 1
    \$\begingroup\$ I must be taller than you; I think an L makes a better nose than a 7, but that means looking down on the face from slightly above right instead of below left. \$\endgroup\$ – Neil Jul 1 at 10:18
12
\$\begingroup\$

JavaScript (ES6),  147 ... 140  139 bytes

Returns either false or a truthy value.

s=>(p='',g=k=>s.replace(/[^7o_]/g,0).match(`o${p}${p+=0}o${S=`.{${w=s.search`
`-k}}(0${p+p}.{${w}})*`}${p+7+p+S}__{${k}}`)||w>0&&g(k+2))(2)

Try it online!

How?

We start with \$k=2\$ and \$p\$ set to an empty string.

At each iteration, we first replace all characters in the input string \$s\$ other than "o", "7" or "_" with zeros. This includes linefeeds. So the first test case:

...o.....o.
......7....
..._______.

is turned into:

flat representation: "...o.....o.¶......7....¶..._______."
after replace()    : "000o00000o00000000700000000_______0"

We then attempt to match the 3 parts of a face of width \$k+1\$.

Eyes

An "o" followed by \$k-1\$ zeros, followed by another "o":

`o${p}${p+=0}o`

Followed by the padding string \$S\$ defined as:

`.{${w=s.search('\n')-k}}(0${p+p}.{${w}})*`
 \______________________/ \____________/ |
   right / left padding      k+1 zeros   +--> repeated any
                          + same padding      number of times

Nose

\$k/2\$ zeros, followed by a "7", followed by \$k/2\$ zeros, followed by the same padding string \$S\$ as above:

`${p+7+p+S}`

Mouth

\$k+1\$ underscores:

`__{${k}}`

In case of failure, we try again with \$k+2\$. Or we stop as soon as the variable \$w\$ used to build \$S\$ is less than \$1\$, meaning that the padding string would become inconsistent at the next iteration.

For the first test case, we successively get the following patterns:

o0o.{9}(000.{9})*070.{9}(000.{9})*__{2}
o000o.{7}(00000.{7})*00700.{7}(00000.{7})*__{4}
o00000o.{5}(0000000.{5})*0007000.{5}(0000000.{5})*__{6}

The 3rd one is a match.

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

05AB1E, 61 60 57 bytes

3тŸãε`I€Œsδùø€Œsδù€`}€`ʒćÁ„ooÅ?sRćÙ'_Qs€Ås7¢y¨J…_7oS¢2ÝQP

Input as a list of lines. Outputs a list of valid faces as truthy, or an empty list [] as falsey. If this is not allowed, the ʒ can be ε and a trailing has to be added, to output 1 for truthy and 0 for falsey.

Try it online or verify all test cases. (Sometimes times out for the last biggest test case.)

Explanation:

Step 1: Transform the input into \$n\$ by \$m\$ blocks:

3тŸ              # Push a list in the range [3,100]
   ã             # Create all possible pairs by taking the cartesian product
ε                # Map each pair [m,n] to:
 `               #  Pop and push the m,n separated to the stack
  I              #  Push the input-list
   €             #  For each row:
    Π           #   Get all substrings
      δ          #  For each list of substrings:
     s ù         #   Keep those of a length equal to `n` (using a swap beforehand)
        ø        #  Zip/transpose; swapping rows/columns
                 #  (we now have a list of columns, each with a width of size `n`)
         €       #  For each column of width `n`:
          Π     #   Get all sublists
            δ    #  For each list of sublists:
           s ù   #   Keep those of a length equal to `m` (using a swap beforehand)
              €` #  And flatten the list of list of lists of strings one level down
}€`              # After the map: flatten the list of list of strings one level down

Try just this first step online.

Step 2: Keep the \$n\$ by \$m\$ blocks which are valid faces:

ʒ                # Filter the list of blocks by:
 ć               #  Extract the first row; pop and push the remainder-list and first row
                 #  separated to the stack
  Á              #  Rotate the characters in the string once towards the right
   „ooÅ?         #  Check if the string now starts with a leading "oo"
 s               #  Swap to get the remaining list of rows
  R              #  Reverse the list
   ć             #  Extract head again, to get the last row separated to the stack
    Ù            #  Uniquify this string
     '_Q        '#  And check if it's now equal to "_"
 s               #  Swap to get the remaining list of rows
  €              #  For each row:
   Ås            #   Only leave the middle character (or middle 2 for even-sized rows)
     7¢          #  Count the amount of 7s in this list
 y               #  Push the entire block again
  ¨              #  Remove the last row (the mouth)
   J             #  Join everything else together
    …_7oS        #  Push string "_7o" as a list of characters: ["_","7","o"]
         ¢       #  Count each in the joined string
          2Ý     #  Push the list [0,1,2]
            Q    #  Check if the two lists are equal
 P               #  And finally, check if all checks on the stack are truthy
                 # (after which the filtered result is output implicitly)
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

Python 3.8, 264 \$\cdots\$ 223 222 bytes

Saved a whopping 16 bytes thanks to Kevin Cruijssen!!!

Saved a byte thanks to Tanmay!!!

import re
b='[^o7_]'
def f(l):
 while l:
  s,p=l.pop(0),1
  while m:=re.compile(f'o{b}+o').search(s,p-1):
   a,p=m.span();d=p-a;e=d//2
   if re.match(f'({b*d})*{b*e}7{b*e}({b*d})*'+'_'*d,''.join(s[a:p]for s in l)):return 1

Try it online!

Inputs a list of strings.
Outputs \$1\$ for a face, None otherwise.

How

Looks for pairs of eyes in each row, starting from the top, by repeatedly removing the top row from the input list. If a pair is found, the columns forming the pair are taken from the remaining rows and concatenated together. This string is then tested against a regex constructed from the distance separating the eyes to see if we've found a face. If not, we continue scanning the current line, beginning at the stage-left eye, looking for more pairs before moving onto the next row.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can put the re.compile('o[^o7_]+o') directly at the r.search(s,p-1): to save a couple of bytes. In addition, both d//2 can be d/2. And you can remove the return 0 and use None as falsey result instead. Try it online 248 bytes \$\endgroup\$ – Kevin Cruijssen Jul 1 at 6:47
  • \$\begingroup\$ @KevinCruijssen Very nice - thanks! :-) \$\endgroup\$ – Noodle9 Jul 1 at 10:15
  • \$\begingroup\$ There is a 22 byte solution You had a space in line def f ;-). The tio link is too long to paste it in comment, but here's a link for the tio link :-) \$\endgroup\$ – Tanmay 20 hours ago
  • 1
    \$\begingroup\$ @Tanmay Oops, well spotted - thanks! :D \$\endgroup\$ – Noodle9 18 hours ago
  • \$\begingroup\$ @Noodle9 You welcome. I was trying to golf your code(It's the first time a did it ;-)) when I went with the cursor to the space. :D \$\endgroup\$ – Tanmay 18 hours ago
5
\$\begingroup\$

APL (Dyalog Unicode), 85 77 bytes (SBCS)

Anonymous monadic function taking a matrix of characters as argument.

1∊∊{⍵∘{(⍉3,⍨a⍪⍵⍪⊖a←2↑⍨2 1÷⍨⍺-1)⍷4-'_o7'⍳A}¨0,¨↓∘.=⍨⍳¯2+2⌷⍵}¨1 2∘+¨2 1∘ר⍳⍴A←⎕

Try it online!

-8 bytes thanks to @Adám

Interesting Bits

This ends up encoding eyes=2, nose=1, underscore=3.

1 2∘+¨2 1∘ר⍳⍴A←⎕ ⍝ Get at least all sizes (m,n) that fit in A such that
                       ⍝ m is odd and n≥3 (surely this can be done shorter)
                       ⍝ The search arrays are constructed transposed, so m ends 
                       ⍝ up being the width
0,¨↓∘.=⍨⍳¯2+2⌷⍵      ⍝ For a given height m, get all nose positions
                       ⍝ e.g. m=3 gives (0 1 0 0)(0 0 1 0)(0 0 0 1)
(2 1÷⍨⍺-1)↑2         ⍝ My favorite expression. Generates one-half of the face
                       ⍝ ⍺ is (m,n), so (2 1÷⍨⍺-1) gives dimension pair ((⍺-1)÷2) (⍺-1)

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Retina 0.8.2, 129 bytes

T`o7\_p`o7=-
((?<=(.)*)(?(1)\3-7-\3|o((-)+)-\3o).*¶(?<-2>.)*(?(2)$)((?<=(.)*)-\3-\3-.*¶(?<-6>.)*(?(6)$))*){2}(?<-4>==)*(?(4)$)===

Try it online! Outputs 0 if there is no face, otherwise a positive integer number of nonoverlapping faces. Explanation:

T`o7\_p`o7=-

Transliterate everything other than o, 7 and _ to -. _ gets transliterated to = as that avoids having to quote it again. (I used - as I find spaces confusing.) The next stage then defaults to a match count stage.

(

Group 1 is just here so that it can be repeated.

(?<=(.)*)

Count the current indentation into capture group 2.

(?(1)\3-7-\3|o((-)+)-\3o)

If capture group 1 has already been matched, then match -7- surrounded by capture group 3 (the nose), otherwise match o, a string of -s into capture group 3 and its count into capture group 4, another -, a copy of capture group 3, and a final o (the eyes).

.*¶(?<-2>.)*(?(2)$)

Match until the same amount of indentation on the next line.

((?<=(.)*)-\3-\3-.*¶(?<-6>.)*(?(6)$))*

Optionally match any number of lines containing three -s and two copies of capture group 3 (empty line), keeping track of and advancing to the same amount of indentation on the next line using capture group 6.

){2}

Match this whole group twice.

(?<-4>==)*(?(4)$)===

Match two =s for each - captured in capture group 4, plus a final three =s (mouth).

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Python 3, 213 bytes

Returns False when it finds a face and True when it doesn't.

lambda s:all(re.subn(f"\\n.{{{p}}}[^o_7]{{{g}}}7[^o_7]{{{g}}}",'',x)[1]-1for p in range(len(s))for g in range(len(s))for x in re.findall(f"^.{{{p}}}o[^o_7]{{{2*g-1}}}o([\S\s]+)^.{{{p}}}__{{{2*g}}}",s,8))
import re

The idea is that for each possible face size and indention, we look for eyes and a mouth in correct location (ignoring noses), then make sure there is exactly one nose that is centered.

p is the left padding of the face, g is the gap from face edge to nose, and 8 is the value of re.MULTILINE.

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Unicode), 90 85 bytes (SBCS)

Anonymous tacit prefix function taking a character matrix argument. Requires ⎕IO←0 (0-based indexing).

1∊∘∊{(∊¨1↑¨¨⍨1+⍳1,⍨⊣\⍴⍵)∘.⍀{'_'⍪⍨(⊢,0 1↓⌽)' 7',⍨2↑'o',1⍵⍴''}¨⍳⊢/⍴⍵}⍷¨∘⊂' '@(~∊∘'o7_')

Try it online!

This works by brute force; generating all possible faces and looking for them in turn.

' '@() amend with spaces at the locations indicated by the following mask:

∊∘'o7_' membership of the set of special symbols

~ negate that

This replaces all non-special characters with spaces.

{}⍷¨∘⊂ mask where each of the following have a top-left corner in the entirety of that:

⍴⍵ the shape of the argument (rows, columns)

⊢/ the rightmost element of that (columns)

 the indices 0…n-1 of that.

{ apply the following function on each index:

  1⍵⍴'' create 1-row argument-column matrix of spaces

  'o', prepend a column of eyes

  2↑ append a blank row (lit. take the first two rows)

  ' 7',⍨ append a column consisting of a space above a nose

  () apply the following tacit function to that:

    mirror the argument (puts the nose column on the left)

   0 1↓ drop no rows but one column (removes the nose column)

   ⊢, prepend the argument (this creates the full eye and nose rows)

  '_'⍪⍨ append a row of underscores (to form the mouth)

This gives us a collection of all possible three-row faces.

()∘.⍀ create all combinations of the following masks expanding (inserting blank rows on zeros) those faces:

  ⍴⍵ the shape of the argument

  ⊣\ two copies of the row-count (lit. cumulative left-argument reduction)

  1,⍨ append a one

   the Cartesian coordinates of an array of that size

  1+ increment

  1↑¨¨⍨ for each of each of those, create a mask of length with a single leading one (lit. take that many elements from one)

  ∊¨ϵnlist (flatten) each

 This gives us all the possible expansion masks

ϵnlist (flatten)

1∊∘ is one a member thereof?

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

J, 101 93 99 97 bytes

1 e.[:,>@{@;&(1+i.)/@$(((-:1 2 3*[:#:i:@_1+2^<:,<.@-:,])*2|]){:@$)@((4|'ao7_'&i.)-.0{0:"+);._3"$]

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Java (OpenJDK 8), 290 bytes

int D(String[]t){for(int a=0,z=t.length,y=t[0].length();a<z;a++)for(int b=0;b<y;b++)for(int c=b+2;c<y;c+=2)for(int d=a+1;d<z;d++)for(int e=d+1;e<z;e++)if(t[a].charAt(b)=='o'&&t[a].charAt(c)=='o'&&t[d].charAt((b+c)/2)=='7'&&t[e].substring(b,c+1).replace("_","").isEmpty())return 1;return 0;}

Try it online!

Takes a String[] broken at the lines as input and outputs 1 and 0 for true and false

| improve this answer | |
\$\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.