Skip to content

Instantly share code, notes, and snippets.

@kylekyle

kylekyle/Key Pad Generator.ipynb

Created April 23, 2019 18:25
Show Gist options
  • Save kylekyle/f9768256d94b03d396cf5f997915c54b to your computer and use it in GitHub Desktop.
Save kylekyle/f9768256d94b03d396cf5f997915c54b to your computer and use it in GitHub Desktop.
Download ZIP
Use simulated annealing to generate a random keypad
Display the source blob
Display the rendered blob
Raw
Key Pad Generator.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Key Pad Generator\n",
"\n",
"This notebook uses the [simulated annealing](http://aimacode.github.io/aima-javascript/4-Beyond-Classical-Search/) to assign numbers to a number pad such that each button is equally likely to used to input a 6-character words. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6-character words or phrases\n",
"\n",
"First, we need a list of 6-character words or phrases to analyze. "
]
},
{
"cell_type": "code",
"execution_count": 95,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>0</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>aahing</td>\n",
" </tr>\n",
" <tr>\n",
" <th>7</th>\n",
" <td>aaliis</td>\n",
" </tr>\n",
" <tr>\n",
" <th>14</th>\n",
" <td>aarrgh</td>\n",
" </tr>\n",
" <tr>\n",
" <th>22</th>\n",
" <td>abacas</td>\n",
" </tr>\n",
" <tr>\n",
" <th>26</th>\n",
" <td>abacus</td>\n",
" </tr>\n",
" <tr>\n",
" <th>30</th>\n",
" <td>abakas</td>\n",
" </tr>\n",
" <tr>\n",
" <th>36</th>\n",
" <td>abamps</td>\n",
" </tr>\n",
" <tr>\n",
" <th>48</th>\n",
" <td>abased</td>\n",
" </tr>\n",
" <tr>\n",
" <th>52</th>\n",
" <td>abaser</td>\n",
" </tr>\n",
" <tr>\n",
" <th>54</th>\n",
" <td>abases</td>\n",
" </tr>\n",
" <tr>\n",
" <th>61</th>\n",
" <td>abasia</td>\n",
" </tr>\n",
" <tr>\n",
" <th>66</th>\n",
" <td>abated</td>\n",
" </tr>\n",
" <tr>\n",
" <th>69</th>\n",
" <td>abater</td>\n",
" </tr>\n",
" <tr>\n",
" <th>71</th>\n",
" <td>abates</td>\n",
" </tr>\n",
" <tr>\n",
" <th>73</th>\n",
" <td>abatis</td>\n",
" </tr>\n",
" <tr>\n",
" <th>75</th>\n",
" <td>abator</td>\n",
" </tr>\n",
" <tr>\n",
" <th>85</th>\n",
" <td>abbacy</td>\n",
" </tr>\n",
" <tr>\n",
" <th>90</th>\n",
" <td>abbess</td>\n",
" </tr>\n",
" <tr>\n",
" <th>93</th>\n",
" <td>abbeys</td>\n",
" </tr>\n",
" <tr>\n",
" <th>97</th>\n",
" <td>abbots</td>\n",
" </tr>\n",
" <tr>\n",
" <th>120</th>\n",
" <td>abduce</td>\n",
" </tr>\n",
" <tr>\n",
" <th>127</th>\n",
" <td>abduct</td>\n",
" </tr>\n",
" <tr>\n",
" <th>143</th>\n",
" <td>abeles</td>\n",
" </tr>\n",
" <tr>\n",
" <th>144</th>\n",
" <td>abelia</td>\n",
" </tr>\n",
" <tr>\n",
" <th>191</th>\n",
" <td>abhors</td>\n",
" </tr>\n",
" <tr>\n",
" <th>195</th>\n",
" <td>abided</td>\n",
" </tr>\n",
" <tr>\n",
" <th>196</th>\n",
" <td>abider</td>\n",
" </tr>\n",
" <tr>\n",
" <th>198</th>\n",
" <td>abides</td>\n",
" </tr>\n",
" <tr>\n",
" <th>216</th>\n",
" <td>abject</td>\n",
" </tr>\n",
" <tr>\n",
" <th>224</th>\n",
" <td>abjure</td>\n",
" </tr>\n",
" <tr>\n",
" <th>...</th>\n",
" <td>...</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173292</th>\n",
" <td>zizith</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173293</th>\n",
" <td>zizzle</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173301</th>\n",
" <td>zlotys</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173305</th>\n",
" <td>zoaria</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173309</th>\n",
" <td>zodiac</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173316</th>\n",
" <td>zoecia</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173318</th>\n",
" <td>zoftig</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173323</th>\n",
" <td>zombie</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173334</th>\n",
" <td>zombis</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173337</th>\n",
" <td>zonary</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173338</th>\n",
" <td>zonate</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173346</th>\n",
" <td>zoners</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173350</th>\n",
" <td>zoning</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173352</th>\n",
" <td>zonked</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173355</th>\n",
" <td>zonula</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173359</th>\n",
" <td>zonule</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173383</th>\n",
" <td>zooids</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173401</th>\n",
" <td>zoomed</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173410</th>\n",
" <td>zoonal</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173462</th>\n",
" <td>zorils</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173464</th>\n",
" <td>zoster</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173466</th>\n",
" <td>zouave</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173468</th>\n",
" <td>zounds</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173470</th>\n",
" <td>zoysia</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173481</th>\n",
" <td>zydeco</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173487</th>\n",
" <td>zygoid</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173488</th>\n",
" <td>zygoma</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173495</th>\n",
" <td>zygose</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173502</th>\n",
" <td>zygote</td>\n",
" </tr>\n",
" <tr>\n",
" <th>173507</th>\n",
" <td>zymase</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"<p>15290 rows × 1 columns</p>\n",
"</div>"
],
"text/plain": [
" 0\n",
"3 aahing\n",
"7 aaliis\n",
"14 aarrgh\n",
"22 abacas\n",
"26 abacus\n",
"30 abakas\n",
"36 abamps\n",
"48 abased\n",
"52 abaser\n",
"54 abases\n",
"61 abasia\n",
"66 abated\n",
"69 abater\n",
"71 abates\n",
"73 abatis\n",
"75 abator\n",
"85 abbacy\n",
"90 abbess\n",
"93 abbeys\n",
"97 abbots\n",
"120 abduce\n",
"127 abduct\n",
"143 abeles\n",
"144 abelia\n",
"191 abhors\n",
"195 abided\n",
"196 abider\n",
"198 abides\n",
"216 abject\n",
"224 abjure\n",
"... ...\n",
"173292 zizith\n",
"173293 zizzle\n",
"173301 zlotys\n",
"173305 zoaria\n",
"173309 zodiac\n",
"173316 zoecia\n",
"173318 zoftig\n",
"173323 zombie\n",
"173334 zombis\n",
"173337 zonary\n",
"173338 zonate\n",
"173346 zoners\n",
"173350 zoning\n",
"173352 zonked\n",
"173355 zonula\n",
"173359 zonule\n",
"173383 zooids\n",
"173401 zoomed\n",
"173410 zoonal\n",
"173462 zorils\n",
"173464 zoster\n",
"173466 zouave\n",
"173468 zounds\n",
"173470 zoysia\n",
"173481 zydeco\n",
"173487 zygoid\n",
"173488 zygoma\n",
"173495 zygose\n",
"173502 zygote\n",
"173507 zymase\n",
"\n",
"[15290 rows x 1 columns]"
]
},
"execution_count": 95,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import random\n",
"import numpy as np\n",
"import pandas as pd\n",
"\n",
"from text import words\n",
"from utils import open_data\n",
"\n",
"text = open_data(\"EN-text/wordlist.txt\").read()\n",
"df = pd.DataFrame(words(text)).drop_duplicates()\n",
"\n",
"six = df[df[0].str.len() == 6]\n",
"three = df[df[0].str.len() == 3]\n",
"\n",
"six"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Frequencies\n",
"\n",
"Now, let's compute the frequency of each character. "
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'a': 0.08193808589492042,\n",
" 'h': 0.02538696315674733,\n",
" 'i': 0.06538042293437978,\n",
" 'n': 0.053466317854807065,\n",
" 'g': 0.028024852844996728,\n",
" 'l': 0.05497056899934598,\n",
" 's': 0.09110529758011772,\n",
" 'r': 0.07317418792238936,\n",
" 'b': 0.02381730978853281,\n",
" 'c': 0.034238064094179205,\n",
" 'u': 0.03844560715064312,\n",
" 'k': 0.015053411816001745,\n",
" 'm': 0.029398299542184436,\n",
" 'p': 0.029649008066274254,\n",
" 'e': 0.12427512535426205,\n",
" 'd': 0.04551994767822106,\n",
" 't': 0.053204708960104645,\n",
" 'o': 0.05989753651624155,\n",
" 'y': 0.021506431218661436,\n",
" 'j': 0.0032483104425550468,\n",
" 'z': 0.005144974929147591,\n",
" 'v': 0.010028340963592761,\n",
" 'w': 0.012393721386527142,\n",
" 'q': 0.0017658600392413343,\n",
" 'x': 0.0035317200784826686,\n",
" 'f': 0.015434924787442773}"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"freqs = {}\n",
"\n",
"for word in six[0]:\n",
" for char in word:\n",
" if char not in freqs:\n",
" freqs[char] = 0\n",
" freqs[char] += 1\n",
"\n",
"total = sum(freqs.values())\n",
"\n",
"for letter in freqs:\n",
" freqs[letter] = freqs[letter] / total\n",
"\n",
"freqs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Search Problem\n",
"\n",
"We'll articulate this problem as an [AIMA search problem](https://github.com/aimacode):"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"import copy\n",
"from search import *\n",
"\n",
"class NumberPad(Problem):\n",
" # we need distances for computing the cost of a state\n",
" # and locations for displaying the map\n",
" def __init__(self, initial, freqs):\n",
" self.freqs = freqs\n",
" Problem.__init__(self, initial)\n",
" \n",
" def swap(self,state):\n",
" next_state = copy.deepcopy(state) \n",
" b1,b2 = random.sample(next_state,2)\n",
" l1,l2 = random.choice(b1), random.choice(b2)\n",
" b1.remove(l1); b2.remove(l2)\n",
" b1.append(l2); b2.append(l1)\n",
" b1.sort(); b2.sort()\n",
" return next_state\n",
" \n",
" def actions(self, state):\n",
" return [self.swap]\n",
" \n",
" def result(self, state, action):\n",
" return action(state)\n",
"\n",
" def value(self, state):\n",
" sums = []\n",
" for button in state:\n",
" sums.append(sum([self.freqs[letter] for letter in button]))\n",
" return -np.array(sums).var()\n",
"\n",
" def display(self,state):\n",
" for j in range(3):\n",
" for i in range(j*3,j*3+3):\n",
" print(str(i+1).center(5),end=\"\")\n",
" print()\n",
" for i in range(j*3,j*3+3):\n",
" print(''.join(state[i]).center(5),end=\"\")\n",
" print()\n",
" print(\"0\".center(15))\n",
" print(''.join(state[9]).center(15))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Initial Solution\n",
"\n",
"We'll generate a random number pad as an initial solution to the problem:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1 2 3 \n",
" jmn hcp zde \n",
" 4 5 6 \n",
" lvr wtu yqs \n",
" 7 8 9 \n",
" af ib kg \n",
" 0 \n",
" ox \n"
]
}
],
"source": [
"letters = list(\"abcdefghijklmnopqrstuvwxyz\")\n",
"split = np.array_split(random.sample(letters, len(letters)),10)\n",
"initial = list(map(lambda x: x.tolist(), split))\n",
"\n",
"NumberPad.display(None,initial)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Anneal\n",
"\n",
"Now we can instantiate our problem and solve it using simulated annealing. We're looking to minimize the variance between the sum of letter frequencies between buttons."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"pad = NumberPad(initial, freqs)\n",
"schedule = exp_schedule(k=100, lam=0.03, limit=1500)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Every time step we will randomly swap to characters between buttons. If the swap decreases the variance between buttons, we'll accept the swap. If it doesn't, then with some probability we'll still accept the swap. That probability is based on the `temperature` parameter, which is always decreasing. The lower the temperature, the less likely we are to accept the swap. \n",
"\n",
"Here is an animation showing the swaps and the overall variance as the algorithm runs:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import time\n",
"from IPython import display\n",
"import matplotlib.pyplot as plt\n",
"\n",
"# returns all intermediate states\n",
"results = simulated_annealing_full(pad,schedule)\n",
"\n",
"for i in range(0,len(results)):\n",
" if results[i] != results[i-1]:\n",
" pad.display(results[i])\n",
" print(\"\\nStep:\",i)\n",
" print(\"Variance:\",round(-pad.value(results[i]),8))\n",
" display.clear_output(wait=True)\n",
" plt.show()\n",
" time.sleep(0.15)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can skip the animation and go straight to a solution:"
]
},
{
"cell_type": "code",
"execution_count": 154,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1 2 3 \n",
" jsz rxy how \n",
" 4 5 6 \n",
" kpt bdg cnv \n",
" 7 8 9 \n",
" eq af lu \n",
" 0 \n",
" im \n",
"\n",
"Variance: 7.81e-05\n"
]
}
],
"source": [
"result = simulated_annealing(pad,schedule)\n",
"pad.display(result)\n",
"print(\"\\nVariance:\",round(-pad.value(result),8))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Choose a six character word\n",
"\n",
"Assuming you are using the following pad:"
]
},
{
"cell_type": "code",
"execution_count": 155,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1 2 3 \n",
" ejq ctv how \n",
" 4 5 6 \n",
" sxz fgn dmy \n",
" 7 8 9 \n",
" ip lu br \n",
" 0 \n",
" ak \n",
"\n",
"Variance: 9.781e-05\n"
]
}
],
"source": [
"result = [\n",
" ['e', 'j', 'q'], ['c', 't', 'v'], ['h', 'o', 'w'], \n",
" ['s', 'x', 'z'], ['f', 'g', 'n'], ['d', 'm', 'y'], \n",
" ['i', 'p'], ['l', 'u'], ['b', 'r'], ['a', 'k']\n",
"]\n",
"\n",
"pad.display(result)\n",
"print(\"\\nVariance:\",round(-pad.value(result),8))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we can choose a 6-letter word or phrase and look up the corresponding digits. First, we'll build a lookup table:"
]
},
{
"cell_type": "code",
"execution_count": 156,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'e': 1,\n",
" 'j': 1,\n",
" 'q': 1,\n",
" 'c': 2,\n",
" 't': 2,\n",
" 'v': 2,\n",
" 'h': 3,\n",
" 'o': 3,\n",
" 'w': 3,\n",
" 's': 4,\n",
" 'x': 4,\n",
" 'z': 4,\n",
" 'f': 5,\n",
" 'g': 5,\n",
" 'n': 5,\n",
" 'd': 6,\n",
" 'm': 6,\n",
" 'y': 6,\n",
" 'i': 7,\n",
" 'p': 7,\n",
" 'l': 8,\n",
" 'u': 8,\n",
" 'b': 9,\n",
" 'r': 9,\n",
" 'a': 0,\n",
" 'k': 0}"
]
},
"execution_count": 156,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lookup = {}\n",
"\n",
"for i in range(10):\n",
" for letter in result[i]:\n",
" lookup[letter] = (i+1)%10\n",
"\n",
"lookup"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now choose a word and lookup its digits:"
]
},
{
"cell_type": "code",
"execution_count": 157,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Word: vacuum\n",
"Digits: 202886\n"
]
}
],
"source": [
"word = random.choice(six[0].values)\n",
"\n",
"print(\"Word:\",word)\n",
"print(\"Digits:\",''.join([str(lookup[letter]) for letter in word]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can do the same thing for sets of 3-character words:"
]
},
{
"cell_type": "code",
"execution_count": 158,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Words: dam elm\n",
"Digits: 606186\n"
]
}
],
"source": [
"words = random.sample(list(three[0].values),2)\n",
"\n",
"print(\"Words:\",' '.join(words))\n",
"print(\"Digits:\",''.join([str(lookup[letter]) for letter in ''.join(words)]))"
]
}
],
"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.6.8"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment