Skip to content

Instantly share code, notes, and snippets.

@mbarkhau

mbarkhau/euler_hack_006.ipynb

Created June 8, 2017 21:18
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mbarkhau/1454b099b5d6834182388db14c33beb0 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mbarkhau/1454b099b5d6834182388db14c33beb0 to your computer and use it in GitHub Desktop.
Download ZIP
euler_hack_006.ipynb
Display the source blob
Display the rendered blob
Raw
euler_hack_006.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Euler Hack #6"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Formalities:\n",
" - Host: admetrics GmbH\n",
" - Facilities/Refreshments\n",
" - Random Problems with increasing difficulty\n",
" - Follow Along\n",
" - Break\n",
" - Jupyter Notebook in comments on meetup.com"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 301: Nim\n",
"\n",
"\n",
"Nim is a game played with heaps of stones, where two players take it in turn to remove any number of stones from any heap until no stones remain.\n",
"\n",
"We'll consider the three-heap normal-play version of Nim, which works as follows:\n",
"- At the start of the game there are three heaps of stones.\n",
"- On his turn the player removes any positive number of stones from any single heap.\n",
"- The first player unable to move (because no stones remain) loses.\n",
"\n",
"If (n1,n2,n3) indicates a Nim position consisting of heaps of size n1, n2 and n3 then there is a simple function X(n1,n2,n3) — that you may look up or attempt to deduce for yourself — that returns:\n",
"\n",
" - zero if, with perfect strategy, the player about to move will eventually lose; or\n",
" - non-zero if, with perfect strategy, the player about to move will eventually win.\n",
"\n",
"For example X(1,2,3) = 0 because, no matter what the current player does, his opponent can respond with a move that leaves two heaps of equal size, at which point every move by the current player can be mirrored by his opponent until no stones remain; so the current player loses. To illustrate:\n",
"- current player moves to (1,2,1)\n",
"- opponent moves to (1,0,1)\n",
"- current player moves to (0,0,1)\n",
"- opponent moves to (0,0,0), and so wins.\n",
"\n",
"For how many positive integers n ≤ 2^30 does X(n,2n,3n) = 0 ?\n"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%load_ext Cython"
]
},
{
"cell_type": "code",
"execution_count": 121,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%%cython\n",
"def faster_X(int a, int b, int c):\n",
" if (a ^ b ^ c) > 0:\n",
" return 1\n",
" return 0"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%%cython\n",
"def fast_X(int a, int b, int c):\n",
" while a + b + c > 0:\n",
" # print(bin(a), bin(b), bin(c), ((a & 1) + (b & 1) + (c & 1)) % 2 > 0)\n",
" if ((a & 1) + (b & 1) + (c & 1)) & 1 == 1:\n",
" return 1\n",
" a >>= 1\n",
" b >>= 1\n",
" c >>= 1\n",
" return 0"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def X(a, b, c):\n",
" while a + b + c > 0:\n",
" # print(bin(a), bin(b), bin(c), ((a & 1) + (b & 1) + (c & 1)) % 2 > 0)\n",
" if ((a & 1) + (b & 1) + (c & 1)) % 2 > 0:\n",
" return 1\n",
" a >>= 1\n",
" b >>= 1\n",
" c >>= 1\n",
" return 0"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1000000 loops, best of 3: 2.49 µs per loop\n"
]
}
],
"source": [
"%timeit X(2, 4, 8)"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The slowest run took 13.59 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
"1000000 loops, best of 3: 222 ns per loop\n"
]
}
],
"source": [
"%timeit fast_X(2, 4, 8)"
]
},
{
"cell_type": "code",
"execution_count": 123,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The slowest run took 24.07 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
"1000000 loops, best of 3: 197 ns per loop\n"
]
}
],
"source": [
"%timeit faster_X(2, 4, 8)"
]
},
{
"cell_type": "code",
"execution_count": 122,
"metadata": {},
"outputs": [],
"source": [
"for n in range(1, 1000):\n",
" a = n\n",
" b = n * 2\n",
" c = n * 3\n",
" # print(n, a, b, c, X(a, b, c), faster_X(a, b, c))\n",
" assert X(a, b, c) == fast_X(a, b, c)\n",
" assert X(a, b, c) == faster_X(a, b, c)\n",
" \n",
"X = faster_X"
]
},
{
"cell_type": "code",
"execution_count": 86,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1 0 1 10 11\n",
" 2 0 10 100 110\n",
" 3 1 11 110 1001\n",
" 4 0 100 1000 1100\n",
" 5 0 101 1010 1111\n",
" 6 1 110 1100 10010\n",
" 7 1 111 1110 10101\n",
" 8 0 1000 10000 11000\n",
" 9 0 1001 10010 11011\n",
" 10 0 1010 10100 11110\n",
" 11 1 1011 10110 100001\n",
" 12 1 1100 11000 100100\n",
" 13 1 1101 11010 100111\n",
" 14 1 1110 11100 101010\n",
" 15 1 1111 11110 101101\n",
" 16 0 10000 100000 110000\n",
" 17 0 10001 100010 110011\n",
" 18 0 10010 100100 110110\n",
" 19 1 10011 100110 111001\n",
" 20 0 10100 101000 111100\n",
" 21 0 10101 101010 111111\n",
" 22 1 10110 101100 1000010\n",
" 23 1 10111 101110 1000101\n",
" 24 1 11000 110000 1001000\n",
" 25 1 11001 110010 1001011\n",
" 26 1 11010 110100 1001110\n",
" 27 1 11011 110110 1010001\n",
" 28 1 11100 111000 1010100\n",
" 29 1 11101 111010 1010111\n",
" 30 1 11110 111100 1011010\n",
" 31 1 11111 111110 1011101\n",
" 32 0 100000 1000000 1100000\n",
" 33 0 100001 1000010 1100011\n",
" 34 0 100010 1000100 1100110\n",
" 35 1 100011 1000110 1101001\n",
" 36 0 100100 1001000 1101100\n",
" 37 0 100101 1001010 1101111\n",
" 38 1 100110 1001100 1110010\n",
" 39 1 100111 1001110 1110101\n",
" 40 0 101000 1010000 1111000\n",
" 41 0 101001 1010010 1111011\n",
" 42 0 101010 1010100 1111110\n",
" 43 1 101011 1010110 10000001\n",
" 44 1 101100 1011000 10000100\n",
" 45 1 101101 1011010 10000111\n",
" 46 1 101110 1011100 10001010\n",
" 47 1 101111 1011110 10001101\n",
" 48 1 110000 1100000 10010000\n",
" 49 1 110001 1100010 10010011\n",
" 50 1 110010 1100100 10010110\n",
" 51 1 110011 1100110 10011001\n",
" 52 1 110100 1101000 10011100\n",
" 53 1 110101 1101010 10011111\n",
" 54 1 110110 1101100 10100010\n",
" 55 1 110111 1101110 10100101\n",
" 56 1 111000 1110000 10101000\n",
" 57 1 111001 1110010 10101011\n",
" 58 1 111010 1110100 10101110\n",
" 59 1 111011 1110110 10110001\n",
" 60 1 111100 1111000 10110100\n",
" 61 1 111101 1111010 10110111\n",
" 62 1 111110 1111100 10111010\n",
" 63 1 111111 1111110 10111101\n",
" 64 0 1000000 10000000 11000000\n",
" 65 0 1000001 10000010 11000011\n",
" 66 0 1000010 10000100 11000110\n",
" 67 1 1000011 10000110 11001001\n",
" 68 0 1000100 10001000 11001100\n",
" 69 0 1000101 10001010 11001111\n",
" 70 1 1000110 10001100 11010010\n",
" 71 1 1000111 10001110 11010101\n",
" 72 0 1001000 10010000 11011000\n",
" 73 0 1001001 10010010 11011011\n",
" 74 0 1001010 10010100 11011110\n",
" 75 1 1001011 10010110 11100001\n",
" 76 1 1001100 10011000 11100100\n",
" 77 1 1001101 10011010 11100111\n",
" 78 1 1001110 10011100 11101010\n",
" 79 1 1001111 10011110 11101101\n",
" 80 0 1010000 10100000 11110000\n",
" 81 0 1010001 10100010 11110011\n",
" 82 0 1010010 10100100 11110110\n",
" 83 1 1010011 10100110 11111001\n",
" 84 0 1010100 10101000 11111100\n",
" 85 0 1010101 10101010 11111111\n",
" 86 1 1010110 10101100 100000010\n",
" 87 1 1010111 10101110 100000101\n",
" 88 1 1011000 10110000 100001000\n",
" 89 1 1011001 10110010 100001011\n",
" 90 1 1011010 10110100 100001110\n",
" 91 1 1011011 10110110 100010001\n",
" 92 1 1011100 10111000 100010100\n",
" 93 1 1011101 10111010 100010111\n",
" 94 1 1011110 10111100 100011010\n",
" 95 1 1011111 10111110 100011101\n",
" 96 1 1100000 11000000 100100000\n",
" 97 1 1100001 11000010 100100011\n",
" 98 1 1100010 11000100 100100110\n",
" 99 1 1100011 11000110 100101001\n"
]
}
],
"source": [
"\n",
"for n in range(1, 100):\n",
" # n = 2 ** n + 1\n",
" a = n\n",
" b = n * 2\n",
" c = n * 3\n",
" x = X(a, b, c)\n",
" print(f\"{n:>5} {x} {a:16b} {b:16b} {c:16b}\")\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 1.0251998901367188e-05\n",
"1 1.6450881958007812e-05\n",
"2 1.4543533325195312e-05\n",
"3 1.0251998901367188e-05\n",
"4 7.3909759521484375e-06\n",
"5 2.5510787963867188e-05\n",
"6 2.7418136596679688e-05\n",
"7 8.702278137207031e-05\n",
"8 0.00012564659118652344\n",
"9 0.0001990795135498047\n",
"10 0.00047397613525390625\n",
"11 0.0009169578552246094\n",
"12 0.0014908313751220703\n",
"13 0.002378225326538086\n",
"14 0.003952503204345703\n",
"15 0.01181340217590332\n",
"16 0.018413543701171875\n",
"17 0.12661123275756836\n",
"18 0.1915276050567627\n",
"19 0.412381649017334\n",
"20 0.8123948574066162\n",
"21 1.9627010822296143\n",
"22 3.305138111114502\n",
"23 7.807108640670776\n"
]
}
],
"source": [
"import time\n",
"for power in range(24):\n",
" t0 = time.time()\n",
" sum(X(n, n * 2, n * 3) for n in range(1, 2**power))\n",
" print(power, time.time() - t0)\n"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [
{
"ename": "KeyboardInterrupt",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-82-5a80e357d430>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0msum\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfast_X\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mn\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m**\u001b[0m\u001b[0;36m30\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;32m<ipython-input-82-5a80e357d430>\u001b[0m in \u001b[0;36m<genexpr>\u001b[0;34m(.0)\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0msum\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfast_X\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mn\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m**\u001b[0m\u001b[0;36m30\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[0;31mKeyboardInterrupt\u001b[0m: "
]
}
],
"source": [
"sum(fast_X(n, n * 2, n * 3) for n in range(1, 2**30))"
]
},
{
"cell_type": "code",
"execution_count": 126,
"metadata": {},
"outputs": [],
"source": [
"%%cython\n",
"# incorrect\n",
"\n",
"def solve(max_n=2**30 + 1):\n",
" cdef int a, b, c, n, res\n",
" res = 0\n",
" for n in range(1, max_n):\n",
" a = n\n",
" b = n * 2\n",
" c = n * 3\n",
" while a + b + c > 0:\n",
" if ((a & 1) + (b & 1) + (c & 1)) & 1 == 1:\n",
" res += 1\n",
" break\n",
" a >>= 1\n",
" b >>= 1\n",
" c >>= 1\n",
" return res"
]
},
{
"cell_type": "code",
"execution_count": 125,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2178309"
]
},
"execution_count": 125,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solve()"
]
},
{
"cell_type": "code",
"execution_count": 131,
"metadata": {},
"outputs": [],
"source": [
"%%cython\n",
"def solve(max_n=2**30 + 1):\n",
" cdef int a, b, c, n, res\n",
" res = 0\n",
" for n in range(1, max_n):\n",
" a = n\n",
" b = n * 2\n",
" c = n * 3\n",
" nim_sum = a ^ b ^ c\n",
" if nim_sum == 0:\n",
" res += 1\n",
" return res"
]
},
{
"cell_type": "code",
"execution_count": 132,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2178308"
]
},
"execution_count": 132,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solve()"
]
},
{
"cell_type": "code",
"execution_count": 112,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'0b0'"
]
},
"execution_count": 112,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"2178309"
]
},
{
"cell_type": "code",
"execution_count": 113,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 113,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"15 & 1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"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.0"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment