Last active
May 17, 2016 22:30
-
-
Save ovolve/77e336ab05fda2aa25ebce8a33677679 to your computer and use it in GitHub Desktop.
Brute forcing a menacing maths problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"[Referencing this blog post](https://medium.com/@fjmubeen/my-nephew-brought-home-this-menacing-maths-problem-e8bbba30e5cb#.79es8wsz2)\n", | |
"\n", | |
"How many combinations are there?" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"331776" | |
] | |
}, | |
"execution_count": 1, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"import math\n", | |
"math.factorial(4)**4" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"Few enough to brute force :)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 2, | |
"metadata": { | |
"collapsed": true | |
}, | |
"outputs": [], | |
"source": [ | |
"from itertools import product, permutations\n", | |
"\n", | |
"# converts a list of ditits to the base 10 integer\n", | |
"to_num = lambda digits: sum(map(lambda (i, n): n*10**i, enumerate(reversed(digits))))\n", | |
"\n", | |
"# all numbers that are permutations of the digits\n", | |
"perms = map(to_num, permutations([1,2,3,4]))\n", | |
"\n", | |
"# all combinations of four of those numbers (itertools.product is Cartesian product)\n", | |
"combos = product(*[perms]*4)\n", | |
"\n", | |
"# sum them\n", | |
"sums = map(sum, combos)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"True\n", | |
"True\n" | |
] | |
} | |
], | |
"source": [ | |
"# sanity checks\n", | |
"print len(sums) == math.factorial(4)**4\n", | |
"print (1234*4, 4321*4) == (min(sums), max(sums))" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 5, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"False" | |
] | |
}, | |
"execution_count": 5, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"9000 in sums" | |
] | |
} | |
], | |
"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.10" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 0 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment