Blur's song Girls & Boys featured the lines

girls who are boys who like boys to be girls
who do boys like they're girls, who do girls like they're boys

in the chorus. These lines have a pretty uniform structure: you have a subject, which is either girls or boys, a relative clause, either who are, who like, or who do, an object, again either girls or boys, and an optional modifier, which is similar to the relative clause, except it can also be like they're or to be. In EBNF this might be written as:

subject ::= "boys" | "girls"
relative_clause ::= "who are" | "who like" | "who do"
modifier ::= relative_clause | "like theyre" | "to be"
tail ::= relative_clause subject (modifier sentence)?
sentence ::= subject tail

The challenge

Your task is to, given a string, see if it is valid in this format. you can assume the string will be all lowercase, and will contain only letters and spaces (this means that theyre will have no apostrophe). It should output a boolean value or 0/1. input and output can be done with any of the standard I/O methods. the input string may be empty. all words will be separated by a single space, but they will not all be valid words. for example, the input will never be girls who likeboys but it might be girls who like bananas

Example I/O

girls who are boys who like boys to be girls who do boys like theyre girls who do girls like theyre boys -> true

boys who like boys -> true

girls to be boys -> false
`to be` is only valid in the modifier position, not as the leading relative clause.

girls who like boys to be girls to be boys -> false
The second `to be` is used in the relative clause position here, since after the first `to be` a new sentence begins, and sentences can't use modifiers in the relative clause position.

boys -> false

boys who are -> false

who are boys -> false

boys boys -> false

<empty input> -> false


This is , so the shortest answer in characters wins.

  • 5
    \$\begingroup\$ Are you sure you want to score in characters? Our site standard is to use bytes for a good reason. \$\endgroup\$
    – pxeger
    Dec 14, 2021 at 22:02
  • 1
    \$\begingroup\$ By the way, we strongly recommend to post your challenges in the sandbox to get feedback like this before posting them on the main site \$\endgroup\$
    – pxeger
    Dec 14, 2021 at 22:05
  • 1
    \$\begingroup\$ Must matching be case-sensitive? Can we assume input is always lowercase? \$\endgroup\$
    – pxeger
    Dec 14, 2021 at 22:11
  • \$\begingroup\$ @pxeger yes, you can assume input is always lowercase \$\endgroup\$
    – sugarfi
    Dec 14, 2021 at 23:47
  • 2
    \$\begingroup\$ Should tail ::= relative_clause (subject modifier)? sentence instead? \$\endgroup\$
    – Neil
    Dec 14, 2021 at 23:52

3 Answers 3


Retina 0.8.2, 99 bytes

^(boy|girl)s( who (are|like|do) (boy|girl)s( (who (are|like|do)|like theyre|to be) (boy|girl)s)?)+$

Try it online! Link includes test cases. Simply the grammar turned into a regex and optimised slightly.


Perl 5 (-p), 82, 80 bytes

From @Neil's Retina answer, but using recursive regex.

-2 thanks to @DomHastings.

$_=/^(boys|girls)( (who (are|like|do)) (?1)( ((?3)|like theyre|to be) (?1))?)+$/

Try it online!

  • \$\begingroup\$ Nice work! You can save another couple of bytes too, grouping the who (...) as (?3): Try it online! \$\endgroup\$ Dec 15, 2021 at 9:11

PEG.js, 92 bytes

S=s r" "s(m" "S)?
r=" who "("are"/"like"/"do")
m=r/" like theyare"/" to be"



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.