Skip to content

Instantly share code, notes, and snippets.

@cstorey
Last active July 20, 2018 11:53
Show Gist options
  • Save cstorey/05e94f825362defd5a04a1699322ca5e to your computer and use it in GitHub Desktop.
Save cstorey/05e94f825362defd5a04a1699322ca5e to your computer and use it in GitHub Desktop.
Display the source blob
Display the rendered blob
Raw
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note:\n",
"\n",
"Contains spoilers for the \"Akh Va'quot\" Shrine from Zelda: Breath of the Wild.\n",
"\n",
"See the post [Solving Zelda Puzzles Satisfactorily](https://ceri.storey.name/posts/2018-05-31-solving-zelda-puzzles-satisfactorily.html)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"from pycryptosat import Solver\n",
"import itertools"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def neg_clause(soln): return [-var if val else var for (var, val) in zip(xrange(len(soln)), soln)[1:]]\n",
"\n",
"def iter_solns(s):\n",
" while True:\n",
" satp, soln = s.solve()\n",
" #print \">\", satp, soln\n",
" if not satp:\n",
" return\n",
" yield soln\n",
" s.add_clause(neg_clause(soln))"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"def next_free_var(s):\n",
" nvars = s.nb_vars()\n",
" # Starts from 1, and we want the one after the one in use\n",
" fresh = nvars + 1\n",
" return fresh\n"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"class Fan(object):\n",
" def __init__(self, name, solver):\n",
" self.name = name\n",
" fvar = next_free_var(solver)\n",
" self.nesw = range(fvar, fvar+4)\n",
" \n",
" N, E, S, W = self.nesw\n",
"\n",
" clauses = [[-d0, -d1] for d0 in self.nesw for d1 in self.nesw if d0 > d1]\n",
" #print clauses\n",
" solver.add_clauses(clauses)\n",
"\n",
" def show(self, soln):\n",
" return \"{}:{}\".format(\n",
" self.name, \",\".join(d for v, d in zip(self.nesw, \"NESW\") if soln[v]))\n",
"\n",
" def __repr__(self):\n",
" return \"<Fan: {};{}>\".format(self.name, self.nesw)\n"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"---\n",
"(0, 0):E\n",
"(0, 3):E\n",
"(2, 1):W\n",
"(3, 0):S\n",
"(3, 2):W\n",
"(4, 3):N\n",
"\n"
]
}
],
"source": [
"def offsets(x, y, dx, dy):\n",
" while True:\n",
" x += dx\n",
" y += dy\n",
" yield x, y\n",
"\"\"\"\n",
"01234\n",
"F..F. # 0\n",
"..F.. # 1\n",
"...F. # 2\n",
"F...F # 3\n",
"\"\"\"\n",
"xsize = 5\n",
"ysize = 4\n",
"s = Solver()\n",
"\n",
"NORTH, EAST, SOUTH, WEST = range(4)\n",
"\n",
"fans = {\n",
" pos: Fan(pos, s)\n",
" for pos in [(0, 0), (3, 0), (2, 1), (3, 2), (0, 3), (4, 3)]\n",
"}\n",
"\n",
"cells = frozenset([(x, y) for x in xrange(xsize) for y in xrange(ysize)])\n",
"# print \"cells\", sorted(cells)\n",
"turbines = cells - set(fans.keys())\n",
"# print \"turbines\", sorted(turbines)\n",
" \n",
"for x, y in sorted(turbines):\n",
" # First, state that each turbine location is true\n",
" # iff any of the fans impacting the location are oriented\n",
" # correctly\n",
" \n",
" # Because a fan that we can see Northwards of a turbine will be blowing south,\n",
" # etc, we use the \"opposite\" fan variable.\n",
" \n",
" # Looking Northwards\n",
" norths = []\n",
" #print \"Northwards\",(x, y), list(itertools.islice(offsets(x, y, 0, -1), 5))\n",
" for pos in itertools.islice(offsets(x, y, 0, -1), 5):\n",
" #print \"Northwards\", pos, pos in fans\n",
" if pos in fans:\n",
" #print(\"turbine\", (x,y), \"<= N\", fans[pos])\n",
" norths.append(fans[pos].nesw[SOUTH])\n",
"\n",
" # Looking Eastwards\n",
" easts = []\n",
" #print \"Eastwards\",(x, y), list(itertools.islice(offsets(x, y, 1, 0), 5))\n",
"\n",
" for pos in itertools.islice(offsets(x, y, 1, 0), 5):\n",
" if pos in fans:\n",
" #print(\"turbine\", (x,y), \"<= E\", fans[pos])\n",
" easts.append(fans[pos].nesw[WEST])\n",
" # Looking South\n",
" souths = []\n",
" #print \"South\",(x, y), list(itertools.islice(offsets(x, y, 0, 1), 5))\n",
"\n",
" for pos in itertools.islice(offsets(x, y, 0, 1), 5):\n",
" if pos in fans:\n",
" #print(\"turbine\", (x,y), \"<= S\", fans[pos])\n",
" souths.append(fans[pos].nesw[NORTH])\n",
" \n",
" # Looking West\n",
" wests = []\n",
" #print \"West\",(x, y), list(itertools.islice(offsets(x, y, -1, 0), 5))\n",
" for pos in itertools.islice(offsets(x, y, -1, 0), 5):\n",
" if pos in fans:\n",
" #print(\"turbine\", (x,y), \"<= W\", fans[pos])\n",
" wests.append(fans[pos].nesw[EAST])\n",
" \n",
" compass = norths + easts + souths + wests\n",
" # Double check that we have some fan covering this turbine\n",
" assert compass\n",
" #print x, y, \"N\", norths, \"E\", easts, \"S\", souths, \"W\", wests\n",
" s.add_clause(compass)\n",
"\n",
" \n",
"for x in itertools.islice(iter_solns(s), 10):\n",
" print \"---\"\n",
" for pos, fan in sorted(fans.items()):\n",
" print fan.show(x)\n",
" print"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.13"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment