35
\$\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\$
12
  • 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\$ Commented Jun 30, 2020 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.
    Commented Jun 30, 2020 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.
    Commented Jun 30, 2020 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.
    Commented Jul 1, 2020 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
    Commented Jul 1, 2020 at 10:18

11 Answers 11

13
\$\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.

\$\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)
\$\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.

\$\endgroup\$
9
  • \$\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\$ Commented Jul 1, 2020 at 6:47
  • \$\begingroup\$ @KevinCruijssen Very nice - thanks! :-) \$\endgroup\$
    – Noodle9
    Commented Jul 1, 2020 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\$
    – math scat
    Commented Jul 11, 2020 at 13:21
  • 1
    \$\begingroup\$ @Tanmay Oops, well spotted - thanks! :D \$\endgroup\$
    – Noodle9
    Commented Jul 11, 2020 at 15:29
  • 1
    \$\begingroup\$ @Alfe l is short for list and only FORTRAN programmers use capital letters! :P \$\endgroup\$
    – Noodle9
    Commented Mar 26, 2021 at 19:52
6
\$\begingroup\$

Regex (PCRE2), 203 193 177 181 bytes

/((?|^()|^(?:.(?=.*
(\2.)))+){2}(?(8)(?=\8$)(?|()|(?:(?6)(?=.+((?6)\3)\7$))++){2}((?6)|(?!\5)7())\3(?=\7$)|o([^o7_])+o)(?|()|\7(?:.(?=.*
.*(.\7)))+){2}
(?=\2(.*)))+\5.*(?=\8)_+\7$/m

Try it on regex101

Explanation

((?|^()|^(?:.(?=.*\n(\2.)))+){2}(?(8)(?=\8$)(?|()|(?:(?6)(?=.+((?6)\3)\7$))++){2}((?6)|(?!\5)7())\3(?=\7$)|o([^o7_])+o)(?|()|\7(?:.(?=.*\n.*(.\7)))+){2}\n(?=\2(.*)))+

Main loop. Matches everything except for the mouth:

(?|^()|^(?:.(?=.*\n(\2.)))+){2} - on each line, match the padding to the left of the face, while counting a matching number of characters of padding into \2 from the start of the next line. This needs to use a Branch Reset Group (?|...) in order to initialize \2 to empty with ^() before building it up one character at a time with (\2.). The {2} guarantees that both stages will execute exactly once, and do so in the correct order due to each one having a ^ anchor (which matches the start of any line due to the /m flag). Replacing the {2} with + wouldn't work because a loop will immediately terminate after any optional iteration that matches zero characters. Note that in the case of zero padding, the first stage will execute twice in a row.

(?(8)...|...eyes...) - Only allow matching the eyes if we haven't already captured \8, i.e. iterated through the main loop at least once.

(?!\7)o([^o7_])+o - match the eyes, and define the subroutine (?6) to do [^o7_].

(?=\8$)(?|()|(?:(?6)(?=.+((?6)\3)\7$))++){2}((?6)|(?!\5)7())\3(?=\7$) - Match the facial part of a row either containing no facial features, or containing the nose.
(?=\8$) - assert that we're starting at the proper column, which was marked when the previous row was processed
(?|()|(?:(?6)(?=.+((?6)\3)\7$))++){2} - build up the facial part of the row one character at a time on the left and right ends. The right part is built up in \3. Both ends a built towards the center. The ++ ensures this is done the maximum number of times; with an even length both ends would meet, and with an odd length one character is left between them.
This uses a Branch Reset Group and {2} the same way as before, except that we guarantee both stages execute in the correct order differently. The ++ guarantees the second stage won't execute twice. The fact that an empty match would result in (?=\7$) failing to match guarantees that the first stage executes first. The fact that executing the two stages in the wrong order would result in too-long row (with the previous value of \3 tacked in) guarantees the stages execute in the correct order.
((?6)|(?!\5)7()) - match either the absence of a nose or a nose. (?6) matches the absence of a nose, and (?!\5)7() matches a nose; () here sets \5 to mark the fact that we've matched a nose, and (?!\5) prevents matching a nose if we've already done so.
\3 - match the right half of the facial part of the row, which we built up.
(?=\7$) - assert that we're now at the first column directly to the right of the face.

(?|()|\7(?:.(?=.*\n.*(.\7)))+){2} - match the padding to the right of the facial part of this line, while counting a matching number of characters of padding into \7 from the corresponding part of the next line. Uses the same Branch Reset Group {2} trick as before, except that we guarantee both stages execute in the correct order in yet another different way. Sticking a \7 in front of the second stage forces it to match too many characters if it tries to execute the second stage first, because the previous value of \7 will be concatenated to the desired number of characters, which would only match in invalid input that has a line longer than the previous line. And the subsequent \n (seen below) prevents the first stage from executing twice on any valid input, because that would only match on a line shorter than the previous line. Note that in the case of zero padding, the first stage will execute twice in a row.

\n(?=\2(.*)) - match the end of the current line, and capture a marker for the desired starting column of the facial part of the next row in \8.

Upon finishing the main loop, we reach \5.*(?=\8)_+\7$:

\5 - assert that we matched a nose.
.*(?=\8) - skip to the correct starting column, as marked when the previous line was processed.
_+ - match the mouth.
\7$ - assert that the mouth ended at the proper column.

Regex (PCRE2), 363 322 283 199 182 184 186 bytes

This version goes above and beyond the problem statement, allowing the input to have variable-length lines.

/((?|^()|^(?:.(?=.*
(\2.)))+){2}(?=(?(8)(?=\8\9)(?|()|(?:(?6)(?=.+((?6)\3)\9))++){2}((?6)|(?!\5)7())\3(?=\9)|o([^o7_
])+o)(.*))(?|()|\8(?:.(?=.*
\2(\8.)(\C*)))+){2}\7
)+\5.*(?=\8)_+\9$/m

Try it on regex101

Explanation

((?|^()|^(?:.(?=.*\n(\2.)))+){2}(?=(?(8)(?=\8\9)(?|()|(?:(?6)(?=.+((?6)\3)\9))++){2}((?6)|(?!\5)7())\3(?=\9)|o([^o7_\n])+o)(.*))(?|()|\8(?:.(?=.*\n\2(\8.)(\C*)))+){2}\7\n)+

Main loop. Matches everything except for the mouth:

(?|^()|^(?:.(?=.*\n(\2.)))+){2} - on each line, match the padding to the left of the face, while counting a matching number of characters of padding into \2 from the start of the next line. This needs to use a Branch Reset Group (?|...) in order to initialize \2 to empty with ^() before building it up one character at a time with (\2.). The {2} guarantees that both stages will execute exactly once, and do so in the correct order due to each one having a ^ anchor (which matches the start of any line due to the /m flag). Replacing the {2} with + wouldn't work because a loop will immediately terminate after any optional iteration that matches zero characters. Note that in the case of zero padding, the first stage will execute twice in a row.

(?(8)...|...eyes...) - Only allow matching the eyes if we haven't already captured \8, i.e. iterated through the main loop at least once.

o([^o7_\n])+o - match the eyes, and define the subroutine (?6) to do [^o7_\n]. We need to explicitly exclude \n because otherwise the first row of the facing (containing the eyes) could be matched with newline(s) included between the eyes, which if orchestrated just right, could result in fooling the rest of the algorithm into matching a face. An alternative way of preventing this would be to capture \7 using (\C*) instead of (.*) (which a previous version did), i.e. capturing everything to the end of the string (including newlines) instead of just to the end of the current line, but this results in worse golf, because we would also need to do (?=\7).*\n instead of \7\n, costing 6 bytes total.

(?=\8\9)(?|()|(?:(?6)(?=.+((?6)\3)\9))++){2}((?6)|(?!\5)7())\3(?=\9) - Match the facial part of a row either containing no facial features, or containing the nose. (Do this in a lookahead so that we can iterate a second time over the same characters, in order to count them.)
(?=\8\9) - assert that we're starting at the proper column, which was marked when the previous row was processed
(?|()|(?:(?6)(?=.+((?6)\3)\9))++){2} - build up the facial part of the row one character at a time on the left and right ends. The right part is built up in \3. Both ends a built towards the center. The ++ ensures this is done the maximum number of times; with an even length both ends would meet, and with an odd length one character is left between them.
This uses a Branch Reset Group and {2} the same way as before, except that we guarantee both stages execute in the correct order differently. The ++ guarantees the second stage won't execute twice. The fact that an empty match would result in (?=\9) failing to match guarantees that the first stage executes first. The fact that executing the two stages in the wrong order would result in too-long row (with the previous value of \3 tacked in) guarantees the stages execute in the correct order.
((?6)|(?!\5)7()) - match either the absence of a nose or a nose. (?6) matches the absence of a nose, and (?!\5)7()) matches a nose; () here sets \5 to mark the fact that we've matched a nose, and (?!\5) prevents matching a nose if we've already done so.
\3 - match the right half of the facial part of the row, which we built up.
(?=\9) - assert that we're now at the first column directly to the right of the face.

(.*) - capture a marker \7 for the column directly to the right of the facial part of the current line

(?|()|\8(?:.(?=.*\n\2(\8.)(\C*)))+){2} - match the facial part of the current line again, this time to count the characters in it, so as to build up a capture in \8 of a matching number of characters from the facial part of the next line, as a marker for column alignment, and capture in \9 a marker for the column directly to the right of the facial part of that line. Uses the same Branch Reset Group {2} trick as before, and a very similar way of guaranteeing that both stages execute in the correct order. Sticking a \8 in front of the second stage forces it to match too many characters if it tries to execute the second stage first, because the previous value of \8, not having been emptied by running the first stage, will be concatenated to the desired number of characters; this prevents \7\n from matching later. And a match can't result from executing the first stage twice – doing so would match an empty row, but the lookahead that matched the facial row the first time already guaranteed that it's of nonzero length.

\7\n - match the non-facial ending of the current line, ensuring that we ended on the correct column.

Upon finishing the main loop, we reach \5.*(?=\8)_+\9$:

\5 - assert that we matched a nose.
.*(?=\8) - skip to the correct starting column, as marked when the previous line was processed.
_+ - match the mouth.
\9$ - assert that the mouth ended at the proper column.

+2 bytes (184 → 186) to fix a bug found by jaytea

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Belated welcome back! Anyway, thanks for using branch reset groups - I had never heard of them before, given that .NET allows you to name multiple capture groups with the same name (or even number) without any difficulty whatsoever. \$\endgroup\$
    – Neil
    Commented Mar 4, 2021 at 11:55
  • \$\begingroup\$ @Neil Thanks! And that's pretty cool; I didn't know .NET could do that. In PCRE, group names can't begin with a digit, and while the /J flag allows reusing group names, this can only override a value that has already been captured if the duplicate name occurs further left (or at the same point) in the pattern than when it was leftmost previously captured, making it of very limited use. For example, /^(?:(?<a>b)?(?<a>a)\k'a'){2}\k'a'$/J matches aaaaa, aababb, bababb, or babbabb, not aabaaa, baaaaa, or baabaaa. \$\endgroup\$
    – Deadcode
    Commented Mar 4, 2021 at 19:07
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)

\$\endgroup\$
1
5
\$\begingroup\$

Retina 0.8.2, 129 120 bytes

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

Try it online! Outputs 0 if there is no face, otherwise a positive integer number of nonoverlapping faces. Edit: Bug fix for minimal-width faces and saved 9 bytes thanks to @Deadcode. 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>.)*)

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

((?<=(.)*)-\3-\3-.*¶(?>(?<-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>==)*)===

Match two =s for each - captured in capture group 4, plus a final three =s (mouth). Here as in the previous two cases of balancing groups, the atomic group requires that any available =s are matched against the balancing group, so that the whole regex fails if there aren't three =s left over.

\$\endgroup\$
2
  • \$\begingroup\$ Fails to match a minimum-width face – fixed by changing o((-)+)-\3o to o((-)*)-\3o. Also, -9 bytes by changing (?<-n>.)*(?(n)$) to (?>(?<-n>.)*). \$\endgroup\$
    – Deadcode
    Commented Mar 4, 2021 at 9:28
  • \$\begingroup\$ @Deadcode Ah yes, this is safe because the balancing group will always consume the characters that would have been subsequently matched. Thanks! \$\endgroup\$
    – Neil
    Commented Mar 4, 2021 at 11:53
4
\$\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?

\$\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!

\$\endgroup\$
3
\$\begingroup\$

PCRE2, 168 bytes

(?=(?13)(.*))o(?6)*(?=(?13)(.*))o((?=(.*?)(.\5|(?13)\2$)|)([^7o_]|(?!\7|(?5))\4()7)(((?=(?13)(.+\1|(?!.*\2)))\C)+(_+()((.(?=(.*+\C+?)(.\16?$)))*+\15?+)(?10))?)?)++\7\12

https://regex101.com/r/dHsdBq/2

@Deadcode made me do it :P

It's theoretically valid but fails that one test because of catastrophic backtracking.

Bonus: https://regex101.com/r/dHsdBq/3 166 bytes, PCRE1 (dropped both possessive +s in (?13))

The general method: (?13) will jump from the current point to the same position on the very last line of the subject. So, at any point in the face, you can compare what is captured in (?=(?13)(.*)) to that captured at any other point in the face, particularly following the eyes (\1 and \2, in order to determine whether or not you're in the face.

(?=(?13)(.+\1|(?!.*\2)) is therefore true when you're not in a face. The regex goes through face characters one at a time, but consumes at once characters from the end of the face on one line to the start of the face on the next. While doing so, it also optionally tests for a mouth.

(?=(.*?)(.\5|(?13)\2$)|) is used to locate the nose in the middle of the face. It collects in \5 characters from the end of the face on the current line, so that (.*?) finally matches the empty string once the middle of the face is reached.

\$\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!

\$\endgroup\$
2
\$\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

\$\endgroup\$
3
  • \$\begingroup\$ 266 bytes \$\endgroup\$
    – ceilingcat
    Commented Jul 7, 2020 at 3:50
  • \$\begingroup\$ May I know how did you come up with the idea? \$\endgroup\$ Commented Mar 8, 2021 at 3:10
  • \$\begingroup\$ @Ticherhas Sure. It uses a literal interpretation of the rules by brute-forcing every single possible place a face could be and returning true upon finding one, here's an explanation I whipped up for each step Then, replace booleans with ints because it's shorter. \$\endgroup\$
    – branboyer
    Commented Mar 8, 2021 at 6:00

Your Answer

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

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