Done puzzle 64
[project-euler.git] / euler43.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 "load 'array-numbers.rb'"
23 ]
24 },
25 {
26 "cell_type": "markdown",
27 "metadata": {},
28 "source": [
29 "* d2d3d4=406 is divisible by 2\n",
30 "* d3d4d5=063 is divisible by 3\n",
31 "* d4d5d6=635 is divisible by 5\n",
32 "* d5d6d7=357 is divisible by 7\n",
33 "* d6d7d8=572 is divisible by 11\n",
34 "* d7d8d9=728 is divisible by 13\n",
35 "* d8d9d10=289 is divisible by 17"
36 ]
37 },
38 {
39 "cell_type": "code",
40 "execution_count": 2,
41 "metadata": {
42 "collapsed": false
43 },
44 "outputs": [
45 {
46 "data": {
47 "text/plain": [
48 ":pluck"
49 ]
50 },
51 "execution_count": 2,
52 "metadata": {},
53 "output_type": "execute_result"
54 }
55 ],
56 "source": [
57 "def pluck(items)\n",
58 " plucked = []\n",
59 " items.each_index do |i|\n",
60 " plucked << [items[i], items[0, i] + items[i+1..-1]]\n",
61 " end\n",
62 " plucked\n",
63 "end"
64 ]
65 },
66 {
67 "cell_type": "code",
68 "execution_count": 3,
69 "metadata": {
70 "collapsed": false
71 },
72 "outputs": [
73 {
74 "data": {
75 "text/plain": [
76 "[[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]]]"
77 ]
78 },
79 "execution_count": 3,
80 "metadata": {},
81 "output_type": "execute_result"
82 }
83 ],
84 "source": [
85 "pluck([0,1,2,3,4])"
86 ]
87 },
88 {
89 "cell_type": "code",
90 "execution_count": 4,
91 "metadata": {
92 "collapsed": false
93 },
94 "outputs": [
95 {
96 "data": {
97 "text/plain": [
98 ":choices"
99 ]
100 },
101 "execution_count": 4,
102 "metadata": {},
103 "output_type": "execute_result"
104 }
105 ],
106 "source": [
107 "def choices(partial_solution)\n",
108 " choices = []\n",
109 " pluck(partial_solution[:remaining]).each do |digit, remaining|\n",
110 " choices << {digits: partial_solution[:digits] + [digit], remaining: remaining}\n",
111 " end\n",
112 " choices\n",
113 "end "
114 ]
115 },
116 {
117 "cell_type": "code",
118 "execution_count": 5,
119 "metadata": {
120 "collapsed": false
121 },
122 "outputs": [
123 {
124 "data": {
125 "text/plain": [
126 "{:digits=>[], :remaining=>[0, 1, 2, 3]}"
127 ]
128 },
129 "execution_count": 5,
130 "metadata": {},
131 "output_type": "execute_result"
132 }
133 ],
134 "source": [
135 "initial = {digits: [], remaining: (0..3).to_a}"
136 ]
137 },
138 {
139 "cell_type": "code",
140 "execution_count": 6,
141 "metadata": {
142 "collapsed": false
143 },
144 "outputs": [
145 {
146 "data": {
147 "text/plain": [
148 "[{:digits=>[0], :remaining=>[1, 2, 3]}, {:digits=>[1], :remaining=>[0, 2, 3]}, {:digits=>[2], :remaining=>[0, 1, 3]}, {:digits=>[3], :remaining=>[0, 1, 2]}]"
149 ]
150 },
151 "execution_count": 6,
152 "metadata": {},
153 "output_type": "execute_result"
154 }
155 ],
156 "source": [
157 "choices(initial)"
158 ]
159 },
160 {
161 "cell_type": "code",
162 "execution_count": 7,
163 "metadata": {
164 "collapsed": false
165 },
166 "outputs": [
167 {
168 "data": {
169 "text/plain": [
170 "[{: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]}]"
171 ]
172 },
173 "execution_count": 7,
174 "metadata": {},
175 "output_type": "execute_result"
176 }
177 ],
178 "source": [
179 "choices(initial).flat_map {|s| choices(s)}"
180 ]
181 },
182 {
183 "cell_type": "code",
184 "execution_count": 8,
185 "metadata": {
186 "collapsed": false
187 },
188 "outputs": [
189 {
190 "data": {
191 "text/plain": [
192 ":solve0"
193 ]
194 },
195 "execution_count": 8,
196 "metadata": {},
197 "output_type": "execute_result"
198 }
199 ],
200 "source": [
201 "def solve0()\n",
202 " initial = {digits: [], remaining: (0..9).to_a}\n",
203 " d0s = choices(initial)\n",
204 " d1s = d0s.flat_map {|s| choices(s)}\n",
205 " d2s = d1s.flat_map {|s| choices(s)}\n",
206 " d3s = d2s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 2 == 0}\n",
207 " d4s = d3s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 3 == 0}\n",
208 " d5s = d4s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 5 == 0}\n",
209 " d6s = d5s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 7 == 0}\n",
210 " d7s = d6s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 11 == 0}\n",
211 " d8s = d7s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 13 == 0}\n",
212 " d9s = d8s.flat_map {|s| choices(s)}.select {|s| s[:digits][-3..-1].to_i % 17 == 0}\n",
213 " # 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",
214 " d9s.map {|s| s[:digits].to_i}.sum\n",
215 "end"
216 ]
217 },
218 {
219 "cell_type": "code",
220 "execution_count": 9,
221 "metadata": {
222 "collapsed": false
223 },
224 "outputs": [
225 {
226 "data": {
227 "text/plain": [
228 ":solve_step"
229 ]
230 },
231 "execution_count": 9,
232 "metadata": {},
233 "output_type": "execute_result"
234 }
235 ],
236 "source": [
237 "def solve_step(partial_solutions, divisor)\n",
238 " solns = partial_solutions.flat_map {|s| choices(s)}\n",
239 " if divisor == 1\n",
240 " solns\n",
241 " else\n",
242 " solns.select {|s| s[:digits][-3..-1].to_i % divisor == 0}\n",
243 " end\n",
244 "end"
245 ]
246 },
247 {
248 "cell_type": "code",
249 "execution_count": 10,
250 "metadata": {
251 "collapsed": false
252 },
253 "outputs": [
254 {
255 "data": {
256 "text/plain": [
257 ":solve"
258 ]
259 },
260 "execution_count": 10,
261 "metadata": {},
262 "output_type": "execute_result"
263 }
264 ],
265 "source": [
266 "def solve()\n",
267 " initial = {digits: [], remaining: (0..9).to_a}\n",
268 " solutions = choices(initial)\n",
269 " [1, 1, 2, 3, 5, 7, 11, 13, 17].each do |d|\n",
270 " # puts \"#{d}, #{solutions.length}, #{solutions[0][:digits].length}\"\n",
271 " solutions = solve_step(solutions, d)\n",
272 " end\n",
273 " solutions.map {|s| s[:digits].to_i}.sum\n",
274 "end"
275 ]
276 },
277 {
278 "cell_type": "code",
279 "execution_count": 11,
280 "metadata": {
281 "collapsed": false
282 },
283 "outputs": [
284 {
285 "data": {
286 "text/plain": [
287 "16695334890"
288 ]
289 },
290 "execution_count": 11,
291 "metadata": {},
292 "output_type": "execute_result"
293 }
294 ],
295 "source": [
296 "solve0"
297 ]
298 },
299 {
300 "cell_type": "code",
301 "execution_count": 12,
302 "metadata": {
303 "collapsed": false
304 },
305 "outputs": [
306 {
307 "data": {
308 "text/plain": [
309 "16695334890"
310 ]
311 },
312 "execution_count": 12,
313 "metadata": {},
314 "output_type": "execute_result"
315 }
316 ],
317 "source": [
318 "solve"
319 ]
320 },
321 {
322 "cell_type": "code",
323 "execution_count": null,
324 "metadata": {
325 "collapsed": true
326 },
327 "outputs": [],
328 "source": []
329 }
330 ],
331 "metadata": {
332 "kernelspec": {
333 "display_name": "Ruby 2.4.0",
334 "language": "ruby",
335 "name": "ruby"
336 },
337 "language_info": {
338 "file_extension": ".rb",
339 "mimetype": "application/x-ruby",
340 "name": "ruby",
341 "version": "2.4.0"
342 }
343 },
344 "nbformat": 4,
345 "nbformat_minor": 0
346 }