し.四角に切れ.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "<div style='float: right'><img src='pic/square.png'/></div>\n",
    "## <div id='square' />四角に切れ"
   ]
  },
  {
   "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",
    "3..3..\n",
    "......\n",
    "6.4...\n",
    "...2.6\n",
    "......\n",
    "..6..6\"\"\".split()\n",
    "nw, nh = len(data[0]), len(data)\n",
    "tgt = [(i, j, int(data[i][j])) for i in range(nh)\n",
    "       for j in range(nw) if data[i][j].isdigit()]\n",
    "nm = len(tgt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 問題\n",
    "* 盤面を数字を1つずつ含む長方形に分割します\n",
    "* 数字は1マスの面積を1とした長方形の面積になるようにします\n",
    "\n",
    "### 変数\n",
    "* v：各位置が各部屋かどうか (1)\n",
    "* vl：候補のどれか (2)\n",
    "\n",
    "### 制約\n",
    "* vは1つの部屋のみ (3)\n",
    "* vlは１つの候補のみ (4)\n",
    "* vlの1つを選んだら、その位置のその部屋は1 (5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "m = LpProblem()\n",
    "v = np.array(addvars(nh, nw, nm)) # (1)\n",
    "for i, j in product(range(nh), range(nw)):\n",
    "    m += lpSum(v[i,j]) == 1 # (3)\n",
    "def make(h, pi, pj, na):\n",
    "    lst = []\n",
    "    for i in range(1, na + 1):\n",
    "        j = na // i\n",
    "        if i * j >= na:\n",
    "            for y in range(i):\n",
    "                if 0 <= pi-y <= nh-i:\n",
    "                    ly = range(pi-y, pi-y+i)\n",
    "                    for x in range(j):\n",
    "                        if 0 <= pj-x <= nw-j:\n",
    "                            lx = range(pj-x, pj-x+j)\n",
    "                            lst.append([v[dy,dx,h] for dy in ly for dx in lx])\n",
    "    return lst\n",
    "for h, (i, j, k) in enumerate(tgt):\n",
    "    lst = make(h, i, j, k)\n",
    "    vl = addbinvars(len(lst))  # (2)\n",
    "    m += lpSum(vl) == 1 # (4)\n",
    "    for l, ll in enumerate(lst):\n",
    "        for t in ll:\n",
    "            m += vl[l] <= t # (5)\n",
    "%time m.solve()\n",
    "(np.vectorize(value)(v.dot(range(nm))).astype(int)+1).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
}