day 59 - colored tiling.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def add(wall, row, col, tile):\n",
    "    assert np.all(wall[row, col, :] == -1)\n",
    "    \n",
    "    # check neighbours if the tile fits\n",
    "    for i, j, m, n in [[-1, 0, 3, 0], [1, 0, 0, 3], [0, -1, 1, 2], [0, 1, 2, 1]]:\n",
    "        t = wall[row + i, col + j, m]\n",
    "        if t != -1 and t != tile[n]:\n",
    "            return False\n",
    "\n",
    "    # add the tile\n",
    "    wall[row, col, :] = tile\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def remove(wall, row, col):\n",
    "    wall[row, col, :] = -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def solve(wall, tiles, row=1, col=1):\n",
    "    # carry on the next row\n",
    "    if col == wall.shape[1] - 1:\n",
    "        row += 1\n",
    "        col = 1\n",
    "\n",
    "    # solution found\n",
    "    if row == wall.shape[0] - 1:\n",
    "        return True\n",
    "\n",
    "    # try each tile\n",
    "    for i in range(len(tiles)):\n",
    "        tile = tiles.popleft()\n",
    "\n",
    "        if add(wall, row, col, tile):\n",
    "            # backtrack\n",
    "            if solve(wall, tiles, row, col + 1):\n",
    "                return True\n",
    "            remove(wall, row, col)\n",
    "\n",
    "        tiles.append(tile)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## wall"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def make_wall(rows, cols):\n",
    "    # create wall\n",
    "    wall = np.zeros((rows, cols, 4), dtype=int) - 1\n",
    "\n",
    "    # randomize wall edges\n",
    "    wall[-1, :, 0] = np.random.randint(0, 2, cols)\n",
    "    wall[:, 0, 1] = np.random.randint(0, 2, rows)\n",
    "    wall[:, -1, 2] = np.random.randint(0, 2, rows)\n",
    "    wall[0, :, 3] = np.random.randint(0, 2, cols)\n",
    "\n",
    "    return wall"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_wall(wall):\n",
    "    chars = np.array(list('01 '))\n",
    "    tile = lambda i, j: ''.join(chars[wall[i, j, :]])\n",
    "\n",
    "    # print rows\n",
    "    for i in range(wall.shape[0]):\n",
    "        row = [tile(i, j)[:2] for j in range(wall.shape[1])]\n",
    "        print(' '.join(row))\n",
    "        row = [tile(i, j)[2:] for j in range(wall.shape[1])]\n",
    "        print(' '.join(row))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "wall = make_wall(7, 7)\n",
    "tiles = deque(np.random.randint(0, 2, (30, 4)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0                  \n",
      " 1  0  0  0  0  1 00\n",
      " 1 01 00 00 01 10   \n",
      "   10 11 01 00 11 0 \n",
      " 0 00 10 10 01 10   \n",
      "   00 01 01 01 11 0 \n",
      " 1 01 10 11 11 10   \n",
      "   10 10 00 10 11 0 \n",
      " 1 00 00 00 00 10   \n",
      "   10 01 00 01 01 0 \n",
      " 0 00 10 01 10 11   \n",
      "   00 00 01 10 01 1 \n",
      "00 0  0  1  0  1  1 \n",
      "                  0 \n"
     ]
    }
   ],
   "source": [
    "solve(wall, tiles)\n",
    "print_wall(wall)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}