Editing 1313: Regex Golf

{{comic
| number    = 1313
| date      = January 6, 2014
| title     = Regex Golf
| image     = regex_golf.png
| titletext = <nowiki>/bu|[rn]t|[coy]e|[mtg]a|j|iso|n[hl]|[ae]d|lev|sh|[lnd]i|[po]o|ls/ matches the last names of elected US presidents but not their opponents.</nowiki>
}}

== Explanation ==
The comic talks about {{w|regular expressions}}, which are a way to specify textual patterns. Given a regular expression, one can search for the pattern it specifies inside a text string.  If the pattern is found, it's said that the pattern "matches" the string; if it's not found, it's said they do not match.

The title of the comic and the first panel is based on "[http://regex.alf.nu/ regex golf]", which is a discipline of "{{w|code golf}}", a game in which programmers attempt to solve a given programming problem using as few characters as possible, analogous to the number of {{w|golf}} shots it takes to reach the goal. In regex golfing, the programmer is given two sets of text fragments, and he/she tries to write the shortest possible regular expression which would match all elements of one set, while at the same time not matching any element from the other set.

The regex golf challenge Megan faces consists of matching all subtitles of ''{{w|Star Wars}}'' episodes, while not matching any subtitle of ''{{w|Star Trek}}'' episodes. ({{w|Subtitle (titling)|Subtitles}} are the secondary titles of the movies, after the ''"Star Trek: "'' or ''"Star Wars Episode N: "''. For example, in ''Star Wars Episode I: The Phantom Menace'', the subtitle is ''The Phantom Menace''.) In the first panel, she created a 12-character regex solving the challenge.

Then she moved on to building a tool which would automatically build such a regex for arbitrary lists of text, which could be described as {{w|meta}}- regex golfing. But as she has lost this tool, she needs to search through her files and chooses a tool called "{{w|grep}}" to find it.  This implies that she needs a regular expression that would find any code that appears to be a regex golf generator, which leads to another "meta-" layer of abstraction. At the end, Megan notes this sequence of meta-meta-... might go to infinity and Cueball quips that she now has "infinite problems" as a result of her efforts; Megan retorts that she already had "infinite problems" because she's geeky enough to run meta-versions of programs on themselves, and stubborn enough to continue on until she fails, to the exclusion of all else. This also seems to be a reference to a famous quote (see also ''[[1171: Perl Problems]]''):

<blockquote>''Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.''</blockquote>

===Regular expressions===
The first regex Megan uses is <code>/m | [tn]|b/</code>, said to match ''Star Wars'' subtitles but not ''Star Trek''.

The forward slashes <code>/</code> just mark the start and end of the regex. The <code>|</code> character means "or", so the regex matches any string that contains the patterns "<code>m </code>", "<code> [tn]</code>" or "<code>b</code>" (including the spaces). The square brackets match one of the enclosed characters, meaning that "<code> [tn]</code>" matches either "<code> t</code>" or "<code> n</code>". The regex is apparently case-insensitive, because it wouldn't work otherwise.

The Star Wars subtitles match the parts of the regex in the following way:
* "The Phanto<u>m </u>Menace" is matched by "<code>m </code>".
* "Attack of<u> t</u>he Clones" is matched by "<code> [tn]</code>".
* "Revenge of<u> t</u>he Sith" is matched by "<code> [tn]</code>".
* "A<u> N</u>ew Hope" is matched by "<code> [tn]</code>".
* "The Empire Strikes <u>B</u>ack" is matched by "<code>b</code>".
* "Return of<u> t</u>he Jedi" is matched by "<code> [tn]</code>".
Note that if one included the animated film "Star Wars: The Clone Wars" it would be matched by "<code> [tn]</code>".

On the other hand, none of the Star Trek subtitles contains an M followed by a space, a T or an N preceded by a space, or any B, so the regex does not match any of them. Note that in the original series all subtitles start with a "T" but it's the first character so it's not preceded by a space.

Here is the list that Megan probably used:
* Original series:
** The Motion Picture
** The Wrath of Khan
** The Search For Spock
** The Voyage Home
** The Final Frontier
** The Undiscovered Country
* The Next Generation:
** Generations
** First Contact
** Insurrection
** Nemesis
* Reboot series:
** ''the one without a subtitle''
** Into Darkness

In the last panel "and beyond" Megan uses the regular expression <code>/(meta-)*regex golf/</code> to describe her problem. <code>*</code> means "zero or more" of the preceding character/group (parentheses <code>()</code> group characters). So this regex matches "regex golf", "meta-regex golf", "meta-meta-regex golf", etc. In a way this is regex golf in itself, matching all levels of meta-regex golf while not matching anything else.

In the title text, there is a long regex that is the solution of another regex golf challenge: matching the last names of all elected US presidents but not their opponents. Note that the list of opponents include some people who were previously or later became presidents, so taken literally this is impossible. To make this work the list of opponents must exclude anyone who was also president. The regular expression itself works in a very similar way to the Star Wars/Trek one, including several different patterns separated by <code>|</code>. Each elected president matches one pattern while each opponent matches none.

Here is a list of elected president and the patterns they match:
{| class="wikitable"
!Number
!President
!Matched expression
|-
|1
|{{w|George Washington|George Wa<u>sh</u>ington}}
|<code>sh</code>
|-
|2
|{{w|John Adams|John <u>Ad</u>ams}}
|<code>[ae]d</code>
|-
|3
|{{w|Thomas Jefferson|Thomas <u>J</u>efferson}}
|<code>j</code>
|-
|4
|{{w|James Madison|James <u>Ma</u>dison}}
|<code>[mtg]a</code>
|-
|5
|{{w|James Monroe|James Monr<u>oe</u>}}
|<code>[coy]e</code>
|-
|6
|{{w|John Quincy Adams|John Quincy <u>Ad</u>ams}}
|<code>[ae]d</code>
|-
|7
|{{w|Andrew Jackson|Andrew <u>J</u>ackson}}
|<code>j</code>
|-
|8
|{{w|Martin Van Buren|Martin Van <u>Bu</u>ren}}
|<code>bu</code>
|-
|9
|{{w|William Henry Harrison|William Henry Harr<u>iso</u>n}}
|<code>iso</code>
|-
|11
|{{w|James K. Polk|James K. <u>Po</u>lk}}
|<code>[po]o</code>
|-
|12
|{{w|Zachary Taylor|Zachary <u>Ta</u>ylor}}
|<code>[mtg]a</code>
|-
|14
|{{w|Franklin Pierce|Franklin Pier<u>ce</u>}}
|<code>[coy]e</code>
|-
|15
|{{w|James Buchanan|James <u>Bu</u>chanan}}
|<code>bu</code>
|-
|16
|{{w|Abraham Lincoln|Abraham <u>Li</u>ncoln}}
|<code>[lnd]i</code>
|-
|17
|{{w|Andrew Johnson|Andrew <u>J</u>ohnson}}
|<code>j</code>
|-
|18
|{{w|Ulysses S. Grant|Ulysses S. Gra<u>nt</u>}}
|<code>[rn]t</code>
|-
|19
|{{w|Rutherford B. Hayes|Rutherford B. Ha<u>ye</u>s}}
|<code>[coy]e</code>
|-
|20
|{{w|James A. Garfield|James A. <u>Ga</u>rfield}}
|<code>[mtg]a</code>
|-
|22
|{{w|Grover Cleveland|Grover C<u>lev</u>eland}}
|<code>lev</code>
|-
|23
|{{w|Benjamin Harrison|Benjamin Harr<u>iso</u>n}}
|<code>iso</code>
|-
|24
|{{w|Grover Cleveland|Grover C<u>lev</u>eland}}
|<code>lev</code>
|-
|25
|{{w|William McKinley|William McKi<u>nl</u>ey}}
|<code>n[hl]</code>
|-
|26
|{{w|Theodore Roosevelt|Theodore R<u>oo</u>sevelt}}
|<code>[po]o</code>
|-
|27
|{{w|William Howard Taft|William Howard <u>Ta</u>ft}}
|<code>[mtg]a</code>
|-
|28
|{{w|Woodrow Wilson|Woodrow Wi<u>ls</u>on}}
|<code>ls</code>
|-
|29
|{{w|Warren G. Harding|Warren G. Har<u>di</u>ng}}
|<code>[lnd]i</code>
|-
|30
|{{w|Calvin Coolidge|Calvin Coo<u>li</u>dge}}
|<code>[lnd]i</code>
|-
|31
|{{w|Herbert Hoover|Herbert H<u>oo</u>ver}}
|<code>[po]o</code>
|-
|32
|{{w|Franklin D. Roosevelt|Franklin D. R<u>oo</u>sevelt}}
|<code>[po]o</code>
|-
|33
|{{w|Harry S. Truman|Harry S. Tru<u>ma</u>n}}
|<code>[mtg]a</code>
|-
|34
|{{w|Dwight D. Eisenhower|Dwight D. Eise<u>nh</u>ower}}
|<code>n[hl]</code>
|-
|35
|{{w|John F. Kennedy|John F. Kenn<u>ed</u>y}}
|<code>[ae]d</code>
|-
|36
|{{w|Lyndon B. Johnson|Lyndon B. <u>J</u>ohnson}}
|<code>j</code>
|-
|37
|{{w|Richard Nixon|Richard <u>Ni</u>xon}}
|<code>[lnd]i</code>
|-
|39
|{{w|Jimmy Carter|Jimmy Ca<u>rt</u>er}}
|<code>[rn]t</code>
|-
|40
|{{w|Ronald Reagan|Ronald Rea<u>ga</u>n}}
|<code>[mtg]a</code>
|-
|41
|{{w|George H. W. Bush|George H. W. <u>Bu</u>sh}}
|<code>bu</code>
|-
|42
|{{w|Bill Clinton|Bill Cli<u>nt</u>on}}
|<code>[rn]t</code>
|-
|43
|{{w|George W. Bush|George W. <u>Bu</u>sh}}
|<code>bu</code>
|-
|44
|{{w|Barack Obama|Barack Oba<u>ma</u>}}
|<code>[mtg]a</code>
|}

Note that some presidents are missing because they weren't elected but became presidents after the resignation/death of their formers.

Note also that Randall's regular expression must be modified slightly, because it also matches {{w|John C. Fremont|John C. Fremo<u>nt</u>}}, the runner-up to James Buchanan in 1856, as discussed by {{w|Peter Norvig}} at [http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb xkcd 1313: Regex Golf].  Note that Norvig provides a small amount of Python code which actually plays regex golf with arbitrary lists, and found a shorter solution than Randall's for the ''Star Wars'' vs ''Star Trek'' game.

== Transcript ==
:Regex golf:
:[Megan is sitting at a laptop. Cueball is standing behind her.]
:Megan: You try to match one group but not the other.
:Megan: /m | [tn]|b/ matches ''Star Wars'' subtitles but not ''Star Trek''.
:Cueball: Cool.

:Meta-regex golf:
:Megan: So I wrote a program that plays regex golf with arbitrary lists...
:Cueball: Uh oh...

:Meta-meta-regex golf:
:Megan: ...But I lost my code, so I'm grepping for files that look like regex golf solvers.

:...And beyond:
:Megan: Really, this is all /(meta-)*regex golf/.
:Cueball: Now you have ''infinite'' problems.
:Megan: No, I had those already.

== Trivia ==
*There are now at least four comics that references regular expressions. The other three are: [[208: Regular Expressions]], [[224: Lisp]] and [[1171: Perl Problems]].
*Additionally, regular expressions are mentioned in title text of [[1277: Ayn Random]].
*A regular expression is used in the [http://what-if.xkcd.com/75/ 75th] episode of [[what if?]] to calculate the answer that week's question.
*Also, Randall mentions [http://regex.alf.nu/ a website with a regexp golf game] he got distracted by while researching for the [http://what-if.xkcd.com/78/ 78th] episode of [[what if?]] (which was published one day after this comic).

{{comic discussion}}
[[Category:Comics featuring Cueball]]
[[Category:Comics featuring Megan]]
[[Category:Computers]]