018-Solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/18-1.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# That is, 3 + 7 + 4 + 9 = 23.\n",
    "\n",
    "# Find the maximum total from top to bottom of the triangle below:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/18-2.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "\n",
    "# We'll do the brute force way this time, and figure out the more elegant solution later"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "list_values = [[75],\n",
    "[95,64],\n",
    "[17,47,82],\n",
    "[18,35,87,10],\n",
    "[20,4,82,47,65],\n",
    "[19,1,23,75,3,34],\n",
    "[88,2,77,73,7,63,67],\n",
    "[99,65,4,28,6,16,70,92],\n",
    "[41,41,26,56,83,40,80,70,33],\n",
    "[41,48,72,33,47,32,37,16,94,29],\n",
    "[53,71,44,65,25,43,91,52,97,51,14],\n",
    "[70,11,33,28,77,73,17,78,39,68,17,57],\n",
    "[91,71,52,38,17,14,91,43,58,50,27,29,48],\n",
    "[63,66,4,68,89,53,67,30,73,16,69,87,40,31],\n",
    "[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "list_paths = [[0]]\n",
    "\n",
    "i = 0\n",
    "while i != 14:\n",
    "    i += 1\n",
    "    list_new = []\n",
    "    for path in list_paths:\n",
    "        for j in [0,1]:\n",
    "            path_extended = path+[j]\n",
    "            list_new.append(path_extended)\n",
    "    list_paths = list_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "list_paths_cumulative = np.cumsum(list_paths, axis = 1, dtype=np.int64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_val = 0\n",
    "for path in list_paths_cumulative:\n",
    "    list_temp = []\n",
    "    for i, val in enumerate(path):\n",
    "        list_temp.append(list_values[i][val])\n",
    "    total = sum(list_temp)\n",
    "    if total > max_val:\n",
    "        max_val = total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1074"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Answer = 1,074"
   ]
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}