From 0c3e0bf4e945f6a57bcb2c0aaf55ef13ca1a4e94 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Tue, 14 Feb 2017 14:54:29 +0000 Subject: [PATCH] Done puzzle 31 --- euler31.ipynb | 374 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 374 insertions(+) create mode 100644 euler31.ipynb diff --git a/euler31.ipynb b/euler31.ipynb new file mode 100644 index 0000000..e7c5bca --- /dev/null +++ b/euler31.ipynb @@ -0,0 +1,374 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "true" + ] + }, + "execution_count": 1, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "require 'set'\n", + "require 'awesome_print'" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[1, 2, 5, 10, 20, 50, 100, 200]" + ] + }, + "execution_count": 2, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "ways = {[0, 0] => 1}\n", + "coins = [1,2,5,10,20,50,100,200]" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "{[0, 0]=>1}" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "ways" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[1, 2, 5, 10, 20, 50, 100]" + ] + }, + "execution_count": 4, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "coins[0...-1]" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":change_count" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def change_count(coins, ncoins, total)\n", + " puts(\"#{coins[0...ncoins]} coins finding #{total}\")\n", + " if total == 0\n", + " 1\n", + " elsif total < 0\n", + " 0\n", + " elsif ncoins < 0 && total > 0\n", + " 0\n", + " else\n", + " change_count(coins, ncoins-1, total) + change_count(coins, ncoins, total-coins[ncoins]) \n", + " end\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "[1, 2, 5] coins finding 5\n", + "[1, 2] coins finding 5\n", + "[1] coins finding 5\n", + "[] coins finding 5\n", + "[1, 2, 5, 10, 20, 50, 100] coins finding 5\n", + "[] coins finding 4\n", + "[1, 2, 5, 10, 20, 50, 100] coins finding 4\n", + "[] coins finding 3\n", + "[1, 2, 5, 10, 20, 50, 100] coins finding 3\n", + "[] coins finding 2\n", + "[1, 2, 5, 10, 20, 50, 100] coins finding 2\n", + "[] coins finding 1\n", + "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n", + "[] coins finding 0\n", + "[1] coins finding 3\n", + "[] coins finding 3\n", + "[1, 2, 5, 10, 20, 50, 100] coins finding 3\n", + "[] coins finding 2\n", + "[1, 2, 5, 10, 20, 50, 100] coins finding 2\n", + "[] coins finding 1\n", + "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n", + "[] coins finding 0\n", + "[1] coins finding 1\n", + "[] coins finding 1\n", + "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n", + "[] coins finding 0\n", + "[1] coins finding -1\n", + "[1, 2] coins finding 0\n", + "[1, 2, 5] coins finding -5\n" + ] + }, + { + "data": { + "text/plain": [ + "4" + ] + }, + "execution_count": 6, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "change_count(coins, 3, 5)" + ] + }, + { + "cell_type": "code", + "execution_count": 40, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + ":change_count_dp" + ] + }, + "execution_count": 40, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def change_count_dp(coins, total, debug: false)\n", + " ncoins = coins.length - 1\n", + " ways = {}\n", + " (0..total).each do |t|\n", + " (0..ncoins).each do |n|\n", + " ways[[n, t]] = 1\n", + " end\n", + " end\n", + " \n", + " (1..total).each do |t|\n", + " (0..ncoins).each do |n|\n", + " # including this coin\n", + " if t >= coins[n]\n", + " including = ways[[n, t-coins[n]]]\n", + " else\n", + " including = 0\n", + " end\n", + " \n", + " # excluding this coin\n", + " if n >= 1\n", + " excluding = ways[[n-1, t]]\n", + " else\n", + " excluding = 0\n", + " end\n", + " \n", + " puts \"n: #{n} (#{coins[n]}p), t: #{t}, inc: #{including}, exc: #{excluding}\" if debug\n", + " ways[[n, t]] = including + excluding\n", + " end\n", + " end\n", + " \n", + " ways[[ncoins, total]]\n", + " # ways\n", + "end" + ] + }, + { + "cell_type": "code", + "execution_count": 41, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "[0, 1, 2, 3, 4, 5, 6, 7, 8]" + ] + }, + "execution_count": 41, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(0..8).to_a" + ] + }, + { + "cell_type": "code", + "execution_count": 45, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "n: 0 (1p), t: 1, inc: 1, exc: 0\n", + "n: 1 (2p), t: 1, inc: 0, exc: 1\n", + "n: 2 (5p), t: 1, inc: 0, exc: 1\n", + "n: 3 (10p), t: 1, inc: 0, exc: 1\n", + "n: 4 (20p), t: 1, inc: 0, exc: 1\n", + "n: 5 (50p), t: 1, inc: 0, exc: 1\n", + "n: 6 (100p), t: 1, inc: 0, exc: 1\n", + "n: 7 (200p), t: 1, inc: 0, exc: 1\n", + "n: 0 (1p), t: 2, inc: 1, exc: 0\n", + "n: 1 (2p), t: 2, inc: 1, exc: 1\n", + "n: 2 (5p), t: 2, inc: 0, exc: 2\n", + "n: 3 (10p), t: 2, inc: 0, exc: 2\n", + "n: 4 (20p), t: 2, inc: 0, exc: 2\n", + "n: 5 (50p), t: 2, inc: 0, exc: 2\n", + "n: 6 (100p), t: 2, inc: 0, exc: 2\n", + "n: 7 (200p), t: 2, inc: 0, exc: 2\n", + "n: 0 (1p), t: 3, inc: 1, exc: 0\n", + "n: 1 (2p), t: 3, inc: 1, exc: 1\n", + "n: 2 (5p), t: 3, inc: 0, exc: 2\n", + "n: 3 (10p), t: 3, inc: 0, exc: 2\n", + "n: 4 (20p), t: 3, inc: 0, exc: 2\n", + "n: 5 (50p), t: 3, inc: 0, exc: 2\n", + "n: 6 (100p), t: 3, inc: 0, exc: 2\n", + "n: 7 (200p), t: 3, inc: 0, exc: 2\n", + "n: 0 (1p), t: 4, inc: 1, exc: 0\n", + "n: 1 (2p), t: 4, inc: 2, exc: 1\n", + "n: 2 (5p), t: 4, inc: 0, exc: 3\n", + "n: 3 (10p), t: 4, inc: 0, exc: 3\n", + "n: 4 (20p), t: 4, inc: 0, exc: 3\n", + "n: 5 (50p), t: 4, inc: 0, exc: 3\n", + "n: 6 (100p), t: 4, inc: 0, exc: 3\n", + "n: 7 (200p), t: 4, inc: 0, exc: 3\n", + "n: 0 (1p), t: 5, inc: 1, exc: 0\n", + "n: 1 (2p), t: 5, inc: 2, exc: 1\n", + "n: 2 (5p), t: 5, inc: 1, exc: 3\n", + "n: 3 (10p), t: 5, inc: 0, exc: 4\n", + "n: 4 (20p), t: 5, inc: 0, exc: 4\n", + "n: 5 (50p), t: 5, inc: 0, exc: 4\n", + "n: 6 (100p), t: 5, inc: 0, exc: 4\n", + "n: 7 (200p), t: 5, inc: 0, exc: 4\n" + ] + }, + { + "data": { + "text/plain": [ + "4" + ] + }, + "execution_count": 45, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "change_count_dp(coins, 5, debug: true)" + ] + }, + { + "cell_type": "code", + "execution_count": 43, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "73682" + ] + }, + "execution_count": 43, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "change_count_dp(coins, 200)" + ] + }, + { + "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