touching-puzzle.ipynb

{"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"}}}}