Problem_114.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "cache = {}\n",
    "def rec(m, n):\n",
    "    if n < m:\n",
    "        return 1\n",
    "    elif n == m:\n",
    "        return 2\n",
    "    elif (m,n) in cache:\n",
    "        return cache[m,n]\n",
    "    else:\n",
    "        ans = rec(m,n-1) + sum(rec(m,n-(p+1)) for p in range(m,n+1))\n",
    "        cache[m,n] = ans\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16475640049"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec(3,50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1089155"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec(3,30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 115"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "F(50,1) = 1\n",
      "F(50,2) = 1\n",
      "F(50,3) = 1\n",
      "F(50,4) = 1\n",
      "F(50,5) = 1\n",
      "F(50,6) = 1\n",
      "F(50,7) = 1\n",
      "F(50,8) = 1\n",
      "F(50,9) = 1\n",
      "F(50,10) = 1\n",
      "F(50,11) = 1\n",
      "F(50,12) = 1\n",
      "F(50,13) = 1\n",
      "F(50,14) = 1\n",
      "F(50,15) = 1\n",
      "F(50,16) = 1\n",
      "F(50,17) = 1\n",
      "F(50,18) = 1\n",
      "F(50,19) = 1\n",
      "F(50,20) = 1\n",
      "F(50,21) = 1\n",
      "F(50,22) = 1\n",
      "F(50,23) = 1\n",
      "F(50,24) = 1\n",
      "F(50,25) = 1\n",
      "F(50,26) = 1\n",
      "F(50,27) = 1\n",
      "F(50,28) = 1\n",
      "F(50,29) = 1\n",
      "F(50,30) = 1\n",
      "F(50,31) = 1\n",
      "F(50,32) = 1\n",
      "F(50,33) = 1\n",
      "F(50,34) = 1\n",
      "F(50,35) = 1\n",
      "F(50,36) = 1\n",
      "F(50,37) = 1\n",
      "F(50,38) = 1\n",
      "F(50,39) = 1\n",
      "F(50,40) = 1\n",
      "F(50,41) = 1\n",
      "F(50,42) = 1\n",
      "F(50,43) = 1\n",
      "F(50,44) = 1\n",
      "F(50,45) = 1\n",
      "F(50,46) = 1\n",
      "F(50,47) = 1\n",
      "F(50,48) = 1\n",
      "F(50,49) = 1\n",
      "F(50,50) = 2\n",
      "F(50,51) = 4\n",
      "F(50,52) = 7\n",
      "F(50,53) = 11\n",
      "F(50,54) = 16\n",
      "F(50,55) = 22\n",
      "F(50,56) = 29\n",
      "F(50,57) = 37\n",
      "F(50,58) = 46\n",
      "F(50,59) = 56\n",
      "F(50,60) = 67\n",
      "F(50,61) = 79\n",
      "F(50,62) = 92\n",
      "F(50,63) = 106\n",
      "F(50,64) = 121\n",
      "F(50,65) = 137\n",
      "F(50,66) = 154\n",
      "F(50,67) = 172\n",
      "F(50,68) = 191\n",
      "F(50,69) = 211\n",
      "F(50,70) = 232\n",
      "F(50,71) = 254\n",
      "F(50,72) = 277\n",
      "F(50,73) = 301\n",
      "F(50,74) = 326\n",
      "F(50,75) = 352\n",
      "F(50,76) = 379\n",
      "F(50,77) = 407\n",
      "F(50,78) = 436\n",
      "F(50,79) = 466\n",
      "F(50,80) = 497\n",
      "F(50,81) = 529\n",
      "F(50,82) = 562\n",
      "F(50,83) = 596\n",
      "F(50,84) = 631\n",
      "F(50,85) = 667\n",
      "F(50,86) = 704\n",
      "F(50,87) = 742\n",
      "F(50,88) = 781\n",
      "F(50,89) = 821\n",
      "F(50,90) = 862\n",
      "F(50,91) = 904\n",
      "F(50,92) = 947\n",
      "F(50,93) = 991\n",
      "F(50,94) = 1036\n",
      "F(50,95) = 1082\n",
      "F(50,96) = 1129\n",
      "F(50,97) = 1177\n",
      "F(50,98) = 1226\n",
      "F(50,99) = 1276\n",
      "F(50,100) = 1327\n",
      "F(50,101) = 1380\n",
      "F(50,102) = 1437\n",
      "F(50,103) = 1501\n",
      "F(50,104) = 1576\n",
      "F(50,105) = 1667\n",
      "F(50,106) = 1780\n",
      "F(50,107) = 1922\n",
      "F(50,108) = 2101\n",
      "F(50,109) = 2326\n",
      "F(50,110) = 2607\n",
      "F(50,111) = 2955\n",
      "F(50,112) = 3382\n",
      "F(50,113) = 3901\n",
      "F(50,114) = 4526\n",
      "F(50,115) = 5272\n",
      "F(50,116) = 6155\n",
      "F(50,117) = 7192\n",
      "F(50,118) = 8401\n",
      "F(50,119) = 9801\n",
      "F(50,120) = 11412\n",
      "F(50,121) = 13255\n",
      "F(50,122) = 15352\n",
      "F(50,123) = 17726\n",
      "F(50,124) = 20401\n",
      "F(50,125) = 23402\n",
      "F(50,126) = 26755\n",
      "F(50,127) = 30487\n",
      "F(50,128) = 34626\n",
      "F(50,129) = 39201\n",
      "F(50,130) = 44242\n",
      "F(50,131) = 49780\n",
      "F(50,132) = 55847\n",
      "F(50,133) = 62476\n",
      "F(50,134) = 69701\n",
      "F(50,135) = 77557\n",
      "F(50,136) = 86080\n",
      "F(50,137) = 95307\n",
      "F(50,138) = 105276\n",
      "F(50,139) = 116026\n",
      "F(50,140) = 127597\n",
      "F(50,141) = 140030\n",
      "F(50,142) = 153367\n",
      "F(50,143) = 167651\n",
      "F(50,144) = 182926\n",
      "F(50,145) = 199237\n",
      "F(50,146) = 216630\n",
      "F(50,147) = 235152\n",
      "F(50,148) = 254851\n",
      "F(50,149) = 275776\n",
      "F(50,150) = 297977\n",
      "F(50,151) = 321505\n",
      "F(50,152) = 346413\n",
      "F(50,153) = 372758\n",
      "F(50,154) = 400604\n",
      "F(50,155) = 430026\n",
      "F(50,156) = 461115\n",
      "F(50,157) = 493984\n",
      "F(50,158) = 528775\n",
      "F(50,159) = 565667\n",
      "F(50,160) = 604885\n",
      "F(50,161) = 646710\n",
      "F(50,162) = 691490\n",
      "F(50,163) = 739652\n",
      "F(50,164) = 791715\n",
      "F(50,165) = 848304\n",
      "F(50,166) = 910165\n",
      "F(50,167) = 978181\n",
      "F(50,168) = 1053389\n",
      "Solution found: 168\n"
     ]
    }
   ],
   "source": [
    "m = 50\n",
    "n = 0\n",
    "check = False\n",
    "while not check:\n",
    "    n += 1\n",
    "    print(f\"F({m},{n}) =\", end=\" \")\n",
    "    count = rec(50, n)\n",
    "    print(count)\n",
    "    if count > 1000000:\n",
    "        print(f\"Solution found: {n}\")\n",
    "        check = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 116"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We modify the recursive function so that there is no need for space between two tiles\n",
    "cache = {}\n",
    "def rec(m, n, colored):\n",
    "    if n < m:\n",
    "        return 1 if colored else 0 # If we didn't put a tile before, no solution\n",
    "    elif n == m:\n",
    "        return 2 if colored else 1 # If we didn't put a tile before, we have to put it here\n",
    "    elif (m,n,colored) in cache:\n",
    "        return cache[m,n,colored]\n",
    "    else:\n",
    "        ans = rec(m,n-1,colored) + rec(m,n-m,True)\n",
    "        cache[m,n,colored] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert(rec(2,5,False) == 7)\n",
    "assert(rec(3,5,False) == 3)\n",
    "assert(rec(4,5,False) == 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Problem116(n):\n",
    "    return rec(2,n,False) + rec(3,n,False) + rec(4,n,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert(Problem116(5) == 12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20492570929"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Problem116(50)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 117\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [],
   "source": [
    "cache = {}\n",
    "def rec(n):\n",
    "    if n < 2:\n",
    "        return 1\n",
    "    elif n in cache:\n",
    "        return cache[n]\n",
    "    else:\n",
    "        ans = sum(rec(n-p) for p in range(1,min(4,n)+1))\n",
    "        cache[n] = ans\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100808458960497"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{}"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}