Skip to content

Instantly share code, notes, and snippets.

@robo-corg

robo-corg/Color Square Isolation.ipynb

Created January 28, 2016 20:57
Show Gist options
  • Save robo-corg/2269ef76603263ce1061 to your computer and use it in GitHub Desktop.
Save robo-corg/2269ef76603263ce1061 to your computer and use it in GitHub Desktop.
Download ZIP
Solves the isolate the color witness puzzles
Display the source blob
Display the rendered blob
Raw
Color Square Isolation.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import networkx as nx"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Generate graphs of the paths in the maze. As well as square_graph that will be used for determining what colored squared exisit in the space between the normal graph.\n",
"\n",
"Example 3x3\n",
"\n",
"graph:\n",
"\n",
" v-v-v\n",
" |s|s|\n",
" v-v-v\n",
" |s|s|\n",
" v-v-v\n",
"\n",
"s = nodes from square graph\n",
"\n",
"square_graph:\n",
"\n",
" v-v\n",
" | |\n",
" v-v\n"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def geneate_grid_graphs(width, height):\n",
" graph = nx.Graph()\n",
" square_graph = nx.Graph()\n",
"\n",
" for x in range(width+1):\n",
" for y in range(height+1):\n",
" graph.add_node((x,y))\n",
"\n",
" for x in range(width):\n",
" for y in range(height):\n",
"\n",
"\n",
" for bx in range(2):\n",
" for by in range(2):\n",
" if bx == 1 and by == 1:\n",
" continue\n",
"\n",
" vx = x + bx\n",
" vy = y + by\n",
"\n",
" if vx < width and vy < height:\n",
" square_graph.add_edge(\n",
" (x,y),\n",
" (vx,vy)\n",
" )\n",
"\n",
" if vx < width:\n",
" graph.add_edge((vx, vy), (vx+1, vy))\n",
"\n",
" if vy < height:\n",
" graph.add_edge((vx, vy), (vx, vy+1))\n",
" \n",
" return graph, square_graph"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%matplotlib inline\n",
"\n",
"import matplotlib.pyplot as plt\n",
"import numpy\n",
"\n",
"def draw_graph(graph, *args, **kwargs):\n",
" pos = {\n",
" node: numpy.array(node)\n",
" for node in graph.nodes()\n",
" }\n",
"\n",
" nx.draw(graph, pos, *args, **kwargs)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAeIAAAFBCAYAAACrYazjAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAADy9JREFUeJzt3T9PW+ffx/HvudUBLFCUSiC2SGlEJ5hw186QLHRrUtpk\n6ZqtFY/AU1OxWKKTA1LWLm3yHDATbETqkNGoRBGV7O3cQ/+ov6hQDId8e8Wvl3RGW1fyOdJbjk7s\nqq7rOgCAFP+XfQAAmGRCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkx\nACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERC\nDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkOiD7AO8\nzwaDQez0enF0cBC/vXkTMzduxOLycnz16FHMzc1lH4+32Kss9iqLvc5W1XVdZx/ifdPv92Or04mf\nX7yIzyKiPRrFbEScRsTe9HT8WNdxd3U1Hm9uRrvdTj4t9iqLvcpirwuoadR2t1svtFr191VVn0TU\n9T9cJxH1k6qqF1qtervbzT7yRLNXWexVFntdjBA3aLvbrW+3WvXLM264t6+XEfXtCb75stmrLPYq\ni70uTogbsre3Vy+McdP9/eZbaLXqfr+f/UeYKPYqi73KYq/xeGq6IVudTnw7HMadMV93JyK+GQ5j\nq9O5jmNxBnuVxV5lsdd4PKzVgMFgEB/fuhW/jEZx8xKvP4mIj6am4ujVq4l/evBdsFdZ7FUWe43P\nJ+IG7PR6sR5xqZsuIuLDiFivqtjp9Zo7FGeyV1nsVRZ7jU+IG3B0cBCfjEZXeo/2cBhHh4cNnYjz\n2Kss9iqLvcbnCz0a8NubNzF7xfeYjYhnu7vxw+5uE0fiHDMR8ekV38Ne7469ytLUXqevXzdwmjL4\nRNyAmRs34vSK73EaEfc3NqL+/Ul21zVenz94YK+CLnuVdTW11+zNy/7jdnmEuAGLy8uxNzV1pffo\nT0/H4tJSQyfiPPYqi73KYq/xeWq6AZ4SLIu9ymKvsthrfD4RN2B+fj7urq7G06q61OufVlXcW1ub\nmJsum73KYq+y2OsSahrhm2TKYq+y2Kss9hqPEDfId6uWxV5lsVdZ7HVxQtywP39t5Mk5vzbya0T9\n3YT/2sh/hb3KYq+y2OtiPKx1Dfb392Or04mfnj+P9aqK9nD41+9v9v/4/c17a2vxeHMzVlZWso87\n8exVFnuVxV7/Toiv0fHxcez0enF0eBjPdnfj/sZGLC4txZcPH07WgwiFsFdZ7FUWe51NiN+RqqrC\nX3U57FUWe5XFXv/Lf18CgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgA\nEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEG\ngERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiI\nASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACT6\nIPsA77PBYBA7vV4cHRzETER8/cUXsbi8HF89ehRzc3PZx+Mt9iqLvcpir7NVdV3X2Yd43/T7/djq\ndOLnFy/is4hoj0YxGxGnEbE3PR0/1nXcXV2Nx5ub0W63k0+Lvcpir7LY6wJqGrXd7dYLrVb9fVXV\nJxF1/Q/XSUT9pKrqhVar3u52s4880exVFnuVxV4XI8QN2u5269utVv3yjBvu7etlRH17gm++bPYq\ni73KYq+LE+KG7O3t1Qtj3HR/v/kWWq263+9n/xEmir3KYq+y2Gs8nppuyFanE98Oh3FnzNfdiYhv\nhsPY6nSu41icwV5lsVdZ7DUeD2s1YDAYxMe3bsUvo1HcvMTrTyLio6mpOHr1auKfHnwX7FUWe5XF\nXuPzibgBO71erEdc6qaLiPgwItarKnZ6veYOxZnsVRZ7lcVe4xPiBhwdHMQno9GV3qM9HMbR4WFD\nJ+I89iqLvcpir/H5Qo8G/PbmTcxe8T1mI+LZ7m78sLvbxJE4x0xEfHrF97DXu2OvsjS11+nr1w2c\npgw+ETdg5saNOL3ie5xGxP2Njah/f5LddY3X5w8e2Kugy15lXU3tNXvzsv+4XR4hbsDi8nLsTU1d\n6T3609OxuLTU0Ik4j73KYq+y2Gt8nppugKcEy2KvstirLPYan0/EDZifn4+7q6vxtKou9fqnVRX3\n1tYm5qbLZq+y2Kss9rqEmkb4Jpmy2Kss9iqLvcYjxA3y3aplsVdZ7FUWe12cEDfsz18beXLOr438\nGlF/N+G/NvJfYa+y2Kss9roYD2tdg/39/djqdOKn589jvaqiPRz+9fub/T9+f/Pe2lo83tyMlZWV\n7ONOPHuVxV5lsde/E+JrdHx8HDu9XhwdHsaz3d24v7ERi0tL8eXDh5P1IEIh7FUWe5XFXmcT4nek\nqqrwV10Oe5XFXmWx1//y35cAIJEQA0AiIQaAREIMAImEGAASCTEAJBJiAEgkxACQSIgBIJEQA0Ai\nIQaAREIMAImEGAASCTEAJBJiAEgkxACQSIgBIJEQA0AiIQaAREIMAImEGAASCTEAJBJiAEgkxACQ\nSIgBIJEQA0AiIQaAREIMAImEGAASCTEAJBJiAEgkxACQSIgBIJEQA0AiIQaAREIMAImEGAASCTEA\nJBJiAEgkxACQSIgBIJEQA0AiIQaAREIMAImEGAASCTEAJBJiAEgkxACQSIgBIJEQA0AiIQaAREIM\nAIk+yD7A+2wwGMROrxdHBwcxExFff/FFLC4vx1ePHsXc3Fz28XiLvcpir7LY62xVXdd19iHeN/1+\nP7Y6nfj5xYv4LCLao1HMRsRpROxNT8ePdR13V1fj8eZmtNvt5NNir7LYqyz2uoCaRm13u/VCq1V/\nX1X1SURd/8N1ElE/qap6odWqt7vd7CNPNHuVxV5lsdfFCHGDtrvd+narVb8844Z7+3oZUd+e4Jsv\nm73KYq+y2OvihLghe3t79cIYN93fb76FVqvu9/vZf4SJYq+y2Kss9hqPp6YbstXpxLfDYdwZ83V3\nIuKb4TC2Op3rOBZnsFdZ7FUWe43Hw1oNGAwG8fGtW/HLaBQ3L/H6k4j4aGoqjl69mvinB98Fe5XF\nXmWx1/h8Im7ATq8X6xGXuukiIj6MiPWqip1er7lDcSZ7lcVeZbHX+IS4AUcHB/HJaHSl92gPh3F0\neNjQiTiPvcpir7LYa3y+0KMBv715E7NXfI/ZiHi2uxs/7O42cSTOMRMRn17xPez17tirLE3tdfr6\ndQOnKYNPxA2YuXEjTq/4HqcRcX9jI+rfn2R3XeP1+YMH9irosldZV1N7zd687D9ul0eIG7C4vBx7\nU1NXeo/+9HQsLi01dCLOY6+y2Kss9hqfp6Yb4CnBstirLPYqi73G5xNxA+bn5+Pu6mo8rapLvf5p\nVcW9tbWJuemy2ass9iqLvS6hphG+SaYs9iqLvcpir/EIcYN8t2pZ7FUWe5XFXhcnxA3789dGnpzz\nayO/RtTfTfivjfxX2Kss9iqLvS7Gw1rXYH9/P7Y6nfjp+fNYr6poD4d//f5m/4/f37y3thaPNzdj\nZWUl+7gTz15lsVdZ7PXvhPgaHR8fx06vF0eHh/Fsdzfub2zE4tJSfPnw4WQ9iFAIe5XFXmWx19mE\n+B2pqir8VZfDXmWxV1ns9b/89yUASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTE\nAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJ\nMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBE\nQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEg\nkRADQKIPsg/wPhsMBrHT68XRwUHMRMTXX3wRi8vL8dWjRzE3N5d9PN5ir7LYqyz2OltV13WdfYj3\nTb/fj61OJ35+8SI+i4j2aBSzEXEaEXvT0/FjXcfd1dV4vLkZ7XY7+bTYqyz2Kou9LqCmUdvdbr3Q\natXfV1V9ElHX/3CdRNRPqqpeaLXq7W43+8gTzV5lsVdZ7HUxQtyg7W63vt1q1S/PuOHevl5G1Lcn\n+ObLZq+y2Kss9ro4IW7I3t5evTDGTff3m2+h1ar7/X72H2Gi2Kss9iqLvcbjqemGbHU68e1wGHfG\nfN2diPhmOIytTuc6jsUZ7FUWe5XFXuPxsFYDBoNBfHzrVvwyGsXNS7z+JCI+mpqKo1evJv7pwXfB\nXmWxV1nsNT6fiBuw0+vFesSlbrqIiA8jYr2qYqfXa+5QnMleZbFXWew1PiFuwNHBQXwyGl3pPdrD\nYRwdHjZ0Is5jr7LYqyz2Gp8v9GjAb2/exOwV32M2Ip7t7sYPu7tNHIlzzETEp1d8D3u9O/YqS1N7\nnb5+3cBpyuATcQNmbtyI0yu+x2lE3N/YiPr3J9ld13h9/uCBvQq67FXW1dReszcv+4/b5RHiBiwu\nL8fe1NSV3qM/PR2LS0sNnYjz2Kss9iqLvcbnqekGeEqwLPYqi73KYq/x+UTcgPn5+bi7uhpPq+pS\nr39aVXFvbW1ibrps9iqLvcpir0uoaYRvkimLvcpir7LYazxC3CDfrVoWe5XFXmWx18UJccP+/LWR\nJ+f82sivEfV3E/5rI/8V9iqLvcpir4vxsNY12N/fj61OJ356/jzWqyraw+Ffv7/Z/+P3N++trcXj\nzc1YWVnJPu7Es1dZ7FUWe/07Ib5Gx8fHsdPrxdHhYZy+fh2zN2/G4tJSfPnw4WQ9iFAIe5XFXmWx\n19mEGAAS+e9LAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBE\nQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEg\nkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIA\nSCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABL9P3dMwirfNZZ7AAAAAElFTkSuQmCC\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x10945ada0>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"draw_graph(geneate_grid_graphs(3, 3)[0])"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"([(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)],\n",
" [(0, 0), (0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2)],\n",
" [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)],\n",
" [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)],\n",
" [(0, 0), (0, 1), (0, 2), (1, 2), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2)],\n",
" [(0, 0), (0, 1), (0, 2), (1, 2), (1, 1), (2, 1), (2, 2)],\n",
" [(0, 0), (1, 0), (2, 0), (2, 1), (1, 1), (0, 1), (0, 2), (1, 2), (2, 2)],\n",
" [(0, 0), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (2, 2)],\n",
" [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)],\n",
" [(0, 0), (1, 0), (1, 1), (0, 1), (0, 2), (1, 2), (2, 2)],\n",
" [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)],\n",
" [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)])"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tuple(nx.all_simple_paths(geneate_grid_graphs(2, 2)[0], (0,0), (2,2)))"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"((-1, 0), (0, 0))"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def add_node(a, b):\n",
" return (\n",
" a[0] + b[0],\n",
" a[1] + b[1]\n",
" )\n",
"\n",
"def sub_node(a, b):\n",
" return (\n",
" a[0] - b[0],\n",
" a[1] - b[1]\n",
" )\n",
"\n",
"def get_separating_edge_from_square_edge(edge):\n",
" edge = tuple(sorted(edge))\n",
" delta = sub_node(*edge)\n",
" a = (-1, 0) if delta[0] == 0 else (0, -1)\n",
" \n",
"\n",
" return (\n",
" add_node(edge[0], a),\n",
" edge[0]\n",
" )\n",
"\n",
"get_separating_edge_from_square_edge(((0, 0), (0, 1)))"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(((-1, 0), (0, 0)), ((0, 0), (0, 1)), ((0, 1), (1, 1)), ((1, 1), (1, 2)))"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"test_path = [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)]\n",
"\n",
"path_edges = tuple(zip(test_path, test_path[1:]))\n",
"\n",
"tuple(map(\n",
" get_separating_edge_from_square_edge,\n",
" path_edges\n",
"))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Creates a variant of square_graph deleting edges where the given path \"blocks\" the connection. We use this later to determine if the colors are actually isolated form each other."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def get_connections_from_path(square_graph, path):\n",
" connections_from_path = square_graph.copy()\n",
"\n",
" path_edges = tuple(zip(path, path[1:]))\n",
"\n",
" for connection in map(get_separating_edge_from_square_edge, path_edges):\n",
" if connections_from_path.has_edge(*connection):\n",
" connections_from_path.remove_edge(*connection)\n",
" \n",
" return connections_from_path\n"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"colors = dict([\n",
" ((0,0), 1),\n",
" ((1,0), 2)\n",
"])\n",
"\n",
"def are_colors_isolated(connections_from_path, colors):\n",
" color_test_graph = connections_from_path.copy()\n",
"\n",
" components = tuple(nx.connected_components(color_test_graph))\n",
"\n",
" colors_per_component = tuple(\n",
" len(set(filter(None, map(colors.get, component)))) > 1\n",
" for component in components\n",
" )\n",
"\n",
" return not any(colors_per_component)\n"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"([(0, 0), (0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2)],\n",
" [(0, 0), (0, 1), (0, 2), (1, 2), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2)],\n",
" [(0, 0), (1, 0), (1, 1), (0, 1), (0, 2), (1, 2), (2, 2)],\n",
" [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)],\n",
" [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)])"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from functools import partial\n",
"\n",
"graph, square_graph = geneate_grid_graphs(2, 2)\n",
"\n",
"colors = dict([\n",
" ((0, 0), 1),\n",
" ((1, 0), 2)\n",
"])\n",
"\n",
"tuple(\n",
" path\n",
" for path in nx.all_simple_paths(graph, (0,0), (2,2))\n",
" if are_colors_isolated(get_connections_from_path(square_graph, path), colors)\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Solves the puzzle by finding all paths on the grid and checking if they are legal solutions using are_colors_isolated"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def solve_color_isolation_maze(width, height, colors, start, end):\n",
" graph, square_graph = geneate_grid_graphs(width, height)\n",
"\n",
" valid_paths_iter = (\n",
" path\n",
" for path in nx.all_simple_paths(graph, start, end)\n",
" if are_colors_isolated(get_connections_from_path(square_graph, path), colors)\n",
" )\n",
"\n",
" return graph, valid_paths_iter"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solving complex puzzle\n",
"\n",
"Turns out it has no solution!"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"ename": "StopIteration",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mStopIteration\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-20-6b269edb1390>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 21\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 22\u001b[0m \u001b[0mgraph\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpaths\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msolve_color_isolation_maze\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcolors\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 23\u001b[0;31m \u001b[0mpath\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpaths\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 24\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 25\u001b[0m \u001b[0mget_ipython\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmagic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'matplotlib inline'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mStopIteration\u001b[0m: "
]
}
],
"source": [
"import numpy\n",
"\n",
"colors = dict([\n",
" ((0, 0), 1),\n",
" ((1, 0), 1),\n",
" ((1, 1), 1),\n",
" ((0, 1), 1),\n",
" ((2, 0), 2),\n",
" ((3, 0), 2),\n",
" ((2, 1), 3),\n",
" ((3, 1), 3),\n",
" ((0, 2), 4),\n",
" ((1, 2), 4),\n",
" ((2, 2), 4),\n",
" ((3, 2), 1),\n",
" ((0, 3), 5),\n",
" ((1, 3), 6),\n",
" ((2, 3), 6),\n",
" ((3, 3), 6),\n",
"])\n",
"\n",
"graph, paths = solve_color_isolation_maze(4, 4, colors, (0, 0), (4, 4))\n",
"path = next(paths)\n",
"\n",
"%matplotlib inline\n",
"\n",
"import matplotlib.pyplot as plt\n",
"\n",
"#pos=nx.spring_layout(graph,iterations=500)\n",
"pos = {\n",
" node: numpy.array(node)\n",
" for node in graph.nodes()\n",
"}\n",
"\n",
"path_edges = set(map(tuple, map(sorted, zip(path, path[1:]))))\n",
"\n",
"normalized_edges = tuple(map(tuple, map(sorted, graph.edges())))\n",
"\n",
"edges = normalized_edges\n",
" \n",
"edge_colors = [\n",
" 'b' if edge in path_edges else 'grey'\n",
" for edge in edges\n",
"]\n",
"\n",
"nx.draw(graph,pos,node_color='k',edges=edges, edge_color=edge_colors, node_size=0,with_labels=False)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Simple Puzzle\n",
"\n",
"Known working solution (intially buggy)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAeIAAAFBCAYAAACrYazjAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAABgJJREFUeJzt2MFx00AAhtEVk3voIOnAJZhOTAcpQWwJdOBUAqkkuANS\ngTgw3HXis8fvVfCPVtI3s8u2bdsAABKf6gEAcM+EGABCQgwAISEGgJAQA0BIiAEgJMQAEBJiAAgJ\nMQCEhBgAQkIMACEhBoCQEANASIgBICTEABASYgAICTEAhIQYAEJCDAAhIQaAkBADQEiIASAkxAAQ\nEmIACAkxAISEGABCQgwAISEGgJAQA0BIiAEgJMQAEBJiAAgJMQCEhBgAQkIMACEhBoCQEANASIgB\nICTEABASYgAICTEAhIQYAEJCDAAhIQaAkBADQEiIASAkxAAQeqgH3Ivz+Twul0s9g51+/DiNt7fn\negY7nU4/x+vrl3oGO51Ov8b5/FzPuBpC/J9cLpexrms9g52+fRtj2+oV7DXn29i2L/UMdprzdYzh\nf/iPq2kACAkxAISEGABCQgwAISEGgJAQA0BIiAEgJMQAEBJiAAgJMQCEhBgAQkIMACEhBoCQEANA\nSIgBICTEABASYgAICTEAhIQYAEJCDAAhIQaAkBADQEiIASAkxAAQEmIACAkxAISEGABCQgwAISEG\ngJAQA0BIiAEgJMQAEBJiAAgJMQCEhBgAQkIMACEhBoCQEANASIgBICTEABASYgAICTEAhIQYAEJC\nDAAhIQaAkBADQEiIASAkxAAQEmIACAkxAISEGABCQgwAISEGgJAQA0BIiAEgJMQAEBJiAAgJMQCE\nhBgAQkIMACEhBoCQEANASIgBICTEABASYgAICTEAhIQYAEJCDAAhIQaAkBADQOihHnAvHh8fx5yz\nnsFOLy9PY1m+1jPY6e951SvY63g8jXWtV1wPIf5PPj4+xurNuxlzzrFt9Qr2mvPivG7IsjzXE66K\nq2kACAkxAISEGABCQgwAISEGgJAQA0BIiAEgJMQAEBJiAAgJMQCEhBgAQkIMACEhBoCQEANASIgB\nICTEABASYgAICTEAhIQYAEJCDAAhIQaAkBADQEiIASAkxAAQEmIACAkxAISEGABCQgwAISEGgJAQ\nA0BIiAEgJMQAEBJiAAgJMQCEhBgAQkIMACEhBoCQEANASIgBICTEABASYgAICTEAhIQYAEJCDAAh\nIQaAkBADQEiIASAkxAAQEmIACAkxAISEGABCQgwAISEGgJAQA0BIiAEgJMQAEBJiAAgJMQCEhBgA\nQkIMACEhBoCQEANASIgBICTEABASYgAICTEAhIQYAEJCDAAhIQaAkBADQOihHnAv3t+PY1nqFex1\nOh3GnLOewU7v7wff1w05Hn+NMZ7jFddj2bZtq0fcg2UZw5O+Hc7rtjiv2zLnHOu61jOuhqtpAAgJ\nMQCEhBgAQkIMACEhBoCQEANASIgBICTEABASYgAICTEAhIQYAEJCDAAhIQaAkBADQEiIASAkxAAQ\nEmIACAkxAISEGABCQgwAISEGgJAQA0BIiAEgJMQAEBJiAAgJMQCEhBgAQkIMACEhBoCQEANASIgB\nICTEABASYgAICTEAhIQYAEJCDAAhIQaAkBADQEiIASAkxAAQEmIACAkxAISEGABCQgwAISEGgJAQ\nA0BIiAEgJMQAEBJiAAgJMQCEhBgAQkIMACEhBoCQEANASIgBICTEABASYgAICTEAhIQYAEJCDAAh\nIQaAkBADQEiIASAkxAAQEmIACAkxAISEGABCQgwAISEGgJAQA0DooR5wL9b155jzrZ7BTofDy1iW\nz/UMdjocfo85v9cz2Onp6amecFWWbdu2egQA3CtX0wAQEmIACAkxAISEGABCQgwAISEGgJAQA0BI\niAEgJMQAEBJiAAgJMQCEhBgAQkIMACEhBoCQEANASIgBICTEABASYgAICTEAhIQYAEJCDAAhIQaA\nkBADQEiIASAkxAAQEmIACAkxAISEGABCQgwAISEGgJAQA0BIiAEgJMQAEBJiAAgJMQCEhBgAQkIM\nACEhBoCQEANASIgBICTEABASYgAICTEAhIQYAEJCDAAhIQaAkBADQEiIASAkxAAQEmIACAkxAISE\nGABCQgwAISEGgJAQA0DoD398U/iRCM5fAAAAAElFTkSuQmCC\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x109512cf8>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import numpy\n",
"\n",
"colors = dict([\n",
" ((0, 0), 1),\n",
" ((2, 0), 2),\n",
" ((2, 2), 3),\n",
" ((0, 2), 4),\n",
"])\n",
"\n",
"graph, paths = solve_color_isolation_maze(3, 3, colors, (0, 0), (3, 3))\n",
"path = next(paths)\n",
"\n",
"%matplotlib inline\n",
"\n",
"import matplotlib.pyplot as plt\n",
"\n",
"#pos=nx.spring_layout(graph,iterations=500)\n",
"pos = {\n",
" node: numpy.array(node)\n",
" for node in graph.nodes()\n",
"}\n",
"\n",
"path_edges = set(map(tuple, map(sorted, zip(path, path[1:]))))\n",
"\n",
"normalized_edges = tuple(map(tuple, map(sorted, graph.edges())))\n",
"\n",
"edges = normalized_edges\n",
" \n",
"edge_colors = [\n",
" 'b' if edge in path_edges else 'grey'\n",
" for edge in edges\n",
"]\n",
"\n",
"nx.draw(graph,pos,node_color='k',edges=edges, edge_color=edge_colors, node_size=0,with_labels=False)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Debuggin Simple puzzle\n",
"\n",
"Take a known working solution and debug are_colors_isolated"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import numpy\n",
"\n",
"colors = dict([\n",
" ((0, 0), 1),\n",
" ((2, 0), 2),\n",
" ((2, 2), 3),\n",
" ((0, 2), 4),\n",
"])\n",
"\n",
"graph, square_graph = geneate_grid_graphs(3, 3)\n",
"\n",
"path = [\n",
" (0, 0),\n",
" (0, 1),\n",
" (1, 1),\n",
" (1, 0),\n",
" (2, 0),\n",
" (2, 1),\n",
" (3, 1),\n",
" (3, 2),\n",
" (2, 2),\n",
" (1, 2),\n",
" (1, 3),\n",
" (2, 3),\n",
" (3, 3)\n",
"]\n",
"\n",
"path_cons = get_connections_from_path(square_graph, path)\n",
" \n",
"are_colors_isolated(path_cons, colors)\n"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAeIAAAFBCAYAAACrYazjAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAADQNJREFUeJzt3T9oVff/x/H3+dkhOSSECAlugpW0S7LU26183SRRCnb7\nttUqFMHJrSXQIU53CS1ZUvKdrgl07dBWR5FuXqdki9LBMUJCiHgzCOc7fKX0T4qak+R97i+PB9zN\ne/lAX8en53KaFFVVVQEApPi/7AMAwHEmxACQSIgBIJEQA0AiIQaAREIMAImEGAASCTEAJBJiAEgk\nxACQSIgBIJEQA0AiIQaAREIMAImEGAASCTEAJBJiAEgkxACQSIgBIJEQA0AiIQaAREIMAImEGAAS\nCTEAJBJiAEgkxACQSIgBIJEQA0AiIQaAREIMAImEGAASCTEAJBJiAEgkxACQSIgBIJEQA0AiIQaA\nREIMAImEGAASCTEAJBJiAEgkxACQSIgBIJEQA0AiIQaAREIMAImEGAASCTEAJBJiAEgkxACQ6J3s\nA/B6GxsbsdzpxPrqajzf3o6hkZGYmJqKL65fj7Gxsezj0XD2Qx32c/iKqqqq7EOwt263Gwvtdvxy\n7158EhGt3d0YjoidiHg4OBg/VlVcnJ6OW7Oz0Wq1kk9L09gPddjPEapopKXFxepUWVbfFUW1GVFV\ne7w2I6pvi6I6VZbV0uJi9pFpEPuhDvs5WkLcQEuLi9WZsqwe/8MF8NfX44jqjIuBV+yHOuzn6Plq\numG63W58fP58/PriRZx9i/c9iYiPyjJ+evAgzp07d1jHo+HshzrsJ4enphtmod2Or3u9t7oIIiLO\nRsRXvV4stNuHcSz6hP1Qh/3kcEfcIBsbG/He6dPx2+5ujO7j/ZsR8e7AQKw/feppxmPIfqjDfvK4\nI26Q5U4nLkfs6yKIiDgZEZeLIpY7nYM7FH3DfqjDfvIIcYOsr67Gh7u7tT6j1evF+traAZ2IfmI/\n1GE/efxAjwZ5vr0dwzU/Yzgidra2DuI49JmD2s8PKyvxn5WVgzgSfWQoIv5V8zP8/bM/7ogbZGhk\nJHZqfsZORAyP7vfLJfrZQe3n0ytXovrf/9rodYxe//7sM3//JBHiBpmYmoqHAwO1PqM7OBgTk5MH\ndCL6if1Qh/3k8dR0g3hqkTrshzrsJ4874gYZHx+Pi9PTcaco9vX+O0URl2ZmXATHlP1Qh/3kcUfc\nMH6yDXXYD3XYTw53xA3TarXi9vx8XCjLePKG73kSERfKMm7Pz7sIjjn7oQ77yXFibm5uLvsQ/NkH\nrVYMnjwZV+/fjxMvX8b7ETG4x5/bjIjviyK+LMv4Zn4+bty8ecQnpYnshzrs5+j5arrBHj16FAvt\ndvx8925cLopo9Xq//z7Q7qvfB3ppZiZuzc76lyh/Yz/UYT9HR4j7wLNnz2K504n1tbX4YWUlPr1y\nJSYmJ+PqtWsejOC1/rifna2tGB4dtR/emP0cPiHuM0VRhP9kAP9/eFgLABIJMQAkEmIASCTEAJBI\niAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAk\nEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwA\niYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRAD\nQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTE\nAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJMQAkEmIASCTEAJBIiAEgkRADQCIhBoBEQgwAiYQYABIJ\nMQAkEmIASCTEAJDonewD8HobGxux3OnE+upqDEXEjc8/j4mpqfji+vUYGxvLPh4N98f9PN/ejqGR\nEfvhjdnP4SuqqqqyD8Heut1uLLTb8cu9e/FJRLR2d2M4InYi4uHgYPxYVXFxejpuzc5Gq9VKPi1N\nYz/UYT9HqKKRlhYXq1NlWX1XFNVmRFXt8dqMqL4tiupUWVZLi4vZR6ZB7Ic67OdoCXEDLS0uVmfK\nsnr8DxfAX1+PI6ozLgZesR/qsJ+j56vphul2u/Hx+fPx64sXcfYt3vckIj4qy/jpwYM4d+7cYR2P\nhrMf6rCfHJ6abpiFdju+7vXe6iKIiDgbEV/1erHQbh/GsegT9kMd9pPDHXGDbGxsxHunT8dvu7sx\nuo/3b0bEuwMDsf70qacZjyH7oQ77yeOOuEGWO524HLGviyAi4mREXC6KWO50Du5Q9A37oQ77ySPE\nDbK+uhof7u7W+oxWrxfra2sHdCL6if1Qh/3k8QM9GuT59nYM1/yM4Yj4YWUl/rOychBHoo8MRcS/\nan6G/RxfB7Wfna2tAzjN8eKOuEGGRkZip+Zn7ETEp1euRPW//zXN6xi9/v3ZZ/bjlb6f4dH9frl9\nfAlxg0xMTcXDgYFan9EdHIyJyckDOhH9xH6ow37yeGq6QTy1SB32Qx32k8cdcYOMj4/HxenpuFMU\n+3r/naKISzMzLoJjyn6ow37yuCNuGD/ZhjrshzrsJ4c74oZptVpxe34+LpRlPHnD9zyJiAtlGbfn\n510Ex5z9UIf95DgxNzc3l30I/uyDVisGT56Mq/fvx4mXL+P9iBjc489tRsT3RRFflmV8Mz8fN27e\nPOKT0kT2Qx32c/R8Nd1gjx49ioV2O36+ezcuF0W0er3ffx9o99XvA700MxO3Zmf9S5S/sR/qsJ+j\nI8R94NmzZ7Hc6cT62lrsbG3F8OhoTExOxtVr1zwYwWv9cT8/rKzEp1eu2A9vzN8/h0+I4RgpiiJc\n8tAsHtYCgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBI\nJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgA\nEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEG\ngERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiI\nASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQS\nYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACR6J/sAvN7GxkYsdzqxvroaz7e3Y2hkJCam\npuKL69djbGws+3g03B/3MxQRNz7/3H54Y/7+OXxFVVVV9iHYW7fbjYV2O365dy8+iYjW7m4MR8RO\nRDwcHIwfqyouTk/HrdnZaLVayaelaeyHOuznCFU00tLiYnWqLKvviqLajKiqPV6bEdW3RVGdKstq\naXEx+8g0iP1Qh/0cLSFuoKXFxepMWVaP/+EC+OvrcUR1xsXAK/ZDHfZz9Hw13TDdbjc+Pn8+fn3x\nIs6+xfueRMRHZRk/PXgQ586dO6zj0XD2Qx32k8NT0w2z0G7H173eW10EERFnI+KrXi8W2u3DOBZ9\nwn6ow35yuCNukI2NjXjv9On4bXc3Rvfx/s2IeHdgINafPvU04zFkP9RhP3ncETfIcqcTlyP2dRFE\nRJyMiMtFEcudzsEdir5hP9RhP3mEuEHWV1fjw93dWp/R6vVifW3tgE5EP7Ef6rCfPELcIM+3t2O4\n5mcMR8TO1tZBHIc+Yz/UYT95hLhBhkZGYqfmZ+xExPDofr9cop/ZD3XYTx4hbpCJqal4ODBQ6zO6\ng4MxMTl5QCein9gPddhPHk9NN4inFqnDfqjDfvK4I26Q8fHxuDg9HXeKYl/vv1MUcWlmxkVwTNkP\nddhPHnfEDeMn21CH/VCH/eRwR9wwrVYrbs/Px4WyjCdv+J4nEXGhLOP2/LyL4JizH+qwnxwn5ubm\n5rIPwZ990GrF4MmTcfX+/Tjx8mW8HxGDe/y5zYj4vijiy7KMb+bn48bNm0d8UprIfqjDfo6er6Yb\n7NGjR7HQbsfPd+/G5aKIVq/3++8D7b76faCXZmbi1uysf4nyN/ZDHfZzdIS4Dzx79iyWO51YX1uL\nna2tGB4djYnJybh67ZoHI3gt+6EO+zl8QgwAiTysBQCJhBgAEgkxACQSYgBIJMQAkEiIASCREANA\nIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQA\nkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkx\nACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERC\nDACJhBgAEgkxACQSYgBIJMQAkEiIASCREANAIiEGgERCDACJhBgAEv0XzjsORwl3E6wAAAAASUVO\nRK5CYII=\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x1094abba8>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"draw_graph(get_connections_from_path(square_graph, path))"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"((((0, 0), (0, 1)), ((-1, 0), (0, 0))),\n",
" (((0, 1), (1, 1)), ((0, 0), (0, 1))),\n",
" (((1, 1), (1, 0)), ((0, 0), (1, 0))),\n",
" (((1, 0), (2, 0)), ((1, -1), (1, 0))),\n",
" (((2, 0), (2, 1)), ((1, 0), (2, 0))),\n",
" (((2, 1), (3, 1)), ((2, 0), (2, 1))),\n",
" (((3, 1), (3, 2)), ((2, 1), (3, 1))),\n",
" (((3, 2), (2, 2)), ((2, 1), (2, 2))),\n",
" (((2, 2), (1, 2)), ((1, 1), (1, 2))),\n",
" (((1, 2), (1, 3)), ((0, 2), (1, 2))),\n",
" (((1, 3), (2, 3)), ((1, 2), (1, 3))),\n",
" (((2, 3), (3, 3)), ((2, 2), (2, 3))))"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tuple(\n",
" (edge, get_separating_edge_from_square_edge(edge))\n",
" for edge in tuple(zip(path, path[1:]))\n",
")"
]
},
{
"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.5.1"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment