04-amidakuji/amidakuji-solution-1.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "Time to hit the beach!\n",
   8     "\n",
   9     "To stop people going straight to the best sunbeds, the hotel has arranged a labyrinthine way of getting to the beach. Instead of heading straight to your chosen sunbed, you pick a lane and follow it through the maze. When you get to a cross-path, you walk along it to the other lane, then carry on down to the beach.\n",
  10     "\n",
  11     "This example network has six lines, numbered zero to five, and fifteen links. You start at the top and move down.\n",
  12     "\n",
  13     "![Example labyrinth](small-expanded-trace.svg.png)\n",
  14     "\n",
  15     "The dashed coloured lines show you some paths you would take going through this labyrinth to the beach. For instance, if you started in lane 1 (the red line), you would switch to lane 4 then lane 3, and you'd emerge on sunbed 3. Entering on lane 5 (the green line) would immediately switch to lane 2, then lane 0, then then lane 4, then finally back to lane 2 where they emerge. Entering on lane zero would take you all round the houses, including crossing the previous tracks, to finally end up back on lane 0.\n",
  16     "\n",
  17     "If you and five friends labelled yourselves `a`, `b`, `c`, `d`, `e`, `f`, your labels when you came out would be in order acfbed.\n",
  18     "\n",
  19     "You'd rather like to know where you and your friends are ending up on the beach, so you've got a copy of the layout plan of the labyrinth. It's given as a sequence of pairs, showing the lane to and from for each cross-path. For instance, the labyrinth above would be described as:\n",
  20     "\n",
  21     "```\n",
  22     "(2, 5)\n",
  23     "(1, 4)\n",
  24     "(0, 3)\n",
  25     "(0, 3)\n",
  26     "(0, 5)\n",
  27     "(3, 5)\n",
  28     "(0, 2)\n",
  29     "(3, 4)\n",
  30     "(2, 4)\n",
  31     "(1, 2)\n",
  32     "(0, 4)\n",
  33     "(1, 2)\n",
  34     "(2, 4)\n",
  35     "(0, 4)\n",
  36     "(1, 4)\n",
  37     "```\n",
  38     "\n",
  39     "For each pair `(a, b)`, you can assume $0 \\le a < b < n$, if there are _n_ lanes. (In other words, all lane numbers are valid, the first lane number is always less than the second, and cross-paths don't go from a lane back to the same lane.)\n",
  40     "\n",
  41     "# Part 1\n",
  42     "\n",
  43     "The full labyrinth description is given in (04-lines.txt). The labyrinth has 26 lines, labelled 0 to 25 inclusive. If you and 25 friends, labelled `a` to `z` in order, entered the labyrinth, in what order would you come out?\n",
  44     "\n",
  45     "(Your answer should be one string of 26 letters, without spaces or punctuation, like `acfbed` .)"
  46    ]
  47   },
  48   {
  49    "cell_type": "code",
  50    "execution_count": 44,
  51    "metadata": {
  52     "collapsed": true
  53    },
  54    "outputs": [],
  55    "source": [
  56     "import collections\n",
  57     "import string\n",
  58     "import itertools\n",
  59     "import re"
  60    ]
  61   },
  62   {
  63    "cell_type": "code",
  64    "execution_count": 45,
  65    "metadata": {
  66     "collapsed": true
  67    },
  68    "outputs": [],
  69    "source": [
  70     "Link = collections.namedtuple('Link', 'height left right')"
  71    ]
  72   },
  73   {
  74    "cell_type": "code",
  75    "execution_count": 46,
  76    "metadata": {
  77     "collapsed": true
  78    },
  79    "outputs": [],
  80    "source": [
  81     "def extract_pairs(net_string):\n",
  82     "    return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
  83    ]
  84   },
  85   {
  86    "cell_type": "code",
  87    "execution_count": 47,
  88    "metadata": {
  89     "collapsed": true
  90    },
  91    "outputs": [],
  92    "source": [
  93     "def read_net_string(net_string):\n",
  94     "    return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
  95    ]
  96   },
  97   {
  98    "cell_type": "code",
  99    "execution_count": 48,
 100    "metadata": {
 101     "collapsed": true
 102    },
 103    "outputs": [],
 104    "source": [
 105     "def read_net(filename, rev=False):\n",
 106     "    with open(filename) as f:\n",
 107     "        pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n",
 108     "        if rev:\n",
 109     "            lrs = [(int(lr[1]), int(lr[2])) for lr in reversed(pairs)]\n",
 110     "        else:\n",
 111     "            lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n",
 112     "        return [Link(h, l, r) \n",
 113     "                for h, (l, r) in enumerate(lrs)]"
 114    ]
 115   },
 116   {
 117    "cell_type": "code",
 118    "execution_count": 15,
 119    "metadata": {},
 120    "outputs": [
 121     {
 122      "data": {
 123       "text/plain": [
 124        "[Link(height=0, left=2, right=5),\n",
 125        " Link(height=1, left=1, right=4),\n",
 126        " Link(height=2, left=0, right=3),\n",
 127        " Link(height=3, left=0, right=3),\n",
 128        " Link(height=4, left=0, right=5),\n",
 129        " Link(height=5, left=3, right=5),\n",
 130        " Link(height=6, left=0, right=2),\n",
 131        " Link(height=7, left=3, right=4),\n",
 132        " Link(height=8, left=2, right=4),\n",
 133        " Link(height=9, left=1, right=2),\n",
 134        " Link(height=10, left=0, right=4),\n",
 135        " Link(height=11, left=1, right=2),\n",
 136        " Link(height=12, left=2, right=4),\n",
 137        " Link(height=13, left=0, right=4),\n",
 138        " Link(height=14, left=1, right=4)]"
 139       ]
 140      },
 141      "execution_count": 15,
 142      "metadata": {},
 143      "output_type": "execute_result"
 144     }
 145    ],
 146    "source": [
 147     "small_net = read_net('04-small.txt')\n",
 148     "small_net"
 149    ]
 150   },
 151   {
 152    "cell_type": "code",
 153    "execution_count": 16,
 154    "metadata": {},
 155    "outputs": [
 156     {
 157      "data": {
 158       "text/plain": [
 159        "10135"
 160       ]
 161      },
 162      "execution_count": 16,
 163      "metadata": {},
 164      "output_type": "execute_result"
 165     }
 166    ],
 167    "source": [
 168     "net = read_net('04-lines.txt')\n",
 169     "len(net)"
 170    ]
 171   },
 172   {
 173    "cell_type": "code",
 174    "execution_count": 36,
 175    "metadata": {},
 176    "outputs": [
 177     {
 178      "data": {
 179       "text/plain": [
 180        "23"
 181       ]
 182      },
 183      "execution_count": 36,
 184      "metadata": {},
 185      "output_type": "execute_result"
 186     }
 187    ],
 188    "source": [
 189     "permnet = read_net('permutations.txt')\n",
 190     "len(permnet)"
 191    ]
 192   },
 193   {
 194    "cell_type": "code",
 195    "execution_count": 41,
 196    "metadata": {},
 197    "outputs": [
 198     {
 199      "data": {
 200       "text/plain": [
 201        "23"
 202       ]
 203      },
 204      "execution_count": 41,
 205      "metadata": {},
 206      "output_type": "execute_result"
 207     }
 208    ],
 209    "source": [
 210     "rpermnet = read_net('permutations.txt', rev=True)\n",
 211     "len(rpermnet)"
 212    ]
 213   },
 214   {
 215    "cell_type": "code",
 216    "execution_count": 18,
 217    "metadata": {
 218     "collapsed": true
 219    },
 220    "outputs": [],
 221    "source": [
 222     "def show_net(links, pair_sep=', '):\n",
 223     "    return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
 224    ]
 225   },
 226   {
 227    "cell_type": "code",
 228    "execution_count": 19,
 229    "metadata": {
 230     "collapsed": true
 231    },
 232    "outputs": [],
 233    "source": [
 234     "def link_ends(link):\n",
 235     "    return set((link.left, link.right))"
 236    ]
 237   },
 238   {
 239    "cell_type": "code",
 240    "execution_count": 20,
 241    "metadata": {
 242     "collapsed": true
 243    },
 244    "outputs": [],
 245    "source": [
 246     "def follow(initial_line, links):\n",
 247     "    line = initial_line\n",
 248     "    heights = sorted(set(l.height for l in links))\n",
 249     "    for h in heights:\n",
 250     "        for l in [l for l in links if l.height == h]:\n",
 251     "            if line in link_ends(l):\n",
 252     "                line = [e for e in link_ends(l) if e != line][0]\n",
 253     "#                 print(l, line)\n",
 254     "    return line"
 255    ]
 256   },
 257   {
 258    "cell_type": "markdown",
 259    "metadata": {},
 260    "source": [
 261     "You've noticed that the beach labyrinth is longer than it needs to be. Rather than putting each cross-link on a separate step away from the hotel, it's possible to put several cross-links at the same distance, so long as none of them shares an end. \n",
 262     "\n",
 263     "For instance, the sample labyrinth\n",
 264     "\n",
 265     "![Example labyrinth](small-expanded.svg.png)\n",
 266     "\n",
 267     "can be packed into this form, with the first three cross-links all placed at the start of the labyrinth. \n",
 268     "\n",
 269     "![Packed labyrinth](small-packed.svg.png)\n",
 270     "\n",
 271     "You can pack a labyrinth by sliding a link up until just before either of its ends would touch an earlier link. The first 2-5 link stays where it is. The next two links (1-4 and 0-3) slide up to also be on the same level. The next 0-3 link then slides up until it's one step from the start. The other links slide up in turn.\n",
 272     "\n",
 273     "This packed labyrinth has the same shuffling behaviour of the original. But where the last cross-link in the original labyrinth is fourteen steps beyond the start, the last cross-link in the packed labyrinth is only ten steps on.\n",
 274     "\n",
 275     "Only slide links; don't be tempted to remove any. The packed labyrinth should have the same number of cross-links as the original.\n",
 276     "\n",
 277     "# Part 2\n",
 278     "\n",
 279     "The labyrinth is still given in 04-lines.txt. \n",
 280     "\n",
 281     "After all the packing and sliding, how far is the last cross-link from the first?"
 282    ]
 283   },
 284   {
 285    "cell_type": "markdown",
 286    "metadata": {},
 287    "source": [
 288     "## Note to self\n",
 289     "Several solutions tried a simplistic approach of packing a layer until a link could not go on that layer, then starting the next. But, this didn't allow for links that could slide more than one layer.\n",
 290     "\n",
 291     "The simple algorithm moved from left net to centre net, but missed you could still pack to form right net.\n",
 292     "\n",
 293     "![Packing variants](packing-variants.svg.png)"
 294    ]
 295   },
 296   {
 297    "cell_type": "code",
 298    "execution_count": 21,
 299    "metadata": {
 300     "collapsed": true
 301    },
 302    "outputs": [],
 303    "source": [
 304     "def pack(net):\n",
 305     "    packed_links = []\n",
 306     "    line_heights = collections.defaultdict(lambda: -1)\n",
 307     "    for link in sorted(net):\n",
 308     "        link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
 309     "        line_heights[link.left] = link_height\n",
 310     "        line_heights[link.right] = link_height\n",
 311     "        packed_links += [Link(link_height, link.left, link.right)]\n",
 312     "    return sorted(packed_links)"
 313    ]
 314   },
 315   {
 316    "cell_type": "code",
 317    "execution_count": 22,
 318    "metadata": {},
 319    "outputs": [
 320     {
 321      "data": {
 322       "text/plain": [
 323        "14"
 324       ]
 325      },
 326      "execution_count": 22,
 327      "metadata": {},
 328      "output_type": "execute_result"
 329     }
 330    ],
 331    "source": [
 332     "max(l.height for l in small_net)"
 333    ]
 334   },
 335   {
 336    "cell_type": "code",
 337    "execution_count": 23,
 338    "metadata": {},
 339    "outputs": [
 340     {
 341      "data": {
 342       "text/plain": [
 343        "10"
 344       ]
 345      },
 346      "execution_count": 23,
 347      "metadata": {},
 348      "output_type": "execute_result"
 349     }
 350    ],
 351    "source": [
 352     "max(l.height for l in pack(small_net))"
 353    ]
 354   },
 355   {
 356    "cell_type": "code",
 357    "execution_count": 24,
 358    "metadata": {},
 359    "outputs": [
 360     {
 361      "data": {
 362       "text/plain": [
 363        "10134"
 364       ]
 365      },
 366      "execution_count": 24,
 367      "metadata": {},
 368      "output_type": "execute_result"
 369     }
 370    ],
 371    "source": [
 372     "max(l.height for l in net)"
 373    ]
 374   },
 375   {
 376    "cell_type": "code",
 377    "execution_count": 25,
 378    "metadata": {
 379     "collapsed": true
 380    },
 381    "outputs": [],
 382    "source": [
 383     "pnet = pack(net)"
 384    ]
 385   },
 386   {
 387    "cell_type": "code",
 388    "execution_count": 26,
 389    "metadata": {},
 390    "outputs": [
 391     {
 392      "data": {
 393       "text/plain": [
 394        "2286"
 395       ]
 396      },
 397      "execution_count": 26,
 398      "metadata": {},
 399      "output_type": "execute_result"
 400     }
 401    ],
 402    "source": [
 403     "max(l.height for l in pnet)"
 404    ]
 405   },
 406   {
 407    "cell_type": "code",
 408    "execution_count": 27,
 409    "metadata": {
 410     "collapsed": true
 411    },
 412    "outputs": [],
 413    "source": [
 414     "def height_groups(net):\n",
 415     "    return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
 416    ]
 417   },
 418   {
 419    "cell_type": "code",
 420    "execution_count": 28,
 421    "metadata": {
 422     "collapsed": true
 423    },
 424    "outputs": [],
 425    "source": [
 426     "def follow_many(in_sequence, net):\n",
 427     "    hgs = height_groups(net)\n",
 428     "    seq = list(in_sequence)\n",
 429     "    for h in hgs:\n",
 430     "        for link in hgs[h]:\n",
 431     "            seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
 432     "    return seq"
 433    ]
 434   },
 435   {
 436    "cell_type": "code",
 437    "execution_count": 29,
 438    "metadata": {},
 439    "outputs": [
 440     {
 441      "data": {
 442       "text/plain": [
 443        "'acfbed'"
 444       ]
 445      },
 446      "execution_count": 29,
 447      "metadata": {},
 448      "output_type": "execute_result"
 449     }
 450    ],
 451    "source": [
 452     "''.join(follow_many('abcdef', small_net))"
 453    ]
 454   },
 455   {
 456    "cell_type": "code",
 457    "execution_count": 69,
 458    "metadata": {},
 459    "outputs": [
 460     {
 461      "name": "stdout",
 462      "output_type": "stream",
 463      "text": [
 464       " 0        ['0', '1', '2', '3', '4', '5']\n",
 465       " 1 (2, 5) ['0', '1', '5', '3', '4', '2']\n",
 466       " 2 (1, 4) ['0', '4', '5', '3', '1', '2']\n",
 467       " 3 (0, 3) ['3', '4', '5', '0', '1', '2']\n",
 468       " 4 (0, 3) ['0', '4', '5', '3', '1', '2']\n",
 469       " 5 (0, 5) ['2', '4', '5', '3', '1', '0']\n",
 470       " 6 (3, 5) ['2', '4', '5', '0', '1', '3']\n",
 471       " 7 (0, 2) ['5', '4', '2', '0', '1', '3']\n",
 472       " 8 (3, 4) ['5', '4', '2', '1', '0', '3']\n",
 473       " 9 (2, 4) ['5', '4', '0', '1', '2', '3']\n",
 474       "10 (1, 2) ['5', '0', '4', '1', '2', '3']\n",
 475       "11 (0, 4) ['2', '0', '4', '1', '5', '3']\n",
 476       "12 (1, 2) ['2', '4', '0', '1', '5', '3']\n",
 477       "13 (2, 4) ['2', '4', '5', '1', '0', '3']\n",
 478       "14 (0, 4) ['0', '4', '5', '1', '2', '3']\n",
 479       "15 (1, 4) ['0', '2', '5', '1', '4', '3']\n"
 480      ]
 481     }
 482    ],
 483    "source": [
 484     "for i in range(len(small_net)+1):\n",
 485     "    pre_net = small_net[:i]\n",
 486     "    if i == 0:\n",
 487     "        print('{:2}'.format(i), \n",
 488     "          \"      \".format(small_net[i-1].left, small_net[i-1].right),\n",
 489     "          follow_many(\"012345\", pre_net))\n",
 490     "    else:\n",
 491     "        print('{:2}'.format(i), \n",
 492     "          \"({}, {})\".format(small_net[i-1].left, small_net[i-1].right),\n",
 493     "          follow_many(\"012345\", pre_net))\n",
 494     "\n",
 495     "        "
 496    ]
 497   },
 498   {
 499    "cell_type": "code",
 500    "execution_count": 66,
 501    "metadata": {},
 502    "outputs": [
 503     {
 504      "data": {
 505       "text/plain": [
 506        "[Link(height=0, left=2, right=5),\n",
 507        " Link(height=1, left=1, right=4),\n",
 508        " Link(height=2, left=0, right=3),\n",
 509        " Link(height=3, left=0, right=3),\n",
 510        " Link(height=4, left=0, right=5),\n",
 511        " Link(height=5, left=3, right=5),\n",
 512        " Link(height=6, left=0, right=2),\n",
 513        " Link(height=7, left=3, right=4),\n",
 514        " Link(height=8, left=2, right=4),\n",
 515        " Link(height=9, left=1, right=2),\n",
 516        " Link(height=10, left=0, right=4),\n",
 517        " Link(height=11, left=1, right=2),\n",
 518        " Link(height=12, left=2, right=4),\n",
 519        " Link(height=13, left=0, right=4),\n",
 520        " Link(height=14, left=1, right=4)]"
 521       ]
 522      },
 523      "execution_count": 66,
 524      "metadata": {},
 525      "output_type": "execute_result"
 526     }
 527    ],
 528    "source": [
 529     "small_net[:15]"
 530    ]
 531   },
 532   {
 533    "cell_type": "code",
 534    "execution_count": 30,
 535    "metadata": {},
 536    "outputs": [
 537     {
 538      "name": "stdout",
 539      "output_type": "stream",
 540      "text": [
 541       "10000 loops, best of 3: 42 µs per loop\n"
 542      ]
 543     }
 544    ],
 545    "source": [
 546     "%%timeit\n",
 547     "follow_many('abcdefghij', small_net)"
 548    ]
 549   },
 550   {
 551    "cell_type": "code",
 552    "execution_count": 37,
 553    "metadata": {},
 554    "outputs": [
 555     {
 556      "data": {
 557       "text/plain": [
 558        "'doqzmbishkwunvltpcexyjgfra'"
 559       ]
 560      },
 561      "execution_count": 37,
 562      "metadata": {},
 563      "output_type": "execute_result"
 564     }
 565    ],
 566    "source": [
 567     "''.join(follow_many(string.ascii_lowercase, net))"
 568    ]
 569   },
 570   {
 571    "cell_type": "code",
 572    "execution_count": 39,
 573    "metadata": {},
 574    "outputs": [
 575     {
 576      "data": {
 577       "text/plain": [
 578        "'zfrasxwigvjoembqcyhplnktud'"
 579       ]
 580      },
 581      "execution_count": 39,
 582      "metadata": {},
 583      "output_type": "execute_result"
 584     }
 585    ],
 586    "source": [
 587     "''.join(follow_many(string.ascii_lowercase, permnet))"
 588    ]
 589   },
 590   {
 591    "cell_type": "code",
 592    "execution_count": 42,
 593    "metadata": {},
 594    "outputs": [
 595     {
 596      "data": {
 597       "text/plain": [
 598        "'doqzmbishkwunvltpcexyjgfra'"
 599       ]
 600      },
 601      "execution_count": 42,
 602      "metadata": {},
 603      "output_type": "execute_result"
 604     }
 605    ],
 606    "source": [
 607     "''.join(follow_many(string.ascii_lowercase, rpermnet))"
 608    ]
 609   },
 610   {
 611    "cell_type": "code",
 612    "execution_count": 43,
 613    "metadata": {},
 614    "outputs": [
 615     {
 616      "data": {
 617       "text/plain": [
 618        "True"
 619       ]
 620      },
 621      "execution_count": 43,
 622      "metadata": {},
 623      "output_type": "execute_result"
 624     }
 625    ],
 626    "source": [
 627     "follow_many(string.ascii_lowercase, net) == follow_many(string.ascii_lowercase, rpermnet)"
 628    ]
 629   },
 630   {
 631    "cell_type": "code",
 632    "execution_count": 32,
 633    "metadata": {},
 634    "outputs": [
 635     {
 636      "name": "stdout",
 637      "output_type": "stream",
 638      "text": [
 639       "10 loops, best of 3: 19.3 ms per loop\n"
 640      ]
 641     }
 642    ],
 643    "source": [
 644     "%%timeit\n",
 645     "follow_many(string.ascii_lowercase, net)"
 646    ]
 647   },
 648   {
 649    "cell_type": "code",
 650    "execution_count": 33,
 651    "metadata": {},
 652    "outputs": [
 653     {
 654      "name": "stdout",
 655      "output_type": "stream",
 656      "text": [
 657       "100 loops, best of 3: 18.7 ms per loop\n"
 658      ]
 659     }
 660    ],
 661    "source": [
 662     "%%timeit\n",
 663     "follow_many(string.ascii_lowercase, pnet)"
 664    ]
 665   },
 666   {
 667    "cell_type": "code",
 668    "execution_count": null,
 669    "metadata": {
 670     "collapsed": true
 671    },
 672    "outputs": [],
 673    "source": []
 674   }
 675  ],
 676  "metadata": {
 677   "kernelspec": {
 678    "display_name": "Python 3",
 679    "language": "python",
 680    "name": "python3"
 681   },
 682   "language_info": {
 683    "codemirror_mode": {
 684     "name": "ipython",
 685     "version": 3
 686    },
 687    "file_extension": ".py",
 688    "mimetype": "text/x-python",
 689    "name": "python",
 690    "nbconvert_exporter": "python",
 691    "pygments_lexer": "ipython3",
 692    "version": "3.5.2+"
 693   }
 694  },
 695  "nbformat": 4,
 696  "nbformat_minor": 2
 697 }