ほ.ホタルビーム.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "<div style='float: right'><img src='pic/hotaru.png'/></div>\n",
    "## <div id='hotaru' />ホタルビーム"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pulp import *\n",
    "from unionfind import unionfind\n",
    "from ortoolpy import addvar, addvars, addbinvar, addbinvars\n",
    "hint = [s.split(',') for s in \"\"\"\\\n",
    "0,0,0,R\n",
    "0,3,2,B\n",
    "0,5,3,L\n",
    "2,1,?,B\n",
    "2,5,4,L\n",
    "3,3,1,T\n",
    "4,0,1,T\n",
    "4,3,0,L\n",
    "5,4,?,T\"\"\".split('\\n')]\n",
    "nw, nh = 6, 6\n",
    "L = 9 # limit length from '?'\n",
    "rh, rw, rh1, rw1 = range(nh), range(nw), range(nh-1), range(nw-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "### 問題\n",
    "* 全ての白丸の黒点から点線上に線をのばして白丸の黒点でないところにつなげます\n",
    "* どの線も白丸以外のところで、途切れたり交差したり枝分かれしたりしてはいけません\n",
    "* 線で全体がひとつながりにならなければいけません\n",
    "* 数字は、その白丸の黒点から出る線が白丸につながるまでに曲がる回数を表します"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "### 変数\n",
    "* 省略\n",
    "\n",
    "### 制約\n",
    "* 省略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "bh = [[(-1, 0) for j in rw] for i in rh] # (id, dir) of hint\n",
    "for k, h in enumerate(hint):\n",
    "    hint[k] = hc = [int(h[0]), int(h[1]), -2 if h[2] == '?' else int(h[2]), 'LTRB'.index(h[3])]\n",
    "    bh[hc[0]][hc[1]] = (k, hc[3])\n",
    "m = LpProblem()\n",
    "cc = [[[LpAffineExpression() for j in rw] for i in rh], # check node overlap \\\n",
    "      [[LpAffineExpression() for j in rw1] for i in rh], # check h_line overlap \\\n",
    "      [[LpAffineExpression() for j in rw] for i in rh1]] # check v_line overlap\n",
    "vas = []\n",
    "def make(cands, y, x, n, d, p0, q0):\n",
    "    dy, dx = [0, -1, 0, 1][d], [-1, 0, 1, 0][d]\n",
    "    ny, nx = y + dy, x + dx\n",
    "    if n == -1 or (ny, nx) in p0 or not (0 <= ny < nh and 0 <= nx < nw) or len(p0) > L:\n",
    "        return\n",
    "    p, q = p0 + [(ny, nx)], q0 + [(0, ny, nx), (1, ny, nx), (0, y, x), (1, y, x)][d:d + 1]\n",
    "    if bh[ny][nx][0] >= 0:\n",
    "        if n <= 0 and d != (bh[ny][nx][1] + 2) % 4:\n",
    "            cands.append((p, q))\n",
    "        return\n",
    "    for k in range(4):\n",
    "        make(cands, ny, nx, n if d == k else n - 1, k, p, q)\n",
    "for h in hint:\n",
    "    cands = []\n",
    "    make(cands, h[0], h[1], h[2], h[3], [(h[0], h[1])], [])\n",
    "    vv = addbinvars(len(cands))\n",
    "    m += lpSum(vv) == 1\n",
    "    for i in range(len(cands)):\n",
    "        vas.append((vv[i], cands[i]))\n",
    "        for j, (w,y,x) in enumerate(cands[i][1]):\n",
    "                cc[0][cands[i][0][j][0]][cands[i][0][j][1]] += vv[i]\n",
    "                cc[w+1][y][x] += vv[i]\n",
    "for i in rh:\n",
    "    for j in rw:\n",
    "        m += cc[0][i][j] <= 1\n",
    "        if j < nw - 1:\n",
    "            m += cc[1][i][j] <= 1\n",
    "        if i < nh - 1:\n",
    "            m += cc[2][i][j] <= 1\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    u = unionfind(len(hint))\n",
    "    l = []\n",
    "    for va, cand in vas:\n",
    "        if value(va) > 0.5:\n",
    "            l.append(va)\n",
    "            (y1, x1), (y2, x2) = cand[0][0], cand[0][-1]\n",
    "            u.unite(bh[y1][x1][0], bh[y2][x2][0])\n",
    "    if all([u.issame(0, k) for k in range(1,len(hint))]):\n",
    "        break\n",
    "    m += lpSum(l) <= len(l) - 1\n",
    "bd = [[' '] * (2 * nw - 1) for i in range(2 * nh - 1)]\n",
    "for h in hint:\n",
    "    bd[h[0] * 2][h[1] * 2] = '?' if h[2] < 0 else str(h[2])\n",
    "for va, cand in vas:\n",
    "    if value(va) > 0.5:\n",
    "        for w,y,x in cand[1]:\n",
    "            bd[2 * y + w][2 * x + 1 - w] = '-|'[w]\n",
    "for b in bd:\n",
    "    print(' '.join(b))"
   ]
  }
 ],
 "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
}