From: Neil Smith Date: Thu, 2 Mar 2017 11:31:03 +0000 (+0000) Subject: Done puzzle 43 X-Git-Url: https://git.njae.me.uk/?p=project-euler.git;a=commitdiff_plain;h=576451a5c91ae67696e7124e357e29256fb5a3df Done puzzle 43 --- diff --git a/.gitignore b/.gitignore index fabe911..09d4d9a 100644 --- a/.gitignore +++ b/.gitignore @@ -61,3 +61,5 @@ build-iPhoneSimulator/ # Profiling information profile.* +# API secrets +secrets.ini diff --git a/euler43.ipynb b/euler43.ipynb new file mode 100644 index 0000000..d11dcb5 --- /dev/null +++ b/euler43.ipynb @@ -0,0 +1,346 @@ +{ + "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 'array-numbers.rb'" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "* d2d3d4=406 is divisible by 2\n", + "* d3d4d5=063 is divisible by 3\n", + "* d4d5d6=635 is divisible by 5\n", + "* d5d6d7=357 is divisible by 7\n", + "* d6d7d8=572 is divisible by 11\n", + "* d7d8d9=728 is divisible by 13\n", + "* d8d9d10=289 is divisible by 17" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":pluck" + ] + }, + "execution_count": 2, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def pluck(items)\n", + " plucked = []\n", + " items.each_index do |i|\n", + " plucked << [items[i], items[0, i] + items[i+1..-1]]\n", + " end\n", + " plucked\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[[0, [1, 2, 3, 4]], [1, [0, 2, 3, 4]], [2, [0, 1, 3, 4]], [3, [0, 1, 2, 4]], [4, [0, 1, 2, 3]]]" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "pluck([0,1,2,3,4])" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":choices" + ] + }, + "execution_count": 4, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def choices(partial_solution)\n", + " choices = []\n", + " pluck(partial_solution[:remaining]).each do |digit, remaining|\n", + " choices << {digits: partial_solution[:digits] + [digit], remaining: remaining}\n", + " end\n", + " choices\n", + "end " + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "{:digits=>[], :remaining=>[0, 1, 2, 3]}" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "initial = {digits: [], remaining: (0..3).to_a}" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[{:digits=>[0], :remaining=>[1, 2, 3]}, {:digits=>[1], :remaining=>[0, 2, 3]}, {:digits=>[2], :remaining=>[0, 1, 3]}, {:digits=>[3], :remaining=>[0, 1, 2]}]" + ] + }, + "execution_count": 6, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "choices(initial)" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[{:digits=>[0, 1], :remaining=>[2, 3]}, {:digits=>[0, 2], :remaining=>[1, 3]}, {:digits=>[0, 3], :remaining=>[1, 2]}, {:digits=>[1, 0], :remaining=>[2, 3]}, {:digits=>[1, 2], :remaining=>[0, 3]}, {:digits=>[1, 3], :remaining=>[0, 2]}, {:digits=>[2, 0], :remaining=>[1, 3]}, {:digits=>[2, 1], :remaining=>[0, 3]}, {:digits=>[2, 3], :remaining=>[0, 1]}, {:digits=>[3, 0], :remaining=>[1, 2]}, {:digits=>[3, 1], :remaining=>[0, 2]}, {:digits=>[3, 2], :remaining=>[0, 1]}]" + ] + }, + "execution_count": 7, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "choices(initial).flat_map {|s| choices(s)}" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":solve0" + ] + }, + "execution_count": 8, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def solve0()\n", + " initial = {digits: [], remaining: (0..9).to_a}\n", + " d0s = choices(initial)\n", + " d1s = d0s.flat_map {|s| choices(s)}\n", + " d2s = d1s.flat_map {|s| choices(s)}\n", + " d3s = d2s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 2 == 0}\n", + " d4s = d3s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 3 == 0}\n", + " d5s = d4s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 5 == 0}\n", + " d6s = d5s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 7 == 0}\n", + " d7s = d6s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 11 == 0}\n", + " d8s = d7s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 13 == 0}\n", + " d9s = d8s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 17 == 0}\n", + " # puts \"0: #{d0s.length}, 1: #{d1s.length}, 2: #{d2s.length}, 3: #{d3s.length}, 4: #{d4s.length}, 5: #{d5s.length}, 6: #{d6s.length}, 7: #{d7s.length}, 8: #{d8s.length}, 9: #{d9s.length}\"\n", + " d9s.map {|s| s[:digits].to_i}.sum\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":solve_step" + ] + }, + "execution_count": 9, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def solve_step(partial_solutions, divisor)\n", + " solns = partial_solutions.flat_map {|s| choices(s)}\n", + " if divisor == 1\n", + " solns\n", + " else\n", + " solns.select {|s| s[:digits][-3..-1].to_i % divisor == 0}\n", + " end\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":solve" + ] + }, + "execution_count": 10, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def solve()\n", + " initial = {digits: [], remaining: (0..9).to_a}\n", + " solutions = choices(initial)\n", + " [1, 1, 2, 3, 5, 7, 11, 13, 17].each do |d|\n", + " # puts \"#{d}, #{solutions.length}, #{solutions[0][:digits].length}\"\n", + " solutions = solve_step(solutions, d)\n", + " end\n", + " solutions.map {|s| s[:digits].to_i}.sum\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "16695334890" + ] + }, + "execution_count": 11, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "solve0" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "16695334890" + ] + }, + "execution_count": 12, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "solve" + ] + }, + { + "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 +}