{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import collections\n",
    "import string\n",
    "import itertools\n",
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Link = collections.namedtuple('Link', 'height left right')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def extract_pairs(net_string):\n",
    "    return [[int(pi) for pi in p.split(', ')] for p in net_string[1:-1].split('), (')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def read_net_string(net_string):\n",
    "    return [Link(h, l, r) for h, (l, r) in enumerate(extract_pairs(net_string))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def read_net(filename, rev=False):\n",
    "    with open(filename) as f:\n",
    "        pairs = [re.split('\\D+', p.strip()) for p in f.readlines()]\n",
    "        if rev:\n",
    "            lrs = [(int(lr[1]), int(lr[2])) for lr in reversed(pairs)]\n",
    "        else:\n",
    "            lrs = [(int(lr[1]), int(lr[2])) for lr in pairs]\n",
    "        return [Link(h, l, r) \n",
    "                for h, (l, r) in enumerate(lrs)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Link(height=0, left=2, right=5),\n",
       " Link(height=1, left=1, right=4),\n",
       " Link(height=2, left=0, right=3),\n",
       " Link(height=3, left=0, right=3),\n",
       " Link(height=4, left=0, right=5),\n",
       " Link(height=5, left=3, right=5),\n",
       " Link(height=6, left=0, right=2),\n",
       " Link(height=7, left=3, right=4),\n",
       " Link(height=8, left=2, right=4),\n",
       " Link(height=9, left=1, right=2),\n",
       " Link(height=10, left=0, right=4),\n",
       " Link(height=11, left=1, right=2),\n",
       " Link(height=12, left=2, right=4),\n",
       " Link(height=13, left=0, right=4),\n",
       " Link(height=14, left=1, right=4)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "small_net = read_net('04-small.txt')\n",
    "small_net"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10135"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "net = read_net('04-lines.txt')\n",
    "len(net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "permnet = read_net('permutations.txt')\n",
    "len(permnet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rpermnet = read_net('permutations.txt', rev=True)\n",
    "len(rpermnet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def show_net(links, pair_sep=', '):\n",
    "    return pair_sep.join('({}, {})'.format(l.left, l.right) for l in sorted(links))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def link_ends(link):\n",
    "    return set((link.left, link.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def follow(initial_line, links):\n",
    "    line = initial_line\n",
    "    heights = sorted(set(l.height for l in links))\n",
    "    for h in heights:\n",
    "        for l in [l for l in links if l.height == h]:\n",
    "            if line in link_ends(l):\n",
    "                line = [e for e in link_ends(l) if e != line][0]\n",
    "#                 print(l, line)\n",
    "    return line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def pack(net):\n",
    "    packed_links = []\n",
    "    line_heights = collections.defaultdict(lambda: -1)\n",
    "    for link in sorted(net):\n",
    "        link_height = max(line_heights[link.left], line_heights[link.right]) + 1\n",
    "        line_heights[link.left] = link_height\n",
    "        line_heights[link.right] = link_height\n",
    "        packed_links += [Link(link_height, link.left, link.right)]\n",
    "    return sorted(packed_links)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(l.height for l in small_net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(l.height for l in pack(small_net))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10134"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(l.height for l in net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pnet = pack(net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2286"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(l.height for l in pnet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def height_groups(net):\n",
    "    return {h: list(g) for h, g in itertools.groupby(pack(net), lambda l: l.height)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def follow_many(in_sequence, net):\n",
    "    hgs = height_groups(net)\n",
    "    seq = list(in_sequence)\n",
    "    for h in hgs:\n",
    "        for link in hgs[h]:\n",
    "            seq[link.right], seq[link.left] = seq[link.left], seq[link.right]\n",
    "    return seq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'acfbed'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "''.join(follow_many('abcdef', small_net))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0        ['0', '1', '2', '3', '4', '5']\n",
      " 1 (2, 5) ['0', '1', '5', '3', '4', '2']\n",
      " 2 (1, 4) ['0', '4', '5', '3', '1', '2']\n",
      " 3 (0, 3) ['3', '4', '5', '0', '1', '2']\n",
      " 4 (0, 3) ['0', '4', '5', '3', '1', '2']\n",
      " 5 (0, 5) ['2', '4', '5', '3', '1', '0']\n",
      " 6 (3, 5) ['2', '4', '5', '0', '1', '3']\n",
      " 7 (0, 2) ['5', '4', '2', '0', '1', '3']\n",
      " 8 (3, 4) ['5', '4', '2', '1', '0', '3']\n",
      " 9 (2, 4) ['5', '4', '0', '1', '2', '3']\n",
      "10 (1, 2) ['5', '0', '4', '1', '2', '3']\n",
      "11 (0, 4) ['2', '0', '4', '1', '5', '3']\n",
      "12 (1, 2) ['2', '4', '0', '1', '5', '3']\n",
      "13 (2, 4) ['2', '4', '5', '1', '0', '3']\n",
      "14 (0, 4) ['0', '4', '5', '1', '2', '3']\n",
      "15 (1, 4) ['0', '2', '5', '1', '4', '3']\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(small_net)+1):\n",
    "    pre_net = small_net[:i]\n",
    "    if i == 0:\n",
    "        print('{:2}'.format(i), \n",
    "          \"      \".format(small_net[i-1].left, small_net[i-1].right),\n",
    "          follow_many(\"012345\", pre_net))\n",
    "    else:\n",
    "        print('{:2}'.format(i), \n",
    "          \"({}, {})\".format(small_net[i-1].left, small_net[i-1].right),\n",
    "          follow_many(\"012345\", pre_net))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Link(height=0, left=2, right=5),\n",
       " Link(height=1, left=1, right=4),\n",
       " Link(height=2, left=0, right=3),\n",
       " Link(height=3, left=0, right=3),\n",
       " Link(height=4, left=0, right=5),\n",
       " Link(height=5, left=3, right=5),\n",
       " Link(height=6, left=0, right=2),\n",
       " Link(height=7, left=3, right=4),\n",
       " Link(height=8, left=2, right=4),\n",
       " Link(height=9, left=1, right=2),\n",
       " Link(height=10, left=0, right=4),\n",
       " Link(height=11, left=1, right=2),\n",
       " Link(height=12, left=2, right=4),\n",
       " Link(height=13, left=0, right=4),\n",
       " Link(height=14, left=1, right=4)]"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "small_net[:15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000 loops, best of 3: 42 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "follow_many('abcdefghij', small_net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'doqzmbishkwunvltpcexyjgfra'"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "''.join(follow_many(string.ascii_lowercase, net))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'zfrasxwigvjoembqcyhplnktud'"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "''.join(follow_many(string.ascii_lowercase, permnet))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'doqzmbishkwunvltpcexyjgfra'"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "''.join(follow_many(string.ascii_lowercase, rpermnet))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "follow_many(string.ascii_lowercase, net) == follow_many(string.ascii_lowercase, rpermnet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 19.3 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "follow_many(string.ascii_lowercase, net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 18.7 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "follow_many(string.ascii_lowercase, pnet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}