{
"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
}