04-08-amidakuji/amidakuji-solution-1.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 27,
   6    "metadata": {
   7     "collapsed": true
   8    },
   9    "outputs": [],
  10    "source": [
  11     "import collections\n",
  12     "import string\n",
  13     "import itertools\n",
  14     "import re"
  15    ]
  16   },
  17   {
  18    "cell_type": "code",
  19    "execution_count": 28,
  20    "metadata": {
  21     "collapsed": true
  22    },
  23    "outputs": [],
  24    "source": [
  25     "Link = collections.namedtuple('Link', 'height left right')"
  26    ]
  27   },
  28   {
  29    "cell_type": "code",
  30    "execution_count": 29,
  31    "metadata": {
  32     "collapsed": true
  33    },
  34    "outputs": [],
  35    "source": [
  36     "def extract_pairs(net_string):\n",
  37     "    return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
  38    ]
  39   },
  40   {
  41    "cell_type": "code",
  42    "execution_count": 30,
  43    "metadata": {
  44     "collapsed": true
  45    },
  46    "outputs": [],
  47    "source": [
  48     "def read_net_string(net_string):\n",
  49     "    return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
  50    ]
  51   },
  52   {
  53    "cell_type": "code",
  54    "execution_count": 31,
  55    "metadata": {
  56     "collapsed": true
  57    },
  58    "outputs": [],
  59    "source": [
  60     "def read_net(filename):\n",
  61     "    with open(filename) as f:\n",
  62     "        pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n",
  63     "        lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n",
  64     "        return [Link(h, l, r) \n",
  65     "                for h, (l, r) in enumerate(lrs)]"
  66    ]
  67   },
  68   {
  69    "cell_type": "code",
  70    "execution_count": 32,
  71    "metadata": {},
  72    "outputs": [
  73     {
  74      "data": {
  75       "text/plain": [
  76        "[Link(height=0, left=2, right=5),\n",
  77        " Link(height=1, left=1, right=4),\n",
  78        " Link(height=2, left=0, right=3),\n",
  79        " Link(height=3, left=0, right=3),\n",
  80        " Link(height=4, left=0, right=5),\n",
  81        " Link(height=5, left=3, right=5),\n",
  82        " Link(height=6, left=0, right=2),\n",
  83        " Link(height=7, left=3, right=4),\n",
  84        " Link(height=8, left=2, right=4),\n",
  85        " Link(height=9, left=1, right=2),\n",
  86        " Link(height=10, left=0, right=4),\n",
  87        " Link(height=11, left=1, right=2),\n",
  88        " Link(height=12, left=2, right=4),\n",
  89        " Link(height=13, left=0, right=4),\n",
  90        " Link(height=14, left=1, right=4)]"
  91       ]
  92      },
  93      "execution_count": 32,
  94      "metadata": {},
  95      "output_type": "execute_result"
  96     }
  97    ],
  98    "source": [
  99     "small_net = read_net('04-small.txt')\n",
 100     "small_net"
 101    ]
 102   },
 103   {
 104    "cell_type": "code",
 105    "execution_count": 33,
 106    "metadata": {},
 107    "outputs": [
 108     {
 109      "data": {
 110       "text/plain": [
 111        "10135"
 112       ]
 113      },
 114      "execution_count": 33,
 115      "metadata": {},
 116      "output_type": "execute_result"
 117     }
 118    ],
 119    "source": [
 120     "net = read_net('04-lines.txt')\n",
 121     "len(net)"
 122    ]
 123   },
 124   {
 125    "cell_type": "code",
 126    "execution_count": 34,
 127    "metadata": {
 128     "collapsed": true
 129    },
 130    "outputs": [],
 131    "source": [
 132     "def show_net(links, pair_sep=', '):\n",
 133     "    return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
 134    ]
 135   },
 136   {
 137    "cell_type": "code",
 138    "execution_count": 35,
 139    "metadata": {
 140     "collapsed": true
 141    },
 142    "outputs": [],
 143    "source": [
 144     "def link_ends(link):\n",
 145     "    return set((link.left, link.right))"
 146    ]
 147   },
 148   {
 149    "cell_type": "code",
 150    "execution_count": 36,
 151    "metadata": {
 152     "collapsed": true
 153    },
 154    "outputs": [],
 155    "source": [
 156     "def follow(initial_line, links):\n",
 157     "    line = initial_line\n",
 158     "    heights = sorted(set(l.height for l in links))\n",
 159     "    for h in heights:\n",
 160     "        for l in [l for l in links if l.height == h]:\n",
 161     "            if line in link_ends(l):\n",
 162     "                line = [e for e in link_ends(l) if e != line][0]\n",
 163     "#                 print(l, line)\n",
 164     "    return line"
 165    ]
 166   },
 167   {
 168    "cell_type": "code",
 169    "execution_count": 37,
 170    "metadata": {
 171     "collapsed": true
 172    },
 173    "outputs": [],
 174    "source": [
 175     "def pack(net):\n",
 176     "    packed_links = []\n",
 177     "    line_heights = collections.defaultdict(lambda: -1)\n",
 178     "    for link in sorted(net):\n",
 179     "        link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
 180     "        line_heights[link.left] = link_height\n",
 181     "        line_heights[link.right] = link_height\n",
 182     "        packed_links += [Link(link_height, link.left, link.right)]\n",
 183     "    return sorted(packed_links)"
 184    ]
 185   },
 186   {
 187    "cell_type": "code",
 188    "execution_count": 38,
 189    "metadata": {},
 190    "outputs": [
 191     {
 192      "data": {
 193       "text/plain": [
 194        "14"
 195       ]
 196      },
 197      "execution_count": 38,
 198      "metadata": {},
 199      "output_type": "execute_result"
 200     }
 201    ],
 202    "source": [
 203     "max(l.height for l in small_net)"
 204    ]
 205   },
 206   {
 207    "cell_type": "code",
 208    "execution_count": 39,
 209    "metadata": {},
 210    "outputs": [
 211     {
 212      "data": {
 213       "text/plain": [
 214        "10"
 215       ]
 216      },
 217      "execution_count": 39,
 218      "metadata": {},
 219      "output_type": "execute_result"
 220     }
 221    ],
 222    "source": [
 223     "max(l.height for l in pack(small_net))"
 224    ]
 225   },
 226   {
 227    "cell_type": "code",
 228    "execution_count": 40,
 229    "metadata": {},
 230    "outputs": [
 231     {
 232      "data": {
 233       "text/plain": [
 234        "10134"
 235       ]
 236      },
 237      "execution_count": 40,
 238      "metadata": {},
 239      "output_type": "execute_result"
 240     }
 241    ],
 242    "source": [
 243     "max(l.height for l in net)"
 244    ]
 245   },
 246   {
 247    "cell_type": "code",
 248    "execution_count": 41,
 249    "metadata": {
 250     "collapsed": true
 251    },
 252    "outputs": [],
 253    "source": [
 254     "pnet = pack(net)"
 255    ]
 256   },
 257   {
 258    "cell_type": "code",
 259    "execution_count": 42,
 260    "metadata": {},
 261    "outputs": [
 262     {
 263      "data": {
 264       "text/plain": [
 265        "2286"
 266       ]
 267      },
 268      "execution_count": 42,
 269      "metadata": {},
 270      "output_type": "execute_result"
 271     }
 272    ],
 273    "source": [
 274     "max(l.height for l in pnet)"
 275    ]
 276   },
 277   {
 278    "cell_type": "code",
 279    "execution_count": 43,
 280    "metadata": {
 281     "collapsed": true
 282    },
 283    "outputs": [],
 284    "source": [
 285     "def height_groups(net):\n",
 286     "    return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
 287    ]
 288   },
 289   {
 290    "cell_type": "code",
 291    "execution_count": 44,
 292    "metadata": {
 293     "collapsed": true
 294    },
 295    "outputs": [],
 296    "source": [
 297     "def follow_many(in_sequence, net):\n",
 298     "    hgs = height_groups(net)\n",
 299     "    seq = list(in_sequence)\n",
 300     "    for h in hgs:\n",
 301     "        for link in hgs[h]:\n",
 302     "            seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
 303     "    return seq"
 304    ]
 305   },
 306   {
 307    "cell_type": "code",
 308    "execution_count": 45,
 309    "metadata": {},
 310    "outputs": [
 311     {
 312      "data": {
 313       "text/plain": [
 314        "'acfbed'"
 315       ]
 316      },
 317      "execution_count": 45,
 318      "metadata": {},
 319      "output_type": "execute_result"
 320     }
 321    ],
 322    "source": [
 323     "''.join(follow_many('abcdef', small_net))"
 324    ]
 325   },
 326   {
 327    "cell_type": "code",
 328    "execution_count": 46,
 329    "metadata": {},
 330    "outputs": [
 331     {
 332      "name": "stdout",
 333      "output_type": "stream",
 334      "text": [
 335       "10000 loops, best of 3: 39.5 µs per loop\n"
 336      ]
 337     }
 338    ],
 339    "source": [
 340     "%%timeit\n",
 341     "follow_many('abcdefghij', small_net)"
 342    ]
 343   },
 344   {
 345    "cell_type": "code",
 346    "execution_count": 47,
 347    "metadata": {},
 348    "outputs": [
 349     {
 350      "data": {
 351       "text/plain": [
 352        "'doqzmbishkwunvltpcexyjgfra'"
 353       ]
 354      },
 355      "execution_count": 47,
 356      "metadata": {},
 357      "output_type": "execute_result"
 358     }
 359    ],
 360    "source": [
 361     "''.join(follow_many(string.ascii_lowercase, net))"
 362    ]
 363   },
 364   {
 365    "cell_type": "code",
 366    "execution_count": 48,
 367    "metadata": {},
 368    "outputs": [
 369     {
 370      "name": "stdout",
 371      "output_type": "stream",
 372      "text": [
 373       "10 loops, best of 3: 19.7 ms per loop\n"
 374      ]
 375     }
 376    ],
 377    "source": [
 378     "%%timeit\n",
 379     "follow_many(string.ascii_lowercase, net)"
 380    ]
 381   },
 382   {
 383    "cell_type": "code",
 384    "execution_count": 49,
 385    "metadata": {},
 386    "outputs": [
 387     {
 388      "name": "stdout",
 389      "output_type": "stream",
 390      "text": [
 391       "100 loops, best of 3: 18.6 ms per loop\n"
 392      ]
 393     }
 394    ],
 395    "source": [
 396     "%%timeit\n",
 397     "follow_many(string.ascii_lowercase, pnet)"
 398    ]
 399   },
 400   {
 401    "cell_type": "code",
 402    "execution_count": null,
 403    "metadata": {
 404     "collapsed": true
 405    },
 406    "outputs": [],
 407    "source": []
 408   }
 409  ],
 410  "metadata": {
 411   "kernelspec": {
 412    "display_name": "Python 3",
 413    "language": "python",
 414    "name": "python3"
 415   },
 416   "language_info": {
 417    "codemirror_mode": {
 418     "name": "ipython",
 419     "version": 3
 420    },
 421    "file_extension": ".py",
 422    "mimetype": "text/x-python",
 423    "name": "python",
 424    "nbconvert_exporter": "python",
 425    "pygments_lexer": "ipython3",
 426    "version": "3.5.2+"
 427   }
 428  },
 429  "nbformat": 4,
 430  "nbformat_minor": 2
 431 }