す.スリザーリンク.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "<div style='float: right'><img src='pic/slither.png'/></div>\n",
    "## <div id='slither' />スリザーリンク"
   ]
  },
  {
   "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 = \"\"\"\\\n",
    "33...3.\n",
    "..2....\n",
    "...21.3\n",
    "23...02\n",
    "0.03...\n",
    "....0..\n",
    ".3...33\"\"\".split()\n",
    "nw, nh = len(data[0]), len(data)\n",
    "M = (nw + 1) * (nh + 1) - 1\n",
    "r2 = range(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 問題\n",
    "* 点の間を線でつなぎ、一つの輪を作ります\n",
    "* 数字は、周囲の線の数に等しいこと\n",
    "* 一つの点から出る線の数は0か2となること\n",
    "\n",
    "### 考え方\n",
    "* 線は無向ですが、有向として考えます\n",
    "* 数字の3がある角を始点とします（必ず通ります）\n",
    "\n",
    "### 変数\n",
    "* vh：0:to left, 1:to right (1)\n",
    "* vv：0:to down, 1:to up (2)\n",
    "* vz：始点からの距離 (3)\n",
    "\n",
    "### 制約\n",
    "* 数字があれば、矢印の数に等しいこと (4)\n",
    "* 矢印の向きは1つ (5)\n",
    "* 始点以外は、矢印があれば距離が増やします (6)\n",
    "* 始点の距離は0 (7)\n",
    "* 距離は、全点数以下 (8)\n",
    "* 入る矢印数は1以下 (9)\n",
    "* 入る数と出る数は同じになること (10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "m = LpProblem()\n",
    "vh = np.array(addbinvars(nh+1, nw, 2)) # 0:to left, 1:to right (1)\n",
    "vv = np.array(addbinvars(nh, nw+1, 2)) # 0:to down, 1:to up (2)\n",
    "vz = np.array(addvars(nh+1, nw+1)) # (3)\n",
    "def dirs(i, j, k):\n",
    "    return ([vh[i,j-l,k^l] for l in r2 if 0 <= j-l < nw] +\n",
    "            [vv[i-l,j,k^l] for l in r2 if 0 <= i-l < nh])\n",
    "for i, j in product(range(nh), range(nw)):\n",
    "    if data[i][j].isdigit():\n",
    "        m += lpSum(vh[i+k,j,l] + vv[i,j+k,l] for l in r2 for k in r2) == int(data[i][j]) # (4)\n",
    "        if data[i][j] == '3':\n",
    "            fy, fx = i, j\n",
    "m += vz[fy,fx] == 0 # (7)\n",
    "for i, j in product(range(nh+1), range(nw)):\n",
    "    m += lpSum(vh[i,j]) <= 1 # (5)\n",
    "    m += vz[i,j] + 1 <= vz[i,j+1] + M * (1 - vh[i,j,0]) # (6)\n",
    "    if (i, j) != (fy, fx):\n",
    "        m += vz[i,j+1] + 1 <= vz[i,j] + M * (1 - vh[i,j,1]) # (6)\n",
    "for i, j in product(range(nh), range(nw+1)):\n",
    "    m += lpSum(vv[i,j]) <= 1 # (5)\n",
    "    m += vz[i,j] + 1 <= vz[i+1,j] + M * (1 - vv[i,j,0]) # (6)\n",
    "    if (i, j) != (fy, fx):\n",
    "        m += vz[i+1,j] + 1 <= vz[i,j] + M * (1 - vv[i,j,1]) # (6)\n",
    "for i, j in product(range(nh+1), range(nw+1)):\n",
    "    m += vz[i,j] <= M # (8)\n",
    "    din = dirs(i, j, 1)\n",
    "    dout = dirs(i, j, 0)\n",
    "    m += lpSum(din) <= 1 # (9)\n",
    "    m += lpSum(din) == lpSum(dout) # (10)\n",
    "%time m.solve()\n",
    "rh = np.vectorize(value)(vh.sum(2))\n",
    "rv = np.vectorize(value)(vv.sum(2))\n",
    "for i in range(nh+1):\n",
    "    print(' ', end='')\n",
    "    for j in range(nw):\n",
    "        print('- ' if rh[i,j] else '  ', end='')\n",
    "    print()\n",
    "    if i == nh: break\n",
    "    for j in range(nw+1):\n",
    "        print('|' if rv[i,j] else ' ', end='')\n",
    "        if j < nh:\n",
    "            print(data[i][j], end='')\n",
    "    print()"
   ]
  }
 ],
 "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
}