Right and Down challenge

right-and-down-challenge.ipynb

right-and-down-solution.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> Testing: \n",
      "[1, 2, 3, 7, 3, 1]\n",
      "[4, 5, 6, 7, 7, 8]\n",
      "[9, 7, 3, 5, 3, 5]\n",
      "> OK: 43\n",
      "\n",
      "> Testing: \n",
      "[1, 2, 3]\n",
      "[4, 5, 6]\n",
      "[7, 8, 9]\n",
      "> OK: 29\n",
      "\n",
      "> All passed!\n"
     ]
    }
   ],
   "source": [
    "from typing import *\n",
    "\n",
    "def max_sum(matr: List[int], debug=False) -> int:\n",
    "    \"\"\" Insert you code here\n",
    "    You are given a matrix NxM. You start at (0,0) and \n",
    "    finish at (n-1, m-1). Find the maximum sum of the path\n",
    "    if you can go only DOWN or RIGHT at a time.\n",
    "    \n",
    "    Example:\n",
    "    Given matrix:  [1,2,3]\n",
    "                   [4,5,6]\n",
    "                   [7,8,9]\n",
    "    Arbitrary path: (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2)\n",
    "    Sum:              1   +    2   +    5   +    6   +    9   == 23\n",
    "    \"\"\"\n",
    "    n, m = len(matr) - 1, len(matr[0]) - 1\n",
    "    path, acc = \"\", 0\n",
    "    \n",
    "    def step(i: int, j: int, path: str, acc: int) -> int:\n",
    "        path = f\"{path}({i},{j})\"\n",
    "        acc += matr[i][j]\n",
    "        \n",
    "        if i == n and j == m:\n",
    "            if debug: print(path, acc)\n",
    "            return acc\n",
    "        \n",
    "        if i == n:\n",
    "            return step(i, j+1, path, acc)\n",
    "        elif j == m:\n",
    "            return step(i+1, j, path, acc)\n",
    "        else:            \n",
    "            right = step(i+1, j, path, acc)\n",
    "            down = step(i, j+1, path, acc)\n",
    "            return max(right, down)\n",
    "    \n",
    "    return step(0, 0, path, acc)\n",
    "\n",
    "test_cases = [\n",
    "    {\n",
    "        'matr': [\n",
    "            [1,2,3,7,3,1],\n",
    "            [4,5,6,7,7,8],\n",
    "            [9,7,3,5,3,5]\n",
    "        ], \n",
    "        'res': 43\n",
    "    },\n",
    "    {\n",
    "        'matr': [\n",
    "            [1,2,3],\n",
    "            [4,5,6],\n",
    "            [7,8,9]\n",
    "        ], \n",
    "        'res': 29\n",
    "    }\n",
    "]\n",
    "\n",
    "failed = False\n",
    "for test in test_cases:\n",
    "    m_repr = '\\n'.join(map(str, test['matr']))\n",
    "    res = max_sum(test['matr'])\n",
    "    \n",
    "    print(f\"> Testing: \\n{m_repr}\")\n",
    "    try: \n",
    "        assert(test['res'] == res)\n",
    "        print(f\"> OK: {res}\")\n",
    "    except AssertionError as e:\n",
    "        print(f\"> Failed: {res}\")\n",
    "        failed = True\n",
    "    finally:\n",
    "        print()\n",
    "\n",
    "if not failed: print(\"> All passed!\")"
   ]
  },
  {
   "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}