27
\$\begingroup\$

We've already got a meta-regex-golf problem as inspired by the xkcd comic

copyright 2013 Randall Munroe

But, this regex golf looks fun, too! I want to distinguish between the states of the US and the regions of Italy. Why? I'm a citizen of both countries, and I always have trouble with this*.

The regions of Italy are

Abruzzo, Valle d'Aosta, Puglia, Basilicata, Calabria, Campania, Emilia-Romagna, Friuli-Venezia Giulia, Lazio, Liguria, Lombardia, Marche, Molise, Piemonte, Sardegna, Sicilia, Trentino-Alto Adige/Südtirol, Toscana, Umbria, Veneto

and the states of the USA are

Alabama, Alaska, Arizona, Arkansas, California, Colorado, Connecticut, Delaware, Florida, Georgia, Hawaii, Idaho, Illinois, Indiana, Iowa, Kansas, Kentucky, Louisiana, Maine, Maryland, Massachusetts, Michigan, Minnesota, Mississippi, Missouri, Montana, Nebraska, Nevada, New Hampshire, New Jersey, New Mexico, New York, North Carolina, North Dakota, Ohio, Oklahoma, Oregon, Pennsylvania, Rhode Island, South Carolina, South Dakota, Tennessee, Texas, Utah, Vermont, Virginia, Washington, West Virginia, Wisconsin, Wyoming

Your job is to write a program which distinguishes these lists with a regular expression. This is a new game, so here's the

Rules

  • Distinguishing between lists must be done with a single matching regular expression.
  • Your score is the length of that regular expression, smaller is better.

To be clear: all work must be done by the regular expression -- no filtering, no replacements, no nothing... even if those are also done with regular expressions. That is, the input should be passed directly into a regular expression, and only the binary answer (match / no match) can be used by later parts of the code. The input should never be inspected or changed by anything but the matching expression. Exception: eating a newline with something akin to Ruby's chomp is fine.

Your program should take a single entry (optionally followed by \n or EOF if it makes things easier) from either list from stdin, and print to stdout the name of that list. In this case, our lists are named Italy and USA.

To test your code, simply run both lists through it. Behavior may be undefined for strings which do not occur in the list.

Scoring Issues

This might have to be done on a language-by-language basis. In Perl,

m/foobarbaz/

is a matching regular expression. However, in Python,

import re
re.compile('foobarbaz')

does the same thing. We wouldn't count the quotes for Python, so I say we don't count the m/ and final / in Perl. In both languages, the above should receive a score of 9.

To clarify a point raised by Abhijit, the actual length of the matching expression is the score, even if you generate it dynamically. For example, if you found a magical expression m,

n="foo(bar|baz)"
m=n+n

then you should not report a score of 12: m has length 24. And just to be extra clear, the generated regular expression can't depend on the input. That would be reading the input before passing it into the regular expression.

Example Session

input> Calabria
Italy
input> New Hampshire
USA
input> Washington
USA
input> Puglia
Italy

* Actually, that's a lie. I have never had any trouble with this at all.

\$\endgroup\$
16
  • \$\begingroup\$ Can you please explain, what you mean by "no filtering, no replacements, no nothing... even if those are also done with regular expressions.". Just to clarify, does it mean filtering, replacements of the list of states/regions or the focus is wider? \$\endgroup\$
    – Abhijit
    Jan 7, 2014 at 4:29
  • \$\begingroup\$ @Abhijit edited. Is that clearer? \$\endgroup\$
    – boothby
    Jan 7, 2014 at 4:34
  • 4
    \$\begingroup\$ @Eliseod'Annunzio: DC is not a state \$\endgroup\$
    – Kyle Kanos
    Jan 7, 2014 at 14:21
  • 2
    \$\begingroup\$ "Behavior may be undefined for strings which do not occur in the list." this rule is broken: it allows one to return USA in case of such a string, hence you would just have to check Italian regions, and return USA otherwise. \$\endgroup\$
    – o0'.
    Jan 14, 2014 at 18:59
  • 1
    \$\begingroup\$ @boothby well, no, it's simple logic: it is basically asking only a regexp to match italian regions, but needlessly worded in a much complicated way. The whole point about american states is totally not relevant to the actual question asked, thanks to this bug. This also makes the question much less interesting. \$\endgroup\$
    – o0'.
    Jan 14, 2014 at 20:52

6 Answers 6

11
\$\begingroup\$

Perl - 51 36 bytes (for regex)

print<>=~/.A|ise|net|te|z.o|[cp]a|[lr]ia|r[cd]/?"Italy
":"USA
"

Nothing special, but may as well post it, because it's different to other 51 bytes solution.

Or alternatively, shorten my already short solution by 15 bytes. This wins for now, I think.

\$\endgroup\$
8
\$\begingroup\$

Perl, 40 chars

Approaching this from the other direction, i.e. matching the U.S. states:

[DNIOWy]|ss|M.n|^A.*a|or|[aguh]i|[sth]\b

The only Perl/PCRE-specific feature in the regexp is the \b word boundary anchor, which I used instead of the $ end-of-string anchor to let it match "South Carolina".

Here's the regexp in a Perl one-liner for testing:

perl -nE 'say /[DNIOWy]|ss|M.n|^A.*a|or|[aguh]i|[sth]\b/ ? "USA" : "Italy"'
\$\endgroup\$
2
  • \$\begingroup\$ This is a more golfy test harness: perl -pe '$_=/re/?"USA\n":"Italy\n"' \$\endgroup\$
    – Pseudonym
    Jan 7, 2014 at 23:09
  • 3
    \$\begingroup\$ @Pseudonym: meh. As long as it doesn't count in the score, might as well keep it readable. \$\endgroup\$ Jan 7, 2014 at 23:29
7
+200
\$\begingroup\$

Regex (POSIX ERE), 28 bytes

Matching the regions of Italy:

[eldrz]..$|[cpVS]a|-|[hst]e$

Try it online!

Since we're being scored on the length of the pure regex, it just makes sense to show that alone above. The TIO test harness uses bash and egrep, but practically any regex engine would work. The only thing that makes this require POSIX ERE instead of POSIX BRE are the unescaped | alternative separators. Here is a bash oneliner to apply it:

egrep -q '[eldrz]..$|[cpVS]a|-|[hst]e$'&&echo Italy||echo USA

I used regexp-golf-coffeescript, with a little parameter tuning, to brute-force this.

You can experiment with deleting characters from the character classes or deleting alternatives in the TIO to see how many correct matches are lost by doing so. For many, it's just one each.

There may be further optimization possible. The script I used only searches the space in which a single character class is used per alternative, but some regex golf problems of this type benefit from multiple character classes in a single alternative, like [bgr].[ei]. However, given the characteristics of this data set, I expect that the benefit, if any, would probably be no more than a couple bytes.

Regex (POSIX ERE), 41 bytes

Matching the states of the USA:

[IfKNOWwhy]..|[kamed].$|t$|iz|ta.|[guaM]i

Try it online!

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

Ruby (plain regex), 44

$_ = gets.chomp
puts /'|-|(([^gn]i|gn|at)a|[hst]e|to|zo)$|To|La|pa/ ? "Italy" : "USA"

You know what? Case sensitivity is the best start-of-word anchor.

I'm not sure, but I think I owe the pa to Hax0r778's answer.

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

Perl - 51

(<STDIN> =~ m/'|-|ru|pu|at|pa|az|gu|mb|rc|ie|rd|ci|os|abr|mol|ven/)?printf("Italy\n"):printf("USA\n");
\$\endgroup\$
0
3
\$\begingroup\$

JavaScript 42

alert(/at|gn|mp|sc|-|'|((zi?|t)o|[hts]e|[lrd]ia)$/g.test(prompt())?"Italy":"USA")

I was initially going to work this out from the USA side, as eliminating KWXY from the USA list strips a lot of the States away... But Italy had it bested by a good 17 characters...

If we go with fat arrow notation we can reduce this to a simple function with a return variable.

r=s=>/at|gn|mp|sc|-|'|((zi?|t)o|[hts]e|[lrd]ia)$/g.test(s)?"Italy":"USA"

> r("South Dakota") // USA
> r("Puglia") // Italy
\$\endgroup\$

Your Answer

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

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