Textbook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Imports"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's import various modules from the Python standard library to get started."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import subprocess\n",
    "import json\n",
    "import collections\n",
    "import random\n",
    "import sys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ASP Tools"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Download the clingo-4.5.0 distribution from SourceForge here: http://sourceforge.net/projects/potassco/files/clingo/4.5.0/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helper Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we'll define some helper functions for invoking the ASP tools, parsing their results, and rendering ASCII-art pictures."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def solve(*args):\n",
    "    \"\"\"Run clingo with the provided argument list and return the parsed JSON result.\"\"\"\n",
    "    \n",
    "    CLINGO = \"./clingo-4.5.0-macos-10.9/clingo\"\n",
    "    \n",
    "    clingo = subprocess.Popen(\n",
    "        [CLINGO, \"--outf=2\"] + list(args),\n",
    "        stdout=subprocess.PIPE,\n",
    "        stderr=subprocess.PIPE)\n",
    "    out, err = clingo.communicate()\n",
    "    if err:\n",
    "        print err\n",
    "        \n",
    "    return parse_json_result(out)\n",
    "\n",
    "def parse_json_result(out):\n",
    "    \"\"\"Parse the provided JSON text and extract a dict\n",
    "    representing the predicates described in the first solver result.\"\"\"\n",
    "\n",
    "    result = json.loads(out)\n",
    "    \n",
    "    assert len(result['Call']) > 0\n",
    "    assert len(result['Call'][0]['Witnesses']) > 0\n",
    "    \n",
    "    witness = result['Call'][0]['Witnesses'][0]['Value']\n",
    "    \n",
    "    class identitydefaultdict(collections.defaultdict):\n",
    "        def __missing__(self, key):\n",
    "            return key\n",
    "    \n",
    "    preds = collections.defaultdict(set)\n",
    "    env = identitydefaultdict()\n",
    "    \n",
    "    for atom in witness:\n",
    "        if '(' in atom:\n",
    "            left = atom.index('(')\n",
    "            functor = atom[:left]\n",
    "            arg_string = atom[left:]\n",
    "            try:\n",
    "                preds[functor].add( eval(arg_string, env) )\n",
    "            except TypeError:\n",
    "                pass # at least we tried...\n",
    "            \n",
    "        else:\n",
    "            preds[atom] = True\n",
    "    \n",
    "    return dict(preds)\n",
    "\n",
    "def solve_randomly(*args):\n",
    "    \"\"\"Like solve() but uses a random sign heuristic with a random seed.\"\"\"\n",
    "    args = list(args) + [\"--sign-def=3\",\"--seed=\"+str(random.randint(0,1<<30))]\n",
    "    return solve(*args) \n",
    "\n",
    "def render_ascii_dungeon(design):\n",
    "    \"\"\"Given a dict of predicates, return an ASCII-art depiction of the a dungeon.\"\"\"\n",
    "    \n",
    "    sprite = dict(design['sprite'])\n",
    "    param = dict(design['param'])\n",
    "    width = param['width']\n",
    "    glyph = dict(space='.', wall='W', altar='a', gem='g', trap='_')\n",
    "    block = ''.join([''.join([glyph[sprite.get((r,c),'space')]+' ' for c in range(width)])+'\\n' for r in range(width)])\n",
    "    return block\n",
    "\n",
    "def render_ascii_touch(design, target):\n",
    "    \"\"\"Given a dict of predicates, return an ASCII-art depiction where the player explored\n",
    "    while in the `target` state.\"\"\"\n",
    "    \n",
    "    touch = collections.defaultdict(lambda: '-')\n",
    "    for cell, state in design['touch']:\n",
    "        if state == target:\n",
    "            touch[cell] = str(target)\n",
    "    param = dict(design['param'])\n",
    "    width = param['width']\n",
    "    block = ''.join([''.join([str(touch[r,c])+' ' for c in range(width)])+'\\n' for r in range(width)])\n",
    "    return block\n",
    "\n",
    "def side_by_side(*blocks):\n",
    "    \"\"\"Horizontally merge two ASCII-art pictures.\"\"\"\n",
    "    \n",
    "    lines = []\n",
    "    for tup in zip(*map(lambda b: b.split('\\n'), blocks)):\n",
    "        lines.append(' '.join(tup))\n",
    "    return '\\n'.join(lines)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dungeon Design Space Development"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section, we'll slowly develop the full dungeon generator by defining and refining a design space definition in ASP.\n",
    "\n",
    "In the cells below, the `%%file` magic tells IPython Notebook to write the following text to the named file. The contents of these cells is AnsProlog source code, however it is mistakenly (and poorly) syntax highlighted as if it were Python code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting level-core.lp\n"
     ]
    }
   ],
   "source": [
    "%%file level-core.lp\n",
    "\n",
    "#const width=10.\n",
    "\n",
    "param(\"width\",width).\n",
    "\n",
    "dim(0..width-1).\n",
    "\n",
    "tile((X,Y)) :- dim(X); dim(Y).\n",
    "    \n",
    "adj((X1,Y1),(X2,Y2)) :- \n",
    "    tile((X1,Y1));\n",
    "    tile((X2,Y2));\n",
    "    |X1-X2| + |Y1-Y2| == 1.\n",
    "    \n",
    "start((0,0)).\n",
    "finish((width-1,width-1)).\n",
    "\n",
    "% tile at most one named sprite\n",
    "0 { sprite(T,(wall;gem;altar;trap)) } 1 :- tile(T).\n",
    "   \n",
    "% there is exactly one gem and one altar in the whole level\n",
    ":- not 1 { sprite(T,altar) } 1.\n",
    ":- not 1 { sprite(T,gem) } 1.\n",
    "    \n",
    "% there are between 2 and 5 traps in the level\n",
    ":- not 2 { sprite(T,trap) } 5.\n",
    "    \n",
    "% the start and finish are clear\n",
    ":- start(T); sprite(T,Name).\n",
    ":- finish(T); sprite(T,Name).\n",
    "    \n",
    "#show param/2.\n",
    "#show tile/1.\n",
    "#show sprite/2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one file actually works as a limited dungeon generator all by itself. Let's invoke the solver on the command line to see what it outputs for this program."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "clingo version 4.5.0\r\n",
      "Reading from level-core.lp\r\n",
      "Solving...\r\n",
      "Answer: 1\r\n",
      "param(\"width\",10) tile((0,0)) tile((1,0)) tile((2,0)) tile((3,0)) tile((4,0)) tile((5,0)) tile((6,0)) tile((7,0)) tile((8,0)) tile((9,0)) tile((0,1)) tile((1,1)) tile((2,1)) tile((3,1)) tile((4,1)) tile((5,1)) tile((6,1)) tile((7,1)) tile((8,1)) tile((9,1)) tile((0,2)) tile((1,2)) tile((2,2)) tile((3,2)) tile((4,2)) tile((5,2)) tile((6,2)) tile((7,2)) tile((8,2)) tile((9,2)) tile((0,3)) tile((1,3)) tile((2,3)) tile((3,3)) tile((4,3)) tile((5,3)) tile((6,3)) tile((7,3)) tile((8,3)) tile((9,3)) tile((0,4)) tile((1,4)) tile((2,4)) tile((3,4)) tile((4,4)) tile((5,4)) tile((6,4)) tile((7,4)) tile((8,4)) tile((9,4)) tile((0,5)) tile((1,5)) tile((2,5)) tile((3,5)) tile((4,5)) tile((5,5)) tile((6,5)) tile((7,5)) tile((8,5)) tile((9,5)) tile((0,6)) tile((1,6)) tile((2,6)) tile((3,6)) tile((4,6)) tile((5,6)) tile((6,6)) tile((7,6)) tile((8,6)) tile((9,6)) tile((0,7)) tile((1,7)) tile((2,7)) tile((3,7)) tile((4,7)) tile((5,7)) tile((6,7)) tile((7,7)) tile((8,7)) tile((9,7)) tile((0,8)) tile((1,8)) tile((2,8)) tile((3,8)) tile((4,8)) tile((5,8)) tile((6,8)) tile((7,8)) tile((8,8)) tile((9,8)) tile((0,9)) tile((1,9)) tile((2,9)) tile((3,9)) tile((4,9)) tile((5,9)) tile((6,9)) tile((7,9)) tile((8,9)) tile((9,9)) sprite((7,0),altar) sprite((2,0),gem) sprite((6,0),trap) sprite((3,6),trap) sprite((4,6),trap) sprite((7,6),trap) sprite((9,6),trap) sprite((3,0),wall) sprite((4,0),wall) sprite((8,0),wall) sprite((9,0),wall) sprite((2,1),wall) sprite((4,1),wall) sprite((8,1),wall) sprite((9,1),wall) sprite((0,2),wall) sprite((1,2),wall) sprite((4,2),wall) sprite((5,2),wall) sprite((6,2),wall) sprite((8,2),wall) sprite((0,3),wall) sprite((1,3),wall) sprite((4,3),wall) sprite((5,3),wall) sprite((6,3),wall) sprite((0,4),wall) sprite((3,4),wall) sprite((4,4),wall) sprite((5,4),wall) sprite((7,4),wall) sprite((8,4),wall) sprite((9,4),wall) sprite((1,5),wall) sprite((2,5),wall) sprite((3,5),wall) sprite((4,5),wall) sprite((7,5),wall) sprite((8,5),wall) sprite((9,5),wall) sprite((5,6),wall) sprite((8,7),wall) sprite((9,7),wall) sprite((2,8),wall) sprite((4,8),wall) sprite((6,8),wall) sprite((7,8),wall) sprite((4,9),wall) sprite((5,9),wall) sprite((8,9),wall)\r\n",
      "SATISFIABLE\r\n",
      "\r\n",
      "Models       : 1+    \r\n",
      "Calls        : 1\r\n",
      "Time         : 0.018s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)\r\n",
      "CPU Time     : 0.020s\r\n"
     ]
    }
   ],
   "source": [
    "!./clingo-4.5.0-macos-10.9/clingo level-core.lp --sign-def=3 --seed=$RANDOM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's a *description* of a dungeon map, but we'll need to render it with one of our helper functions to make it visible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". W W W W W . . W W \n",
      "W W W W . . . . . W \n",
      "a W . . W . _ W W . \n",
      "W . W . . . _ . W W \n",
      "g . W . W W W W W . \n",
      ". W W W W . _ . W W \n",
      ". . W . . W . . . W \n",
      ". W W . . . _ W . . \n",
      "W W W W W . W . W W \n",
      ". . . W W W _ W W . \n",
      "\n"
     ]
    }
   ],
   "source": [
    "design = solve_randomly(\"level-core.lp\",\"-c\",\"width=10\")\n",
    "print render_ascii_dungeon(design)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks like a rudimentary dungeon. However, the `gem` and `altar` are in strange places, walls are all over the place. We can do better if we define some style constraints that restrict the design space to more reasonable designs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting level-style.lp\n"
     ]
    }
   ],
   "source": [
    "%%file level-style.lp\n",
    "\n",
    "% style: at least half of the map has wall sprites\n",
    ":- not (width*width)/2 { sprite(T,wall) }.\n",
    " \n",
    "% style: every wall has at least two neighboring walls\n",
    ":- sprite(T1,wall); not 2 { sprite(T2,wall) : adj(T1,T2) }.\n",
    "   \n",
    "% style: altars have no surrounding sprites for two steps\n",
    ":- sprite(T1,altar); not 0 { sprite(T2,S) : adj(T1,T2) } 0.\n",
    ":- sprite(T1,altar); not 0 { sprite(T3,S) : adj(T1,T2), adj(T2,T3), T1 != T3 } 0.\n",
    "    \n",
    "% style: altars have four adjacent tiles (not on a map border)\n",
    ":- sprite(T1,altar); not 4 { adj(T1,T2) }.\n",
    "    \n",
    "% style: gems have exactly three surrounding walls\n",
    ":- sprite(T1,gem); not 3 { sprite(T2,wall) : adj(T1,T2) } 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This time, we'll invoke the solver with both programs as input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". . W W W W W W W W \n",
      ". . W . W W W . g W \n",
      ". . W _ _ W W W W W \n",
      ". . W _ . . W . . . \n",
      "W W W _ W W W W . . \n",
      "W W W . W . W W . . \n",
      ". . . . W . W W . . \n",
      "W W W _ W W . . . . \n",
      "W . W W W W . . a . \n",
      "W W W . . . . . . . \n",
      "\n"
     ]
    }
   ],
   "source": [
    "design = solve_randomly(\"level-core.lp\", \"level-style.lp\")\n",
    "print render_ascii_dungeon(design)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Any local region of the dungeon looks okay now, but, globally, the dungeons are often unplayable -- there's nothing yet to ensure there's a path from the `start` to the `finish`. Once we add the next program, we'll be seeing generated dungeons that are absolutely guaranteed to be playable because we're generating a dungeon *and* a reference solution for that dungeon at the same time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting level-sim.lp\n"
     ]
    }
   ],
   "source": [
    "%%file level-sim.lp\n",
    "\n",
    "% states:\n",
    "% 1 --> initial\n",
    "% 2 --> after picking up gem\n",
    "% 3 --> after putting gem in altar\n",
    "state(1..3).\n",
    "\n",
    "% you start in state 1\n",
    "\n",
    "touch(T,1) :- start(T).\n",
    "    \n",
    "special(T) :- sprite(T,gem).\n",
    "special(T) :- sprite(T,altar).\n",
    "\n",
    "% possible navigation paths\n",
    "{ step(T1,1,T2,2):adj(T1,T2) } 1 :- touch(T1,1); sprite(T1,gem).\n",
    "{ step(T1,2,T2,3):adj(T1,T2) } 1 :- touch(T1,2); sprite(T1,altar).\n",
    "{ step(T1,S,T2,S):adj(T1,T2) } 1 :- touch(T1,S); not special(T1); not finish(T1).\n",
    "\n",
    "touch(T2,S2) :- step(T1,S1,T2,S2).\n",
    "\n",
    "% you can't touch a wall in any state\n",
    ":- sprite(T,wall); touch(T,S).\n",
    "    \n",
    "% you can't touch a trap after picking up the gem\n",
    ":- sprite(T,trap); touch(T,S); S > 1.\n",
    "\n",
    "% the finish tile must be touched in state 3\n",
    "completed :- finish(T); touch(T,3).\n",
    ":- not completed.\n",
    "    \n",
    "#show touch/2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the program above, the `step/4` predicate works like the `prev` dict in our past search algorithms. A term like `step(T1,S1,T2,S2)` says that, in some simulated play, the player reached tile T2 in upgrade-state S2 by coming from tile T1 in upgrade-state S1. Unlike `prev`, it is only defined for the specific steps taken on a single solution path. For each possible dungeon designs, there are many solutions, so the number of possible solutions to come out of the ASP solver has just gone up significantly!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "clingo version 4.5.0\n",
      "Reading from level-core.lp ...\n",
      "Solving...\n",
      "SATISFIABLE\n",
      "\n",
      "Models       : 1+    \n",
      "Calls        : 1\n",
      "Time         : 0.254s (Solving: 0.14s 1st Model: 0.14s Unsat: 0.00s)\n",
      "CPU Time     : 0.240s\n",
      "\n",
      "real\t0m0.266s\n",
      "user\t0m0.251s\n",
      "sys\t0m0.011s\n"
     ]
    }
   ],
   "source": [
    "!time ./clingo-4.5.0-macos-10.9/clingo level-core.lp level-style.lp level-sim.lp -q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yikes, that took some time. We can do better. Let's tell the solver to use multiple threads while it is searching for a solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "clingo version 4.5.0\n",
      "Reading from level-core.lp ...\n",
      "Solving...\n",
      "SATISFIABLE\n",
      "\n",
      "Models       : 1+    \n",
      "Calls        : 1\n",
      "Time         : 0.108s (Solving: 0.01s 1st Model: 0.01s Unsat: 0.00s)\n",
      "CPU Time     : 0.130s\n",
      "Threads      : 4        (Winner: 2)\n",
      "\n",
      "real\t0m0.123s\n",
      "user\t0m0.144s\n",
      "sys\t0m0.010s\n"
     ]
    }
   ],
   "source": [
    "!time ./clingo-4.5.0-macos-10.9/clingo level-core.lp level-style.lp level-sim.lp -q --parallel-mode=4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's better. Using 4 threads gave us much more than a 4x speedup in this situation. Non-linear scaling is quite common, but it isn't guaranteed.\n",
    "\n",
    "Now how do these levels look with their generated reference solutions?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". . . . . . . . . _  1 1 - - 1 1 1 1 1 -  - - 2 2 2 2 2 2 2 -  3 3 3 3 3 3 3 3 3 - \n",
      ". . . a . . W W . .  - 1 1 - 1 - - - 1 1  2 2 2 2 2 - - - 2 2  3 3 3 - 3 3 - - 3 3 \n",
      ". . . . . . W W _ .  - - 1 1 1 - - - - 1  2 2 2 - 2 2 - - - 2  3 3 3 3 3 3 - - - 3 \n",
      "W W . . . . W . . .  - - 1 1 - - - 1 1 1  - - 2 2 2 2 - 2 2 2  - - 3 3 3 3 - 3 3 3 \n",
      "W W W W . . W . . .  - - - - - - - 1 1 1  - - - - 2 2 - 2 - -  - - - - - - - 3 3 3 \n",
      "W W W W W W W . W W  - - - - - - - 1 - -  - - - - - - - 2 - -  - - - - - - - 3 - - \n",
      "W W W W W W g . W W  - - - - - - 1 1 - -  - - - - - - - 2 - -  - - - - - - - 3 - - \n",
      "W W W W W W W . . .  - - - - - - - - - -  - - - - - - - - - -  - - - - - - - 3 3 3 \n",
      "W W W W W W W W W .  - - - - - - - - - -  - - - - - - - - - -  - - - - - - - - - 3 \n",
      "W W W W W W W W W .  - - - - - - - - - -  - - - - - - - - - -  - - - - - - - - - 3 \n",
      "   \n"
     ]
    }
   ],
   "source": [
    "design = solve_randomly(\"level-core.lp\", \"level-style.lp\", \"level-sim.lp\",\"--parallel-mode=4\")\n",
    "print side_by_side(render_ascii_dungeon(design), *[render_ascii_touch(design,i) for i in range(1,4)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the space of all dungeons and all solutions for each of those dungeons, there are a lot of silly dungeons and silly solutions. We're still missing a major constraint on the *function* of dungeon designs. They should *make* the player explore, not merely allow exploration sometimes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shortcut-Free Dungeon Generation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "According to \"Quantifying Over Play: Constraining Undesirable Solutions in Puzzle Design\" (https://adamsmith.as/papers/fdg2013_shortcuts.pdf), we need to now tell the solver which parts of our dungeon-and-solution pairs coresponds to a dungeon level design and what property we want to enforce across all possible solutions.\n",
    "\n",
    "In the little program below, we state that the sprites uniquely identify a level design. We also state that the required property (the *concept* we want the player to practice, in educational game design terms) is that the player spends at least `width` many steps in each upgrade-state and touches a trap at least once. This isn't a very exciting concept, but it does the job of making dungeons with mandatory exploration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting level-shortcuts.lp\n"
     ]
    }
   ],
   "source": [
    "%%file level-shortcuts.lp\n",
    "\n",
    "__level_design(sprite(T,Name)) :- sprite(T,Name).\n",
    "\n",
    "wander(S) :- state(S); 1 { touch(T,S):tile(T) }.\n",
    "wander_in_every_state :- wander(S):state(S).\n",
    "        \n",
    "trap_step :- touch(T,S); sprite(T,trap).\n",
    "    \n",
    "__concept :- wander_in_every_state; trap_step.\n",
    "\n",
    "        \n",
    "#show __level_design/1.\n",
    "#show __concept/0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can't just append this program to our stack and expect to see any differences right away. The `__level_design/1` and `__concept/0` don't have any special meaning in standard ASP -- that's why Smith et al. had to extend it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". . _ _ . _ . . . .  1 1 1 1 1 1 1 1 1 1  - - - - - - - - - -  - - - - - - - - - - \n",
      "W W W W W _ W W W .  - - - - - - - - - 1  - - - - - - - - - -  - - - - - - - - - - \n",
      "W W W W W W W W W .  - - - - - - - - - 1  - - - - - - - - - -  - - - - - - - - - - \n",
      "W W W W W W W W . .  - - - - - - - - 1 1  - - - - - - - - 2 2  - - - - - - - - - - \n",
      "W W W W W W W . . .  - - - - - - - - 1 1  - - - - - - - 2 2 2  - - - - - - - - - - \n",
      "W W W W W W . . a .  - - - - - - - - - 1  - - - - - - - 2 2 2  - - - - - - - - - 3 \n",
      "W W W W W W W . . .  - - - - - - - - - 1  - - - - - - - 2 2 2  - - - - - - - - 3 3 \n",
      "W _ W g . W W W . .  - - - 1 1 - - - 1 1  - - - - 2 - - - - 2  - - - - - - - - 3 - \n",
      "W W W W . W W W . .  - - - - 1 - - - 1 -  - - - - 2 - - - 2 2  - - - - - - - - 3 - \n",
      "W W W W . . . . . .  - - - - 1 1 1 1 1 -  - - - - 2 2 2 2 2 -  - - - - - - - - 3 3 \n",
      "   \n"
     ]
    }
   ],
   "source": [
    "design = solve_randomly(\"level-core.lp\", \"level-style.lp\", \"level-sim.lp\",\"level-shortcuts.lp\",\"--parallel-mode=4\")\n",
    "print side_by_side(render_ascii_dungeon(design), *[render_ascii_touch(design,i) for i in range(1,4)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A rather esoteric few lines is required to give these predicates a special meaning. Here, we're expressing a meta-program (a program for transforming programs into other programs)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting metaS.lp\n"
     ]
    }
   ],
   "source": [
    "%%file metaS.lp\n",
    "\n",
    "level_design(A) :- show(A,__level_design(_)).\n",
    "concept(A) :- show(A,__concept).\n",
    "\n",
    "criteria(0,0,0,A) :- level_design(A).\n",
    "criteria(0,0,0,-A) :- level_design(A).\n",
    "criteria(0,0,0,A) :- concept(A).\n",
    "\n",
    "optimize(0,0,incl).\n",
    "\n",
    ":- concept(A), not hold(A)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The command for using meta-programs is also tricky. We're going to form a pipeline of three processes: A | B | C. The first program, A, will read in our level-\\*.lp files and ground (but not solve) their first-order logic definitions. The second program, B, will turn the output of A into a bunch of logical facts describing the structure of the original program. The final program, C, interprets those facts using a collection of meta-programs and solves the resulting problem.\n",
    "\n",
    "Because the full command line is complex, we'll capture the logic in a shell script that we can use later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting shortcut_solver.sh\n"
     ]
    }
   ],
   "source": [
    "%%file shortcut_solver.sh\n",
    "./clingo-4.5.0-macos-10.9/gringo $@ \\\n",
    "    | ./clingo-4.5.0-macos-10.9/reify \\\n",
    "    | ./clingo-4.5.0-macos-10.9/clingo --parallel-mode=4 --outf=2 --sign-def=3 --seed=$RANDOM \\\n",
    "            - \\\n",
    "            metaS.lp \\\n",
    "            ./clingo-4.5.0-macos-10.9/examples/reify/meta*.lp 2>/dev/null"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "!chmod a+x shortcut_solver.sh"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What does `shortcut_solver.sh` output? JSON text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{\n",
      "  \"Solver\": \"clingo version 4.5.0\",\n",
      "  \"Input\": [\n",
      "    \"-\",\"metaS.lp\",\"./clingo-4.5.0-macos-10.9/examples/reify/meta.lp\",\"./clingo-4.5.0-macos-10.9/examples/reify/metaD.lp\",\"./clingo-4.5.0-macos-10.9/examples/reify/metaO.lp\"\n",
      "  ],\n",
      "  \"Call\": [\n",
      "    {\n",
      "      \"Witnesses\": [\n",
      "        {\n",
      "          \"Value\": [\n",
      "            \"__concept\", \"param(\\\"width\\\",7)\", \"__level_design(sprite((1,0),trap))\", \"__level_design(sprite((0,1),trap))\", \"__level_design(sprite((3,1),altar))\", \"__level_design(sprite((0,2),wall))\", \"__level_design(sprite((1,2),wall))\", \"__level_design(sprite((0,3),wall))\", \"__level_design(sprite((1,3),wall))\", \"__level_design(sprite((2,3),wall))\", \"__level_design(sprite((4,3),wall))\", \"__level_design(sprite((5,3),wall))\", \"__level_design(sprite((0,4),wall))\", \"__level_design(sprite((1,4),wall))\", \"__level_design(sprite((2,4),wall))\", \"__level_design(sprite((3,4),gem))\", \"__level_design(sprite((4,4),wall))\", \"__level_design(sprite((5,4),wall))\", \"__level_design(sprite((0,5),wall))\", \"__level_design(sprite((1,5),wall))\", \"__level_design(sprite((2,5),wall))\", \"__level_design(sprite((3,5),wall))\", \"__level_design(sprite((4,5),wall))\", \"__level_design(sprite((5,5),wall))\", \"__level_design(sprite((0,6),wall))\", \"__level_design(sprite((1,6),wall))\", \"__level_design(sprite((2,6),wall))\", \"__level_design(sprite((3,6),wall))\", \"__level_design(sprite((4,6),wall))\", \"__level_design(sprite((5,6),wall))\", \"tile((0,0))\", \"tile((1,0))\", \"tile((2,0))\", \"tile((3,0))\", \"tile((4,0))\", \"tile((5,0))\", \"tile((6,0))\", \"tile((0,1))\", \"tile((1,1))\", \"tile((2,1))\", \"tile((3,1))\", \"tile((4,1))\", \"tile((5,1))\", \"tile((6,1))\", \"tile((0,2))\", \"tile((1,2))\", \"tile((2,2))\", \"tile((3,2))\", \"tile((4,2))\", \"tile((5,2))\", \"tile((6,2))\", \"tile((0,3))\", \"tile((1,3))\", \"tile((2,3))\", \"tile((3,3))\", \"tile((4,3))\", \"tile((5,3))\", \"tile((6,3))\", \"tile((0,4))\", \"tile((1,4))\", \"tile((2,4))\", \"tile((3,4))\", \"tile((4,4))\", \"tile((5,4))\", \"tile((6,4))\", \"tile((0,5))\", \"tile((1,5))\", \"tile((2,5))\", \"tile((3,5))\", \"tile((4,5))\", \"tile((5,5))\", \"tile((6,5))\", \"tile((0,6))\", \"tile((1,6))\", \"tile((2,6))\", \"tile((3,6))\", \"tile((4,6))\", \"tile((5,6))\", \"tile((6,6))\", \"sprite((1,0),trap)\", \"sprite((0,1),trap)\", \"sprite((3,1),altar)\", \"sprite((0,2),wall)\", \"sprite((1,2),wall)\", \"sprite((0,3),wall)\", \"sprite((1,3),wall)\", \"sprite((2,3),wall)\", \"sprite((4,3),wall)\", \"sprite((5,3),wall)\", \"sprite((0,4),wall)\", \"sprite((1,4),wall)\", \"sprite((2,4),wall)\", \"sprite((3,4),gem)\", \"sprite((4,4),wall)\", \"sprite((5,4),wall)\", \"sprite((0,5),wall)\", \"sprite((1,5),wall)\", \"sprite((2,5),wall)\", \"sprite((3,5),wall)\", \"sprite((4,5),wall)\", \"sprite((5,5),wall)\", \"sprite((0,6),wall)\", \"sprite((1,6),wall)\", \"sprite((2,6),wall)\", \"sprite((3,6),wall)\", \"sprite((4,6),wall)\", \"sprite((5,6),wall)\", \"touch((0,0),1)\", \"touch((0,1),1)\", \"touch((2,0),1)\", \"touch((1,1),1)\", \"touch((2,0),2)\", \"touch((3,0),1)\", \"touch((2,1),1)\", \"touch((3,0),2)\", \"touch((2,1),2)\", \"touch((3,0),3)\", \"touch((4,0),1)\", \"touch((4,0),2)\", \"touch((3,1),2)\", \"touch((2,2),2)\", \"touch((4,0),3)\", \"touch((4,1),1)\", \"touch((3,2),1)\", \"touch((5,0),2)\", \"touch((4,1),2)\", \"touch((3,2),2)\", \"touch((4,1),3)\", \"touch((5,1),1)\", \"touch((4,2),1)\", \"touch((3,3),1)\", \"touch((6,0),2)\", \"touch((4,2),2)\", \"touch((3,3),2)\", \"touch((4,2),3)\", \"touch((6,1),1)\", \"touch((5,2),1)\", \"touch((3,4),1)\", \"touch((6,1),2)\", \"touch((5,2),2)\", \"touch((5,2),3)\", \"touch((6,2),1)\", \"touch((6,2),2)\", \"touch((6,2),3)\", \"touch((6,3),3)\", \"touch((6,4),3)\", \"touch((6,5),3)\", \"touch((6,6),3)\"\n",
      "          ]\n",
      "        }\n",
      "      ]\n",
      "    }\n",
      "  ],\n",
      "  \"Result\": \"SATISFIABLE\",\n",
      "  \"Models\": {\n",
      "    \"Number\": 1,\n",
      "    \"More\": \"yes\"\n",
      "  },\n",
      "  \"Calls\": 1,\n",
      "  \"Time\": {\n",
      "    \"Total\": 0.962,\n",
      "    \"Solve\": 0.062,\n",
      "    \"Model\": 0.061,\n",
      "    \"Unsat\": 0.000,\n",
      "    \"CPU\": 1.060\n",
      "  },\n",
      "  \"Threads\": 4,\n",
      "  \"Winner\": 0\n",
      "}\n",
      "\n",
      "real\t0m1.056s\n",
      "user\t0m1.165s\n",
      "sys\t0m0.069s\n"
     ]
    }
   ],
   "source": [
    "!time ./shortcut_solver.sh -c width=7 level*.lp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's use the shorcut solver to process our dungeon generation rules (including `level-shortcuts.lp`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". W W . . . . .  1 - - 1 1 1 1 1  - - - - 2 2 2 2  - - - 3 3 3 3 3 \n",
      "_ W W . . W W .  1 - - 1 1 - - 1  - - - - 2 - - 2  - - - 3 - - - 3 \n",
      ". . . . . W W .  1 1 1 - 1 - - 1  - 2 2 2 2 - - 2  - - - 3 3 - - 3 \n",
      "_ . . a . . W .  1 1 1 - 1 - - 1  - 2 2 2 2 - - 2  - - 3 - 3 - - 3 \n",
      "W W . . . W W .  - - 1 1 1 - - 1  - - 2 2 2 - - 2  - - 3 3 3 - - 3 \n",
      "W W W . W W g .  - - - - - - 1 1  - - - - - - - 2  - - - - - - - 3 \n",
      "W W W W W W W .  - - - - - - - -  - - - - - - - -  - - - - - - - 3 \n",
      "W W W W W W W .  - - - - - - - -  - - - - - - - -  - - - - - - - 3 \n",
      "   \n",
      "CPU times: user 6.42 ms, sys: 6.24 ms, total: 12.7 ms\n",
      "Wall time: 1.9 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "lines = !./shortcut_solver.sh -c width=8 level*.lp\n",
    "json_text = '\\n'.join(lines)\n",
    "design = parse_json_result(json_text)\n",
    "print side_by_side(render_ascii_dungeon(design), *[render_ascii_touch(design,i) for i in range(1,4)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No matching processes belonging to you were found\r\n"
     ]
    }
   ],
   "source": [
    "!killall clingo"
   ]
  }
 ],
 "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}