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

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