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