{
 "metadata": {
  "name": "",
  "signature": "sha256:19e3752b2e7b6f5dbb9d14513de43a092ad72d63f644c33413b120fb323a1324"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def is_anagram(first, second):\n",
      "    return sorted(str(first)) == sorted(str(second))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "is_anagram(1264, 1543)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "is_anagram(1264, 1642)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cubes = {}\n",
      "cube_lens = {}\n",
      "n = 1\n",
      "cube = 1\n",
      "while len(str(cube)) < 15:\n",
      "    cubes[n] = cube\n",
      "    cube_lens[n] = len(str(cube))\n",
      "    n += 1\n",
      "    cube = n ** 3"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "La version pas super efficace"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "max(cubes.keys())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 58,
       "text": [
        "46415"
       ]
      }
     ],
     "prompt_number": 58
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "candidates = [cubes[i] for i in range(1, max(cubes.keys())) if cube_lens[i] == 8]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 59
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "anagrams = {}\n",
      "for c in candidates:\n",
      "    for o in candidates:\n",
      "        if is_anagram(c, o):\n",
      "            if c not in anagrams:\n",
      "                anagrams[c] = [o]\n",
      "            else:\n",
      "                anagrams[c].append(o)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 60
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[anagrams[c] for c in anagrams.keys() if len(anagrams[c]) >= 3]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 62,
       "text": [
        "[[41063625, 56623104, 66430125],\n",
        " [41063625, 56623104, 66430125],\n",
        " [41063625, 56623104, 66430125]]"
       ]
      }
     ],
     "prompt_number": 62
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "c"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 63,
       "text": [
        "64481201"
       ]
      }
     ],
     "prompt_number": 63
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "La version un peu plus efficace ?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "candidates = [cubes[i] for i in range(1, max(cubes.keys())) if cube_lens[i] == 12]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 64
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sorted_candidates = [\"\".join(sorted(str(c))) for c in candidates]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 65
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from collections import Counter\n",
      "c = Counter(sorted_candidates)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 66
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "c.most_common(5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 67,
       "text": [
        "[('012334566789', 5),\n",
        " ('012334556789', 5),\n",
        " ('122334566788', 4),\n",
        " ('011245567789', 4),\n",
        " ('011223346789', 4)]"
       ]
      }
     ],
     "prompt_number": 67
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for c in candidates:\n",
      "    if is_anagram(c, 102334556789):\n",
      "        print(c)\n",
      "        break"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "127035954683\n"
       ]
      }
     ],
     "prompt_number": 68
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "C'est beaucoup plus efficace comme \u00e7a !\n",
      "\n",
      "La raison ? On a plus besoin de faire toutes les comparaisons dans les anagrammes. Sachant que si $n$ est le nombre de candidates, on a $n^2$ comparaisons d'anagrammes \u00e0 faire, ce qui est beaucoup.\n",
      "\n",
      "Dans cette m\u00e9thode, il suffit de compter le nombre d'occurences d'une permutation et on prend le plus grand nombre d'occurences."
     ]
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "En plus propre"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "candidates = [cubes[i] for i in range(1, max(cubes.keys())) if cube_lens[i] == 14]\n",
      "len_dict = {}\n",
      "for c in candidates:\n",
      "    key = \"\".join(sorted(str(c)))\n",
      "    if key not in len_dict:\n",
      "        len_dict[key] = [c]\n",
      "    else:\n",
      "        len_dict[key].append(c)\n",
      "s = sorted(list(len_dict.iteritems()), key=lambda s: len(s[1]), reverse=True)\n",
      "max_len = len(s[0][1])\n",
      "for i in range(5):\n",
      "    print \"{0} combinations, smallest cube: {1}\".format(len(s[i][1]), s[i][1][0])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "9 combinations, smallest cube: 13465983902671\n",
        "8 combinations, smallest cube: 10314675896832\n",
        "8 combinations, smallest cube: 10340284735656\n",
        "8 combinations, smallest cube: 15302864497283\n",
        "8 combinations, smallest cube: 12620043581768\n"
       ]
      }
     ],
     "prompt_number": 69
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Au lieu de calculer des permutations, il est plus simples de juste prendre une seule repr\u00e9sentation du nombre sous forme de chiffres tri\u00e9s qu'on utilise comme cl\u00e9 dans un dictionnaire. C'est cool \u00e7a !"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}