Is there a face in this image?
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.
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)
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.