notebooks/Intro.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "random-trinidad",
   "metadata": {},
   "source": [
    "# Python Programming Puzzles\n",
    "See how your program solving abilities compare with the latest AI technologies by solving the puzzles below. \n",
    "\n",
    "**What is a Python Programming Puzzle?** Each puzzle is a Python function `sat`, and the goal is to find a *satisfying input*, meaning an  that makes `sat` return `True`. \n",
    "For example:\n",
    "\n",
    "```python\n",
    "def sat(s: str):\n",
    "    return \"Hello \" + s == \"Hello world\"\n",
    "```\n",
    "\n",
    "The solution is `\"world\"` because `sat(\"world\")` evaluates to `True`.\n",
    "\n",
    "What's makes puzzles so good for teaching AI to program? Previously, programming challenges were often written in English with some examples. But this requires teaching the computer English, which is hard and [unrelated](https://news.mit.edu/2020/brain-reading-computer-code-1215). \n",
    "Puzzles require reading *code* which is more relevant. Also, puzzles are *objective*---there is no arguing about whether a solution is correct. This is unlike the classic *what's the next number* problems where any answer could be justified.\n",
    "\n",
    "## Next steps\n",
    "* If you have some extra time and want to try the timed version, try the full 30-puzzle [user study notebook](https://aka.ms/python_puzzles_study) where you have 6 minutes to solve each puzzle and there is no cheating.\n",
    "* **Try solving some of the puzzles below** to get a sense of what the deep learning systems did and did not solve. These systems include [GPT-3](https://en.wikipedia.org/wiki/GPT-3) which \"picked up\" how to program from a huge text corpus that included source code. \n",
    "* **Read our [arXiv paper](https://arxiv.org/abs/2106.05784)**. The main contribution is introducing a dataset of this new type of problem to teach and evaluate computers (and humans) programming. While AI is world champions at games like chess and go, human programmers still way outperform *program synthesis* systems.\n",
    "* **Visit our open-source GitHub repository** https://github.com/microsoft/PythonProgrammingPuzzles to explore the full dataset and **please contribute your own new puzzles**\n",
    "* **Share this notebook**: https://aka.ms/python_puzzles\n",
    "\n",
    "## Instructions to use the notebook below\n",
    "* Click on a cell and press the \"&#x25B6; Run\" button above to run the code.\n",
    "* For each puzzle, run the cell with the puzzle, then run your solution.\n",
    "* An example is given below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "worthy-strap",
   "metadata": {},
   "outputs": [],
   "source": [
    "# first click on this cell and press the Run button above\n",
    "\n",
    "from typing import List, Set # this line just does some setup for later\n",
    "\n",
    "def sat(s: str):  # s: str means that that the solution should be a string\n",
    "    return \"Hello \" + s == \"Hello world\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "beautiful-standing",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Run this cell next. It has the correct answer for this easy puzzle\n",
    "\n",
    "sat(\"world\")  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "remarkable-soccer",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(s: str):\n",
    "    return len(s) == 2 and (\"hello\" * 100).count(s) == 99"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "through-blues",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# we know the string has to be 2 characters because `len(s) == 2`\n",
    "sat(\"he\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "unlike-sugar",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hellohellohellohellohellohellohellohellohellohello\n"
     ]
    }
   ],
   "source": [
    "# If you're not sure what multiplying a string by a number is, try it out\n",
    "\n",
    "print(\"hello\" * 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "sudden-elite",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "10\n",
      "10\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "# OK, so...\n",
    "\n",
    "print((\"hello\" * 10).count(\"he\"))\n",
    "print((\"hello\" * 10).count(\"el\"))\n",
    "print((\"hello\" * 10).count(\"ll\"))\n",
    "print((\"hello\" * 10).count(\"lo\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "technological-amazon",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sat(\"oh\") # after some thinking, Eureka!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "satisfied-wales",
   "metadata": {},
   "source": [
    "**How satisfying**! And you may have learned about the `count` function or `*` for strings."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "radical-verse",
   "metadata": {},
   "source": [
    "# Problems the AI models solved\n",
    "How many can you solve? Below are seven problems the at least one of our AI baseline models solved. In our user study, participants only had 6 minutes to solve each problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "postal-charles",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(s: str):\n",
    "    return s.count('o') == 1000 and s.count('oo') == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "imperial-treatment",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "south-wilderness",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(li: List[int]):\n",
    "    return li.count(17) == 3 and li.count(3) >= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "reduced-orchestra",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here (you can add more cells with the + button above)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "fitting-questionnaire",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(li: List[int]):\n",
    "    return li[li[0]] != li[li[1]] and li[li[li[0]]] == li[li[li[1]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "detected-logic",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "agricultural-compatibility",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(li: List[int]):\n",
    "    return all([li[i] != li[i + 1] for i in range(10)]) and len(set(li)) == 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "pressing-economy",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "massive-upper",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(ls: List[str]):\n",
    "    return tuple(ls) in zip('dee', 'doo', 'dah!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "seeing-transsexual",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "obvious-wildlife",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(si: Set[int]):\n",
    "    return {i + j for i in si for j in si} == {0, 1, 2, 3, 4, 5, 6, 17, 18, 19, 20, 34}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "postal-border",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "traditional-dictionary",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(li: List[int]):\n",
    "    return all([123 * li[i] % 1000 < 123 * li[i + 1] % 1000 and li[i] in range(1000) for i in range(20)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "occupational-bruce",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "multiple-regard",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(quine: str):\n",
    "    return len(quine) < 6 and eval(quine) == quine"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "fitting-lecture",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hired-commons",
   "metadata": {},
   "source": [
    "The models include a few-shot GPT-3 solver and enumerative search techniques using random forests and deep models. The last is a puzzle version of the classic [quine](https://en.wikipedia.org/wiki/Quine_(computing)) programming challenge of writing a program that prints itself out---this puzzle asks for a string whose evaluation is the same string itself. Moreover, the string has to have fewer than 6 characters. This puzzle was created during a fun [Microsoft Hackathon](https://github.com/microsoft/PythonProgrammingPuzzles#hackathon).\n",
    "\n",
    "\n",
    "This was solved by the GPT-3 model. The way the GPT-3 API works is that you give it a *prompt* and you ask it to complete the prompt. We gave it the following prompt:\n",
    "```python\n",
    "def sat(quine: str):\n",
    "    return len(quine) < 6 and eval(quine) == quine\n",
    "```\n",
    "\n",
    "```python\n",
    "assert True == sat(\n",
    "```\n",
    "\n",
    "GPT-3's first completion was \n",
    "\n",
    "```python\n",
    "'''Print[myself]''')\n",
    "```\n",
    "\n",
    "While it's too long and does not evaluate to itself, it clearly seems like the AI has some \"idea\" of what it is supposed to generate, but this type of quine is different than the standard one which needs to print something out. However, on the 37th completion, it outputted a valid solution. Is that cheating? No, the AI can make multiple tries just programmers often do. Did you make multiple attempts before solving some of the above problems? The objective advantage of puzzles is that the solver knows when it's done. If this were a programming competition where you only get one submission, you would evaluate your own submissions first of course to see if they are right. And the computer evaluates its own submissions really quickly!\n",
    "\n",
    "See [our paper](https://arxiv.org/abs/2106.05784) for details."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "purple-edwards",
   "metadata": {},
   "source": [
    "# Problems GPT-3 didn't solve\n",
    "Below are five problems none of our AI models solved. *Update*: Codex eventually solved all 30 puzzles! See its\n",
    "solutions (in order of easiest to hardest puzzles) at:\n",
    "[https://github.com/microsoft/PythonProgrammingPuzzles/blob/main/puzzles/README.md#study](https://github.com/microsoft/PythonProgrammingPuzzles/blob/main/puzzles/README.md#study)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "assigned-elder",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(s: str):\n",
    "    return s.count('o') == 1000 and s.count('oo') == 100 and s.count('ho') == 801"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "ethical-starter",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "canadian-anaheim",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(s: str):\n",
    "    return sorted(s) == sorted('Permute me true') and s == s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "surgical-edmonton",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "standard-mandate",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(s: str):\n",
    "    return s[::2] in s and len(set(s)) == 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "brilliant-qualification",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "interior-repeat",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(moves: List[List[int]]):\n",
    "    towers = ([8, 7, 6, 5, 4, 3, 2, 1], [], [])\n",
    "    for [i, j] in moves:\n",
    "        towers[j].append(towers[i].pop())\n",
    "        assert towers[j][-1] == min(towers[j]), \"larger disk on top of smaller disk\"\n",
    "    return towers[2] == [8, 7, 6, 5, 4, 3, 2, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "resident-announcement",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "trying-tenant",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sat(x: List[int]): \n",
    "    s = \"Dynamic programming solves this classic job-interview puzzle!!!\"\n",
    "    return all(s[x[i]] <= s[x[i+1]] and x[i] < x[i+1] for i in range(25))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "apart-salon",
   "metadata": {},
   "outputs": [],
   "source": [
    "# your solution here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "surprised-friendship",
   "metadata": {},
   "source": [
    "# Want more?\n",
    "* Most of the problems came from a 30-puzzle user study we ran where participants had 6 minutes to solve each puzzle. You can try it out at [this notebook](https://aka.ms/python_puzzles_study)\n",
    "* **Visit our open-source GitHub repository** https://github.com/microsoft/PythonProgrammingPuzzles to explore the full dataset and **please contribute your own new puzzles**\n",
    "* **Share this notebook**: https://aka.ms/python_puzzles\n",
    "* **Read our [arXiv paper](https://arxiv.org/abs/2106.05784)**. "
   ]
  }
 ],
 "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}