NANDutils.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Utility code\n",
    "\n",
    "This is a notebook with all sorts of general utility code that is used for the rest of the notebooks.\n",
    "Some of the code is duplicated from other notebooks.\n",
    "Eventually the authorative version should be here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "def NAND(x,y):\n",
    "    \"\"\"Compute the NAND of two 0/1 valued variables.\"\"\"\n",
    "    return 1 - x*y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "def splitline(line):\n",
    "    foo,bar,blah, = filter(None,re.split('\\s*=\\s*NAND\\s*\\(\\s*|\\s*\\,\\s*|\\s*\\)\\s*|\\s+',line))\n",
    "    return (foo,bar,blah)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "def EVAL(prog,x):\n",
    "    \"\"\"Evaluate NAND program prog on input x.\"\"\"\n",
    "    (n,m) = numinout(prog) # utility function to get num of inputs/outputs\n",
    "    vartable = defaultdict(int) # dictionary for variables\n",
    "    \n",
    "    for i in range(n): vartable[f'X[{i}]']=x[i] # assign x[i] to variable \"X[i]\"\n",
    "    \n",
    "    for line in filter(None,prog.split('\\n')): # split into lines, throw out empty ones\n",
    "        # split to components of a line:\n",
    "        foo,bar,blah = splitline(line)\n",
    "        vartable[foo] =  NAND(vartable[bar],vartable[blah])\n",
    "    \n",
    "    return [vartable[f'Y[{j}]'] for j in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# utility function\n",
    "def numinout(prog):\n",
    "    '''Compute the number of inputs and outputs of a NAND program, given as a string of source code.'''\n",
    "    n = max([int(s[2:-1]) for s in re.findall(r'X\\[\\d+\\]',prog)])+1\n",
    "    m = max([int(s[2:-1]) for s in re.findall(r'Y\\[\\d+\\]',prog)])+1\n",
    "    return n,m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Some utility functions \n",
    "# (can ignore on first read, uses some Python trickery that's not so important for us)\n",
    "\n",
    "from inspect import signature\n",
    "def numarguments(f):\n",
    "    \"\"\"Number of arguments a Python function takes.\"\"\"\n",
    "    return len(signature(f).parameters)\n",
    "\n",
    "def runwith(f,*args):\n",
    "    \"\"\"Evaluate function f binding name to func\"\"\"\n",
    "    g = globals()\n",
    "    old = {}\n",
    "    new = {}\n",
    "    for j in range(0,len(args),2):\n",
    "        old[args[j]] = g[args[j]]\n",
    "        new[args[j]] = args[j+1]\n",
    "        # a little bit of an ugly hack \n",
    "        # if you know a nicer way, please let me know\n",
    "    try:\n",
    "        for name in new: g[name] = new[name]\n",
    "        res = f()\n",
    "    finally:\n",
    "        for name in old: g[name] = old[name]\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def NOT(a):\n",
    "    return NAND(a,a)\n",
    "\n",
    "def AND(a,b):\n",
    "    return NOT(NAND(a,b))\n",
    "\n",
    "def OR(a,b):\n",
    "    return NAND(NOT(a),NOT(b))\n",
    "\n",
    "def one(a):\n",
    "    return NAND(a,NOT(a))\n",
    "\n",
    "def zero(a):\n",
    "    return NOT(one(a))\n",
    "\n",
    "def COPY(a):\n",
    "    return NOT(NOT(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format = 'svg'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Use Graphviz to visualize circuits\n",
    "import graphviz\n",
    "from graphviz import Graph\n",
    "from graphviz import Digraph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Graphviz version\n",
    "def gvnandcircuit(f):\n",
    "    \"\"\"Compute the graph representating a NAND circuit for a NAND program, given as a Python function.\"\"\"\n",
    "    n = numarguments(f)\n",
    "    counter = 0 # to ensure unique temporary variables.\n",
    "    G =  Digraph(graph_attr= {\"rankdir\":\"LR\"}, strict=False) # schem.Drawing(unit=.5)\n",
    "  \n",
    "    def tempNAND(bar,blah):\n",
    "        nonlocal G, counter \n",
    "        var = f'Temp[{counter}]'\n",
    "        counter += 1\n",
    "        G.node(var,label=\"∧\\u0305\",shape='invhouse',orientation=\"90\")\n",
    "        G.edge(bar,var)\n",
    "        G.edge(blah,var)\n",
    "        return var\n",
    "    \n",
    "    for i in range(n):\n",
    "        G.node(f'X[{i}]',label=f'X[{i}]', fontcolor='blue',shape='circle') \n",
    "        \n",
    "    outputs = runwith(lambda: f(*[f'X[{i}]' for i in range(n)]),'NAND',tempNAND)\n",
    "    \n",
    "    if type(outputs)==str: outputs = [outputs] # make single output into singleton list\n",
    "        \n",
    "    for j in range(len(outputs)):\n",
    "        G.node(f'out_{j}',label=f'Y[{j}]',fontcolor='red',shape='diamond')\n",
    "        G.edge(outputs[j],f'out_{j}')\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nandcircuit(f,method=\"Graphviz\"):\n",
    "    return gvnandcircuit(f) if method==\"Graphviz\" else sdnandcircuit(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "def MAJ(a,b,c):\n",
    "    return NAND(NAND(NAND(NAND(a,b),NAND(a,c)),NAND(NAND(a,b),NAND(a,c))),NAND(b,c))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LOOKUP(T,i):\n",
    "    l = len(i)\n",
    "    if l==1:\n",
    "        return IF(i[0],T[1],T[0])\n",
    "    return IF(i[l-1],LOOKUP(T[2**(l-1):],i[:-1]),LOOKUP(T[:2**(l-1)],i[:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A more efficient IF .. not strictly necessary\n",
    "def IF(cond,a,b):\n",
    "    notcond = NAND(cond,cond)\n",
    "    temp = NAND(b,notcond)\n",
    "    temp1 = NAND(a,cond)\n",
    "    return NAND(temp,temp1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "# generalize restrict to handle functions that take more than one array\n",
    "def restrict(f,*numinputs):\n",
    "    \"\"\"Create function that restricts the function f to exactly given input lengths n0,n1,...\"\"\"\n",
    "    k = len(numinputs)\n",
    "    args = []\n",
    "    t = 0\n",
    "    for i in range(k):\n",
    "        if numinputs[i]: args = args + [\", \".join(f'arg_{i}_{j}' for j in range(numinputs[i]))]\n",
    "    sig = \", \".join(args)\n",
    "    call = \", \".join(f\"[{a}]\" for a in args)\n",
    "    code = rf'''\n",
    "def _temp({sig}):\n",
    "    return f({call})\n",
    "'''\n",
    "    l = dict(locals())\n",
    "    exec(code,l)\n",
    "    return l[\"_temp\"]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "def funclookup(l):\n",
    "    return restrict(LOOKUP,2**l,l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Representing NAND programs as lists of triples\n",
    "\n",
    "We can represent a NAND program in many ways including  the string of its source code, as the graph corresponding to its circuit. One simple representation of a NAND program we will use is as the following:\n",
    "\n",
    "We represent a NAND program of $t$ intermediate variables, $s$ lines, $n$ input variables, and $m$ input variables  as a triple $(n,m,L)$ where $L$ is a list of $s$ triples of the form $(a,b,c)$ of numbers in $[n+t+m]$. \n",
    "\n",
    "A triple $(a,b,c)$ corresponds to the line assigning to the variable corresponding $a$ the NAND of the variables corresponding to $b$ and $c$. We identify the first $n$ variables  with the input and the last $m$ variables with the outputs.\n",
    "\n",
    "We can again compute this representation using Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nandrepresent(f,numargs=0):\n",
    "    \"\"\"Compute the list of triple representation for a NAND program, given by a Python function.\"\"\"\n",
    "    n = numargs if numargs else numarguments(f)\n",
    "    counter = n # to ensure unique temporary variables.\n",
    "    L = [] # list of tuples\n",
    "  \n",
    "    \n",
    "    def tempNAND(bar,blah):\n",
    "        nonlocal L, counter \n",
    "        var = counter\n",
    "        counter += 1\n",
    "        L += [(var,bar,blah)] \n",
    "        return var\n",
    "    \n",
    "    \n",
    "    if(numargs):\n",
    "        outputs = runwith(lambda: f(range(n)), \"NAND\", tempNAND) \n",
    "    else:\n",
    "        outputs = runwith(lambda: f(*range(n)), \"NAND\", tempNAND) \n",
    "    \n",
    "    if type(outputs)==int: outputs = [outputs] # make single output into singleton list\n",
    "    m = len(outputs)\n",
    "    \n",
    "    # make sure outputs are last m variables\n",
    "    for j in range(m):\n",
    "        \n",
    "        def flip(a):\n",
    "            nonlocal counter, outputs, j\n",
    "            if a==outputs[j]:  return counter+j\n",
    "            return a\n",
    "        \n",
    "        L = [(flip(a),flip(b),flip(c)) for (a,b,c) in L]\n",
    "                \n",
    "    return (n,m,compact(L))\n",
    "\n",
    "# utlity function\n",
    "def compact(L):\n",
    "    \"\"\"Compact list of triples to remove unused variables.\"\"\"\n",
    "    s = sorted(set.union(*[set(T) for T in L]))\n",
    "    return [ (s.index(a),s.index(b),s.index(c)) for (a,b,c) in L]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can directly evaluate a NAND program based on its list of triples representation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "def EVALnand(prog,X):\n",
    "    \"\"\"Evaluate a NAND program from its list of triple representation.\"\"\"\n",
    "    n,m,L = prog\n",
    "    vartable = X+[0]*(max(max(a,b,c) for (a,b,c) in L)-n+1)\n",
    "    for (a,b,c) in L:\n",
    "        vartable[a] = NAND(vartable[b],vartable[c])\n",
    "    \n",
    "    return [vartable[-m+j] for j in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "def code2rep(code):\n",
    "    \"\"\"Transform code to triples representation\"\"\"\n",
    "    s = code.count(\"\\n\")\n",
    "    n = 0\n",
    "    varnums = {}\n",
    "    \n",
    "    \n",
    "    while code.find(f\"X[{n}]\")>= 0: \n",
    "        varnums[f\"X[{n}]\"] = n\n",
    "        n+=1\n",
    "    t = n\n",
    "    def getnum(var):\n",
    "        nonlocal t\n",
    "        if not var in varnums: \n",
    "            varnums[var]= t\n",
    "            t += 1\n",
    "        return varnums[var]\n",
    "    \n",
    "    m = 0\n",
    "    while code.find(f\"Y[{m}]\")>= 0: \n",
    "        varnums[f\"Y[{m}]\"] = 3*s+m\n",
    "        m += 1\n",
    "    \n",
    "    L = []\n",
    "    for line in code.split(\"\\n\"):\n",
    "        if not line.strip(): continue\n",
    "        foo,bar,blah, = filter(None,re.split('\\s*=\\s*NAND\\s*\\(\\s*|\\s*\\,\\s*|\\s*\\)\\s*|\\s+',line))\n",
    "        L.append([getnum(foo),getnum(bar),getnum(blah)])\n",
    "    return (n,m,compact(L))\n",
    "\n",
    "\n",
    "        \n",
    "def code2circuit(code, pruneit=True): \n",
    "    return rep2circuit(prune(code2rep(code))) if pruneit else rep2circuit(code2rep(code))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pruning (optional)\n",
    "\n",
    "\n",
    "We can do some simple transformations to reduce the size of our programs/circuits. For example, if two gates have exactly the same inputs then we can identify them with one another.\n",
    "We can also use the equality NOT(NOT(a))=a, as well as remove unused variables.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [],
   "source": [
    "def makeunique(prog):\n",
    "    \"\"\"Ensure that every working variable is only assigned a value once\"\"\"\n",
    "    n,m,L = prog\n",
    "    t = max([max(a,b,c) for (a,b,c)in L])+1\n",
    "    last = {i:i for i in range(n) }\n",
    "    res = []\n",
    "    maxval = len(L)+n\n",
    "    cur = n\n",
    "    outputs = {}\n",
    "    for (a,b,c) in L:\n",
    "        _b = last[b]\n",
    "        _c = last[c]\n",
    "        if a>= t-m:\n",
    "            outputs[a-t+m] = cur \n",
    "        _a = cur\n",
    "        last[a] = cur\n",
    "        cur += 1\n",
    "        res.append((_a,_b,_c))\n",
    "    def update(a):\n",
    "        nonlocal maxval\n",
    "        for (o,b) in list(outputs.items()):\n",
    "            if b==a: return maxval-m+o\n",
    "        return a\n",
    "    temp = [(update(a),b,c) for (a,b,c) in res]\n",
    "    return n,m,compact(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prune(prog):\n",
    "    \"\"\"Prune representation of program as tuples, removing duplicate lines and unused variables.\"\"\"\n",
    "    n,m,L = makeunique(prog)\n",
    "    L = list(L)\n",
    "    def identify(L,e,f):\n",
    "        # identify vertex e with vertex f\n",
    "        def ident(k): \n",
    "            nonlocal e,f\n",
    "            return f if k==e else k\n",
    "        \n",
    "        return [(ident(a),ident(b),ident(c)) for (a,b,c) in L]\n",
    "    \n",
    "    \n",
    "    \n",
    "    t = max([max(a,b,c) for (a,b,c) in L])+1\n",
    "\n",
    "    \n",
    "    while True:\n",
    "        neighborhood = {}\n",
    "        neighbors = {}\n",
    "        \n",
    "        found = False \n",
    "        for (a,b,c) in L:\n",
    "            N = frozenset([b,c])\n",
    "            if a>=t-m: continue # don't remove output variables\n",
    "            if N in neighborhood: # there was prior duplicate line\n",
    "                L.remove((a,b,c))\n",
    "                L = identify(L,a,neighborhood[N])\n",
    "                found = True\n",
    "                break\n",
    "            if b==c and b in neighbors and len(neighbors[b])==1: # line is NOT of NOT of prior line\n",
    "                L.remove((a,b,c))\n",
    "                L = identify(L,a,next(iter(neighbors[b])))\n",
    "                found = True\n",
    "                break\n",
    "            neighborhood[N] = a\n",
    "            neighbors[a] = N\n",
    "            \n",
    "        touched   = {a: False for a in range(t)} \n",
    "        for (a,b,c) in L: \n",
    "            touched[b] = True\n",
    "            touched[c] = True\n",
    "\n",
    "        for d in range(n,t-m,1): # remove non output and input variables that are not used\n",
    "            if not touched[d]: \n",
    "                for (a,b,c) in L:\n",
    "                    if a==d:\n",
    "                        L.remove((a,b,c))\n",
    "                        found =True\n",
    "        if not found: break\n",
    "    \n",
    "    return (n,m,compact(L))        \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Majority\n",
    "def MAJ(a,b,c): return NAND(NAND(NAND(NAND(a,b),NAND(a,c)),NAND(NAND(a,b),NAND(a,c))),NAND(b,c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## From representation to code or graph\n",
    "\n",
    "We can use the list of triples representation as a starting point to obtain the NAND program as a list of lines of code, or as a circuit (i.e., directed acyclic graph)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Graphviz version\n",
    "def gvrep2circuit(P,sizeparam=\"11,5\"):\n",
    "    \"\"\"Return circuit (i.e., graph) corresponding to NAND program P given in list of tuples representation.\"\"\"\n",
    "    \n",
    "    n,m,L = P\n",
    "    G = Digraph(graph_attr= {\"rankdir\":\"LR\"},strict=False)\n",
    "    last = {}\n",
    "  \n",
    "    for i in range(n):\n",
    "        G.node(f\"v{i}\",label=f'X[{i}]', fontcolor='blue',shape='circle')\n",
    "        last[i] = f\"v{i}\"\n",
    "    \n",
    "    t = n\n",
    "    ctr = n\n",
    "    for (a,b,c) in L:\n",
    "        G.node(f\"v{ctr}\",label='∧\\u0305',shape='invhouse',orientation='90')  # shape='none' image='NAND_gate.png') \n",
    "        if b in last: G.edge(last[b],f\"v{ctr}\")\n",
    "        if c in last: G.edge(last[c],f\"v{ctr}\")\n",
    "        last[a] = f\"v{ctr}\"\n",
    "        ctr += 1\n",
    "        t = max(t,a,b,c)\n",
    "\n",
    "    t += 1\n",
    "    for j in range(m):\n",
    "        G.node(f\"out{t-m+j}\",label=f'Y[{j}]',fontcolor='red',shape='diamond')\n",
    "        if (t-m+j) in last: G.edge(last[t-m+j],f\"out{t-m+j}\")\n",
    "    \n",
    "    G.graph_attr.update(size=sizeparam, ratio=\"fill\")\n",
    "    return G\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rep2code(P):\n",
    "    \"\"\"Return NAND code corresponding to NAND program P, given in list of tuples representation\"\"\"\n",
    "    n,m,L = P\n",
    "    code = \"\"\n",
    "  \n",
    "    t = max([max(a,b,c) for (a,b,c) in L])+1\n",
    "    \n",
    "    def var(a):\n",
    "        if a<n: return f\"X[{a}]\"\n",
    "        if a>=t-m: return f\"Y[{a-t+m}]\"\n",
    "        return f\"Temp[{a-n}]\"\n",
    "    \n",
    "    for (a,b,c) in L:\n",
    "        code += f\"{var(a)} = NAND({var(b)},{var(c)})\\n\"\n",
    "\n",
    "    return code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rep2circuit(P,method=\"Graphviz\"):\n",
    "    return gvrep2circuit(P) if method==\"Graphviz\" else sdrep2circuit(P)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now redefine the `nandcircuit` and  `nandcode` functions to work as follows:\n",
    "\n",
    "1. First  obtain the list of triples representation\n",
    "2. Then prune it\n",
    "3. Then transform it to either code or circuit appropriately"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nandcode(f,pruneit=False,numargs=0):\n",
    "    R = prune(nandrepresent(f,numargs)) if pruneit else nandrepresent(f,numargs)  \n",
    "    return rep2code(R)\n",
    "\n",
    "def nandcircuit(f, pruneit = False, method=\"Graphviz\",numargs=0):\n",
    "    R = prune(nandrepresent(f,numargs)) if pruneit else nandrepresent(f,numargs)  \n",
    "    return rep2circuit(R,method)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Universal circuit evaluation or NAND interpreter in NAND\n",
    "\n",
    "We can construct a NAND program $P$ that given the representation of a NAND program $Q$ and an input $x$, outputs $Q(x)$. We can obviously compute such a function since every finite function is computable by a NAND program, but it turns out we can do so in a program that is polynomial in the size of $P$ (even quasiliinear but we won't show that here). \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We start with a reimplementation of `NANDEVAL` in Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "def GET(V,i): return V[i]\n",
    "\n",
    "def UPDATE(V,i,b):\n",
    "    V[i]=b\n",
    "    return V\n",
    "\n",
    "\n",
    "def NANDEVAL(n,m,L,X):\n",
    "    # Evaluate a NAND program from its list of triple representation.\n",
    "    s = len(L) # number of lines\n",
    "    t = max(max(a,b,c) for (a,b,c) in L)+1 # maximum index in L + 1\n",
    "\n",
    "    Vartable = [0] * t # we'll simply use an array to store data\n",
    "\n",
    "    \n",
    "\n",
    "    # load input values to Vartable:\n",
    "    for i in range(n): Vartable = UPDATE(Vartable,i,X[i])\n",
    "\n",
    "    # Run the program\n",
    "    for (i,j,k) in L:\n",
    "        a = GET(Vartable,j)\n",
    "        b = GET(Vartable,k)\n",
    "        c = NAND(a,b)\n",
    "        Vartable = UPDATE(Vartable,i,c)\n",
    "\n",
    "    # Return outputs Vartable[t-m], Vartable[t-m+1],....,Vartable[t-1]\n",
    "    return [GET(Vartable,t-m+j) for j in range(m)]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now transform this to work with the representation of `L` as a binary string, namely as a sequence of $3s$ numbers in $[t]$, each represented as a string of length $\\ell = \\lceil \\log 3s \\rceil$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import ceil, floor, log2\n",
    "def triplelist2string(L):\n",
    "    \"\"\"Transform list of triples into its representation as a binary string\"\"\"\n",
    "    s = len(L)\n",
    "    ell = ceil(log2(3*s))\n",
    "    B = [0]*(3*s*ell)\n",
    "    FlatL = [a for T in L for a in T]\n",
    "    for i in range(3*s):\n",
    "        for j in range(ell):\n",
    "            B[ell*i + j] = floor(FlatL[i]/ 2**j) % 2\n",
    "    return B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluating a NAND program given its string representation\n",
    "\n",
    "We can now present `NANDEVALBIN`  which will be a Python function that evaluates a NAND program given the representation of the program as a binary string. (We assume the parameters $n,m,s,t$ are given: we could have assumed they are part of the string representation, but this only makes things messier.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def NANDEVALBIN(n,m,s,t,B,X):\n",
    "    \"\"\"Evaluate nand program given its description as a binary array\"\"\"\n",
    "\n",
    "    ell = ceil(log2(3*s))\n",
    "    Vartable = [0] * (2**ell) # we'll simply use an array to store data\n",
    "    \n",
    "    # load input values to Vartable:\n",
    "    for i in range(n): Vartable[i] = X[i] \n",
    "\n",
    "    # Run the program\n",
    "    for c in range(s):\n",
    "        i = [B[c*3*ell+d] for d in range(ell)]\n",
    "        j = [B[c*3*ell+ell+d] for d in range(ell)]\n",
    "        k = [B[c*3*ell+2*ell+d] for d in range(ell)]\n",
    "        a = GETB(Vartable,j)\n",
    "        b = GETB(Vartable,k)\n",
    "        c = NAND(a,b)\n",
    "        Vartable = UPDATEB(Vartable,i,c)\n",
    "\n",
    "    # Return outputs Vartable[t-m], Vartable[t-m+1],....,Vartable[t-1]\n",
    "    return [Vartable[t-m+j] for j in range(m)]\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll need some utility functions to deal with the binary representation (you can ignore these at a first read)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "# utility functions\n",
    "def nandconst(b,x):\n",
    "    \"\"\"Transform 0 or 1 to NAND zero or one functions\"\"\"\n",
    "    if b: return one(x)\n",
    "    return zero(x)\n",
    "\n",
    "def i2s(i,ell=0):\n",
    "    \"\"\"Transform integer to binary representation of length ell\"\"\"\n",
    "    if not ell: ell = ceil(log2(i))\n",
    "    return [floor(i/2**j) %2  for j in range(ell)]\n",
    "\n",
    "def GETB(V,i):\n",
    "    return LOOKUP(V,i)\n",
    "\n",
    "def EQUALB(j,i):\n",
    "    flag = zero(i[0]) # if flag is one then i is different from j\n",
    "    for t in range(len(j)):\n",
    "        if type(j[t])==int:\n",
    "            temp = NOT(i[t]) if j[t] else COPY(i[t])\n",
    "        else:\n",
    "            temp = OR(AND(j[t],NOT(i[t])),AND(NOT(j[t]),i[t]))\n",
    "        flag = OR(temp,flag)\n",
    "    return NOT(flag)\n",
    "\n",
    "def UPDATEB(V,i,b):\n",
    "    ell = ceil(log2(len(V)))\n",
    "    UV = [0]*len(V)\n",
    "    for j in range(len(V)):\n",
    "        a = EQUALB(i2s(j,ell),i)\n",
    "        UV[j] = IF(a,b,V[j])\n",
    "    \n",
    "    return UV\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's test this out on the XOR function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### From Python to NAND\n",
    "\n",
    "We now transform the Python program NANDEVALBIN into a NAND program.\n",
    "In fact, it turns out that all our python code can be thought of as \"syntacic sugar\" and hence we can do this transformation automatically.\n",
    "\n",
    "Specifically, for every numbers $n,m,s,t$  we will construct a NAND program $P$ on $3s\\ell+n$ inputs (for $\\ell = \\lceil \\log_2(3s) \\rceil$ that on input a string $B\\in \\{0,1\\}^{3s\\ell}$ and $x\\in \\{0,1\\}^n$  outputs $P(x)$ where $P$ is the program represented by $B$.\n",
    "\n",
    "To do so, we simply first restrict `NANDEVALBIN` to the parameters $n,m,s,t$ and then run our usual \"unsweetener\" to extract the NAND code from it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nandevalfunc(n,m,s,t):\n",
    "    \"\"\"Given n,m,s,t, return a function f that on input B,X returns the evaluation of the program encoded by B on X\"\"\"\n",
    "    ell = ceil(log2(3*s))\n",
    "    return restrict(lambda B,X: NANDEVALBIN(n,m,s,t,B,X),3*s*ell,n)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, let us set $n,m,s,t$ to be the parameters as in the XOR function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# NAND++ utility code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ignore this utility function in first and even second and third read\n",
    "import inspect\n",
    "import ast\n",
    "import astor\n",
    "\n",
    "def noop(f):\n",
    "    return f;\n",
    "\n",
    "def runwithstate(f):\n",
    "    \"\"\"Modify a function f to take and return an argument state and make all names relative to state.\"\"\"\n",
    "    tree = ast.parse(inspect.getsource(f))\n",
    "    tmp = ast.parse(\"def _temp(state):\\n    pass\\n\").body[0]\n",
    "    args = tmp.args\n",
    "    name = tmp.name\n",
    "    tree.body[0].args = args\n",
    "    tree.body[0].name = name\n",
    "    tree.body[0].decorator_list = []\n",
    "    \n",
    "\n",
    "    class AddState(ast.NodeTransformer):\n",
    "        def visit_Name(self, node: ast.Name):\n",
    "            if node.id == \"enandpp\": return ast.Name(id=\"noop\", ctx=Load())\n",
    "            new_node = ast.Attribute(ast.copy_location(ast.Name('state', ast.Load()), node), node.id,\n",
    "                                     ast.copy_location(ast.Load(), node))\n",
    "            return ast.copy_location(new_node, node)\n",
    "        \n",
    "    tree = AddState().visit(tree)\n",
    "    tree.body[0].body = tree.body[0].body + [ast.parse(\"return state\")]\n",
    "    tree = ast.fix_missing_locations(tree)\n",
    "    src = astor.to_source(tree)\n",
    "    # print(src)\n",
    "    exec(src,globals())\n",
    "    _temp.original_func = f\n",
    "    return _temp\n",
    "\n",
    "    \n",
    "def enandpp(f):\n",
    "    g = runwithstate(f)\n",
    "    def _temp1(X):\n",
    "        nonlocal g\n",
    "        return ENANDPPEVAL(g,X)\n",
    "    _temp1.original_func = f\n",
    "    _temp1.transformed_func = g\n",
    "    return _temp1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ignore utility class in first and even second or third read\n",
    "\n",
    "from  collections import defaultdict\n",
    "class NANDPPstate:\n",
    "    \"\"\"State of a NAND++ program.\"\"\"\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.scalars = defaultdict(int)\n",
    "        self.arrays  = defaultdict(lambda: defaultdict(int))\n",
    "        # eventually should make self.i non-negative integer type\n",
    "        \n",
    "    def __getattr__(self,var):\n",
    "        g =  globals()\n",
    "        if var in g and callable(g[var]): return g[var]\n",
    "        if var[0].isupper():\n",
    "            return self.arrays[var]\n",
    "        else:\n",
    "            return self.scalars[var]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ENANDPPEVAL(f,X):\n",
    "    \"\"\"Evaluate an enhanced NAND++ function on input X\"\"\"\n",
    "    s = NANDPPstate()\n",
    "    for i in range(len(X)):\n",
    "        s.X[i] = X[i]\n",
    "        s.Xvalid[i] = 1\n",
    "    while True:\n",
    "        s = f(s)\n",
    "        if not s.loop: break\n",
    "    res = []\n",
    "    i = 0\n",
    "    while s.Yvalid[i]: \n",
    "        res += [s.Y[i]]\n",
    "        i+= 1\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rreplace(s, old, new, occurrence=1): # from stackoverflow\n",
    "    li = s.rsplit(old, occurrence)\n",
    "    return new.join(li)\n",
    "\n",
    "    \n",
    "        \n",
    "def ENANDPPcode(P):\n",
    "    \"\"\"Return ENAND++ code of given function\"\"\"\n",
    "    \n",
    "    code = ''\n",
    "    counter = 0\n",
    "    \n",
    "    class CodeENANDPPcounter:\n",
    "        def __init__(self,name=\"i\"): \n",
    "            self.name = name\n",
    "        \n",
    "        def __iadd__(self,var):\n",
    "            nonlocal code\n",
    "            code += f'\\ni += {var}'\n",
    "            return self\n",
    "        \n",
    "        def __isub__(self,var):\n",
    "            nonlocal code\n",
    "            code += f'\\ni -= {var}'\n",
    "            return self\n",
    "        \n",
    "        def __str__(self): return self.name\n",
    "    \n",
    "    class CodeNANDPPstate:\n",
    "    \n",
    "    \n",
    "        def __getattribute__(self,var):\n",
    "            # print(f\"getting {var}\")\n",
    "            if var=='i': return CodeENANDPPcounter()\n",
    "            g =  globals()\n",
    "            if var in g and callable(g[var]): return g[var]\n",
    "            if var[0].isupper():  \n",
    "                class Temp:\n",
    "                    def __getitem__(self,k):  return f\"{var}[{str(k)}]\"\n",
    "                    def __setitem__(s,k,v): setattr(self,f\"{var}[{str(k)}]\",v)            \n",
    "                return Temp()\n",
    "            return var\n",
    "    \n",
    "        def __init__(self):\n",
    "            pass\n",
    "    \n",
    "        def __setattr__(self,var,val):\n",
    "            nonlocal code\n",
    "            if var=='i': return\n",
    "            if code.find(val)==-1:\n",
    "                code += f'\\n{var} = {val}'\n",
    "            else:\n",
    "                code = rreplace(code,val,var)\n",
    "    \n",
    "    s = CodeNANDPPstate()\n",
    "    \n",
    "    def myNAND(a,b):\n",
    "        nonlocal code, counter\n",
    "        var = f'temp_{counter}'\n",
    "        counter += 1\n",
    "        code += f'\\n{var} = NAND({a},{b})'\n",
    "        return var\n",
    "    \n",
    "        \n",
    "    \n",
    "    \n",
    "    \n",
    "    s = runwith(lambda : P.transformed_func(s),\"NAND\",myNAND) \n",
    "    \n",
    "    return code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## \"Vanilla\" NAND++\n",
    "\n",
    "In \"vanilla\" NAND++ we do not have the commands `i += foo` and `i -= foo` but rather `i` travels obliviously according to the sequence $0,1,0,1,2,1,0,1,2,3,2,1,0,1,2,\\ldots$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def index():\n",
    "    \"\"\"Generator for the values of i in the NAND++ sequence\"\"\"\n",
    "    i = 0\n",
    "    last = 0\n",
    "    direction  = 1\n",
    "    while True:\n",
    "        yield i\n",
    "        i += direction\n",
    "        if i> last: \n",
    "            direction = -1\n",
    "            last = i\n",
    "        if i==0: direction = +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "def NANDPPEVAL(f,X):\n",
    "    \"\"\"Evaluate a NAND++ function on input X\"\"\"\n",
    "    s = NANDPPstate() # intialize state\n",
    "    \n",
    "    # copy input:\n",
    "    for i in range(len(X)): \n",
    "        s.X[i] = X[i]\n",
    "        s.Xvalid[i] = 1\n",
    "        \n",
    "    # main loop:\n",
    "    for  i in index(): \n",
    "        s.i = i\n",
    "        s = f(s)\n",
    "        if not s.loop: break\n",
    "    \n",
    "    # copy output:\n",
    "    res = [] \n",
    "    i = 0\n",
    "    while s.Yvalid[i]: \n",
    "        res += [s.Y[i]]\n",
    "        i+= 1\n",
    "    return res\n",
    "\n",
    "\n",
    "\n",
    "def nandpp(f):\n",
    "    \"\"\"Modify python code to obtain NAND++ program\"\"\"\n",
    "    g = runwithstate(f)\n",
    "    def _temp1(X):\n",
    "        return NANDPPEVAL(g,X)\n",
    "    _temp1.original_func = f\n",
    "    _temp1.transformed_func = g\n",
    "    return _temp1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the increment function in vanilla NAND++. Note that we need to keep track of an Array `Visited` to make sure we only add the carry once per location."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def NANDPPcode(P):\n",
    "    \"\"\"Return NAND++ code of given function\"\"\"\n",
    "    \n",
    "    code = ''\n",
    "    counter = 0\n",
    "    \n",
    "    \n",
    "    class CodeNANDPPstate:\n",
    "    \n",
    "    \n",
    "        def __getattribute__(self,var):\n",
    "            # print(f\"getting {var}\")\n",
    "            g =  globals()\n",
    "            if var in g and callable(g[var]): return g[var]\n",
    "            if var ==\"i\": return \"i\"\n",
    "            if var[0].isupper():  \n",
    "                class Temp:\n",
    "                    def __getitem__(self,k):  return var+f\"[{k}]\"\n",
    "                    def __setitem__(s,k,v):   \n",
    "                        setattr(self,var+f\"[{k}]\",v)            \n",
    "                return Temp()\n",
    "            return var\n",
    "    \n",
    "        def __init__(self):\n",
    "            pass\n",
    "    \n",
    "        def __setattr__(self,var,val):\n",
    "            nonlocal code\n",
    "            # print(f\"setting {var} to {val}\")\n",
    "            if code.find(val)==-1:\n",
    "                code += f'{var} = {val}\\n'\n",
    "            else:\n",
    "                code = rreplace(code,val,var)\n",
    "    \n",
    "    s = CodeNANDPPstate()\n",
    "    \n",
    "    def myNAND(a,b):\n",
    "        nonlocal code, counter\n",
    "        var = f'temp_{counter}'\n",
    "        counter += 1\n",
    "        code += f'{var} = NAND({a},{b})\\n'\n",
    "        return var\n",
    "    \n",
    "        \n",
    "    \n",
    "    \n",
    "    \n",
    "    s = runwith(lambda : P.transformed_func(s),\"NAND\",myNAND) \n",
    "    \n",
    "    return code\n",
    "\n",
    "\n",
    "# utility code - replace string from right, taken from stackoverflow\n",
    "def rreplace(s, old, new, occurrence=1): \n",
    "    li = s.rsplit(old, occurrence)\n",
    "    return new.join(li)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Unrolling the loop "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from math import sqrt\n",
    "\n",
    "def indexat(k):\n",
    "    return min([abs(k-int(r)*(int(r)+1)) for r in [sqrt(k)-0.5,sqrt(k)+0.5]])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def zoom(G,factor=4):\n",
    "    s1 = 11*factor\n",
    "    s2 = 5*factor\n",
    "    G.graph_attr.update(size=f\"{s1},{s2}!\", ratio=\"fill\")\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def unroll__(P,n,m,T):\n",
    "    result = r'''\n",
    "temp = NAND(X[0],X[0])\n",
    "one = NAND(X[0],temp)\n",
    "zero = NAND(one,one)\n",
    "'''[1:]\n",
    "    for t in range(T // P.count('\\n')):\n",
    "        i = indexat(t) # value of i in T-th iteration\n",
    "        valid = ('one' if i < n else 'zero' )\n",
    "        inp   = ('X[i]' if i < n else 'zero')\n",
    "        out   = ('Y[i]' if i < m else 'temp' )\n",
    "        result += P.replace('Xvalid[i]',valid).replace('X[i]',inp\n",
    "                           ).replace('Y[i]',out).replace('[i]',f'[{i}]')\n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def unroll_(f,n,m,T=0):\n",
    "    if not T:\n",
    "        T = time(f,[0]*n)\n",
    "    P = NANDPPcode(f)\n",
    "    result = r'''\n",
    "temp = NAND(X[0],X[0])\n",
    "one = NAND(X[0],temp)\n",
    "zero = NAND(one,one)\n",
    "'''[1:]\n",
    "    for t in range(T // P.count('\\n')):\n",
    "        i = indexat(t) # value of i in T-th iteration\n",
    "        valid = ('one' if i < n else 'zero' )\n",
    "        inp   = ('X[i]' if i < n else 'zero')\n",
    "        out   = ('Y[i]' if i < m else 'temp' )\n",
    "        result += P.replace('Xvalid[i]',valid).replace('X[i]',inp).replace('Y[i]',out).replace('[i]',f'[{i}]')\n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def unroll(f,n,m,T=0):\n",
    "    '''Gets f = NAND PP program, T - time bound, n - number of inputs, m - number of outputs\n",
    "    Produces NAND program of O(T) lines that computes the restriction of f to inputs of length n and T steps'''\n",
    "    if not T:\n",
    "        T = time(f,[0]*n)\n",
    "    P = NANDPPcode(f)\n",
    "    lines = [l for l in P.split('\\n') if l]\n",
    "    result = r'''\n",
    "temp = NAND(X[0],X[0])\n",
    "one = NAND(X[0],temp)\n",
    "zero = NAND(one,one)\n",
    "nothalted = NAND(X[0],temp)\n",
    "halted = NAND(one,one)\n",
    "'''[1:]\n",
    "    \n",
    "    # assign_to = IF(halted,old_value,new_value)\n",
    "    IFCODE = r'''\n",
    "iftemp_0 = NAND(new_value,nothalted)\n",
    "iftemp_1 = NAND(assign_to,halted)\n",
    "assign_to = NAND(iftemp_0,iftemp_1)\n",
    "'''[1:]\n",
    "    \n",
    "    UPDATEHALTED = r'''\n",
    "halted = NAND(nothalted,loop)\n",
    "nothalted = NAND(halted,halted)\n",
    "'''[1:]\n",
    "\n",
    "    for t in range(T // len(lines)):\n",
    "        j = indexat(t)\n",
    "        for line in lines:\n",
    "            if j>= m:\n",
    "                line = line.replace('Y[i]','temp')\n",
    "            if j< n:\n",
    "                line = line.replace('Xvalid[i]','one')\n",
    "            else:\n",
    "                line = line.replace('Xvalid[i]','zero')\n",
    "                line = line.replace('X[i]','zero')\n",
    "        \n",
    "            line = line.replace('[i]',f'[{j}]')\n",
    "            idx = line.find(\"=\")\n",
    "            lefthand = line[:idx].strip()\n",
    "            righthand = line[idx+1:].strip()\n",
    "            result += \"new_value = \" + righthand + \"\\n\"\n",
    "            result += IFCODE.replace(\"assign_to\",lefthand)\n",
    "        result += UPDATEHALTED\n",
    "        \n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def time(f,x):\n",
    "    counter = 0\n",
    "    def tempNAND(a,b):\n",
    "        nonlocal counter\n",
    "        counter += 1\n",
    "        return 1 - a*b\n",
    "    runwith(lambda: f(x), \"NAND\", tempNAND)\n",
    "    return counter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reductions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "inputHidden": false,
    "outputHidden": false,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import Image\n",
    "from IPython.core.display import HTML "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import functools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import graphviz\n",
    "from graphviz import Graph\n",
    "from graphviz import Digraph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "\n",
    "import matplotlib\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from IPython.display import Image\n",
    "\n",
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")\n",
    "\n",
    "import math\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "\n",
    "import matplotlib\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from IPython.display import Image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import pydotplus\n",
    "\n",
    "def nxgraph(G):\n",
    "    P = pydotplus.graph_from_dot_data(G.source)\n",
    "    return nx.drawing.nx_pydot.from_pydot(P)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")\n",
    "\n",
    "# import matplotlib.cbook\n",
    "# warnings.filterwarnings(\"ignore\",category=matplotlib.cbook.mplDeprecation)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "def subscriptdigit(d):\n",
    "    return [\"₀\",\"₁\",\"₂\",\"₃\",\"₄\",\"₅\",\"₆\",\"₇\",\"₈\",\"₉\"][d]\n",
    "\n",
    "def subscript(s):\n",
    "    digits = [\"0\",\"1\",\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\"]\n",
    "    return \"\".join([subscriptdigit(int(s[i])) if s[i] in digits else s[i] for i in range(len(s))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def scale(G,sizeparam=\"10,5\"):\n",
    "    G.graph_attr.update(size=sizeparam, ratio=\"fill\")\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Evaluate 3CNF φ on assignment x \n",
    "# Both are represented as strings\n",
    "def evalcnf(φ,x):\n",
    "\n",
    "    def varval(v):\n",
    "        return (1-int(x[int(v[2:])])  if v[0]==\"¬\" else int(x[int(v[1:])]))\n",
    "    \n",
    "    for (v0,v1,v2) in getclauses(φ):\n",
    "        # print(c+str([varval(v0),varval(v1),varval(v2)]))\n",
    "        if not varval(v0)+varval(v1)+varval(v2): return False\n",
    "    \n",
    "    return True\n",
    "\n",
    "# Clause list of a 3CNF φ\n",
    "def getclauses(φ):\n",
    "    clauses =  φ.split(\"∧\")\n",
    "    res = []\n",
    "    for c in clauses:\n",
    "        (v0,_,v1,_,v2) = c.strip()[1:-1].split()\n",
    "        res.append((v0.strip(),v1.strip(),v2.strip()))\n",
    "    return res\n",
    "    \n",
    "\n",
    "# number of variables of a formula φ\n",
    "def numvars(φ):\n",
    "    for n in range(len(φ)-1,0,-1):\n",
    "        if φ.find('x'+str(n))>= 0: return n+1\n",
    "    raise Exception\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Some bigger instances (DIMACS format)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def from_dimacs(cnf):\n",
    "    φ = \"\"\n",
    "    m = 0\n",
    "    n = 0\n",
    "    def var(idx): return f\"x{int(idx)-1}\" if int(idx)>0 else f\"¬x{-int(idx)-1}\"\n",
    "    \n",
    "    for line in cnf.split(\"\\n\"):\n",
    "        if not line.strip() or line[0]==\"c\" or line[0]==\"%\" or line[0]==\"0\": continue\n",
    "        if line[0]==\"p\":\n",
    "            _,t,n_,m_ = line.split()\n",
    "            if t!=\"cnf\": raise Exception(\"Only handle CNF!\")\n",
    "            n = int(n_)\n",
    "            m = int(m_)\n",
    "            continue\n",
    "        a,b,c,_ = line.split()\n",
    "        if _ != \"0\": raise Exception(\"Only handle 3CNF!\")\n",
    "        φ += f\"({var(a)} ∨ {var(b)} ∨ {var(c)} ) ∧ \"\n",
    "    φ = φ[:-3]\n",
    "    return φ\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [],
   "source": [
    "def from_dimacs_assign(assign):\n",
    "    avals = {}\n",
    "    n = 0\n",
    "    for a in assign.split():\n",
    "        if a == \"v\": continue\n",
    "        a = int(a)\n",
    "        if a>0:\n",
    "            avals[a-1] = \"1\"\n",
    "            n = max(n,a)\n",
    "        if a<0:\n",
    "            avals[-a-1] = \"0\"\n",
    "            n = max(n,-a)\n",
    "        if a == 0:\n",
    "            break\n",
    "    x = \"\"\n",
    "    for i in range(n):\n",
    "        x += avals[i]\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finished running utility code\n"
     ]
    }
   ],
   "source": [
    "print(\"Finished running utility code\")"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}