{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "https://projecteuler.net/problem=206" ] }, { "cell_type": "code", "execution_count": 95, "metadata": { "collapsed": true }, "outputs": [], "source": [ "pattern = '1_2_3_4_5_6_7_8_9_0'" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Is compatible " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's write a function that says if a given number is compatible with the pattern." ] }, { "cell_type": "code", "execution_count": 176, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def is_compatible(number, pattern, start_from_end=True, joker='_'):\n", " \"\"\"Checks whether number is compatible with pattern.\n", " Can start the check at the beginning or the end of the number.\"\"\"\n", " number = int(number)\n", " if start_from_end:\n", " number_str = str(number)[::-1]\n", " pattern = pattern[::-1]\n", " else:\n", " number_str = str(number)\n", " until = min(len(number_str), len(pattern))\n", " for a, b in zip(number_str, pattern):\n", " if b == joker:\n", " continue\n", " if a != b:\n", " return False\n", " return True" ] }, { "cell_type": "code", "execution_count": 177, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 177, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_compatible(123, '1_3')" ] }, { "cell_type": "code", "execution_count": 178, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 178, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_compatible(123, '12_')" ] }, { "cell_type": "code", "execution_count": 179, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 179, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_compatible(123, '12_', start_from_end=False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Building numbers " ] }, { "cell_type": "code", "execution_count": 180, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [ "from itertools import product" ] }, { "cell_type": "code", "execution_count": 181, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "data": { "text/plain": [ "[(0, 0), (3, 0), (7, 0)]" ] }, "execution_count": 181, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(product([0, 3, 7], [0]))" ] }, { "cell_type": "code", "execution_count": 286, "metadata": { "collapsed": true, "deletable": true, "editable": true }, "outputs": [], "source": [ "def build_numbers(*last_possible_digits):\n", " if len(last_possible_digits) == 1 and len(last_possible_digits[0]) == 0:\n", " yield 0\n", " else:\n", " for tup in product(*last_possible_digits):\n", " yield int(sum(d * 10**(len(tup) -1 - i) for i, d in enumerate(tup)))" ] }, { "cell_type": "code", "execution_count": 287, "metadata": { "collapsed": false, "deletable": true, "editable": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n", "30\n", "70\n" ] } ], "source": [ "for n in build_numbers([0, 3, 7], [0]):\n", " print(n)" ] }, { "cell_type": "code", "execution_count": 288, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "100\n", "130\n", "170\n", "200\n", "230\n", "270\n" ] } ], "source": [ "for n in build_numbers([1, 2], [0, 3, 7], [0]):\n", " print(n)" ] }, { "cell_type": "code", "execution_count": 289, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n" ] } ], "source": [ "for n in build_numbers([]):\n", " print(n)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Last digit 1" ] }, { "cell_type": "code", "execution_count": 253, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0]" ] }, "execution_count": 253, "metadata": {}, "output_type": "execute_result" } ], "source": [ "possible_digits = set()\n", "for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " n = digit\n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", "list(possible_digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Before last 2 " ] }, { "cell_type": "code", "execution_count": 254, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0, 3, 7]" ] }, "execution_count": 254, "metadata": {}, "output_type": "execute_result" } ], "source": [ "possible_digits = set()\n", "for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " for remainder in build_numbers([0]):\n", " n = 10 * digit + remainder\n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", "list(possible_digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Before last last 3 " ] }, { "cell_type": "code", "execution_count": 255, "metadata": { "collapsed": false, "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "[0, 8, 4, 5]" ] }, "execution_count": 255, "metadata": {}, "output_type": "execute_result" } ], "source": [ "possible_digits = set()\n", "for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " for remainder in build_numbers([0, 3, 7], [0]):\n", " n = 100 * digit + remainder\n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", "list(possible_digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Digit 4 " ] }, { "cell_type": "code", "execution_count": 256, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0]" ] }, "execution_count": 256, "metadata": {}, "output_type": "execute_result" } ], "source": [ "possible_digits = set()\n", "for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " for remainder in build_numbers([0, 8, 4, 5], [0, 3, 7], [0]):\n", " n = 1000 * digit + remainder\n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", "list(possible_digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Digit 5" ] }, { "cell_type": "code", "execution_count": 257, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0, 4]" ] }, "execution_count": 257, "metadata": {}, "output_type": "execute_result" } ], "source": [ "possible_digits = set()\n", "for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " for remainder in build_numbers([0], [0, 8, 4, 5], [0, 3, 7], [0]):\n", " n = 10000 * digit + remainder\n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", "list(possible_digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Digit 6 " ] }, { "cell_type": "code", "execution_count": 258, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0]" ] }, "execution_count": 258, "metadata": {}, "output_type": "execute_result" } ], "source": [ "possible_digits = set()\n", "for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " for remainder in build_numbers([0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):\n", " n = int(100000 * digit + remainder)\n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", "list(possible_digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Digit 7 " ] }, { "cell_type": "code", "execution_count": 259, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0]" ] }, "execution_count": 259, "metadata": {}, "output_type": "execute_result" } ], "source": [ "possible_digits = set()\n", "for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " for remainder in build_numbers([0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):\n", " n = int(1000000 * digit + remainder)\n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", "list(possible_digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Digit 8 " ] }, { "cell_type": "code", "execution_count": 260, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0]" ] }, "execution_count": 260, "metadata": {}, "output_type": "execute_result" } ], "source": [ "possible_digits = set()\n", "for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " for remainder in build_numbers([0], [0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):\n", " n = int(10000000 * digit + remainder)\n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", "list(possible_digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Digit 9 " ] }, { "cell_type": "code", "execution_count": 261, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0]" ] }, "execution_count": 261, "metadata": {}, "output_type": "execute_result" } ], "source": [ "possible_digits = set()\n", "for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " for remainder in build_numbers([0], [0], [0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):\n", " n = int(100000000 * digit + remainder)\n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", "list(possible_digits)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Final number " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since the first digit is a 1, we can finish this." ] }, { "cell_type": "code", "execution_count": 262, "metadata": { "collapsed": false }, "outputs": [], "source": [ "for n in build_numbers([0, 1], [0], [0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):\n", " if is_compatible(n**2, pattern, start_from_end=False):\n", " print(n)" ] }, { "cell_type": "code", "execution_count": 299, "metadata": { "collapsed": false }, "outputs": [], "source": [ "n = 40830" ] }, { "cell_type": "code", "execution_count": 300, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1667088900" ] }, "execution_count": 300, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n**2" ] }, { "cell_type": "code", "execution_count": 301, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'1_2_3_4_5_6_7_8_9_0'" ] }, "execution_count": 301, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pattern" ] }, { "cell_type": "code", "execution_count": 303, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 303, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_compatible(n**2, pattern, start_from_end=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Single loop " ] }, { "cell_type": "code", "execution_count": 311, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n", "0 [0]\n", "0\n", "30\n", "70\n", "1 [0, 3, 7]\n", "0\n", "30\n", "70\n", "430\n", "530\n", "830\n", "2 [0, 8, 4, 5]\n", "0\n", "30\n", "70\n", "830\n", "430\n", "530\n", "3 [0]\n", "0\n", "30\n", "70\n", "830\n", "430\n", "530\n", "40830\n", "4 [0, 4]\n", "0\n", "30\n", "70\n", "830\n", "430\n", "530\n", "40830\n", "5 [0]\n", "0\n", "30\n", "70\n", "830\n", "430\n", "530\n", "40830\n", "6 [0]\n", "0\n", "30\n", "70\n", "830\n", "430\n", "530\n", "40830\n", "7 [0]\n", "0\n", "30\n", "70\n", "830\n", "430\n", "530\n", "40830\n", "8 [0]\n", "0\n", "30\n", "70\n", "830\n", "430\n", "530\n", "40830\n", "9 [0]\n", "0\n", "30\n", "70\n", "830\n", "430\n", "530\n", "40830\n", "10 [0]\n", "0\n", "30\n", "70\n", "830\n", "430\n", "530\n", "40830\n", "11 [0]\n" ] } ], "source": [ "end_digits = []\n", "for current_power in range(12):\n", " possible_digits = set()\n", " for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:\n", " for remainder in build_numbers(*end_digits):\n", " n = digit * 10**current_power + remainder\n", " \n", " if is_compatible(n**2, pattern, start_from_end=True):\n", " possible_digits.add(digit)\n", " print(n)\n", " print(current_power, list(possible_digits))\n", " end_digits.insert(0, list(possible_digits))" ] }, { "cell_type": "code", "execution_count": 309, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "24" ] }, "execution_count": 309, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(str(n**2))" ] }, { "cell_type": "code", "execution_count": 310, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "19" ] }, "execution_count": 310, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(pattern)" ] }, { "cell_type": "code", "execution_count": 296, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[[0], [0], [0], [0], [0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]]" ] }, "execution_count": 296, "metadata": {}, "output_type": "execute_result" } ], "source": [ "end_digits" ] }, { "cell_type": "code", "execution_count": 270, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3000000000" ] }, "execution_count": 270, "metadata": {}, "output_type": "execute_result" } ], "source": [ "3 * 10**9" ] }, { "cell_type": "code", "execution_count": 273, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[]" ] }, "execution_count": 273, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(build_numbers([]))" ] }, { "cell_type": "code", "execution_count": 274, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 274, "metadata": {}, "output_type": "execute_result" } ], "source": [ "build_numbers([])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Smallest and largest n" ] }, { "cell_type": "code", "execution_count": 348, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from math import sqrt" ] }, { "cell_type": "code", "execution_count": 353, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1389026623" ] }, "execution_count": 353, "metadata": {}, "output_type": "execute_result" } ], "source": [ "maxi = int(sqrt(int(pattern.replace('_', '9'))))\n", "maxi" ] }, { "cell_type": "code", "execution_count": 355, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1010101010" ] }, "execution_count": 355, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mini = int(sqrt(int(pattern.replace('_', '0'))))\n", "mini" ] }, { "cell_type": "code", "execution_count": 356, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'40830'" ] }, "execution_count": 356, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"40830\"" ] }, { "cell_type": "code", "execution_count": 375, "metadata": { "collapsed": false }, "outputs": [], "source": [ "for i in range(1000000, 138999):\n", " n = int(str(i) + str(830))\n", " if is_compatible(n**2, pattern, start_from_end=False):\n", " print(n)" ] }, { "cell_type": "code", "execution_count": 376, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 376, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_compatible(n**2, pattern, start_from_end=False)" ] }, { "cell_type": "code", "execution_count": 377, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1389040830" ] }, "execution_count": 377, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n" ] }, { "cell_type": "code", "execution_count": 378, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1929434427407088900" ] }, "execution_count": 378, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n**2" ] }, { "cell_type": "code", "execution_count": 379, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'1_2_3_4_5_6_7_8_9_0'" ] }, "execution_count": 379, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pattern" ] }, { "cell_type": "code", "execution_count": 380, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "19" ] }, "execution_count": 380, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(str(n**2))" ] }, { "cell_type": "code", "execution_count": 381, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "19" ] }, "execution_count": 381, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(pattern)" ] }, { "cell_type": "code", "execution_count": 382, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 382, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_compatible(7088900, pattern, start_from_end=True)" ] }, { "cell_type": "code", "execution_count": 383, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "688900" ] }, "execution_count": 383, "metadata": {}, "output_type": "execute_result" } ], "source": [ "830**2" ] }, { "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.5.2" } }, "nbformat": 4, "nbformat_minor": 0 }