1
\$\begingroup\$

Awhile back I encountered a simple programming puzzle to determine whether a string was a pangram, or a perfect pangram. (Although it's worth noting that this particular challenge gave a different meaning than the standard definition of a "perfect pangram," to mean any sentence where every letter appears n times for some positive n). And it was a fun challenge. But recently it got me wondering whether it would be possible to solve this challenge purely with regular expressions. If it is, I expect it will be a pretty gnarly regex. But I'm not even sure it is possible.

Still, if anyone is able to do it, it would be the folks here at Code Golf. So here's the challenge:

Write a regular expression which can determine whether or not a given string is a pangram. You can assume that all non-alpha characters have already been stripped out (or don't, if you really want to challenge yourself), and that everything has been transformed into lowercase.

Bonus challenge: write another regular expression to determine whether the given string is a "perfect pangram" by the definition given above.

Examples of an ordinary pangram:

thequickbrownfoxjumpsoverthelazydog

Example of perfect pangrams:

abcdefghijklmnopqrstuvwxyz

jocknymphswaqfdrugvexblitz

squdgykilpjobzarfnthcwmvexhmfjordwaltzcinqbuskpyxveg

I'm not really sure if this is even possible just with regex alone. If you find that it is, kudos!

\$\endgroup\$

closed as off-topic by Luis Mendo, Sriotchilism O'Zaic, Jo King, Giuseppe, Luis felipe De jesus Munoz Sep 26 '18 at 3:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Sriotchilism O'Zaic, Jo King, Giuseppe
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ Pity that Martin is on leave \$\endgroup\$ – Luis Mendo Sep 25 '18 at 21:53
  • 1
    \$\begingroup\$ Pangram, not anagram \$\endgroup\$ – soapergem Sep 25 '18 at 22:02
  • \$\begingroup\$ Quoted verbatim from the question above (read the question): "any sentence where every letter appears n times for some positive n." \$\endgroup\$ – soapergem Sep 25 '18 at 22:05
  • 8
    \$\begingroup\$ Let me rephrase, as my previous comment was a mess: 1) This needs a winning criterion. Code golf? 2) Bonuses are almost always a bad idea. There should be a single task/objective to the challenge. Having two is confusing, and probably useless, as people will go fot the easier one. 3) What flavours of regexes are allowed? \$\endgroup\$ – Luis Mendo Sep 25 '18 at 22:20
  • 2
    \$\begingroup\$ Not sure what regexes are able to do, but the grammar is certainly not regular which can easily be proven with the Pumping Lemma (just set \$w = a^p b^p \cdots z^p\$) - so it's likely a regex won't not do the job (it's regular-expression after all). \$\endgroup\$ – ბიმო Sep 26 '18 at 16:09
4
\$\begingroup\$

Assuming you're using a flavor of regex that include look-aheads, detecting a pangram is straightforward, but tedious. Using Python syntax:

r"(?=.*a)(?=.*b)(?=.*c)(?=.*d)(?=.*e)(?=.*f)(?=.*g)(?=.*h)(?=.*i)(?=.*j)(?=.*k)(?=.*l)(?=.*m)(?=.*n)(?=.*o)(?=.*p)(?=.*q)(?=.*r)(?=.*s)(?=.*t)(?=.*u)(?=.*v)(?=.*w)(?=.*x)(?=.*y)(?=.*z).*"

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

The (?=.*a) block tests if what follows after that point matches .*a; another way to say that is, is this expression followed by any characters and then an a, or just, does this include an a? Then repeat that check for every letter of the alphabet.

Without lookaheads, it's still possible, but even more tedious, because you have to account for every possible ordering of the alphabet. If you were limited to the letters abc, here's what it might look like:

r".*(a.*b.*c|a.*c.*b|b.*a.*c|b.*c.*a|c.*a.*b|c.*b.*a).*"

https://regex101.com/r/OnXQe7/1/

This checks for an a, any set of characters, a b, any set of characters, then a c, OR an a, any set of characters, a c, any set of characters, then a b, OR...you get the idea.

You could use the same approach to check for the standard meaning of perfect pangram (every character exactly once), but not the modified version used here.

\$\endgroup\$
  • \$\begingroup\$ This doesn't work for abcdefghijklmnopqrstuvwxyza.. \$\endgroup\$ – ბიმო Sep 26 '18 at 16:06
  • \$\begingroup\$ That link shows abcdefghijklmnopqrstuvwxyza as matching the regex, which is correct, though? I'm specifically answering the ordinary pangram question, not the perfect pangram. \$\endgroup\$ – Jack Brounstein Sep 26 '18 at 16:11
  • \$\begingroup\$ Nvm, I misunderstood the question.. I thought that an ordinary pangram is just a generalized pangram where \$n = 1\$. Sorry about that! \$\endgroup\$ – ბიმო Sep 26 '18 at 16:15
  • \$\begingroup\$ No worries. If you want a perfect pangram with n=1, you could specify that the matching string has exactly 26 characters: regex101.com/r/Z7NjEQ/4 You could also extend this to work for any given n, but I don't know of a way to extend it to all n. \$\endgroup\$ – Jack Brounstein Sep 26 '18 at 16:22
  • 1
    \$\begingroup\$ I believe you're right for pure regular expressions, but many regex engines have support for additional features/types of match that might allow it. Regular expressions shouldn't be able to match palindromes, either, but PCRE can do it. I don't know enough about those advanced features to see how it would work, but I'd lean very slightly toward it being possible. \$\endgroup\$ – Jack Brounstein Sep 26 '18 at 18:09
1
\$\begingroup\$

Regexp: 45 43 20 19 18 bytes

(?!.*(.).*\1).{26}

Assuming the input is [a-z] (lowercase, only alphabets a to z, spaces etc removed)

A byte saved, thanks to Neil

\$\endgroup\$
  • 1
    \$\begingroup\$ If you're assuming the input format then . instead of \w? \$\endgroup\$ – Neil Sep 25 '18 at 22:41
  • \$\begingroup\$ @Neil oh, thanks, stupid me \$\endgroup\$ – FatalError Sep 25 '18 at 23:23
  • \$\begingroup\$ @Shaggy "You can assume that all non-alpha characters have already been stripped out", just notified about the assumption \$\endgroup\$ – FatalError Sep 25 '18 at 23:24
  • \$\begingroup\$ This doesn’t work for either the regular challenge or the bonus. Doesn’t match thequickbrownfoxjumpsoverthelazydog (regular pangram) or squdgykil... (the bonus). \$\endgroup\$ – FrownyFrog Sep 26 '18 at 0:29

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