Done puzzle 31
[project-euler.git] / euler31.ipynb
1 {
2 "cells": [
3 {
4 "cell_type": "code",
5 "execution_count": 1,
6 "metadata": {
7 "collapsed": false
8 },
9 "outputs": [
10 {
11 "data": {
12 "text/plain": [
13 "true"
14 ]
15 },
16 "execution_count": 1,
17 "metadata": {},
18 "output_type": "execute_result"
19 }
20 ],
21 "source": [
22 "require 'set'\n",
23 "require 'awesome_print'"
24 ]
25 },
26 {
27 "cell_type": "code",
28 "execution_count": 2,
29 "metadata": {
30 "collapsed": false
31 },
32 "outputs": [
33 {
34 "data": {
35 "text/plain": [
36 "[1, 2, 5, 10, 20, 50, 100, 200]"
37 ]
38 },
39 "execution_count": 2,
40 "metadata": {},
41 "output_type": "execute_result"
42 }
43 ],
44 "source": [
45 "ways = {[0, 0] => 1}\n",
46 "coins = [1,2,5,10,20,50,100,200]"
47 ]
48 },
49 {
50 "cell_type": "code",
51 "execution_count": 3,
52 "metadata": {
53 "collapsed": false
54 },
55 "outputs": [
56 {
57 "data": {
58 "text/plain": [
59 "{[0, 0]=>1}"
60 ]
61 },
62 "execution_count": 3,
63 "metadata": {},
64 "output_type": "execute_result"
65 }
66 ],
67 "source": [
68 "ways"
69 ]
70 },
71 {
72 "cell_type": "code",
73 "execution_count": 4,
74 "metadata": {
75 "collapsed": false
76 },
77 "outputs": [
78 {
79 "data": {
80 "text/plain": [
81 "[1, 2, 5, 10, 20, 50, 100]"
82 ]
83 },
84 "execution_count": 4,
85 "metadata": {},
86 "output_type": "execute_result"
87 }
88 ],
89 "source": [
90 "coins[0...-1]"
91 ]
92 },
93 {
94 "cell_type": "code",
95 "execution_count": 5,
96 "metadata": {
97 "collapsed": false
98 },
99 "outputs": [
100 {
101 "data": {
102 "text/plain": [
103 ":change_count"
104 ]
105 },
106 "execution_count": 5,
107 "metadata": {},
108 "output_type": "execute_result"
109 }
110 ],
111 "source": [
112 "def change_count(coins, ncoins, total)\n",
113 " puts(\"#{coins[0...ncoins]} coins finding #{total}\")\n",
114 " if total == 0\n",
115 " 1\n",
116 " elsif total < 0\n",
117 " 0\n",
118 " elsif ncoins < 0 && total > 0\n",
119 " 0\n",
120 " else\n",
121 " change_count(coins, ncoins-1, total) + change_count(coins, ncoins, total-coins[ncoins]) \n",
122 " end\n",
123 "end"
124 ]
125 },
126 {
127 "cell_type": "code",
128 "execution_count": 6,
129 "metadata": {
130 "collapsed": false
131 },
132 "outputs": [
133 {
134 "name": "stdout",
135 "output_type": "stream",
136 "text": [
137 "[1, 2, 5] coins finding 5\n",
138 "[1, 2] coins finding 5\n",
139 "[1] coins finding 5\n",
140 "[] coins finding 5\n",
141 "[1, 2, 5, 10, 20, 50, 100] coins finding 5\n",
142 "[] coins finding 4\n",
143 "[1, 2, 5, 10, 20, 50, 100] coins finding 4\n",
144 "[] coins finding 3\n",
145 "[1, 2, 5, 10, 20, 50, 100] coins finding 3\n",
146 "[] coins finding 2\n",
147 "[1, 2, 5, 10, 20, 50, 100] coins finding 2\n",
148 "[] coins finding 1\n",
149 "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n",
150 "[] coins finding 0\n",
151 "[1] coins finding 3\n",
152 "[] coins finding 3\n",
153 "[1, 2, 5, 10, 20, 50, 100] coins finding 3\n",
154 "[] coins finding 2\n",
155 "[1, 2, 5, 10, 20, 50, 100] coins finding 2\n",
156 "[] coins finding 1\n",
157 "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n",
158 "[] coins finding 0\n",
159 "[1] coins finding 1\n",
160 "[] coins finding 1\n",
161 "[1, 2, 5, 10, 20, 50, 100] coins finding 1\n",
162 "[] coins finding 0\n",
163 "[1] coins finding -1\n",
164 "[1, 2] coins finding 0\n",
165 "[1, 2, 5] coins finding -5\n"
166 ]
167 },
168 {
169 "data": {
170 "text/plain": [
171 "4"
172 ]
173 },
174 "execution_count": 6,
175 "metadata": {},
176 "output_type": "execute_result"
177 }
178 ],
179 "source": [
180 "change_count(coins, 3, 5)"
181 ]
182 },
183 {
184 "cell_type": "code",
185 "execution_count": 40,
186 "metadata": {
187 "collapsed": false
188 },
189 "outputs": [
190 {
191 "data": {
192 "text/plain": [
193 ":change_count_dp"
194 ]
195 },
196 "execution_count": 40,
197 "metadata": {},
198 "output_type": "execute_result"
199 }
200 ],
201 "source": [
202 "def change_count_dp(coins, total, debug: false)\n",
203 " ncoins = coins.length - 1\n",
204 " ways = {}\n",
205 " (0..total).each do |t|\n",
206 " (0..ncoins).each do |n|\n",
207 " ways[[n, t]] = 1\n",
208 " end\n",
209 " end\n",
210 " \n",
211 " (1..total).each do |t|\n",
212 " (0..ncoins).each do |n|\n",
213 " # including this coin\n",
214 " if t >= coins[n]\n",
215 " including = ways[[n, t-coins[n]]]\n",
216 " else\n",
217 " including = 0\n",
218 " end\n",
219 " \n",
220 " # excluding this coin\n",
221 " if n >= 1\n",
222 " excluding = ways[[n-1, t]]\n",
223 " else\n",
224 " excluding = 0\n",
225 " end\n",
226 " \n",
227 " puts \"n: #{n} (#{coins[n]}p), t: #{t}, inc: #{including}, exc: #{excluding}\" if debug\n",
228 " ways[[n, t]] = including + excluding\n",
229 " end\n",
230 " end\n",
231 " \n",
232 " ways[[ncoins, total]]\n",
233 " # ways\n",
234 "end"
235 ]
236 },
237 {
238 "cell_type": "code",
239 "execution_count": 41,
240 "metadata": {
241 "collapsed": false
242 },
243 "outputs": [
244 {
245 "data": {
246 "text/plain": [
247 "[0, 1, 2, 3, 4, 5, 6, 7, 8]"
248 ]
249 },
250 "execution_count": 41,
251 "metadata": {},
252 "output_type": "execute_result"
253 }
254 ],
255 "source": [
256 "(0..8).to_a"
257 ]
258 },
259 {
260 "cell_type": "code",
261 "execution_count": 45,
262 "metadata": {
263 "collapsed": false
264 },
265 "outputs": [
266 {
267 "name": "stdout",
268 "output_type": "stream",
269 "text": [
270 "n: 0 (1p), t: 1, inc: 1, exc: 0\n",
271 "n: 1 (2p), t: 1, inc: 0, exc: 1\n",
272 "n: 2 (5p), t: 1, inc: 0, exc: 1\n",
273 "n: 3 (10p), t: 1, inc: 0, exc: 1\n",
274 "n: 4 (20p), t: 1, inc: 0, exc: 1\n",
275 "n: 5 (50p), t: 1, inc: 0, exc: 1\n",
276 "n: 6 (100p), t: 1, inc: 0, exc: 1\n",
277 "n: 7 (200p), t: 1, inc: 0, exc: 1\n",
278 "n: 0 (1p), t: 2, inc: 1, exc: 0\n",
279 "n: 1 (2p), t: 2, inc: 1, exc: 1\n",
280 "n: 2 (5p), t: 2, inc: 0, exc: 2\n",
281 "n: 3 (10p), t: 2, inc: 0, exc: 2\n",
282 "n: 4 (20p), t: 2, inc: 0, exc: 2\n",
283 "n: 5 (50p), t: 2, inc: 0, exc: 2\n",
284 "n: 6 (100p), t: 2, inc: 0, exc: 2\n",
285 "n: 7 (200p), t: 2, inc: 0, exc: 2\n",
286 "n: 0 (1p), t: 3, inc: 1, exc: 0\n",
287 "n: 1 (2p), t: 3, inc: 1, exc: 1\n",
288 "n: 2 (5p), t: 3, inc: 0, exc: 2\n",
289 "n: 3 (10p), t: 3, inc: 0, exc: 2\n",
290 "n: 4 (20p), t: 3, inc: 0, exc: 2\n",
291 "n: 5 (50p), t: 3, inc: 0, exc: 2\n",
292 "n: 6 (100p), t: 3, inc: 0, exc: 2\n",
293 "n: 7 (200p), t: 3, inc: 0, exc: 2\n",
294 "n: 0 (1p), t: 4, inc: 1, exc: 0\n",
295 "n: 1 (2p), t: 4, inc: 2, exc: 1\n",
296 "n: 2 (5p), t: 4, inc: 0, exc: 3\n",
297 "n: 3 (10p), t: 4, inc: 0, exc: 3\n",
298 "n: 4 (20p), t: 4, inc: 0, exc: 3\n",
299 "n: 5 (50p), t: 4, inc: 0, exc: 3\n",
300 "n: 6 (100p), t: 4, inc: 0, exc: 3\n",
301 "n: 7 (200p), t: 4, inc: 0, exc: 3\n",
302 "n: 0 (1p), t: 5, inc: 1, exc: 0\n",
303 "n: 1 (2p), t: 5, inc: 2, exc: 1\n",
304 "n: 2 (5p), t: 5, inc: 1, exc: 3\n",
305 "n: 3 (10p), t: 5, inc: 0, exc: 4\n",
306 "n: 4 (20p), t: 5, inc: 0, exc: 4\n",
307 "n: 5 (50p), t: 5, inc: 0, exc: 4\n",
308 "n: 6 (100p), t: 5, inc: 0, exc: 4\n",
309 "n: 7 (200p), t: 5, inc: 0, exc: 4\n"
310 ]
311 },
312 {
313 "data": {
314 "text/plain": [
315 "4"
316 ]
317 },
318 "execution_count": 45,
319 "metadata": {},
320 "output_type": "execute_result"
321 }
322 ],
323 "source": [
324 "change_count_dp(coins, 5, debug: true)"
325 ]
326 },
327 {
328 "cell_type": "code",
329 "execution_count": 43,
330 "metadata": {
331 "collapsed": false
332 },
333 "outputs": [
334 {
335 "data": {
336 "text/plain": [
337 "73682"
338 ]
339 },
340 "execution_count": 43,
341 "metadata": {},
342 "output_type": "execute_result"
343 }
344 ],
345 "source": [
346 "change_count_dp(coins, 200)"
347 ]
348 },
349 {
350 "cell_type": "code",
351 "execution_count": null,
352 "metadata": {
353 "collapsed": true
354 },
355 "outputs": [],
356 "source": []
357 }
358 ],
359 "metadata": {
360 "kernelspec": {
361 "display_name": "Ruby 2.4.0",
362 "language": "ruby",
363 "name": "ruby"
364 },
365 "language_info": {
366 "file_extension": ".rb",
367 "mimetype": "application/x-ruby",
368 "name": "ruby",
369 "version": "2.4.0"
370 }
371 },
372 "nbformat": 4,
373 "nbformat_minor": 0
374 }