From 04766a127c6257e4676fb0d2edafc9b9fa927ccb Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Mon, 27 Mar 2017 16:55:11 +0100 Subject: [PATCH] Done puzzle 51 --- euler51.ipynb | 485 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 485 insertions(+) create mode 100644 euler51.ipynb diff --git a/euler51.ipynb b/euler51.ipynb new file mode 100644 index 0000000..5681187 --- /dev/null +++ b/euler51.ipynb @@ -0,0 +1,485 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "true" + ] + }, + "execution_count": 1, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "load 'primes.rb'\n", + "load 'array-numbers.rb'\n", + "primes = Primes.instance\n", + "true" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":replace" + ] + }, + "execution_count": 2, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def replace(num, positions, replace_with)\n", + " digits = num.to_digits\n", + " positions.each do |p|\n", + " digits[p] = replace_with\n", + " end\n", + " digits.to_i\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "56993" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "replace(56003, [2, 3], 9)" + ] + }, + { + "cell_type": "code", + "execution_count": 38, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":replace_in_positions" + ] + }, + "execution_count": 38, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def replace_in_positions(num, positions)\n", + " (0..9).map {|d| replace num, positions, d}.select {|n| n.to_digits.length == num.to_digits.length}\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883, 56993]" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "replace_in_positions(56003, [2, 3])" + ] + }, + { + "cell_type": "code", + "execution_count": 50, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":count_primes_in_positions" + ] + }, + "execution_count": 50, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def count_primes_in_positions(num, positions)\n", + " others = replace_in_positions(num, positions).select {|n| n.prime?}\n", + " if others.include?(num)\n", + " others.length\n", + " else\n", + " 0\n", + " end\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "0" + ] + }, + "execution_count": 52, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "count_primes_in_positions(56004, [2, 3])" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":best_count_primes_r" + ] + }, + "execution_count": 8, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def best_count_primes_r(num, n_digits)\n", + " possibles = (0...num.to_digits.length).to_a\n", + " possibles.combination(n_digits).map {|ps| count_primes_in_positions(num, ps)}.max\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7" + ] + }, + "execution_count": 9, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "best_count_primes_r(56003, 2)" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "4" + ] + }, + "execution_count": 15, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "best_count_primes_r(3, 1)" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":best_count_primes" + ] + }, + "execution_count": 18, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def best_count_primes(num)\n", + " replacements = (1..num.to_digits.length).to_a\n", + " replacements.map {|n| best_count_primes_r(num, n)}.max\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "7" + ] + }, + "execution_count": 21, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "best_count_primes(56003)" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "4" + ] + }, + "execution_count": 20, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "best_count_primes(4)" + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":sequence" + ] + }, + "execution_count": 26, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def sequence(&generator)\n", + " Enumerator.new do |yielder|\n", + " n = 0\n", + " loop do\n", + " yielder.yield generator.call(n)\n", + " n = n + 1\n", + " end\n", + " end\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 53, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[[2, 4], [3, 4], [5, 4], [7, 4], [11, 5], [13, 6], [17, 5], [19, 5], [23, 6], [29, 5], [31, 5], [37, 5], [41, 5], [43, 6], [47, 5], [53, 6], [59, 5], [61, 5], [67, 5], [71, 5]]" + ] + }, + "execution_count": 53, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "primes.take(20).map {|p| [p, best_count_primes(p)]}" + ] + }, + { + "cell_type": "code", + "execution_count": 56, + "metadata": { + "collapsed": false, + "scrolled": true + }, + "outputs": [ + { + "data": { + "text/plain": [ + "121313" + ] + }, + "execution_count": 56, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "i = 1\n", + "while best_count_primes(primes[i]) < 8 do\n", + " i += 1\n", + "end\n", + "primes[i]" + ] + }, + { + "cell_type": "code", + "execution_count": 55, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "3" + ] + }, + "execution_count": 55, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "best_count_primes 120383" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[[333383, 555383, 777383], [110183, 330383, 660683, 880883], [], [330383, 770387, 990389], [323383, 525583, 626683, 929983], [121313, 222323, 323333, 424343, 525353, 626363, 828383, 929393], [323383, 929389], [620663, 720773], [120181], [920399], [], [122323, 166363], [], [100003, 120223, 140443, 160663, 170773, 180883], [], [110311], [], [121181], [], []]" + ] + }, + "execution_count": 48, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "num = 120383\n", + "possibles = (0...num.to_digits.length).to_a\n", + "possibles.combination(3).map {|ps| replace_in_positions(num, ps).select {|n| n.prime?}}# .map {|ps| count_primes_in_positions(num, ps)}" + ] + }, + { + "cell_type": "code", + "execution_count": 25, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "8" + ] + }, + "execution_count": 25, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "best_count_primes(121313)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Ruby 2.4.0", + "language": "ruby", + "name": "ruby" + }, + "language_info": { + "file_extension": ".rb", + "mimetype": "application/x-ruby", + "name": "ruby", + "version": "2.4.0" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} -- 2.34.1