{
 "metadata": {
  "name": "",
  "signature": "sha256:762d7ea2e3d132ccef32d9e2037813880db440be51c5ac394faed73046ea0921"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from gmpy2 import mpq # not used, the formula is evaluted the python way, not mathematically\n",
      "from __future__ import division\n",
      "from itertools import *\n",
      "def powerset(iterable):\n",
      "    \"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)\"\n",
      "    s = list(iterable)\n",
      "    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))\n",
      "# originally, use the code from http://mattdodge.net/24-a-childhood-game-taken-to-the-next-level/\n",
      "# but it is buggy, cannot find solution of [12,12,12,10]\n",
      "# so I wrote my own\n",
      "def ev(nums):\n",
      "    if len(nums)==1:\n",
      "        return {nums[0]:\"%d\"%nums[0], -nums[0]:\"-%d\"%nums[0]}\n",
      "    rtn =dict()\n",
      "    for idx in powerset(range(len(nums))):\n",
      "        if len(idx) in (0, len(nums)):\n",
      "            continue\n",
      "        s1 = sorted(nums[i] for i in idx)\n",
      "        s2 = sorted(nums[i] for i in range(len(nums)) if i not in idx)\n",
      "        if s1>s2:\n",
      "            continue\n",
      "        r1, r2 = ev(s1), ev(s2)\n",
      "        for a,a1 in r1.items():\n",
      "            for b,b1 in r2.items():\n",
      "                rtn[a+b]=\"(%s)+(%s)\"%(a1,b1)\n",
      "                rtn[a*b]=\"(%s)*(%s)\"%(a1,b1)\n",
      "                # the code is ugly because it was originally wrote for rational numbers (mpq)\n",
      "                # but then, modified the code for floating numbers instead because of // operator\n",
      "                try:\n",
      "                    rtn[a/b]=\"(%s)/(%s)\"%(a1,b1)\n",
      "                except:\n",
      "                    pass\n",
      "                try:\n",
      "                    rtn[b/a]=\"(%s)/(%s)\"%(b1,a1)\n",
      "                except:\n",
      "                    pass\n",
      "                try:\n",
      "                    rtn[a//b]=\"(%s)//(%s)\"%(a1,b1)\n",
      "                except:\n",
      "                    pass\n",
      "                try:\n",
      "                    rtn[b//a]=\"(%s)//(%s)\"%(b1,a1)\n",
      "                except:\n",
      "                    pass\n",
      "                rtn[a-b]=\"(%s)-(%s)\"%(a1,b1)\n",
      "                rtn[b-a]=\"(%s)-(%s)\"%(b1,a1)\n",
      "                try:\n",
      "                    if b< 100: # avoid very large power\n",
      "                        rtn[a**b]=\"(%s)**(%s)\"%(a1,b1)\n",
      "                except:\n",
      "                    pass\n",
      "                try:\n",
      "                    if a< 100:\n",
      "                        rtn[b**a]=\"(%s)**(%s)\"%(b1,a1)\n",
      "                except:\n",
      "                    pass\n",
      "    return rtn\n",
      "        \n",
      "def solve(n, nums):  \n",
      "    n = float(n)\n",
      "    rtn = ev(nums)\n",
      "    for k,v in rtn.items():\n",
      "        if abs(k-n)<0.000000001:\n",
      "            return v\n",
      "    \n",
      "    \n",
      " "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "solve(24, [5,5,5,2]) "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "'(-5)//(((-2)//(5))/(5))'"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import telnetlib\n",
      "import sys\n",
      "tel = telnetlib.Telnet(\"210.65.89.59\",2424)\n",
      "print \"start\"\n",
      "sys.stdout.flush()\n",
      "for i in range(1,25):\n",
      "    r = tel.read_until(\"Question (%d of 24): \"%i)\n",
      "    print r\n",
      "    sys.stdout.flush()\n",
      "    r = tel.read_until(\"]\")\n",
      "    nums = map(int, r[1:-1].split(\",\"))\n",
      "    ans = solve(24, nums)\n",
      "    print nums, ans\n",
      "    sys.stdout.flush()\n",
      "    tel.write(\"%s\\n\"%ans)\n",
      "print tel.read_all()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "start\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "===================================================\n",
        "===           Welcome to the 24 game!           ===\n",
        "=== You have 2 minutes to answer all questions. ===\n",
        "===================================================\n",
        "\n",
        "Question (1 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[12, 1, 1, 1] (-12)//(((-1)+(-1))**(-1))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (2 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[4, 2, 6, 6] ((6)//((-2)//(6)))*(-4)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (3 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[8, 12, 5, 5] (((5)*(5))//(-12))*(-8)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (4 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[8, 8, 6, 5] (8)-(((-6)//(5))*(8))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (5 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[5, 2, 4, 2] (((2)//(-2))-(5))*(-4)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (6 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[9, 3, 5, 4] (((-3)//(9))-(5))*(-4)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (7 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[5, 7, 2, 11] (-5)-((-7)-((-2)*(-11)))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (8 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[7, 11, 1, 4] (-11)-(((-1)-(4))*(7))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (9 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[10, 10, 9, 2] (10)-(((10)//(-2))+(-9))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (10 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[7, 2, 7, 10] (((10)/(7))-(-2))*(7)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (11 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[3, 7, 3, 7] ((-3)-((-3)/(-7)))*(-7)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (12 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1, 4, 5, 6] (((-1)//(6))-(5))*(-4)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (13 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[10, 10, 4, 2] ((-2)+((4)/(-10)))*(-10)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (14 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[5, 10, 5, 2] (((-2)/(10))+(5))*(5)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (15 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[7, 5, 7, 11] (7)//(((11)//(5))/(7))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (16 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[11, 2, 1, 5] (11)//((5)**((-2)**(-1)))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (17 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[8, 2, 1, 12] (((-1)//(12))+(-2))*(-8)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (18 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[3, 5, 5, 5] (-5)//(((-3)//(5))/(5))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (19 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[5, 1, 11, 13] (11)-((13)//((-1)**(5)))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (20 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[5, 5, 5, 13] ((5)*(5))+((5)//(-13))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (21 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[12, 13, 7, 13] (12)-((-13)-((7)//(-13)))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (22 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[10, 10, 12, 6] (10)-(((-10)//(6))-(12))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (23 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[6, 8, 12, 13] ((13)//((6)-(12)))*(-8)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Great!\n",
        "\n",
        "Question (24 of 24): \n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1, 4, 13, 13] (13)//((13)**((-1)/(4)))\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Answer: Good job! Here's your flag: HITCON{24_GAme_15_FUN}\n",
        "\n"
       ]
      }
     ],
     "prompt_number": 3
    }
   ],
   "metadata": {}
  }
 ]
}