Created
September 30, 2015 21:33
-
-
Save tdierks/7a80d8862ea03eb10b9d to your computer and use it in GitHub Desktop.
Revisions
-
tdierks created this gist
Sep 30, 2015 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1 @@ {"nbformat_minor": 0, "cells": [{"source": "Solution for http://wordplay.blogs.nytimes.com/2015/09/28/chartier-2/", "cell_type": "markdown", "metadata": {}}, {"execution_count": 53, "cell_type": "code", "source": "# for each value, the set pixels top-to-bottom; left, then right; space = empty, non-space = set\nlayout_strs = [\n [ \"xxxxx\", \"xxxxx\" ],\n [ \" x x\", \" x\" ],\n [ \"x xxx\", \"xxx x\" ],\n [ \"x x x\", \"xxxxx\" ],\n [ \"xxx \", \"xxxxx\" ],\n [ \"xxx x\", \"x xxx\" ],\n [ \"xxxxx\", \"x xxx\" ],\n [ \"xx \", \"xxxxx\" ],\n [ \"xxxxx\", \"xxxxx\" ],\n [ \"xxx x\", \"xxxxx\" ],\n]\ndef str_to_mask(s):\n return sum(map(lambda _: _[0] != \" \" and 1 << _[1] or 0, zip(s, range(len(s)))))\nlayout_masks = [[str_to_mask(s) for s in mask_strs] for mask_strs in layout_strs]", "outputs": [], "metadata": {"collapsed": false, "trusted": true}}, {"execution_count": 54, "cell_type": "code", "source": "def set_bits(v):\n n = 0\n i_mask = 1\n while v:\n if v & i_mask:\n n += 1\n v = v ^ i_mask\n i_mask = i_mask << 1\n return n\nbit_count = [set_bits(i) for i in range(32)]", "outputs": [], "metadata": {"collapsed": true, "trusted": true}}, {"execution_count": 55, "cell_type": "code", "source": "def score(order):\n total = 0\n # is left-side indices\n for n in range(len(order)-1):\n overlap = bit_count[layout_masks[order[n]][1] & layout_masks[order[n+1]][0]]\n total += overlap*(order[n]+order[n+1])\n return total", "outputs": [], "metadata": {"collapsed": false, "trusted": true}}, {"execution_count": 56, "cell_type": "code", "source": "def test_score(str_order, expected_value):\n s = score(map(int, str_order))\n print(\"score for '{}' is {}; should be {}: {}\".format(\n str_order, s, expected_value,\n s == expected_value and \"OK\" or \"FAIL\"))\ntest_score(\"0123456789\", 277)\ntest_score(\"1357902468\", 289)", "outputs": [{"output_type": "stream", "name": "stdout", "text": "score for '0123456789' is 277; should be 277: OK\nscore for '1357902468' is 289; should be 289: OK\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"execution_count": 59, "cell_type": "code", "source": "from itertools import permutations\n\nmax_p = (-1, None)\nmin_p = (500, None)\nfor p in permutations(range(10)):\n p_score = score(p)\n if p_score == max_p[0]:\n max_p[1].append(p)\n elif p_score > max_p[0]:\n max_p = (p_score, [p])\n if p_score == min_p[0]:\n min_p[1].append(p)\n elif p_score < min_p[0]:\n min_p = (p_score, [p])", "outputs": [], "metadata": {"collapsed": true, "trusted": true}}, {"execution_count": 69, "cell_type": "code", "source": "def format_ps(p_tuple):\n return \"{} {}\".format(\n p_tuple[0],\n \", \".join(map(lambda _: \"'{}'\".format(_),\n [\"\".join(map(str, p)) for p in p_tuple[1]])))\nprint \"Max: {}\".format(format_ps(max_p))\nprint \"Min: {}\".format(format_ps(min_p))", "outputs": [{"output_type": "stream", "name": "stdout", "text": "Max: 352 '0753498621'\nMin: 181 '8305426719'\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"collapsed": true, "trusted": true}}], "nbformat": 4, "metadata": {"kernelspec": {"display_name": "Python 2", "name": "python2", "language": "python"}, "language_info": {"mimetype": "text/x-python", "nbconvert_exporter": "python", "version": "2.7.9", "name": "python", "file_extension": ".py", "pygments_lexer": "ipython2", "codemirror_mode": {"version": 2, "name": "ipython"}}}}