ipynb/Menu.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: right\" align=\"right\"><i>Peter Norvig, Oct 2022</i></div>\n",
    "\n",
    "# Efficiently Selecting Names from a Menu \n",
    "\n",
    "We've all been faced with the task of selecting an item from an online menu. Usually you have the following options:\n",
    "\n",
    "- You can select an item by clicking on it.\n",
    "- You can type a few letters to move the menu's cursor to the first item whose prefix matches those letters (case ignored). \n",
    "- You can move the cursor up or down with the arrow keys.\n",
    "\n",
    "In this notebook we're going to ignore the \"clicking on it\" option and concentrate on finding the shortest sequence of keystrokes (letters or arrow keys) that will select an item in the menu.\n",
    "\n",
    "# Country Menu\n",
    "\n",
    "I live in the United States, but when faced with a country menu, I think of my home as \"`un↓↓`\". I know that typing \"`un`\" will get me to \"United Arab Emirates\" (roughly 185 items deep in the menu) and then two down arrows will take me past \"United Kingdom\" to \"United States.\" \n",
    "\n",
    "But questions remain:\n",
    "- Is that the shortest possible key sequence? \n",
    "- What are shortest sequences for other country names? \n",
    "- What's the average key sequence length? \n",
    "- What about other menus (with items other than countries)? \n",
    "\n",
    "Let's answer these questions. First some preliminary imports and declarations, and a list of country names:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Dict, List, Iterable\n",
    "from collections import Counter\n",
    "import numpy as np\n",
    "\n",
    "up     = '↑' # up arrow key\n",
    "down   = '↓' # down arrow key\n",
    "\n",
    "Item   = str # Type for a menu item, e.g. 'United States'\n",
    "Keyseq = str # Type for a sequence of keystrokes (a string of letters and arrows, e.g. 'Un↓↓')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "countries = [\n",
    "    'Afghanistan', 'Albania', 'Algeria', 'Andorra', 'Angola', 'Antigua and Barbuda', 'Argentina', 'Armenia', \n",
    "    'Australia', 'Austria', 'Azerbaijan', 'Bahamas, The', 'Bahrain', 'Bangladesh', 'Barbados', 'Belarus', \n",
    "    'Belgium', 'Belize', 'Benin', 'Bhutan', 'Bolivia', 'Bosnia and Herzegovina', 'Botswana', 'Brazil', 'Brunei', \n",
    "    'Bulgaria', 'Burkina Faso', 'Burundi', 'Cabo Verde', 'Cambodia', 'Cameroon', 'Canada', \n",
    "    'Central African Republic', 'Chad', 'Chile', 'China', 'Colombia', 'Comoros', 'Congo, Democratic Republic of the', \n",
    "    'Congo, Republic of the', 'Costa Rica', \"Cote d'Ivoire\", 'Croatia', 'Cuba', 'Cyprus', 'Czech Republic', 'Denmark', \n",
    "    'Djibouti', 'Dominica', 'Dominican Republic', 'East Timor', 'Ecuador', 'Egypt', 'El Salvador', \n",
    "    'Equatorial Guinea', 'Eritrea', 'Estonia', 'Eswatini', 'Ethiopia', 'Fiji', 'Finland', 'France', 'Gabon', \n",
    "    'Gambia, The', 'Georgia', 'Germany', 'Ghana', 'Greece', 'Grenada', 'Guatemala', 'Guinea', 'Guinea-Bissau', \n",
    "    'Guyana', 'Haiti', 'Honduras', 'Hungary', 'Iceland', 'India', 'Indonesia', 'Iran', 'Iraq', 'Ireland', 'Israel', \n",
    "    'Italy', 'Jamaica', 'Japan', 'Jordan', 'Kazakhstan', 'Kenya', 'Kiribati', 'Korea, North', 'Korea, South', 'Kosovo', \n",
    "    'Kuwait', 'Kyrgyzstan', 'Laos', 'Latvia', 'Lebanon', 'Lesotho', 'Liberia', 'Libya', 'Liechtenstein', 'Lithuania', \n",
    "    'Luxembourg', 'Madagascar', 'Malawi', 'Malaysia', 'Maldives', 'Mali', 'Malta', 'Marshall Islands', 'Mauritania', \n",
    "    'Mauritius', 'Mexico', 'Micronesia, Federated States of', 'Moldova', 'Monaco', 'Mongolia', 'Montenegro', 'Morocco', \n",
    "    'Mozambique', 'Myanmar', 'Namibia', 'Nauru', 'Nepal', 'Netherlands', 'New Zealand', 'Nicaragua', 'Niger', \n",
    "    'Nigeria', 'North Macedonia', 'Norway', 'Oman', 'Pakistan', 'Palau', 'Panama', 'Papua New Guinea', 'Paraguay', \n",
    "    'Peru', 'Philippines', 'Poland', 'Portugal', 'Qatar', 'Romania', 'Russia', 'Rwanda', 'Saint Kitts and Nevis', \n",
    "    'Saint Lucia', 'Saint Vincent and the Grenadines', 'Samoa', 'San Marino', 'Sao Tome and Principe', 'Saudi Arabia', \n",
    "    'Senegal', 'Serbia', 'Seychelles', 'Sierra Leone', 'Singapore', 'Slovakia', 'Slovenia', 'Solomon Islands', 'Somalia', \n",
    "    'South Africa', 'Spain', 'Sri Lanka', 'Sudan', 'Sudan, South', 'Suriname', 'Sweden', 'Switzerland', 'Syria', \n",
    "    'Taiwan', 'Tajikistan', 'Tanzania', 'Thailand', 'Togo', 'Tonga', 'Trinidad and Tobago', 'Tunisia', 'Turkey', \n",
    "    'Turkmenistan', 'Tuvalu', 'Uganda', 'Ukraine', 'United Arab Emirates', 'United Kingdom', 'United States', 'Uruguay', \n",
    "    'Uzbekistan', 'Vanuatu', 'Vatican City', 'Venezuela', 'Vietnam', 'Yemen', 'Zambia', 'Zimbabwe']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Shortest Key Sequence \n",
    "\n",
    "My strategy to find the **shortest key sequence for every item in a menu** is:\n",
    "- Generate all \"sensible\" key sequences in shortest-first order. For each one:\n",
    "  - Determine what menu item is selected by the key sequence. \n",
    "  - If that item has not been assigned a key sequence before, assign it. This is guaranteed to be a shortest possible key sequence for the item, because we're considering the sequences in shortest-first order.\n",
    "- When all menu items have been assigned, we're done; return the assignments of shortest possible key sequences.\n",
    "\n",
    "The function `shortest_keyseqs` implements this strategy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortest_keyseqs(items) -> Dict[Item, Keyseq]:\n",
    "    \"\"\"Compute a dict of {'Item': 'Shortest Keyseq'}, e.g. {'Iceland': 'I', Japan': 'J↓'}.\"\"\"\n",
    "    assigned = {}\n",
    "    for keyseq in all_sensible_keyseqs(items):\n",
    "        item = select_from_menu(keyseq, items)\n",
    "        if item not in assigned:\n",
    "            assigned[item] = keyseq\n",
    "            if len(assigned) == len(items):\n",
    "                return assigned"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A \"sensible\" key sequence consists of zero or more letters constituting a prefix of one of the menu item names, followed by zero or more arrows. \n",
    "\n",
    "It wouldn't make sense to generate a sequence of letters that is not a prefix of an item name, because the non-matching letter(s) wouldn't move the menu's cursor. It also wouldn't make sense to have both an up and a down arrow in a key sequence, because they cancel each other out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def all_sensible_keyseqs(items) -> Iterable[Keyseq]:\n",
    "    \"\"\"All sensible key sequences, in shortest-first order.\n",
    "    (For ties, use fewer arrows first; if still tied, use alphabetical ordering.)\"\"\"\n",
    "    longest = max(map(len, items))\n",
    "    for n in range(longest + 1):    # `n` is total length of key sequence; shortest first\n",
    "        for a in range(n + 1):      # `a` is number of arrows in key sequence; fewer first\n",
    "            keyseqs = {item[:n - a] + a * arrow \n",
    "                       for item in items for arrow in (up, down)}\n",
    "            yield from sorted(keyseqs) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, here are the first 30 sensible key sequences (note that no country starts with `'W'` or `'X'`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'' 'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' 'N' 'O' 'P' 'Q' 'R' 'S' 'T' 'U' 'V' 'Y' 'Z' '↑' '↓' 'Af' 'Al' 'An'\n"
     ]
    }
   ],
   "source": [
    "keyseqs = all_sensible_keyseqs(countries)\n",
    "print(*(repr(next(keyseqs)) for _ in range(30)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only one function remains to be defined: `select_from_menu(keyseq, items)` returns the menu item selected by `keyseq`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def select_from_menu(keyseq, items: List[str]) -> str:\n",
    "    \"\"\"Select a menu item from `items` according to `keyseq`.\"\"\"\n",
    "    letters = keyseq.replace(up, '').replace(down, '') # The keyseq without the arrows\n",
    "    for i, item in enumerate(items):\n",
    "        if item.startswith(letters): \n",
    "            i = i - keyseq.count(up) + keyseq.count(down) # Arrow keys can move cursor `i` up or down,\n",
    "            return items[np.clip(i, 0, len(items) - 1)]   # but not above or below the extent of the menu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving the Problem: You're Up!\n",
    "\n",
    "We are now ready to  find a shortest key sequence for every country:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 24.9 ms, sys: 294 µs, total: 25.2 ms\n",
      "Wall time: 25.1 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'Afghanistan': '',\n",
       " 'Bahamas, The': 'B',\n",
       " 'Cabo Verde': 'C',\n",
       " 'Denmark': 'D',\n",
       " 'East Timor': 'E',\n",
       " 'Fiji': 'F',\n",
       " 'Gabon': 'G',\n",
       " 'Haiti': 'H',\n",
       " 'Iceland': 'I',\n",
       " 'Jamaica': 'J',\n",
       " 'Kazakhstan': 'K',\n",
       " 'Laos': 'L',\n",
       " 'Madagascar': 'M',\n",
       " 'Namibia': 'N',\n",
       " 'Oman': 'O',\n",
       " 'Pakistan': 'P',\n",
       " 'Qatar': 'Q',\n",
       " 'Romania': 'R',\n",
       " 'Saint Kitts and Nevis': 'S',\n",
       " 'Taiwan': 'T',\n",
       " 'Uganda': 'U',\n",
       " 'Vanuatu': 'V',\n",
       " 'Yemen': 'Y',\n",
       " 'Zambia': 'Z',\n",
       " 'Albania': '↓',\n",
       " 'Andorra': 'An',\n",
       " 'Argentina': 'Ar',\n",
       " 'Australia': 'Au',\n",
       " 'Azerbaijan': 'Az',\n",
       " 'Belarus': 'Be',\n",
       " 'Bhutan': 'Bh',\n",
       " 'Bolivia': 'Bo',\n",
       " 'Brazil': 'Br',\n",
       " 'Bulgaria': 'Bu',\n",
       " 'Central African Republic': 'Ce',\n",
       " 'Chad': 'Ch',\n",
       " 'Colombia': 'Co',\n",
       " 'Croatia': 'Cr',\n",
       " 'Cuba': 'Cu',\n",
       " 'Cyprus': 'Cy',\n",
       " 'Czech Republic': 'Cz',\n",
       " 'Djibouti': 'Dj',\n",
       " 'Dominica': 'Do',\n",
       " 'Ecuador': 'Ec',\n",
       " 'Egypt': 'Eg',\n",
       " 'El Salvador': 'El',\n",
       " 'Equatorial Guinea': 'Eq',\n",
       " 'Eritrea': 'Er',\n",
       " 'Estonia': 'Es',\n",
       " 'Ethiopia': 'Et',\n",
       " 'France': 'Fr',\n",
       " 'Georgia': 'Ge',\n",
       " 'Ghana': 'Gh',\n",
       " 'Greece': 'Gr',\n",
       " 'Guatemala': 'Gu',\n",
       " 'Honduras': 'Ho',\n",
       " 'Hungary': 'Hu',\n",
       " 'India': 'In',\n",
       " 'Iran': 'Ir',\n",
       " 'Israel': 'Is',\n",
       " 'Italy': 'It',\n",
       " 'Jordan': 'Jo',\n",
       " 'Kenya': 'Ke',\n",
       " 'Kiribati': 'Ki',\n",
       " 'Korea, North': 'Ko',\n",
       " 'Kuwait': 'Ku',\n",
       " 'Kyrgyzstan': 'Ky',\n",
       " 'Lebanon': 'Le',\n",
       " 'Liberia': 'Li',\n",
       " 'Luxembourg': 'Lu',\n",
       " 'Mexico': 'Me',\n",
       " 'Micronesia, Federated States of': 'Mi',\n",
       " 'Moldova': 'Mo',\n",
       " 'Myanmar': 'My',\n",
       " 'Nepal': 'Ne',\n",
       " 'Nicaragua': 'Ni',\n",
       " 'North Macedonia': 'No',\n",
       " 'Peru': 'Pe',\n",
       " 'Philippines': 'Ph',\n",
       " 'Poland': 'Po',\n",
       " 'Russia': 'Ru',\n",
       " 'Rwanda': 'Rw',\n",
       " 'Senegal': 'Se',\n",
       " 'Sierra Leone': 'Si',\n",
       " 'Slovakia': 'Sl',\n",
       " 'Solomon Islands': 'So',\n",
       " 'Spain': 'Sp',\n",
       " 'Sri Lanka': 'Sr',\n",
       " 'Sudan': 'Su',\n",
       " 'Sweden': 'Sw',\n",
       " 'Syria': 'Sy',\n",
       " 'Thailand': 'Th',\n",
       " 'Togo': 'To',\n",
       " 'Trinidad and Tobago': 'Tr',\n",
       " 'Tunisia': 'Tu',\n",
       " 'Ukraine': 'Uk',\n",
       " 'United Arab Emirates': 'Un',\n",
       " 'Uruguay': 'Ur',\n",
       " 'Uzbekistan': 'Uz',\n",
       " 'Venezuela': 'Ve',\n",
       " 'Vietnam': 'Vi',\n",
       " 'Zimbabwe': 'Zi',\n",
       " 'Bahrain': 'B↓',\n",
       " 'Burundi': 'C↑',\n",
       " 'Cambodia': 'C↓',\n",
       " 'Dominican Republic': 'E↑',\n",
       " 'Finland': 'F↓',\n",
       " 'Gambia, The': 'G↓',\n",
       " 'Guyana': 'H↑',\n",
       " 'Japan': 'J↓',\n",
       " 'Latvia': 'L↓',\n",
       " 'Malawi': 'M↓',\n",
       " 'Nauru': 'N↓',\n",
       " 'Norway': 'O↑',\n",
       " 'Palau': 'P↓',\n",
       " 'Portugal': 'Q↑',\n",
       " 'Saint Lucia': 'S↓',\n",
       " 'Tajikistan': 'T↓',\n",
       " 'Tuvalu': 'U↑',\n",
       " 'Vatican City': 'V↓',\n",
       " 'Algeria': '↓↓',\n",
       " 'Angola': 'Ang',\n",
       " 'Antigua and Barbuda': 'Ant',\n",
       " 'Armenia': 'Arm',\n",
       " 'Bangladesh': 'Ban',\n",
       " 'Barbados': 'Bar',\n",
       " 'Benin': 'Ben',\n",
       " 'Bosnia and Herzegovina': 'Bos',\n",
       " 'Botswana': 'Bot',\n",
       " 'Brunei': 'Bru',\n",
       " 'Burkina Faso': 'Bur',\n",
       " 'Canada': 'Can',\n",
       " 'Chile': 'Chi',\n",
       " 'Comoros': 'Com',\n",
       " 'Congo, Democratic Republic of the': 'Con',\n",
       " 'Costa Rica': 'Cos',\n",
       " \"Cote d'Ivoire\": 'Cot',\n",
       " 'Eswatini': 'Esw',\n",
       " 'Germany': 'Ger',\n",
       " 'Guinea': 'Gui',\n",
       " 'Ireland': 'Ire',\n",
       " 'Kosovo': 'Kos',\n",
       " 'Lesotho': 'Les',\n",
       " 'Liechtenstein': 'Lie',\n",
       " 'Lithuania': 'Lit',\n",
       " 'Marshall Islands': 'Mar',\n",
       " 'Mauritania': 'Mau',\n",
       " 'Monaco': 'Mon',\n",
       " 'Morocco': 'Mor',\n",
       " 'Mozambique': 'Moz',\n",
       " 'Netherlands': 'Net',\n",
       " 'New Zealand': 'New',\n",
       " 'Niger': 'Nig',\n",
       " 'Panama': 'Pan',\n",
       " 'Papua New Guinea': 'Pap',\n",
       " 'Paraguay': 'Par',\n",
       " 'Samoa': 'Sam',\n",
       " 'San Marino': 'San',\n",
       " 'Sao Tome and Principe': 'Sao',\n",
       " 'Saudi Arabia': 'Sau',\n",
       " 'Serbia': 'Ser',\n",
       " 'Seychelles': 'Sey',\n",
       " 'Singapore': 'Sin',\n",
       " 'Somalia': 'Som',\n",
       " 'South Africa': 'Sou',\n",
       " 'Suriname': 'Sur',\n",
       " 'Switzerland': 'Swi',\n",
       " 'Tanzania': 'Tan',\n",
       " 'Tonga': 'Ton',\n",
       " 'Turkey': 'Tur',\n",
       " 'Austria': 'Au↓',\n",
       " 'Belgium': 'Be↓',\n",
       " 'China': 'Co↑',\n",
       " 'Grenada': 'Gr↓',\n",
       " 'Indonesia': 'In↓',\n",
       " 'Iraq': 'Ir↓',\n",
       " 'Korea, South': 'Ko↓',\n",
       " 'Libya': 'Li↓',\n",
       " 'Mauritius': 'Me↑',\n",
       " 'Nigeria': 'No↑',\n",
       " 'Slovenia': 'Sl↓',\n",
       " 'Sudan, South': 'Su↓',\n",
       " 'United Kingdom': 'Un↓',\n",
       " 'United States': 'Ur↑',\n",
       " 'Cameroon': 'C↓↓',\n",
       " 'Guinea-Bissau': 'H↑↑',\n",
       " 'Malaysia': 'M↓↓',\n",
       " 'Saint Vincent and the Grenadines': 'S↓↓',\n",
       " 'Turkmenistan': 'U↑↑',\n",
       " 'Belize': 'Beli',\n",
       " 'Maldives': 'Mald',\n",
       " 'Mali': 'Mali',\n",
       " 'Malta': 'Malt',\n",
       " 'Mongolia': 'Mong',\n",
       " 'Montenegro': 'Mont',\n",
       " 'Congo, Republic of the': 'Con↓'}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time results = shortest_keyseqs(countries)\n",
    "results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Nice!* The results seem sensible, and it only took a couple dozen milliseconds (even though I emphasized clarity over efficiency in the code). There is a surprise: instead of the expected four-character key sequence `'Un↓↓'` for \"United States,\" there is a shorter key sequence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Ur↑'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "results['United States']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The mnemonic \"**you're up**\" may help you remember this.\n",
    "\n",
    "Here is a function to report on the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def report(results):\n",
    "    \"\"\"Report stats on the number of keystrokes needed to select each item.\"\"\"\n",
    "    N       = len(results)\n",
    "    lengths = [len(results[item]) for item in results]\n",
    "    counts  = dict(Counter(lengths))\n",
    "    print(f'{N} items; Lengths: mean={sum(lengths)/N:3.2f}, max={max(lengths)}, counts={counts}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "196 items; Lengths: mean=2.29, max=4, counts={0: 1, 1: 24, 2: 96, 3: 68, 4: 7}\n"
     ]
    }
   ],
   "source": [
    "report(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that the average over the 196 countries is a bit over 2 keystrokes, and that only 7 countries require the maximum of 4 keystrokes.\n",
    "\n",
    "# State Menu\n",
    "\n",
    "To show that the code generalizes to different menus, let's examine US states (and territories):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "states = [\n",
    "    'Alabama', 'Alaska', 'American Samoa', 'Arizona', 'Arkansas', 'California', 'Colorado', 'Connecticut', 'Delaware',\n",
    "    'District of Columbia', 'Federated States of Micronesia', 'Florida', 'Georgia', 'Guam', 'Hawaii', 'Idaho', 'Illinois',\n",
    "    'Indiana', 'Iowa', 'Kansas', 'Kentucky', 'Louisiana', 'Maine', 'Marshall Islands', 'Maryland', 'Massachusetts', \n",
    "    'Michigan', 'Minnesota', 'Mississippi', 'Missouri', 'Montana', 'Nebraska', 'Nevada', 'New Hampshire', 'New Jersey', \n",
    "    'New Mexico', 'New York', 'North Carolina', 'North Dakota', 'Northern Mariana Islands', 'Ohio', 'Oklahoma', 'Oregon', \n",
    "    'Palau', 'Pennsylvania', 'Puerto Rico', 'Rhode Island', 'South Carolina', 'South Dakota', 'Tennessee', 'Texas', 'Utah', \n",
    "    'Vermont', 'Virgin Island', 'Virginia', 'Washington', 'West Virginia', 'Wisconsin', 'Wyoming']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Alabama': '',\n",
       " 'California': 'C',\n",
       " 'Delaware': 'D',\n",
       " 'Federated States of Micronesia': 'F',\n",
       " 'Georgia': 'G',\n",
       " 'Hawaii': 'H',\n",
       " 'Idaho': 'I',\n",
       " 'Kansas': 'K',\n",
       " 'Louisiana': 'L',\n",
       " 'Maine': 'M',\n",
       " 'Nebraska': 'N',\n",
       " 'Ohio': 'O',\n",
       " 'Palau': 'P',\n",
       " 'Rhode Island': 'R',\n",
       " 'South Carolina': 'S',\n",
       " 'Tennessee': 'T',\n",
       " 'Utah': 'U',\n",
       " 'Vermont': 'V',\n",
       " 'Washington': 'W',\n",
       " 'Alaska': '↓',\n",
       " 'American Samoa': 'Am',\n",
       " 'Arizona': 'Ar',\n",
       " 'Colorado': 'Co',\n",
       " 'District of Columbia': 'Di',\n",
       " 'Florida': 'Fl',\n",
       " 'Guam': 'Gu',\n",
       " 'Illinois': 'Il',\n",
       " 'Indiana': 'In',\n",
       " 'Iowa': 'Io',\n",
       " 'Kentucky': 'Ke',\n",
       " 'Michigan': 'Mi',\n",
       " 'Montana': 'Mo',\n",
       " 'North Carolina': 'No',\n",
       " 'Oklahoma': 'Ok',\n",
       " 'Oregon': 'Or',\n",
       " 'Pennsylvania': 'Pe',\n",
       " 'Puerto Rico': 'Pu',\n",
       " 'Virgin Island': 'Vi',\n",
       " 'West Virginia': 'We',\n",
       " 'Wisconsin': 'Wi',\n",
       " 'Wyoming': 'Wy',\n",
       " 'Arkansas': 'C↑',\n",
       " 'Connecticut': 'D↑',\n",
       " 'Marshall Islands': 'M↓',\n",
       " 'Nevada': 'N↓',\n",
       " 'Northern Mariana Islands': 'O↑',\n",
       " 'South Dakota': 'S↓',\n",
       " 'Texas': 'T↓',\n",
       " 'Virginia': 'W↑',\n",
       " 'Massachusetts': 'Mas',\n",
       " 'Minnesota': 'Min',\n",
       " 'Mississippi': 'Mis',\n",
       " 'New Hampshire': 'New',\n",
       " 'Missouri': 'Mo↑',\n",
       " 'New York': 'No↑',\n",
       " 'North Dakota': 'No↓',\n",
       " 'Maryland': 'M↓↓',\n",
       " 'New Jersey': 'New↓',\n",
       " 'New Mexico': 'No↑↑'}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortest_keyseqs(states)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "59 items; Lengths: mean=1.85, max=4, counts={0: 1, 1: 19, 2: 29, 3: 8, 4: 2}\n"
     ]
    }
   ],
   "source": [
    "report(shortest_keyseqs(states))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The average is under two keystrokes, and only two states, New Jersey and New Mexico, require 4 keystrokes (New Hampshire and New York only need 3).\n",
    "\n",
    "# Color Menu\n",
    "\n",
    "One more example: the 140 [Web color names](https://en.wikipedia.org/wiki/Web_colors) recognized by modern browsers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "colors = [\n",
    "    'AliceBlue', 'AntiqueWhite', 'Aqua', 'Aquamarine', 'Azure', 'Beige', 'Bisque', 'Black', 'BlanchedAlmond', 'Blue', 'BlueViolet', \n",
    "    'Brown', 'BurlyWood', 'CadetBlue', 'Chartreuse', 'Chocolate', 'Coral', 'CornflowerBlue', 'Cornsilk', 'Crimson', 'Cyan', \n",
    "    'DarkBlue', 'DarkCyan', 'DarkGoldenRod', 'DarkGrey', 'DarkGreen', 'DarkKhaki', 'DarkMagenta', 'DarkOliveGreen', 'Darkorange', \n",
    "    'DarkOrchid', 'DarkRed', 'DarkSalmon', 'DarkSeaGreen', 'DarkSlateBlue', 'DarkSlateGrey', 'DarkTurquoise', 'DarkViolet', \n",
    "    'DeepPink', 'DeepSkyBlue', 'DimGray', 'DodgerBlue', 'FireBrick', 'FloralWhite', 'ForestGreen', 'Fuchsia', 'Gainsboro', \n",
    "    'GhostWhite', 'Gold', 'GoldenRod', 'Grey', 'Green', 'GreenYellow', 'HoneyDew', 'HotPink', 'IndianRed', 'Indigo', 'Ivory', \n",
    "    'Khaki', 'Lavender', 'LavenderBlush', 'LawnGreen', 'LemonChiffon', 'LightBlue', 'LightCoral', 'LightCyan', 'LightGoldenRodYellow',\n",
    "    'LightGrey', 'LightGreen', 'LightPink', 'LightSalmon', 'LightSeaGreen', 'LightSkyBlue', 'LightSlateGrey', 'LightSteelBlue', \n",
    "    'LightYellow', 'Lime', 'LimeGreen', 'Linen', 'Magenta', 'Maroon', 'MediumAquaMarine', 'MediumBlue', 'MediumOrchid', 'MediumPurple',\n",
    "    'MediumSeaGreen', 'MediumSlateBlue', 'MediumSpringGreen', 'MediumTurquoise', 'MediumVioletRed', 'MidnightBlue', 'MintCream', \n",
    "    'MistyRose', 'Moccasin', 'NavajoWhite', 'Navy', 'OldLace', 'Olive', 'OliveDrab', 'Orange', 'OrangeRed', 'Orchid', 'PaleGoldenRod',\n",
    "    'PaleGreen', 'PaleTurquoise', 'PaleVioletRed', 'PapayaWhip', 'PeachPuff', 'Peru', 'Pink', 'Plum', 'PowderBlue', 'Purple', 'Red', \n",
    "    'RosyBrown', 'RoyalBlue', 'SaddleBrown', 'Salmon', 'SandyBrown', 'SeaGreen', 'SeaShell', 'Sienna', 'Silver', 'SkyBlue', \n",
    "    'SlateBlue', 'SlateGrey', 'Snow', 'SpringGreen', 'SteelBlue', 'Tan', 'Teal', 'Thistle', 'Tomato', 'Turquoise', 'Violet', \n",
    "    'Wheat', 'White', 'WhiteSmoke', 'Yellow', 'YellowGreen']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'AliceBlue': '',\n",
       " 'Beige': 'B',\n",
       " 'CadetBlue': 'C',\n",
       " 'DarkBlue': 'D',\n",
       " 'FireBrick': 'F',\n",
       " 'Gainsboro': 'G',\n",
       " 'HoneyDew': 'H',\n",
       " 'IndianRed': 'I',\n",
       " 'Khaki': 'K',\n",
       " 'Lavender': 'L',\n",
       " 'Magenta': 'M',\n",
       " 'NavajoWhite': 'N',\n",
       " 'OldLace': 'O',\n",
       " 'PaleGoldenRod': 'P',\n",
       " 'Red': 'R',\n",
       " 'SaddleBrown': 'S',\n",
       " 'Tan': 'T',\n",
       " 'Violet': 'V',\n",
       " 'Wheat': 'W',\n",
       " 'Yellow': 'Y',\n",
       " 'AntiqueWhite': '↓',\n",
       " 'Aqua': 'Aq',\n",
       " 'Azure': 'Az',\n",
       " 'Bisque': 'Bi',\n",
       " 'Black': 'Bl',\n",
       " 'Brown': 'Br',\n",
       " 'BurlyWood': 'Bu',\n",
       " 'Chartreuse': 'Ch',\n",
       " 'Coral': 'Co',\n",
       " 'Crimson': 'Cr',\n",
       " 'Cyan': 'Cy',\n",
       " 'DeepPink': 'De',\n",
       " 'DimGray': 'Di',\n",
       " 'DodgerBlue': 'Do',\n",
       " 'FloralWhite': 'Fl',\n",
       " 'ForestGreen': 'Fo',\n",
       " 'Fuchsia': 'Fu',\n",
       " 'GhostWhite': 'Gh',\n",
       " 'Gold': 'Go',\n",
       " 'Grey': 'Gr',\n",
       " 'Ivory': 'Iv',\n",
       " 'LemonChiffon': 'Le',\n",
       " 'LightBlue': 'Li',\n",
       " 'MediumAquaMarine': 'Me',\n",
       " 'MidnightBlue': 'Mi',\n",
       " 'Moccasin': 'Mo',\n",
       " 'Orange': 'Or',\n",
       " 'PeachPuff': 'Pe',\n",
       " 'Pink': 'Pi',\n",
       " 'Plum': 'Pl',\n",
       " 'PowderBlue': 'Po',\n",
       " 'Purple': 'Pu',\n",
       " 'RosyBrown': 'Ro',\n",
       " 'SeaGreen': 'Se',\n",
       " 'Sienna': 'Si',\n",
       " 'SkyBlue': 'Sk',\n",
       " 'SlateBlue': 'Sl',\n",
       " 'Snow': 'Sn',\n",
       " 'SpringGreen': 'Sp',\n",
       " 'SteelBlue': 'St',\n",
       " 'Teal': 'Te',\n",
       " 'Thistle': 'Th',\n",
       " 'Tomato': 'To',\n",
       " 'Turquoise': 'Tu',\n",
       " 'DarkCyan': 'D↓',\n",
       " 'GreenYellow': 'H↑',\n",
       " 'HotPink': 'H↓',\n",
       " 'Indigo': 'I↓',\n",
       " 'LavenderBlush': 'L↓',\n",
       " 'Linen': 'M↑',\n",
       " 'Maroon': 'M↓',\n",
       " 'Navy': 'N↓',\n",
       " 'Olive': 'O↓',\n",
       " 'Orchid': 'P↑',\n",
       " 'PaleGreen': 'P↓',\n",
       " 'RoyalBlue': 'S↑',\n",
       " 'Salmon': 'S↓',\n",
       " 'White': 'W↓',\n",
       " 'WhiteSmoke': 'Y↑',\n",
       " 'YellowGreen': 'Y↓',\n",
       " 'Blue': 'Blu',\n",
       " 'Chocolate': 'Cho',\n",
       " 'LawnGreen': 'Law',\n",
       " 'Lime': 'Lim',\n",
       " 'MintCream': 'Min',\n",
       " 'MistyRose': 'Mis',\n",
       " 'PapayaWhip': 'Pap',\n",
       " 'Peru': 'Per',\n",
       " 'SandyBrown': 'San',\n",
       " 'Silver': 'Sil',\n",
       " 'Aquamarine': 'Aq↓',\n",
       " 'BlanchedAlmond': 'Bl↓',\n",
       " 'BlueViolet': 'Br↑',\n",
       " 'CornflowerBlue': 'Co↓',\n",
       " 'Cornsilk': 'Cr↑',\n",
       " 'DarkViolet': 'De↑',\n",
       " 'DeepSkyBlue': 'De↓',\n",
       " 'GoldenRod': 'Go↓',\n",
       " 'Green': 'Gr↓',\n",
       " 'LightCoral': 'Li↓',\n",
       " 'MediumBlue': 'Me↓',\n",
       " 'MediumVioletRed': 'Mi↑',\n",
       " 'OliveDrab': 'Or↑',\n",
       " 'OrangeRed': 'Or↓',\n",
       " 'SeaShell': 'Se↓',\n",
       " 'SlateGrey': 'Sl↓',\n",
       " 'DarkGoldenRod': 'D↓↓',\n",
       " 'LimeGreen': 'M↑↑',\n",
       " 'PaleTurquoise': 'P↓↓',\n",
       " 'LightYellow': 'Lim↑',\n",
       " 'PaleVioletRed': 'Pap↑',\n",
       " 'DarkTurquoise': 'De↑↑',\n",
       " 'LightCyan': 'Li↓↓',\n",
       " 'MediumOrchid': 'Me↓↓',\n",
       " 'MediumTurquoise': 'Mi↑↑',\n",
       " 'DarkGrey': 'D↓↓↓',\n",
       " 'DarkKhaki': 'DarkK',\n",
       " 'DarkMagenta': 'DarkM',\n",
       " 'DarkOliveGreen': 'DarkO',\n",
       " 'DarkRed': 'DarkR',\n",
       " 'DarkSalmon': 'DarkS',\n",
       " 'Darkorange': 'Darko',\n",
       " 'LightSteelBlue': 'Lim↑↑',\n",
       " 'DarkSlateGrey': 'De↑↑↑',\n",
       " 'LightGoldenRodYellow': 'Li↓↓↓',\n",
       " 'MediumPurple': 'Me↓↓↓',\n",
       " 'MediumSpringGreen': 'Mi↑↑↑',\n",
       " 'DarkGreen': 'D↓↓↓↓',\n",
       " 'DarkOrchid': 'DarkOr',\n",
       " 'DarkSeaGreen': 'DarkSe',\n",
       " 'DarkSlateBlue': 'DarkSl',\n",
       " 'LightPink': 'LightP',\n",
       " 'LightSalmon': 'LightS',\n",
       " 'LightSlateGrey': 'Lim↑↑↑',\n",
       " 'LightGrey': 'Li↓↓↓↓',\n",
       " 'MediumSeaGreen': 'Me↓↓↓↓',\n",
       " 'MediumSlateBlue': 'Mi↑↑↑↑',\n",
       " 'LightSeaGreen': 'LightSe',\n",
       " 'LightSkyBlue': 'LightSk',\n",
       " 'LightGreen': 'LightP↑'}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortest_keyseqs(colors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "140 items; Lengths: mean=2.77, max=7, counts={0: 1, 1: 20, 2: 59, 3: 29, 4: 7, 5: 12, 6: 9, 7: 3}\n"
     ]
    }
   ],
   "source": [
    "report(shortest_keyseqs(colors))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This time the average length is close to 3 letters. There are 12 color names that require 6 or 7 keystrokes, and another 12 that require 5 keystrokes. The difficulty is the large number of color names that start with the prefix \"Light\", \"Medium\", or \"Dark\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Light': 13, 'Medium': 9, 'Dark': 17}"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{shade: sum(name.startswith(shade) for name in colors) \n",
    " for shade in (\"Light\", \"Medium\", \"Dark\")}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}