な.ナンバーリンク.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "<div style='float: right'><img src='pic/numberlink.png'/></div>\n",
    "## <div id='numberlink' />ナンバーリンク"
   ]
  },
  {
   "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 ortoolpy import addvar, addvars, addbinvar, addbinvars\n",
    "data = np.array([list(s) for s in \"\"\"\\\n",
    "1.4....\n",
    "2....3.\n",
    "...2...\n",
    ".......\n",
    ".......\n",
    "..5.4..\n",
    "1.3...5\"\"\".split()])\n",
    "data[data == '.'] = '0'\n",
    "data = data.astype(int)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 問題\n",
    "* 各マスには2つ以上の線が入ってはいけません\n",
    "* 異なる線同士が交わってはいけません\n",
    "\n",
    "### 変数\n",
    "* vr:どのタイプのラインに含まれるか (1)\n",
    "* vh:水平に出るかどうか (2)\n",
    "* vv:垂直に出るかどうか (3)\n",
    "\n",
    "### 制約\n",
    "* 始点と終点が指定のラインに含まれること (4)\n",
    "* 始点と終点は、1本だけ出ること (5)\n",
    "* 始点終点以外の各マスに接続されるのは、0本か2本 (6)\n",
    "* 接続したら、両端のタイプは同じになること (7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "mx = data.max()\n",
    "m = LpProblem()\n",
    "vr = addvars(*data.shape) # (1)\n",
    "vh = addbinvars(data.shape[0], data.shape[1]-1) # (2)\n",
    "vv = addbinvars(data.shape[0]-1, data.shape[1]) # (3)\n",
    "def dirs(i, j):\n",
    "    return ([vh[i][j - k] for k in range(2) if 0 <= j-k < data.shape[1] - 1]\n",
    "          + [vv[i - k][j] for k in range(2) if 0 <= i-k < data.shape[0] - 1])\n",
    "for i, j in product(range(data.shape[0]), range(data.shape[1])):\n",
    "    s = dirs(i, j)\n",
    "    if data[i][j]:\n",
    "        m += vr[i][j] == data[i][j] # (4)\n",
    "        m += lpSum(s) == 1 # (5)\n",
    "    else:\n",
    "        m += lpSum(s) == 2 * addbinvar() # (6)\n",
    "    if i < data.shape[0] - 1:\n",
    "        m += vr[i][j] <= vr[i + 1][j] + mx * (1 - vv[i][j]) # (7)\n",
    "        m += vr[i + 1][j] <= vr[i][j] + mx * (1 - vv[i][j]) # (7)\n",
    "    if j < data.shape[1] - 1:\n",
    "        m += vr[i][j] <= vr[i][j + 1] + mx * (1 - vh[i][j]) # (7)\n",
    "        m += vr[i][j + 1] <= vr[i][j] + mx * (1 - vh[i][j]) # (7)\n",
    "%time m.solve()\n",
    "np.vectorize(value)(vr).astype(int).tolist()"
   ]
  }
 ],
 "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
}