は.パイプリンク.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "<div style='float: right'><img src='pic/pipelink.png'/></div>\n",
    "## <div id='pipelink' />パイプリンク"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from itertools import product\n",
    "from pulp import *\n",
    "from unionfind import unionfind\n",
    "from ortoolpy import addvar, addvars, addbinvar, addbinvars\n",
    "data = \"\"\"\\\n",
    " . - . . \n",
    ". . | . .\n",
    " . - . . \n",
    ". | | . |\n",
    " . . - . \n",
    ". . . . |\n",
    " - - . . \n",
    ". . . . .\n",
    " . . . . \"\"\".split('\\n')\n",
    "nw, nh = (len(data[0])+1)//2, (len(data)+1)//2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 問題\n",
    "* すべてのマスに線をひき１つのリンクにします\n",
    "* 線は交差してもよいが、枝分かれはしません\n",
    "* 最初に線が引いてあるマスは形を変えてはいけません\n",
    "\n",
    "### 変数\n",
    "* vh (1)\n",
    "* vv (2)\n",
    "* vr：表示用 (3)\n",
    "\n",
    "### 制約\n",
    "* 指定した形はそのままとすること (4)\n",
    "* 全マスに線を引くこと (5)\n",
    "* 交差はいいが、枝分かれしないこと (6)\n",
    "* １つのリンクにすること (7)\n",
    "* 外にはみ出ないこと (8)\n",
    "* vrをvhとvvで表現 (9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "m = LpProblem()\n",
    "vh = np.array(addbinvars(nh, nw+1)) # (1)\n",
    "vv = np.array(addbinvars(nh+1, nw)) # (2)\n",
    "vr = np.array(addvars(nh, nw)) # (3)\n",
    "vh[:,0] = vh[:,nw] = vv[0,:] = vv[nh,:] = 0 # (8)\n",
    "for i, j in product(range(nh), range(nw)):\n",
    "    if j > 0 and data[2*i][2*j-1] == '-':\n",
    "        m += vh[i,j] == 1 # (4)\n",
    "    if i > 0 and data[2*i-1][2*j] == '|':\n",
    "        m += vv[i,j] == 1 # (4)\n",
    "    l = [vv[i,j], vh[i,j], vv[i+1,j], vh[i,j+1]]\n",
    "    m += lpSum(l) >= 2 # (5)\n",
    "    for x in l:\n",
    "        m += lpSum(l) <= 2+2*x # (6)\n",
    "    m += lpDot(np.power(2, np.arange(4)), l) == vr[i,j] # (9)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    rh = np.vectorize(value)(vh).astype(int)\n",
    "    rv = np.vectorize(value)(vv).astype(int)\n",
    "    rr = np.vectorize(value)(vr).astype(int)\n",
    "    b = rr == 15\n",
    "    u = unionfind(nh * nw)\n",
    "    for i, j in product(range(nh), range(nw)):\n",
    "        if b[i,j]:\n",
    "            u.unite(i - 1 + j * nw, i + 1 + j * nw)\n",
    "            u.unite(i + j * nw - nw, i + j * nw + nw)\n",
    "        else:\n",
    "            if rv[i,j] and (i == 0 or not b[i-1,j]):\n",
    "                u.unite(i + j * nw, i - 1 + j * nw)\n",
    "            if rh[i,j] and (j == 0 or not b[i,j-1]):\n",
    "                u.unite(i + j * nw, i + j * nw - nw)\n",
    "    if all([b[i,j] or u.issame(0, i + j * nw) for i in range(nh) for j in range(nw)]):\n",
    "        break\n",
    "    for gr in u.groups():\n",
    "        if len(gr) == 1:\n",
    "            continue\n",
    "        l = []\n",
    "        for k in gr:\n",
    "            i, j = k % nw, k // nw\n",
    "            l.extend(vv[i+p,j] for p in range(2) if rv[i+p,j])\n",
    "            l.extend(vh[i,j+p] for p in range(2) if rh[i,j+p])\n",
    "        m += lpSum(l) <= len(l) - 2 # (7)\n",
    "print('\\n'.join(''.join(s) for s in np.vectorize(lambda x: '012┘4│┐78└─1┌34┼'[x])(rr)))"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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": 1
}