place tiles on a board

fill_board_with_tiles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Brilliant Challenge](https://brilliant.org/weekly-problems/2018-02-26/intermediate/?p=5)\n",
    "How many $1\\times 1$ and $2\\times 1$ tiles can be placed on a $10\\times2$ board (orientation is arbitrary)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _get_from_board(board, point, piece):\n",
    "    y, x = point\n",
    "    result = []\n",
    "    for i, row in enumerate(piece):\n",
    "        result.append([board[x+i][y+j] if v else 0 for j, v in enumerate(row)])\n",
    "    return result\n",
    "\n",
    "\n",
    "def _replace_on_board(board, point, piece, n):\n",
    "    y, x = point\n",
    "    f = list(list(row) for row in board)\n",
    "    for i, row in enumerate(piece):\n",
    "        for j, val in enumerate(row):\n",
    "            if val:\n",
    "                f[x+i][y+j] = n\n",
    "    return tuple(tuple(row) for row in f)\n",
    "\n",
    "\n",
    "def placements(board, pieces, point=(0, 0), n=1):\n",
    "    '''yield boards with all possible piece-placements at the specified point'''\n",
    "    for piece in pieces:\n",
    "        try:\n",
    "            cutout = _get_from_board(board, point, piece)\n",
    "            if any(map(any, cutout)):\n",
    "                continue\n",
    "            yield _replace_on_board(board, point, piece, n)\n",
    "        except IndexError:\n",
    "            pass\n",
    "\n",
    "\n",
    "def first_free(board):\n",
    "    '''find first filed without a tile'''\n",
    "    for y, row in enumerate(board):\n",
    "        try:\n",
    "            return (row.index(0), y)\n",
    "        except ValueError:\n",
    "            pass\n",
    "\n",
    "\n",
    "def find_all_placements(board, pieces):\n",
    "    queue = deque([(board, 1)])\n",
    "    while queue:\n",
    "        b, n = queue.popleft()\n",
    "        p = first_free(b)\n",
    "        if p is None:\n",
    "            yield b\n",
    "            continue\n",
    "        for placement in placements(b, pieces, p, n):\n",
    "            queue.append((placement, n+1))\n",
    "\n",
    "\n",
    "def print_board(board):\n",
    "    print('\\n'.join(' '.join('{: >2}'.format(x)\n",
    "                             for x in row) for row in board))\n",
    "\n",
    "def ilen(it):\n",
    "    return sum(1 for _ in it)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "there is a total of  78243  solutions\n",
      "Example solution:\n",
      " 1  1  2  2  3  4  5  6  6  7\n",
      " 8  8  9  9  3  4  5 10 10  7\n"
     ]
    }
   ],
   "source": [
    "field = tuple(tuple(0 for _ in range(10)) for _ in range(2))\n",
    "pieces = [((1,),),((1,1),),((1,),(1,))]\n",
    "f = find_all_placements(field, pieces)\n",
    "print('there is a total of ', ilen(f), ' solutions')\n",
    "f = find_all_placements(field, pieces)\n",
    "for _ in zip(range(10),f): pass\n",
    "print('Example solution:')\n",
    "print_board(next(f))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.5.2"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": "120"
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}