Akh Va'quot Shrine.ipynb

{
 "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
}