04-amidakuji/amidakuji-solution-1.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 44,
   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": 45,
  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": 46,
  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": 47,
  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": 48,
  55    "metadata": {
  56     "collapsed": true
  57    },
  58    "outputs": [],
  59    "source": [
  60     "def read_net(filename, rev=False):\n",
  61     "    with open(filename) as f:\n",
  62     "        pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n",
  63     "        if rev:\n",
  64     "            lrs = [(int(lr[1]), int(lr[2])) for lr in reversed(pairs)]\n",
  65     "        else:\n",
  66     "            lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n",
  67     "        return [Link(h, l, r) \n",
  68     "                for h, (l, r) in enumerate(lrs)]"
  69    ]
  70   },
  71   {
  72    "cell_type": "code",
  73    "execution_count": 15,
  74    "metadata": {},
  75    "outputs": [
  76     {
  77      "data": {
  78       "text/plain": [
  79        "[Link(height=0, left=2, right=5),\n",
  80        " Link(height=1, left=1, right=4),\n",
  81        " Link(height=2, left=0, right=3),\n",
  82        " Link(height=3, left=0, right=3),\n",
  83        " Link(height=4, left=0, right=5),\n",
  84        " Link(height=5, left=3, right=5),\n",
  85        " Link(height=6, left=0, right=2),\n",
  86        " Link(height=7, left=3, right=4),\n",
  87        " Link(height=8, left=2, right=4),\n",
  88        " Link(height=9, left=1, right=2),\n",
  89        " Link(height=10, left=0, right=4),\n",
  90        " Link(height=11, left=1, right=2),\n",
  91        " Link(height=12, left=2, right=4),\n",
  92        " Link(height=13, left=0, right=4),\n",
  93        " Link(height=14, left=1, right=4)]"
  94       ]
  95      },
  96      "execution_count": 15,
  97      "metadata": {},
  98      "output_type": "execute_result"
  99     }
 100    ],
 101    "source": [
 102     "small_net = read_net('04-small.txt')\n",
 103     "small_net"
 104    ]
 105   },
 106   {
 107    "cell_type": "code",
 108    "execution_count": 16,
 109    "metadata": {},
 110    "outputs": [
 111     {
 112      "data": {
 113       "text/plain": [
 114        "10135"
 115       ]
 116      },
 117      "execution_count": 16,
 118      "metadata": {},
 119      "output_type": "execute_result"
 120     }
 121    ],
 122    "source": [
 123     "net = read_net('04-lines.txt')\n",
 124     "len(net)"
 125    ]
 126   },
 127   {
 128    "cell_type": "code",
 129    "execution_count": 36,
 130    "metadata": {},
 131    "outputs": [
 132     {
 133      "data": {
 134       "text/plain": [
 135        "23"
 136       ]
 137      },
 138      "execution_count": 36,
 139      "metadata": {},
 140      "output_type": "execute_result"
 141     }
 142    ],
 143    "source": [
 144     "permnet = read_net('permutations.txt')\n",
 145     "len(permnet)"
 146    ]
 147   },
 148   {
 149    "cell_type": "code",
 150    "execution_count": 41,
 151    "metadata": {},
 152    "outputs": [
 153     {
 154      "data": {
 155       "text/plain": [
 156        "23"
 157       ]
 158      },
 159      "execution_count": 41,
 160      "metadata": {},
 161      "output_type": "execute_result"
 162     }
 163    ],
 164    "source": [
 165     "rpermnet = read_net('permutations.txt', rev=True)\n",
 166     "len(rpermnet)"
 167    ]
 168   },
 169   {
 170    "cell_type": "code",
 171    "execution_count": 18,
 172    "metadata": {
 173     "collapsed": true
 174    },
 175    "outputs": [],
 176    "source": [
 177     "def show_net(links, pair_sep=', '):\n",
 178     "    return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
 179    ]
 180   },
 181   {
 182    "cell_type": "code",
 183    "execution_count": 19,
 184    "metadata": {
 185     "collapsed": true
 186    },
 187    "outputs": [],
 188    "source": [
 189     "def link_ends(link):\n",
 190     "    return set((link.left, link.right))"
 191    ]
 192   },
 193   {
 194    "cell_type": "code",
 195    "execution_count": 20,
 196    "metadata": {
 197     "collapsed": true
 198    },
 199    "outputs": [],
 200    "source": [
 201     "def follow(initial_line, links):\n",
 202     "    line = initial_line\n",
 203     "    heights = sorted(set(l.height for l in links))\n",
 204     "    for h in heights:\n",
 205     "        for l in [l for l in links if l.height == h]:\n",
 206     "            if line in link_ends(l):\n",
 207     "                line = [e for e in link_ends(l) if e != line][0]\n",
 208     "#                 print(l, line)\n",
 209     "    return line"
 210    ]
 211   },
 212   {
 213    "cell_type": "code",
 214    "execution_count": 21,
 215    "metadata": {
 216     "collapsed": true
 217    },
 218    "outputs": [],
 219    "source": [
 220     "def pack(net):\n",
 221     "    packed_links = []\n",
 222     "    line_heights = collections.defaultdict(lambda: -1)\n",
 223     "    for link in sorted(net):\n",
 224     "        link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
 225     "        line_heights[link.left] = link_height\n",
 226     "        line_heights[link.right] = link_height\n",
 227     "        packed_links += [Link(link_height, link.left, link.right)]\n",
 228     "    return sorted(packed_links)"
 229    ]
 230   },
 231   {
 232    "cell_type": "code",
 233    "execution_count": 22,
 234    "metadata": {},
 235    "outputs": [
 236     {
 237      "data": {
 238       "text/plain": [
 239        "14"
 240       ]
 241      },
 242      "execution_count": 22,
 243      "metadata": {},
 244      "output_type": "execute_result"
 245     }
 246    ],
 247    "source": [
 248     "max(l.height for l in small_net)"
 249    ]
 250   },
 251   {
 252    "cell_type": "code",
 253    "execution_count": 23,
 254    "metadata": {},
 255    "outputs": [
 256     {
 257      "data": {
 258       "text/plain": [
 259        "10"
 260       ]
 261      },
 262      "execution_count": 23,
 263      "metadata": {},
 264      "output_type": "execute_result"
 265     }
 266    ],
 267    "source": [
 268     "max(l.height for l in pack(small_net))"
 269    ]
 270   },
 271   {
 272    "cell_type": "code",
 273    "execution_count": 24,
 274    "metadata": {},
 275    "outputs": [
 276     {
 277      "data": {
 278       "text/plain": [
 279        "10134"
 280       ]
 281      },
 282      "execution_count": 24,
 283      "metadata": {},
 284      "output_type": "execute_result"
 285     }
 286    ],
 287    "source": [
 288     "max(l.height for l in net)"
 289    ]
 290   },
 291   {
 292    "cell_type": "code",
 293    "execution_count": 25,
 294    "metadata": {
 295     "collapsed": true
 296    },
 297    "outputs": [],
 298    "source": [
 299     "pnet = pack(net)"
 300    ]
 301   },
 302   {
 303    "cell_type": "code",
 304    "execution_count": 26,
 305    "metadata": {},
 306    "outputs": [
 307     {
 308      "data": {
 309       "text/plain": [
 310        "2286"
 311       ]
 312      },
 313      "execution_count": 26,
 314      "metadata": {},
 315      "output_type": "execute_result"
 316     }
 317    ],
 318    "source": [
 319     "max(l.height for l in pnet)"
 320    ]
 321   },
 322   {
 323    "cell_type": "code",
 324    "execution_count": 27,
 325    "metadata": {
 326     "collapsed": true
 327    },
 328    "outputs": [],
 329    "source": [
 330     "def height_groups(net):\n",
 331     "    return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
 332    ]
 333   },
 334   {
 335    "cell_type": "code",
 336    "execution_count": 28,
 337    "metadata": {
 338     "collapsed": true
 339    },
 340    "outputs": [],
 341    "source": [
 342     "def follow_many(in_sequence, net):\n",
 343     "    hgs = height_groups(net)\n",
 344     "    seq = list(in_sequence)\n",
 345     "    for h in hgs:\n",
 346     "        for link in hgs[h]:\n",
 347     "            seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
 348     "    return seq"
 349    ]
 350   },
 351   {
 352    "cell_type": "code",
 353    "execution_count": 29,
 354    "metadata": {},
 355    "outputs": [
 356     {
 357      "data": {
 358       "text/plain": [
 359        "'acfbed'"
 360       ]
 361      },
 362      "execution_count": 29,
 363      "metadata": {},
 364      "output_type": "execute_result"
 365     }
 366    ],
 367    "source": [
 368     "''.join(follow_many('abcdef', small_net))"
 369    ]
 370   },
 371   {
 372    "cell_type": "code",
 373    "execution_count": 69,
 374    "metadata": {},
 375    "outputs": [
 376     {
 377      "name": "stdout",
 378      "output_type": "stream",
 379      "text": [
 380       " 0        ['0', '1', '2', '3', '4', '5']\n",
 381       " 1 (2, 5) ['0', '1', '5', '3', '4', '2']\n",
 382       " 2 (1, 4) ['0', '4', '5', '3', '1', '2']\n",
 383       " 3 (0, 3) ['3', '4', '5', '0', '1', '2']\n",
 384       " 4 (0, 3) ['0', '4', '5', '3', '1', '2']\n",
 385       " 5 (0, 5) ['2', '4', '5', '3', '1', '0']\n",
 386       " 6 (3, 5) ['2', '4', '5', '0', '1', '3']\n",
 387       " 7 (0, 2) ['5', '4', '2', '0', '1', '3']\n",
 388       " 8 (3, 4) ['5', '4', '2', '1', '0', '3']\n",
 389       " 9 (2, 4) ['5', '4', '0', '1', '2', '3']\n",
 390       "10 (1, 2) ['5', '0', '4', '1', '2', '3']\n",
 391       "11 (0, 4) ['2', '0', '4', '1', '5', '3']\n",
 392       "12 (1, 2) ['2', '4', '0', '1', '5', '3']\n",
 393       "13 (2, 4) ['2', '4', '5', '1', '0', '3']\n",
 394       "14 (0, 4) ['0', '4', '5', '1', '2', '3']\n",
 395       "15 (1, 4) ['0', '2', '5', '1', '4', '3']\n"
 396      ]
 397     }
 398    ],
 399    "source": [
 400     "for i in range(len(small_net)+1):\n",
 401     "    pre_net = small_net[:i]\n",
 402     "    if i == 0:\n",
 403     "        print('{:2}'.format(i), \n",
 404     "          \"      \".format(small_net[i-1].left, small_net[i-1].right),\n",
 405     "          follow_many(\"012345\", pre_net))\n",
 406     "    else:\n",
 407     "        print('{:2}'.format(i), \n",
 408     "          \"({}, {})\".format(small_net[i-1].left, small_net[i-1].right),\n",
 409     "          follow_many(\"012345\", pre_net))\n",
 410     "\n",
 411     "        "
 412    ]
 413   },
 414   {
 415    "cell_type": "code",
 416    "execution_count": 66,
 417    "metadata": {},
 418    "outputs": [
 419     {
 420      "data": {
 421       "text/plain": [
 422        "[Link(height=0, left=2, right=5),\n",
 423        " Link(height=1, left=1, right=4),\n",
 424        " Link(height=2, left=0, right=3),\n",
 425        " Link(height=3, left=0, right=3),\n",
 426        " Link(height=4, left=0, right=5),\n",
 427        " Link(height=5, left=3, right=5),\n",
 428        " Link(height=6, left=0, right=2),\n",
 429        " Link(height=7, left=3, right=4),\n",
 430        " Link(height=8, left=2, right=4),\n",
 431        " Link(height=9, left=1, right=2),\n",
 432        " Link(height=10, left=0, right=4),\n",
 433        " Link(height=11, left=1, right=2),\n",
 434        " Link(height=12, left=2, right=4),\n",
 435        " Link(height=13, left=0, right=4),\n",
 436        " Link(height=14, left=1, right=4)]"
 437       ]
 438      },
 439      "execution_count": 66,
 440      "metadata": {},
 441      "output_type": "execute_result"
 442     }
 443    ],
 444    "source": [
 445     "small_net[:15]"
 446    ]
 447   },
 448   {
 449    "cell_type": "code",
 450    "execution_count": 30,
 451    "metadata": {},
 452    "outputs": [
 453     {
 454      "name": "stdout",
 455      "output_type": "stream",
 456      "text": [
 457       "10000 loops, best of 3: 42 µs per loop\n"
 458      ]
 459     }
 460    ],
 461    "source": [
 462     "%%timeit\n",
 463     "follow_many('abcdefghij', small_net)"
 464    ]
 465   },
 466   {
 467    "cell_type": "code",
 468    "execution_count": 37,
 469    "metadata": {},
 470    "outputs": [
 471     {
 472      "data": {
 473       "text/plain": [
 474        "'doqzmbishkwunvltpcexyjgfra'"
 475       ]
 476      },
 477      "execution_count": 37,
 478      "metadata": {},
 479      "output_type": "execute_result"
 480     }
 481    ],
 482    "source": [
 483     "''.join(follow_many(string.ascii_lowercase, net))"
 484    ]
 485   },
 486   {
 487    "cell_type": "code",
 488    "execution_count": 39,
 489    "metadata": {},
 490    "outputs": [
 491     {
 492      "data": {
 493       "text/plain": [
 494        "'zfrasxwigvjoembqcyhplnktud'"
 495       ]
 496      },
 497      "execution_count": 39,
 498      "metadata": {},
 499      "output_type": "execute_result"
 500     }
 501    ],
 502    "source": [
 503     "''.join(follow_many(string.ascii_lowercase, permnet))"
 504    ]
 505   },
 506   {
 507    "cell_type": "code",
 508    "execution_count": 42,
 509    "metadata": {},
 510    "outputs": [
 511     {
 512      "data": {
 513       "text/plain": [
 514        "'doqzmbishkwunvltpcexyjgfra'"
 515       ]
 516      },
 517      "execution_count": 42,
 518      "metadata": {},
 519      "output_type": "execute_result"
 520     }
 521    ],
 522    "source": [
 523     "''.join(follow_many(string.ascii_lowercase, rpermnet))"
 524    ]
 525   },
 526   {
 527    "cell_type": "code",
 528    "execution_count": 43,
 529    "metadata": {},
 530    "outputs": [
 531     {
 532      "data": {
 533       "text/plain": [
 534        "True"
 535       ]
 536      },
 537      "execution_count": 43,
 538      "metadata": {},
 539      "output_type": "execute_result"
 540     }
 541    ],
 542    "source": [
 543     "follow_many(string.ascii_lowercase, net) == follow_many(string.ascii_lowercase, rpermnet)"
 544    ]
 545   },
 546   {
 547    "cell_type": "code",
 548    "execution_count": 32,
 549    "metadata": {},
 550    "outputs": [
 551     {
 552      "name": "stdout",
 553      "output_type": "stream",
 554      "text": [
 555       "10 loops, best of 3: 19.3 ms per loop\n"
 556      ]
 557     }
 558    ],
 559    "source": [
 560     "%%timeit\n",
 561     "follow_many(string.ascii_lowercase, net)"
 562    ]
 563   },
 564   {
 565    "cell_type": "code",
 566    "execution_count": 33,
 567    "metadata": {},
 568    "outputs": [
 569     {
 570      "name": "stdout",
 571      "output_type": "stream",
 572      "text": [
 573       "100 loops, best of 3: 18.7 ms per loop\n"
 574      ]
 575     }
 576    ],
 577    "source": [
 578     "%%timeit\n",
 579     "follow_many(string.ascii_lowercase, pnet)"
 580    ]
 581   },
 582   {
 583    "cell_type": "code",
 584    "execution_count": null,
 585    "metadata": {
 586     "collapsed": true
 587    },
 588    "outputs": [],
 589    "source": []
 590   }
 591  ],
 592  "metadata": {
 593   "kernelspec": {
 594    "display_name": "Python 3",
 595    "language": "python",
 596    "name": "python3"
 597   },
 598   "language_info": {
 599    "codemirror_mode": {
 600     "name": "ipython",
 601     "version": 3
 602    },
 603    "file_extension": ".py",
 604    "mimetype": "text/x-python",
 605    "name": "python",
 606    "nbconvert_exporter": "python",
 607    "pygments_lexer": "ipython3",
 608    "version": "3.5.2+"
 609   }
 610  },
 611  "nbformat": 4,
 612  "nbformat_minor": 2
 613 }