{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "# xkcd 1313: Regex Golf\n", "\n", "

Peter Norvig
January 2014
new movies, November 2015
Python 3, March 2026

\n", "\n", "I ❤️ [**xkcd**](http://xkcd.com)! It reliably provides top-rate [insights](http://xkcd.com/285/), [humor](http://xkcd.com/612/), or [both](http://xkcd.com/627/). I was thrilled when I got to [introduce Randall Monroe](http://www.youtube.com/watch?v=zJOS0sV2a24) for a talk in 2007. \n", "\n", "But in [xkcd #1313](http://xkcd.com/1313), \n", "\n", "\n", "\n", "I found that the hover text, \"/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\", contains a confusing contradiction. I'm old enough to remember that Jimmy Carter won one term and lost a second. No regular expression could both match and not match \"Carter\"!\n", "\n", "But this got me thinking: can I come up with an algorithm to match or beat Randall's regex golf scores? The game is on.\n", "\n", "# Part 1: Presidents\n", " \n", "I started by finding a [listing](http://www.anesi.com/presname.htm) of presidential elections, giving me these winners and losers:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [], "source": [ "import re\n", "import itertools\n", "\n", "def words(text: str) -> set[str]: return set(text.split())\n", "\n", "winners = words('''washington adams jefferson jefferson madison madison monroe \n", " monroe adams jackson jackson van-buren harrison polk taylor pierce buchanan \n", " lincoln lincoln grant grapartnt hayes garfield cleveland harrison cleveland mckinley\n", " mckinley roosevelt taft wilson wilson harding coolidge hoover roosevelt \n", " roosevelt roosevelt roosevelt truman eisenhower eisenhower kennedy johnson nixon \n", " nixon carter reagan reagan bush clinton clinton bush bush obama obama''')\n", "\n", "losers = words('''clinton jefferson adams pinckney pinckney clinton king adams \n", " jackson adams clay van-buren van-buren clay cass scott fremont breckinridge \n", " mcclellan seymour greeley tilden hancock blaine cleveland harrison bryan bryan \n", " parker bryan roosevelt hughes cox davis smith hoover landon willkie dewey dewey \n", " stevenson stevenson nixon goldwater humphrey mcgovern ford carter mondale \n", " dukakis bush dole gore kerry mccain romney''')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "We can see that there are multiple names that are both winners and losers:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "data": { "text/plain": [ "{'adams',\n", " 'bush',\n", " 'carter',\n", " 'cleveland',\n", " 'clinton',\n", " 'harrison',\n", " 'hoover',\n", " 'jackson',\n", " 'jefferson',\n", " 'nixon',\n", " 'roosevelt',\n", " 'van-buren'}" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "winners & losers" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "Clinton? He won both his elections, didn't he? Yes, *Bill* Clinton did, but *George* Clinton (the Revolutionary War leader, not the Funkadelic leader) was a losing opponent in 1792 and 1812. To avoid the contradiction, I decided to eliminate all winners from the set of losers (and in fact Randall later confirmed that that was his intent):" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [], "source": [ "losers = losers - winners" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "# Defining the Problem\n", "\n", "\n", "Let's be clear exactly what we're trying to achieve. We're looking for a Python regular expression which, when used with the `re.search` function, will match all of the winners but none of the losers. We can define the function `mistakes` to return a set of misclassifications; if `mistakes` is empty then the regular expression is verified correct:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [], "source": [ "def mistakes(regex, winners, losers) -> set[str]:\n", " \"\"\"The set of mistakes made by this regex in classifying winners and not losers.\"\"\"\n", " return ({\"Should have matched: \" + W for W in winners if not re.search(regex, W)}\n", " | {\"Should not have matched: \" + L for L in losers if re.search(regex, L)})" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "Let's check the xkcd regex:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "data": { "text/plain": [ "{'Should not have matched: fremont'}" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "xkcd = \"bu|[rn]t|[coy]e|[mtg]a|j|iso|n[hl]|[ae]d|lev|sh|[lnd]i|[po]o|ls\"\n", "\n", "mistakes(xkcd, winners, losers)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "The xkcd regex incorrectly matches `\"fremont\"`, representing John C. Frémont, the Republican candidate who lost to James Buchanan in 1856. Could Randall Monroe have made an error? Is someone **[wrong](http://xkcd.com/386/)** on the Internet? Investigating the [1856 election](http://en.wikipedia.org/wiki/United_States_presidential_election,_1856), I see that Randall must have used Millard Fillmore, the third-party candidate, as the opponent. Fillmore is more famous, having served as the 13th president (although he never won an election; he became president when Taylor died in office). But Fillmore only got 8 electoral votes in 1856 while Fremont got 114, so I will stick with Fremont in *my* list of losers. \n", "\n", "Under the interpretation that Fillmore, not Fremont, was the loser, Randall's regex makes no mistakes:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "alternative_losers = {'fillmore'} | losers - {'fremont'}\n", "\n", "not mistakes(xkcd, winners, alternative_losers)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "# Strategy for Finding a Regex\n", "\n", "\n", "We need a strategy to find a regex that matches all the winners but none of the losers. I came up with this approach:\n", " \n", "- Generate a pool of regex *parts*: small regexes of a few characters, such as `\"bu\"` or `\"r.e$\"` or `\"j\"`.\n", "- Consider only parts that match at least one winner, but no losers.\n", "- Our solution will be formed by \"or\"-ing together some of these parts (e.g. `\"bu|n.e|j\"`).\n", "- This is a [set cover problem](http://en.wikipedia.org/wiki/Set_cover_problem): pick some of the parts so that they cover all the winners.\n", "- Set cover is an NP-hard problem, so I feel justified in using an approximation approach that finds a small but not necessarily smallest solution.\n", "- For many NP-hard problems a good approximation can be had with a [greedy algorithm](http://en.wikipedia.org/wiki/Greedy_algorithm): Pick the \"best\" part first (the one that covers the most winners with the fewest characters), and repeat, choosing the \"best\" each time until there are no more winners to cover.\n", "- To guarantee that we will find a solution, make sure that each winner has at least one part that matches it.\n", "- The quality (shortness) of our solution depends on generating good parts and on searching over them well.\n", "\n", "There are three ways this strategy can fail to find the shortest possible regex:\n", "\n", "- The shortest regex might not be a disjunction. Our strategy can only find disjunctions (of the form `\"a|b|c|...\"`). \n", "- The shortest regex might be a disjunction formed with different parts. For example, `\"[rn]t\"` is not in our pool of parts.\n", "- The greedy algorithm isn't guaranteed to find the shortest solution. We might have all the right parts, but pick the wrong ones.\n", "\n", "Just to be clear, I define the terms I will be using:\n", "\n", "- *winners:* A set of strings; our solution is required to match each of them.\n", "- *losers:* A set of strings; our solution is not allowed to match any of them.\n", "- *part:* A small regular expression, a string, such as `'bu'` or `'a.a'`.\n", "- *pool:* A set of parts from which we will pick a subset to form the solution.\n", "- *regex:* A [regular expression](http://docs.python.org/2/library/re.html); a pattern used to match against a string. \n", "- *solution:* A regular expression that matches all winners but no losers.\n", "- *whole:* A part that matches a whole word (and nothing else): `'^word$'`\n", "\n", "# Main Algorithm\n", "\n", "The algorithm is below. Our pool of parts is a set of strings created with `regex_parts(winners, losers)`. We accumulate parts into the list `solution`, which starts empty. On each iteration choose the best part: the one with a maximum score. (I decided by default to score 4 points for each winner matched, minus one point for each character in the part.) We then add the best part to `solution`, and remove from winners all the strings that are matched by `best`. Finally, we update the pool, keeping only those parts that still match one or more of the remaining winners. When there are no more winners left, OR together all the solution parts to give the final regular expression string." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [], "source": [ "def findregex(winners, losers, k=4) -> str:\n", " \"\"\"Find a regex that matches all winners but no losers (sets of strings).\"\"\"\n", " # Make a pool of regex parts, then pick from them to cover winners.\n", " # On each iteration, add the 'best' part to 'solution',\n", " # remove winners covered by best, and keep in 'pool' only parts\n", " # that still match some winner.\n", " pool = regex_parts(winners, losers)\n", " solution = []\n", " def score(part: str) -> int: return k * len(matches(part, winners)) - len(part)\n", " while winners:\n", " best = max(pool, key=score)\n", " solution.append(best)\n", " winners = winners - matches(best, winners)\n", " pool = {r for r in pool if matches(r, winners) and r != best}\n", " return OR(solution)\n", "\n", "def matches(regex, strings: set[str]) -> set[str]:\n", " \"\"\"Return a set of all the strings that are matched by regex.\"\"\"\n", " return {s for s in strings if re.search(regex, s)}\n", "\n", "OR = '|'.join # Join a sequence of strings with '|' between them" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "# Regex Parts\n", "\n", "Now we need to define what the `regex_parts` are. Here's what I came up with:\n", "\n", "- For each winner, include a regex that matches the entire string exactly. I call this regex a *whole*.\n", " - Example: for `'word'`, include `'^word$'`\n", " - This way, we know there is at least one part that will match each winner.\n", "- For each whole, generate *subparts* consisting of 1 to 4 consecutive characters.\n", " - Example: `subparts('^it$')` == `{'^', 'i', 't', '$', '^i', 'it', 't$', '^it', 'it$', '^it$'}`\n", "- For each subpart, generate all ways to replace any of the letters with a dot (the \"match any\" character).\n", " - Example: `dotify('it')` == `{'it', 'i.', '.t', '..'}`\n", "- Keep only the dotified subparts that do not match any of the losers.\n", "\n", "Note that I only used a few of the regular expression mechanisms: `'.'`, `'^'`, and `'$'` (all joined with `|`). I didn't try to use character classes (`[a-z]`), nor any of the repetition operators, nor other advanced mechanisms. Why? I thought that the advanced features usually take too many characters. For example, I don't allow the part `'[rn]t'`, but I can achieve the same effect with the same number of characters by combining two parts: `'rt|nt'`. I could add more complicated mechanisms later, but for now, [YAGNI](https://en.wikipedia.org/wiki/You_aren%27t_gonna_need_it). Here is the code:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [], "source": [ "def regex_parts(winners, losers) -> set[str]:\n", " \"\"\"Return parts that match at least one winner, but no loser.\"\"\"\n", " wholes = {'^' + w + '$' for w in winners}\n", " sub_parts = union(map(subparts, wholes))\n", " parts = union(map(dotify, sub_parts))\n", " return wholes | {p for p in parts if not matches(p, losers)}\n", "\n", "def subparts(word: str, N=4) -> set[str]:\n", " \"\"\"Return a set of subparts of word: consecutive characters up to length N (default 4).\"\"\"\n", " return {word[i:i+n+1] for i in range(len(word)) for n in range(N)}\n", " \n", "def dotify(part: str) -> set[str]:\n", " \"\"\"Return all ways to replace a subset of chars in `part` with '.'.\"\"\"\n", " choices = [(c if c in '^$' else c + '.') for c in part]\n", " return {cat(chars) for chars in itertools.product(*choices)}\n", "\n", "def union(collections) -> set: \n", " \"\"\"The union of some sets.\"\"\"\n", " return set().union(*collections)\n", "\n", "cat = ''.join # cat(strs: Collection[str]) -> str: concatenate strings " ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "Our program is complete! To better view the output I define `report` to either take a solution as input or call `findregex` to create a solution, and then to verify the solution, and print some stats: the number of characters in the solution, the number of parts, the *competitive ratio* (the ratio between the lengths of a trivial solution and the actual solution), and the number of winners and losers. Let's try it:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [], "source": [ "def report(winners, losers, solution=None):\n", " \"\"\"Find a regex to match winners but not losers. Print summary.\"\"\"\n", " solution = solution or findregex(winners, losers)\n", " assert not mistakes(solution, winners, losers)\n", " N = len(solution)\n", " T = len('^(' + OR(winners) + ')$')\n", " print(f'Characters: {N}, Parts: {solution.count(\"|\") + 1}, Competitive ratio: '\n", " f'{T / N:.1f}, Winners: {len(winners)}, Losers: {len(losers)}')\n", " return solution" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 54, Parts: 15, Competitive ratio: 5.1, Winners: 35, Losers: 34\n" ] }, { "data": { "text/plain": [ "'a.a|a..i|j|li|a.t|i..n|oo|bu|ay.|n.e|r.e$|ru|ls|po|v.l'" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "report(winners, losers)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 54, Parts: 15, Competitive ratio: 5.1, Winners: 35, Losers: 34\n" ] }, { "data": { "text/plain": [ "'a.a|a..i|j|li|a.t|i..n|oo|bu|ay.|n.e|r.e$|ru|ls|po|v.l'" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "report(winners, alternative_losers)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We get the same regex, regardless of which set of losers we use. How does that compare to Randall's solution?" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 63, Parts: 13, Competitive ratio: 4.4, Winners: 35, Losers: 34\n" ] }, { "data": { "text/plain": [ "'bu|[rn]t|[coy]e|[mtg]a|j|iso|n[hl]|[ae]d|lev|sh|[lnd]i|[po]o|ls'" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "report(winners, alternative_losers, solution=xkcd)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Our regex is shorter than Randall's by 10 characters." ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "# Test Suite\n", "\n", "Here's a test suite to give us more confidence in (and familiarity with) our functions:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "data": { "text/plain": [ "'tests pass'" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def tests():\n", " assert subparts('^it$') == {'^', 'i', 't', '$', '^i', 'it', 't$', '^it', 'it$', '^it$'}\n", " assert subparts('this') == {'t', 'h', 'i', 's', 'th', 'hi', 'is', 'thi', 'his', 'this'}\n", " subparts('banana') == {'a', 'an', 'ana', 'anan', 'b', 'ba', 'ban', 'bana', \n", " 'n', 'na', 'nan', 'nana'}\n", " \n", " assert dotify('it') == {'it', 'i.', '.t', '..'}\n", " assert dotify('^it$') == {'^it$', '^i.$', '^.t$', '^..$'}\n", " assert dotify('this') == {'this', 'thi.', 'th.s', 'th..', 't.is', 't.i.', 't..s', 't...',\n", " '.his', '.hi.', '.h.s', '.h..', '..is', '..i.', '...s', '....'}\n", " assert regex_parts({'win'}, {'losers', 'bin', 'won'}) == {\n", " '^win$', '^win', '^wi.', 'wi.', 'wi', '^wi', 'win$', 'win', 'wi.$'}\n", " assert regex_parts({'win'}, {'bin', 'won', 'wine', 'wit'}) == {'^win$', 'win$'}\n", " regex_parts({'boy', 'coy'}, \n", " {'ahoy', 'toy', 'book', 'cook', 'boycott', 'cowboy', 'cod', 'buy', 'oy', \n", " 'foil', 'coyote'}) == {'^boy$', '^coy$', 'c.y$', 'coy$'}\n", " \n", " assert matches('a|b|c', {'a', 'b', 'c', 'd', 'e'}) == {'a', 'b', 'c'}\n", " assert matches('a|b|c', {'any', 'bee', 'succeed', 'dee', 'eee!'}) == {\n", " 'any', 'bee', 'succeed'}\n", " \n", " assert OR(['a', 'b', 'c']) == 'a|b|c'\n", " assert OR(['a']) == 'a'\n", " assert OR([]) == ''\n", " \n", " assert words('this is a test this is') == {'this', 'is', 'a', 'test'}\n", " \n", " assert findregex({\"ahahah\", \"ciao\"}, {\"ahaha\", \"bye\"}) == 'a.$'\n", " assert findregex({\"this\", \"that\", \"the other\"}, {\"one\", \"two\", \"here\", \"there\"}) == 'h..$'\n", " assert findregex({'boy', 'coy', 'toy', 'joy'}, {'ahoy', 'buy', 'oy', 'foil'}) == '^.oy'\n", " \n", " assert not mistakes('a|b|c', {'ahoy', 'boy', 'coy'}, {'joy', 'toy'})\n", " assert not mistakes('^a|^b|^c', {'ahoy', 'boy', 'coy'}, {'joy', 'toy', 'kickback'})\n", " assert mistakes('^.oy', {'ahoy', 'boy', 'coy'}, {'joy', 'ploy'}) == {\n", " \"Should have matched: ahoy\", \n", " \"Should not have matched: joy\"}\n", " return 'tests pass'\n", "\n", "tests()" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "\n", "\n", "# Part 2: A Program that Plays Regex Golf with Arbitrary Lists\n", "\n", "\n", "Let's move on to arbitrary lists. Two arbitrary lists are the top 10 [boys and girls names](http://www.ssa.gov/oact/babynames/) for 2012:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 11, Parts: 3, Competitive ratio: 6.4, Winners: 10, Losers: 10\n" ] }, { "data": { "text/plain": [ "'a.$|e.$|a.o'" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "boys = words('jacob mason ethan noah william liam jayden michael alexander aiden')\n", "girls = words('sophia emma isabella olivia ava emily abigail mia madison elizabeth')\n", "\n", "report(boys, girls)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "This is interesting because `'a.$|e.$|a.o'` is an example of something that could be re-written in a shorter form if we allowed more complex parts. The following would save one character:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 10, Parts: 2, Competitive ratio: 7.0, Winners: 10, Losers: 10\n" ] }, { "data": { "text/plain": [ "'[ae].(o|$)'" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "report(boys, girls, solution='[ae].(o|$)')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Of course we can always go the other way:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 10, Parts: 3, Competitive ratio: 7.1, Winners: 10, Losers: 10\n" ] }, { "data": { "text/plain": [ "'a$|^..i|is'" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "report(girls, boys)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 15, Parts: 6, Competitive ratio: 5.3, Winners: 10, Losers: 10\n" ] }, { "data": { "text/plain": [ "'o.$|x|ir|q|f|og'" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "drugs = words('lipitor nexium plavix advair ablify seroquel singulair crestor actos epogen')\n", "cities = words('paris trinidad capetown riga zurich shanghai vancouver chicago adelaide auckland')\n", "\n", "report(drugs, cities)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 11, Parts: 4, Competitive ratio: 7.6, Winners: 10, Losers: 10\n" ] }, { "data": { "text/plain": [ "'ri|an|ca|de'" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "report(cities, drugs)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's try [separating the sheeps from the goats](https://www.biblegateway.com/passage/?search=Matthew%2025%3A31-46&version=NIV):" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 16, Parts: 5, Competitive ratio: 5.2, Winners: 10, Losers: 10\n" ] }, { "data": { "text/plain": [ "'^..r|c.|es|.m|k$'" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sheep = words('merino leicester lincoln dorset dorper hampshire suffolk barbados jacob friesian')\n", "goats = words('alpine nubian toffenburg oberhasli sable spanish boer kalahari kiko myotonic')\n", "\n", "report(sheep, goats)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "\n", "\n", "# Star (Wars|Trek)\n", "\n", "The challenge from the first panel of the strip can be answered with this code:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 9, Parts: 3, Competitive ratio: 13.0, Winners: 6, Losers: 9\n" ] }, { "data": { "text/plain": [ "' T|E.P|PE'" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def phrases(text, sep='/'): return {line.upper().strip() for line in text.split(sep)}\n", "\n", "starwars = phrases('''The Phantom Menace / Attack of the Clones / Revenge of the Sith /\n", " A New Hope / The Empire Strikes Back / Return of the Jedi''')\n", "\n", "startrek = phrases('''The Wrath of Khan / The Search for Spock / The Voyage Home /\n", " The Final Frontier / The Undiscovered Country / Generations / \n", " First Contact / Insurrection / Nemesis''')\n", "\n", "report(starwars, startrek)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "Neat—our solution is one character shorter than Randall's. We can verify that Randall's solution is also correct:" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 10, Parts: 3, Competitive ratio: 11.7, Winners: 6, Losers: 9\n" ] }, { "data": { "text/plain": [ "'M | [TN]|B'" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "report(starwars, startrek, solution='M | [TN]|B')" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "## Update (Nov 2015): There are two new movies in the works!\n", "\n", "
\n", "\n", "\n", "\n", "
\n", "\n", "Let's add them:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 10, Parts: 3, Competitive ratio: 13.5, Winners: 7, Losers: 10\n" ] }, { "data": { "text/plain": [ "' T|KE|E..H'" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "starwars.add('THE FORCE AWAKENS')\n", "startrek.add('BEYOND')\n", "\n", "report(starwars, startrek)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "The two movies cost us one more character.\n", "\n", "There are lots of examples to play with over at [regex.alf.nu](http://regex.alf.nu), like this one:" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 3, Parts: 1, Competitive ratio: 53.7, Winners: 21, Losers: 21\n" ] }, { "data": { "text/plain": [ "'f.o'" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "foo = words('''afoot catfoot dogfoot fanfoot foody foolery foolish fooster \n", " footage foothot footle footpad footway hotfoot jawfoot mafoo nonfood padfoot \n", " prefool sfoot unfool''')\n", "\n", "bar = words('''Atlas Aymoro Iberic Mahran Ormazd Silipan altared chandoo crenel \n", " crooked fardo folksy forest hebamic idgah manlike marly palazzi sixfold \n", " tarrock unfold''')\n", "\n", "report(foo, bar)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "The answer varies with different runs; sometimes it is `'foo'` and sometimes `'f.o'`. (Both have 3 characters, but `'f.o'` is smaller in terms of the total amount of ink/pixels needed to render it.) You may ask how can the answer vary, when the program has no calls to any `random` function? The answer is that the program does use `max` to iterate over a set, and the order of elements in a set is *unspecified* by Python, and depends on details of memory layout that can vary from run to run. \n", "\n", "This is an example that is designed to be much harder in the other direction:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Characters: 26, Parts: 8, Competitive ratio: 6.0, Winners: 21, Losers: 21\n" ] }, { "data": { "text/plain": [ "'r..$|k|.m|...n|la|ld|es|dg'" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "report(bar, foo)" ] }, { "cell_type": "markdown", "metadata": { "button": false, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "# What To Do Next? \n", "\n", "I see two options:\n", "\n", "- Stop here and declare victory! *Yay!*\n", "- Try to make the program faster and capable of finding shorter regexes. \n", "\n", "My first inclination was \"stop here\", and that's what this notebook will shortly do. But several correspondents offered very interesting suggestions, so I returned to the problem in **[a second notebook](http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313-part2.ipynb?create=1)**. \n", "\n", "I was asked whether Randall was **[wrong](http://xkcd.com/386/)** to come up with \"only\" a 10-character Star Wars regex, whereas I showed there is a 9-character version. I would say that, given his role as a cartoonist, author, public speaker, educator, and entertainer, he has [chosen ... wisely](https://www.youtube.com/watch?v=-_IlNbsILLE). He wrote a program that was good enough to allow him to make a great webcomic. A 9-character regex would not improve the comic. Randall stated that he used a genetic algorithm to find his regexes, and it has been said that genetic algorithms are often the second (or was it the third?) best method to solve any problem, and that's all he needed. But if you consider that in addition to all those roles, Randall is also still a practicing computer scientist, you could say\n", "[he chose ... poorly](https://www.youtube.com/watch?v=Ubw5N8iVDHI). Genetic algorithms are good when you want to combine the structure of two solutions to yield a better solution, so they would work well if the best regexes had a complicated tree structure. But they don't! The best solutions are disjunctions of small parts. So the genetic algorithm is trying to combine the first half of one disjunction with the second half of another—but that isn't useful, because the components of a disjunction are unordered; imposing an ordering on them doesn't help.\n", "\n", "# Summary\n", "\n", "That was fun! I hope this page gives you an idea of how to think about problems like this. Let's review what we did:\n", "\n", "- Found an interesting problem (in a comic strip) and realized that it would not be hard to program a solution.\n", "- Wrote the function `mistakes` to prove that we really understand exactly what the problem is.\n", "- Came up with an approach: create lots of regex parts, and \"or\" together a subset of them.\n", "- Realized that this is an instance of a known problem, *set cover*.\n", "- Since set cover is computationally expensive, decide to use a *greedy algorithm*, which will be efficient (although not optimal).\n", "- Decided what goes into the pool of regex parts.\n", "- Implemented an algorithm to greedily pick parts from the pool (the function `findregex`).\n", "- Tried the algorithm on some examples.\n", "- Declared victory!\n", "\n", " \n", "# Thanks!\n", "\n", "\n", "Thanks especially to [Randall Monroe](http://xkcd.com/) for inspiring me to do this, to [regex.alf.nu](http://regex.alf.nu) for inspiring Randall, to Sean Lip for correcting \"Wilkie\" to \"Willkie,\" and to [Davide Canton](https://plus.sandbox.google.com/108324296451294887432/posts), [Thomas Breuel](https://plus.google.com/118190679520611168174/posts), and [Stefan Pochmann](http://www.stefan-pochmann.info/spocc/) for providing suggestions to improve my code; see my **[second notebook](http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313-part2.ipynb?create=1)**.\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python [conda env:base] *", "language": "python", "name": "conda-base-py" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.9" } }, "nbformat": 4, "nbformat_minor": 4 }