Skip to content

Instantly share code, notes, and snippets.

@rossant

rossant/ruzzle

Created February 21, 2013 00:32
Show Gist options
  • Save rossant/5000970 to your computer and use it in GitHub Desktop.
Save rossant/5000970 to your computer and use it in GitHub Desktop.
Download ZIP
Playing with Ruzzle in Python
Raw
ruzzle
{
"metadata": {
"name": "ruzzle"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "code",
"collapsed": false,
"input": [
"# http://fr.wikipedia.org/wiki/Fr%C3%A9quence_d'apparition_des_lettres_en_fran%C3%A7ais\n",
"def get_frequencies():\n",
" return loadtxt('letters.txt', dtype=str), loadtxt('frequencies.txt')"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# http://www.pallier.org/ressources/dicofr/dicofr.html\n",
"def get_dictionary():\n",
" dictionary = loadtxt('dictionary.txt', dtype=str)\n",
" return dictionary\n",
"dictionary = get_dictionary()\n",
"dictionary_count = len(dictionary)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def get_word(positions):\n",
" return ''.join([g.grid[(i, j)] for (i, j) in positions])"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 3
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# http://stackoverflow.com/questions/11015320/how-to-create-a-trie-in-python\n",
"_end = '_end_'\n",
"def make_trie(*words):\n",
" root = dict()\n",
" for word in words:\n",
" current_dict = root\n",
" for letter in word:\n",
" current_dict = current_dict.setdefault(letter, {})\n",
" current_dict = current_dict.setdefault(_end, _end)\n",
" return root\n",
"\n",
"def in_trie(trie, word):\n",
" current_dict = trie\n",
" for letter in word:\n",
" if letter in current_dict:\n",
" current_dict = current_dict[letter]\n",
" else:\n",
" return False\n",
" else:\n",
" if _end in current_dict:\n",
" return True\n",
" else:\n",
" return False\n",
"\n",
"def prefix_in_trie(trie, word):\n",
" current_dict = trie\n",
" for letter in word:\n",
" if letter in current_dict:\n",
" current_dict = current_dict[letter]\n",
" else:\n",
" return False\n",
" return True"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 4
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"trie = make_trie(*dictionary)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 5
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"neighbors = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]\n",
"def explore(positions, words):\n",
" # process current word\n",
" word = get_word(positions)\n",
" if len(word) >= 2 and in_trie(trie, word) and word not in words:\n",
" #if len(word) >= 2 and word in dictionary and word not in words:\n",
" words.append(word)\n",
" # stop if this path is condamned, i.e. no more word possible\n",
" if not prefix_in_trie(trie, word):\n",
" return\n",
" # go through all neighbors of the last position\n",
" pos = positions[-1]\n",
" for neighbor in neighbors:\n",
" npos = (pos[0] + neighbor[0], pos[1] + neighbor[1])\n",
" # check if the neighbor is admissible\n",
" if npos[0] >= 0 and npos[0] < g.rows and npos[1] >= 0 and npos[1] < g.columns:\n",
" if npos not in positions:\n",
" npositions = positions + [npos]\n",
" # explore the new path\n",
" explore(npositions, words)\n",
" \n",
"def find_words(grid):\n",
" words = []\n",
" for row in xrange(grid.rows):\n",
" for column in xrange(grid.columns):\n",
" explore([(row, column)], words)\n",
" words = sorted(words, cmp=lambda k,v: len(k)-len(v))[::-1]\n",
" return words"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 6
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"class Grid(object):\n",
" def __init__(self, rows, columns):\n",
" self.rows = rows\n",
" self.columns = columns\n",
" self.count = self.rows * self.columns\n",
" self.letters, self.frequencies = get_frequencies()\n",
" self.frequencies_cum = cumsum(self.frequencies)\n",
" dig = digitize(rand(self.count), self.frequencies_cum)\n",
" self.grid = self.letters[dig].reshape((self.rows, self.columns))\n",
" \n",
" def _repr_html_(self):\n",
" style_td = \"\"\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \"\"\"\n",
" html = '<table>\\n'\n",
" for row in xrange(self.rows):\n",
" html += '<tr>\\n'\n",
" for column in xrange(self.columns):\n",
" html += '<td style=\"{0:s}\">{1:s}</td>\\n'.format(\n",
" style_td, self.grid[row, column])\n",
" html += '</tr>\\n'\n",
" html += '</table>'\n",
" return html"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 7
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"g = Grid(4, 4)\n",
"g"
],
"language": "python",
"metadata": {},
"outputs": [
{
"html": [
"<table>\n",
"<tr>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">e</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">u</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">q</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">e</td>\n",
"</tr>\n",
"<tr>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">e</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">r</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">e</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">v</td>\n",
"</tr>\n",
"<tr>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">e</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">e</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">p</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">l</td>\n",
"</tr>\n",
"<tr>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">s</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">a</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">a</td>\n",
"<td style=\"\n",
" width: 50px;\n",
" height: 50px;\n",
" font-size: 24pt;\n",
" text-align: center;\n",
" vertical-align: middle;\n",
" text-transform: uppercase;\n",
" font-weight: bold;\n",
" background: #eee;\n",
" \">e</td>\n",
"</tr>\n",
"</table>"
],
"output_type": "pyout",
"prompt_number": 8,
"text": [
"<__main__.Grid at 0x3ffcdf0>"
]
}
],
"prompt_number": 8
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"words = find_words(g)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 9
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print len(words)\n",
"print words"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"112\n",
"['apeurees', 'pleurees', 'epeurees', 'epalees', 'apeures', 'apeuree', 'sapeque', 'pleures', 'pleuree', 'epeures', 'epeuree', 'apeure', 'aerees', 'sepale', 'sapeur', 'lapees', 'lepres', 'pelees', 'palees', 'paleur', 'pleure', 'epelee', 'epeler', 'epeure', 'epalee', 'epaler', 'vepres', 'eveque', 'eleve', 'alpes', 'apres', 'aeres', 'aeree', 'serpe', 'saper', 'sapee', 'lapas', 'lapes', 'laper', 'lapee', 'lepre', 'prele', 'pelee', 'peler', 'peser', 'pesee', 'peres', 'palee', 'pleur', 'epele', 'epela', 'epees', 'epale', 'ruees', 'reale', 'repas', 'urees', 'alpe', 'apre', 'aere', 'sape', 'sapa', 'lapa', 'lape', 'leur', 'leve', 'pres', 'peur', 'pela', 'pele', 'pese', 'pesa', 'pere', 'pale', 'vela', 'vele', 'epee', 'ruee', 'reel', 'real', 'reas', 'rees', 'reve', 'quel', 'ures', 'uree', 'eres', 'ale', 'sep', 'leu', 'lev', 'pas', 'pre', 'peu', 'pal', 'ver', 'rue', 'rea', 'ree', 'que', 'ure', 'ere', 'eue', 'as', 'se', 'sa', 'la', 'le', 'es', 'ru', 're', 'eu']\n"
]
}
],
"prompt_number": 10
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment