や.ヤジリン.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "<div style='float: right'><img src='pic/yajirin.png'/></div>\n",
    "## <div id='yajirin' />ヤジリン"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from itertools import product\n",
    "from pulp import *\n",
    "from ortoolpy import addvar, addvars, addbinvar, addbinvars\n",
    "hint = [[int(c) for c in s[:-2].split(',')]+[s[-1]] for s in \"\"\"\\\n",
    "0,9,2,D\n",
    "1,7,1,L\n",
    "2,1,1,L\n",
    "3,4,2,U\n",
    "4,2,1,L\n",
    "4,7,1,L\n",
    "5,1,0,L\n",
    "5,6,0,L\n",
    "7,0,0,D\n",
    "7,2,1,D\n",
    "7,4,3,R\"\"\".split('\\n')]\n",
    "nw, nh = 10, 10\n",
    "M = nh * nw\n",
    "mx = max(nh, nw)\n",
    "r2 = range(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "### 問題\n",
    "* 線を引いて全体で１つの輪を作り、線が通らないマスは黒くぬります\n",
    "* 数字は、矢印の方向に入る黒マスの数を表します\n",
    "* 数字のマスに線を引いたり、黒マスにしたりしてはいけません\n",
    "* 線は、マスの中央を通るようにタテヨコに引き、線を交差させたり、枝分かれさせたりしてはいけません\n",
    "* 黒マスをタテヨコに連続させてはいけません"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "### 変数\n",
    "* 略\n",
    "\n",
    "### 制約\n",
    "* 略"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "m = LpProblem()\n",
    "vh = np.array(addbinvars(nh, nw+1, 2)) # 0:L, 1:R\n",
    "vv = np.array(addbinvars(nh+1, nw, 2)) # 0:U, 1:D\n",
    "vhs = np.array(addvars(nh, nw+1))\n",
    "vvs = np.array(addvars(nh+1, nw))\n",
    "vr = np.array(addvars(nh, nw)) # shape\n",
    "vb = np.array(addbinvars(nh, nw)) # 1:black, 0:o.w.\n",
    "vd = np.array(addvars(nh, nw))\n",
    "dic = {}\n",
    "for h in hint:\n",
    "    y,x,n,d = *h[:3],'LURD'.index(h[3])\n",
    "    dy, dx = [0, -1, 0, 1][d], [-1, 0, 1, 0][d]\n",
    "    m += vr[y,x] == 0\n",
    "    m += vb[y,x] == 0\n",
    "    m += lpSum(vb[y+dy*i,x+dx*i] for i in range(1,mx)\n",
    "        if 0 <= y+dy*i < nh and 0 <= x+dx*i < nw) == n\n",
    "    dic[y,x] = '%d%c'%(n,h[3])\n",
    "    if n == 0:\n",
    "        py, px = y+dy, x+dx\n",
    "vv[0,:,:] = vv[nh,:,:] = vh[:,0,:] = vh[:,nw,:] = 0\n",
    "for i, j in product(range(nh+1), range(nw)):\n",
    "    m += lpSum(vv[i,j]) == vvs[i,j]\n",
    "    m += vvs[i,j] <= 1\n",
    "for i, j in product(range(nh), range(nw+1)):\n",
    "    m += lpSum(vh[i,j]) == vhs[i,j]\n",
    "    m += vhs[i,j] <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i, j in product(range(nh), range(nw)):\n",
    "    m+=(lpSum(vv[i+k,j,1-k] + vh[i,j+k,1-k] for k in r2)  # in\n",
    "      ==lpSum(vv[i+k,j,k]   + vh[i,j+k,k]   for k in r2)) # out\n",
    "    l = [vvs[i,j], vhs[i,j], vvs[i+1,j], vhs[i,j+1]]\n",
    "    m += lpDot([1,2,4,8], l) == vr[i,j]\n",
    "    m += lpSum(l) <= 2\n",
    "    if (i,j) not in dic:\n",
    "        m += vr[i,j] + vb[i,j] >= 1\n",
    "        m += vr[i,j] <= 12 * (1-vb[i,j])\n",
    "    m += vd[i,j] <= M\n",
    "    if j > 0:\n",
    "        m += vb[i,j-1] + vb[i,j] <= 1\n",
    "        if (i,j-1) != (py,px):\n",
    "            m += vd[i,j-1] + M*(1-vh[i,j,0]) >= vd[i,j]+1\n",
    "        if (i,j) != (py,px):\n",
    "            m += vd[i,j] + M*(1-vh[i,j,1]) >= vd[i,j-1]+1\n",
    "    if i > 0:\n",
    "        m += vb[i-1,j] + vb[i,j] <= 1\n",
    "        if (i-1,j) != (py,px):\n",
    "            m += vd[i-1,j] + M * (1-vv[i,j,0]) >= vd[i,j] + 1\n",
    "        if (i,j) != (py,px):\n",
    "            m += vd[i,j] + M * (1-vv[i,j,1]) >= vd[i-1,j] + 1\n",
    "%time m.solve()\n",
    "rr = np.vectorize(value)(vr).astype(int)\n",
    "rb = np.vectorize(value)(vb).astype(int)\n",
    "for i in range(nh):\n",
    "    for j in range(nw):\n",
    "        print(dic.get((i,j), '■' if rb[i,j] else\n",
    "            '　12┘4│┐78└─1┌34┼'[rr[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": 2
}