え.ABCプレース.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "<div style='float: right'><img src='pic/abcplace.png'/></div>\n",
    "## <div id='paint' />ABCプレース"
   ]
  },
  {
   "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",
    " B B  C \n",
    "A......B\n",
    "B...... \n",
    "C...... \n",
    " ......A\n",
    " ......C\n",
    " ...... \n",
    "  BC CA \"\"\".split('\\n')\n",
    "nn = len(data)-2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 問題\n",
    "* 各行各列にA、B、Cを1つずつ置く。\n",
    "* 外側のヒントは、最も近い文字を表す。\n",
    "\n",
    "### 変数\n",
    "* v：各文字 (1)\n",
    "\n",
    "### 制約\n",
    "* ヒントを満たす (2)\n",
    "* 各行各列に1つ (3)\n",
    "* 文字は1つ (4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "m = LpProblem()\n",
    "v = np.array(addbinvars(nn, nn, 4)) # (1)\n",
    "def chk(m, c, y, x, dy, dx):\n",
    "    d = ord(c)-64\n",
    "    if d > 0:\n",
    "        for i, k in product(range(1,nn), range(1,4)):\n",
    "            if k != d:\n",
    "                for j in range(i):\n",
    "                    m += v[y+dy*j,x+dx*j,k] <= 1-v[y+dy*i,x+dx*i,d] # (2)\n",
    "for i in range(nn):\n",
    "    for k in range(1, 4):\n",
    "        m += lpSum(v[i,:,k]) == 1 # (3)\n",
    "        m += lpSum(v[:,i,k]) == 1 # (3)\n",
    "    chk(m, data[0][i+1], 0, i, 1, 0)\n",
    "    chk(m, data[nn+1][i+1], nn-1, i, -1, 0)\n",
    "    chk(m, data[i+1][0], i, 0, 0, 1)\n",
    "    chk(m, data[i+1][nn+1], i, nn-1, 0, -1)\n",
    "for i, j in product(range(nn), range(nn)):\n",
    "    m += lpSum(v[i,j]) == 1 # (4)\n",
    "%time m.solve()\n",
    "print('\\n'.join(' '.join('.ABC'[i] for i in j)\n",
    "    for j in np.vectorize(value)(v).dot(range(4)).astype(int)))"
   ]
  }
 ],
 "metadata": {
  "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
}