cpp-codingbat-11-AP-1.ipynb


{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
	"#include <iostream>\n",
	"#include <iomanip>\n",
	"#include <vector>\n",
	"\n",
	"using namespace std;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
	"namespace testns { template<class A> void printTest( string str, A run, A expected )\n",
	"{\n",
	"    if( run == expected )\n",
	"        cout << boolalpha << \"\\033[1;32m\"\n",
	"            << \"Expected: \" << setw(60) << left << str << \" Run: \" << setw(20) << left << run << \"\\t\\tOK\"\n",
	"            << \"\\033[0m\" << endl;\n",
	"    else\n",
	"        cerr << boolalpha << \"\\033[1;31m\"\n",
	"            << \"Expected: \" << setw(60) << left << str << \" Run: \" << setw(20) << left << run << \"\\t\\tX\"\n",
	"            << \"\\033[0m\" << endl;\n",
	"} } using namespace testns;\n",
	"void printTest( string str, string run, const char* expected ){ printTest( str, \"\\\"\"+run+\"\\\"\", \"\\\"\"+string( expected )+\"\\\"\" ); }\n",
	"template<class A> void printTest( string str, vector<A> run, vector<A> expected )\n",
	"{\n",
	"    string runStr = \"[\"; for( A a : run ) runStr += to_string( a ) + \", \";\n",
	"    if( runStr.length() > 1 ) runStr = runStr.substr(0, runStr.length()-2); runStr += \"]\";\n",
	"    string expStr = \"[\"; for( A a : expected ) expStr += to_string( a ) + \", \";\n",
	"    if( expStr.length() > 1 ) expStr = expStr.substr(0, expStr.length()-2); expStr += \"]\";\n",
	"    printTest( str, runStr, expStr );\n",
	"}"
   ]
  },
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > scoresIncreasing"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of scores, return true if each score is equal or greater than the\n", "one before. The array will be length 2 or more.\n", "\n", "scoresIncreasing([1, 3, 4]) \u2192 true\n", "scoresIncreasing([1, 3, 2]) \u2192 false\n", "scoresIncreasing([1, 1, 4]) \u2192 true\n", "*/\n", "\n", "bool scoresIncreasing(vector<int> scores) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"scoresIncreasing([1, 3, 4]) \u2192 true\", scoresIncreasing({1, 3, 4}), true );\n", "printTest( \"scoresIncreasing([1, 3, 2]) \u2192 false\", scoresIncreasing({1, 3, 2}), false );\n", "printTest( \"scoresIncreasing([1, 1, 4]) \u2192 true\", scoresIncreasing({1, 1, 4}), true );\n", "printTest( \"scoresIncreasing([1, 1, 2, 4, 4, 7]) \u2192 true\", scoresIncreasing({1, 1, 2, 4, 4, 7}), true );\n", "printTest( \"scoresIncreasing([1, 1, 2, 4, 3, 7]) \u2192 false\", scoresIncreasing({1, 1, 2, 4, 3, 7}), false );\n", "printTest( \"scoresIncreasing([-5, 4, 11]) \u2192 true\", scoresIncreasing({-5, 4, 11}), true );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > scores100"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of scores, return true if there are scores of 100 next to each\n", "other in the array. The array length will be at least 2.\n", "\n", "scores100([1, 100, 100]) \u2192 true\n", "scores100([1, 100, 99, 100]) \u2192 false\n", "scores100([100, 1, 100, 100]) \u2192 true\n", "*/\n", "\n", "bool scores100(vector<int> scores) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"scores100([1, 100, 100]) \u2192 true\", scores100({1, 100, 100}), true );\n", "printTest( \"scores100([1, 100, 99, 100]) \u2192 false\", scores100({1, 100, 99, 100}), false );\n", "printTest( \"scores100([100, 1, 100, 100]) \u2192 true\", scores100({100, 1, 100, 100}), true );\n", "printTest( \"scores100([100, 1, 100, 1]) \u2192 false\", scores100({100, 1, 100, 1}), false );\n", "printTest( \"scores100([1, 2, 3, 4, 5]) \u2192 false\", scores100({1, 2, 3, 4, 5}), false );\n", "printTest( \"scores100([1, 2, 100, 4, 5]) \u2192 false\", scores100({1, 2, 100, 4, 5}), false );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > scoresClump"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of scores sorted in increasing order, return true if the array\n", "contains 3 adjacent scores that differ from each other by at most 2, such as\n", "with {3, 4, 5} or {3, 5, 5}.\n", "\n", "scoresClump([3, 4, 5]) \u2192 true\n", "scoresClump([3, 4, 6]) \u2192 false\n", "scoresClump([1, 3, 5, 5]) \u2192 true\n", "*/\n", "\n", "bool scoresClump(vector<int> scores) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"scoresClump([3, 4, 5]) \u2192 true\", scoresClump({3, 4, 5}), true );\n", "printTest( \"scoresClump([3, 4, 6]) \u2192 false\", scoresClump({3, 4, 6}), false );\n", "printTest( \"scoresClump([1, 3, 5, 5]) \u2192 true\", scoresClump({1, 3, 5, 5}), true );\n", "printTest( \"scoresClump([2, 4, 5, 6]) \u2192 true\", scoresClump({2, 4, 5, 6}), true );\n", "printTest( \"scoresClump([2, 4, 5, 7]) \u2192 false\", scoresClump({2, 4, 5, 7}), false );\n", "printTest( \"scoresClump([2, 4, 4, 7]) \u2192 true\", scoresClump({2, 4, 4, 7}), true );\n", "printTest( \"scoresClump([3, 3, 6, 7, 9]) \u2192 false\", scoresClump({3, 3, 6, 7, 9}), false );\n", "printTest( \"scoresClump([3, 3, 7, 7, 9]) \u2192 true\", scoresClump({3, 3, 7, 7, 9}), true );\n", "printTest( \"scoresClump([4, 5, 8]) \u2192 false\", scoresClump({4, 5, 8}), false );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > scoresAverage"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of scores, compute the int average of the first half and the\n", "second half, and return whichever is larger. We\u02bcll say that the second half\n", "begins at index length/2. The array length will be at least 2. To practice\n", "decomposition, write a separate helper method int average(int[] scores, int\n", "start, int end) {  which computes the average of the elements between indexes\n", "start..end. Call your helper method twice to implement scoresAverage(). Write\n", "your helper method after your scoresAverage() method in the JavaBat text area.\n", "Normally you would compute averages with doubles, but here we use ints so the\n", "expected results are exact.\n", "\n", "scoresAverage([2, 2, 4, 4]) \u2192 4\n", "scoresAverage([4, 4, 4, 2, 2, 2]) \u2192 4\n", "scoresAverage([3, 4, 5, 1, 2, 3]) \u2192 4\n", "*/\n", "\n", "int scoresAverage(vector<int> scores) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"scoresAverage([2, 2, 4, 4]) \u2192 4\", scoresAverage({2, 2, 4, 4}), 4 );\n", "printTest( \"scoresAverage([4, 4, 4, 2, 2, 2]) \u2192 4\", scoresAverage({4, 4, 4, 2, 2, 2}), 4 );\n", "printTest( \"scoresAverage([3, 4, 5, 1, 2, 3]) \u2192 4\", scoresAverage({3, 4, 5, 1, 2, 3}), 4 );\n", "printTest( \"scoresAverage([5, 6]) \u2192 6\", scoresAverage({5, 6}), 6 );\n", "printTest( \"scoresAverage([5, 4]) \u2192 5\", scoresAverage({5, 4}), 5 );\n", "printTest( \"scoresAverage([5, 4, 5, 6, 2, 1, 2, 3]) \u2192 5\", scoresAverage({5, 4, 5, 6, 2, 1, 2, 3}), 5 );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > wordsCount"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of strings, return the count of the number of strings with the\n", "given length.\n", "\n", "wordsCount([\"a\", \"bb\", \"b\", \"ccc\"], 1) \u2192 2\n", "wordsCount([\"a\", \"bb\", \"b\", \"ccc\"], 3) \u2192 1\n", "wordsCount([\"a\", \"bb\", \"b\", \"ccc\"], 4) \u2192 0\n", "*/\n", "\n", "int wordsCount(vector<string> words, int len) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"wordsCount([\\\"a\\\", \\\"bb\\\", \\\"b\\\", \\\"ccc\\\"], 1) \u2192 2\", wordsCount({\"a\", \"bb\", \"b\", \"ccc\"}, 1), 2 );\n", "printTest( \"wordsCount([\\\"a\\\", \\\"bb\\\", \\\"b\\\", \\\"ccc\\\"], 3) \u2192 1\", wordsCount({\"a\", \"bb\", \"b\", \"ccc\"}, 3), 1 );\n", "printTest( \"wordsCount([\\\"a\\\", \\\"bb\\\", \\\"b\\\", \\\"ccc\\\"], 4) \u2192 0\", wordsCount({\"a\", \"bb\", \"b\", \"ccc\"}, 4), 0 );\n", "printTest( \"wordsCount([\\\"xx\\\", \\\"yyy\\\", \\\"x\\\", \\\"yy\\\", \\\"z\\\"], 1) \u2192 2\", wordsCount({\"xx\", \"yyy\", \"x\", \"yy\", \"z\"}, 1), 2 );\n", "printTest( \"wordsCount([\\\"xx\\\", \\\"yyy\\\", \\\"x\\\", \\\"yy\\\", \\\"z\\\"], 2) \u2192 2\", wordsCount({\"xx\", \"yyy\", \"x\", \"yy\", \"z\"}, 2), 2 );\n", "printTest( \"wordsCount([\\\"xx\\\", \\\"yyy\\\", \\\"x\\\", \\\"yy\\\", \\\"z\\\"], 3) \u2192 1\", wordsCount({\"xx\", \"yyy\", \"x\", \"yy\", \"z\"}, 3), 1 );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > wordsFront"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of strings, return a new array containing the first N strings. N\n", "will be in the range 1..length.\n", "\n", "wordsFront([\"a\", \"b\", \"c\", \"d\"], 1) \u2192 [\"a\"]\n", "wordsFront([\"a\", \"b\", \"c\", \"d\"], 2) \u2192 [\"a\", \"b\"]\n", "wordsFront([\"a\", \"b\", \"c\", \"d\"], 3) \u2192 [\"a\", \"b\", \"c\"]\n", "*/\n", "\n", "std::vector<string> wordsFront(vector<string> words, int n) {\n", "    return new vector<string>{};\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"wordsFront([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"d\\\"], 1) \u2192 [\\\"a\\\"]\", wordsFront({\"a\", \"b\", \"c\", \"d\"}, 1), {\"a\"} );\n", "printTest( \"wordsFront([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"d\\\"], 2) \u2192 [\\\"a\\\", \\\"b\\\"]\", wordsFront({\"a\", \"b\", \"c\", \"d\"}, 2), {\"a\", \"b\"} );\n", "printTest( \"wordsFront([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"d\\\"], 3) \u2192 [\\\"a\\\", \\\"b\\\", \\\"c\\\"]\", wordsFront({\"a\", \"b\", \"c\", \"d\"}, 3), {\"a\", \"b\", \"c\"} );\n", "printTest( \"wordsFront([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"d\\\"], 4) \u2192 [\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"d\\\"]\", wordsFront({\"a\", \"b\", \"c\", \"d\"}, 4), {\"a\", \"b\", \"c\", \"d\"} );\n", "printTest( \"wordsFront([\\\"Hi\\\", \\\"There\\\"], 1) \u2192 [\\\"Hi\\\"]\", wordsFront({\"Hi\", \"There\"}, 1), {\"Hi\"} );\n", "printTest( \"wordsFront([\\\"Hi\\\", \\\"There\\\"], 2) \u2192 [\\\"Hi\\\", \\\"There\\\"]\", wordsFront({\"Hi\", \"There\"}, 2), {\"Hi\", \"There\"} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > wordsWithoutList"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of strings, return a new List (e.g. an ArrayList) where all the\n", "strings of the given length are omitted. See wordsWithout() below which is more\n", "difficult because it uses arrays.\n", "\n", "wordsWithoutList([\"a\", \"bb\", \"b\", \"ccc\"], 1) \u2192 [\"bb\", \"ccc\"]\n", "wordsWithoutList([\"a\", \"bb\", \"b\", \"ccc\"], 3) \u2192 [\"a\", \"bb\", \"b\"]\n", "wordsWithoutList([\"a\", \"bb\", \"b\", \"ccc\"], 4) \u2192 [\"a\", \"bb\", \"b\", \"ccc\"]\n", "*/\n", "\n", "vector wordsWithoutvector(vector<string> words, int len) {\n", "    return null;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"wordsWithoutList([\\\"a\\\", \\\"bb\\\", \\\"b\\\", \\\"ccc\\\"], 1) \u2192 [\\\"bb\\\", \\\"ccc\\\"]\", wordsWithoutList({\"a\", \"bb\", \"b\", \"ccc\"}, 1), {\"bb\", \"ccc\"} );\n", "printTest( \"wordsWithoutList([\\\"a\\\", \\\"bb\\\", \\\"b\\\", \\\"ccc\\\"], 3) \u2192 [\\\"a\\\", \\\"bb\\\", \\\"b\\\"]\", wordsWithoutList({\"a\", \"bb\", \"b\", \"ccc\"}, 3), {\"a\", \"bb\", \"b\"} );\n", "printTest( \"wordsWithoutList([\\\"a\\\", \\\"bb\\\", \\\"b\\\", \\\"ccc\\\"], 4) \u2192 [\\\"a\\\", \\\"bb\\\", \\\"b\\\", \\\"ccc\\\"]\", wordsWithoutList({\"a\", \"bb\", \"b\", \"ccc\"}, 4), {\"a\", \"bb\", \"b\", \"ccc\"} );\n", "printTest( \"wordsWithoutList([\\\"xx\\\", \\\"yyy\\\", \\\"x\\\", \\\"yy\\\", \\\"z\\\"], 1) \u2192 [\\\"xx\\\", \\\"yyy\\\", \\\"yy\\\"]\", wordsWithoutList({\"xx\", \"yyy\", \"x\", \"yy\", \"z\"}, 1), {\"xx\", \"yyy\", \"yy\"} );\n", "printTest( \"wordsWithoutList([\\\"xx\\\", \\\"yyy\\\", \\\"x\\\", \\\"yy\\\", \\\"z\\\"], 2) \u2192 [\\\"yyy\\\", \\\"x\\\", \\\"z\\\"]\", wordsWithoutList({\"xx\", \"yyy\", \"x\", \"yy\", \"z\"}, 2), {\"yyy\", \"x\", \"z\"} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > hasOne"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given a positive int n, return true if it contains a 1 digit. Note: use % to get\n", "the rightmost digit, and / to discard the rightmost digit.\n", "\n", "hasOne(10) \u2192 true\n", "hasOne(22) \u2192 false\n", "hasOne(220) \u2192 false\n", "*/\n", "\n", "bool hasOne(int n) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"hasOne(10) \u2192 true\", hasOne(10), true );\n", "printTest( \"hasOne(22) \u2192 false\", hasOne(22), false );\n", "printTest( \"hasOne(220) \u2192 false\", hasOne(220), false );\n", "printTest( \"hasOne(212) \u2192 true\", hasOne(212), true );\n", "printTest( \"hasOne(1) \u2192 true\", hasOne(1), true );\n", "printTest( \"hasOne(9) \u2192 false\", hasOne(9), false );\n", "printTest( \"hasOne(211112) \u2192 true\", hasOne(211112), true );\n", "printTest( \"hasOne(121121) \u2192 true\", hasOne(121121), true );\n", "printTest( \"hasOne(222222) \u2192 false\", hasOne(222222), false );\n", "printTest( \"hasOne(56156) \u2192 true\", hasOne(56156), true );\n", "printTest( \"hasOne(56556) \u2192 false\", hasOne(56556), false );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > dividesSelf"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "We'll say that a positive int divides itself if every digit in the number\n", "divides into the number evenly. So for example 128 divides itself since 1, 2,\n", "and 8 all divide into 128 evenly. We'll say that 0 does not divide into anything\n", "evenly, so no number with a 0 digit divides itself. Note: use % to get the\n", "rightmost digit, and / to discard the rightmost digit.\n", "\n", "dividesSelf(128) \u2192 true\n", "dividesSelf(12) \u2192 true\n", "dividesSelf(120) \u2192 false\n", "*/\n", "\n", "bool dividesSelf(int n) {\n", "    return false;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"dividesSelf(128) \u2192 true\", dividesSelf(128), true );\n", "printTest( \"dividesSelf(12) \u2192 true\", dividesSelf(12), true );\n", "printTest( \"dividesSelf(120) \u2192 false\", dividesSelf(120), false );\n", "printTest( \"dividesSelf(122) \u2192 true\", dividesSelf(122), true );\n", "printTest( \"dividesSelf(13) \u2192 false\", dividesSelf(13), false );\n", "printTest( \"dividesSelf(32) \u2192 false\", dividesSelf(32), false );\n", "printTest( \"dividesSelf(22) \u2192 true\", dividesSelf(22), true );\n", "printTest( \"dividesSelf(42) \u2192 false\", dividesSelf(42), false );\n", "printTest( \"dividesSelf(212) \u2192 true\", dividesSelf(212), true );\n", "printTest( \"dividesSelf(213) \u2192 false\", dividesSelf(213), false );\n", "printTest( \"dividesSelf(162) \u2192 true\", dividesSelf(162), true );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > copyEvens"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of positive ints, return a new array of length \"count\" containing\n", "the first even numbers from the original array. The original array will contain\n", "at least \"count\" even numbers.\n", "\n", "copyEvens([3, 2, 4, 5, 8], 2) \u2192 [2, 4]\n", "copyEvens([3, 2, 4, 5, 8], 3) \u2192 [2, 4, 8]\n", "copyEvens([6, 1, 2, 4, 5, 8], 3) \u2192 [6, 2, 4]\n", "*/\n", "\n", "std::vector<int> copyEvens(vector<int> nums, int count) {\n", "    return vector<int>{};\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"copyEvens([3, 2, 4, 5, 8], 2) \u2192 [2, 4]\", copyEvens({3, 2, 4, 5, 8}, 2), {2, 4} );\n", "printTest( \"copyEvens([3, 2, 4, 5, 8], 3) \u2192 [2, 4, 8]\", copyEvens({3, 2, 4, 5, 8}, 3), {2, 4, 8} );\n", "printTest( \"copyEvens([6, 1, 2, 4, 5, 8], 3) \u2192 [6, 2, 4]\", copyEvens({6, 1, 2, 4, 5, 8}, 3), {6, 2, 4} );\n", "printTest( \"copyEvens([6, 1, 2, 4, 5, 8], 4) \u2192 [6, 2, 4, 8]\", copyEvens({6, 1, 2, 4, 5, 8}, 4), {6, 2, 4, 8} );\n", "printTest( \"copyEvens([3, 1, 4, 1, 5], 1) \u2192 [4]\", copyEvens({3, 1, 4, 1, 5}, 1), {4} );\n", "printTest( \"copyEvens([2], 1) \u2192 [2]\", copyEvens({2}, 1), {2} );\n", "printTest( \"copyEvens([6, 2, 4, 8], 2) \u2192 [6, 2]\", copyEvens({6, 2, 4, 8}, 2), {6, 2} );\n", "printTest( \"copyEvens([6, 2, 4, 8], 3) \u2192 [6, 2, 4]\", copyEvens({6, 2, 4, 8}, 3), {6, 2, 4} );\n", "printTest( \"copyEvens([6, 2, 4, 8], 4) \u2192 [6, 2, 4, 8]\", copyEvens({6, 2, 4, 8}, 4), {6, 2, 4, 8} );\n", "printTest( \"copyEvens([1, 8, 4], 1) \u2192 [8]\", copyEvens({1, 8, 4}, 1), {8} );\n", "printTest( \"copyEvens([1, 8, 4], 2) \u2192 [8, 4]\", copyEvens({1, 8, 4}, 2), {8, 4} );\n", "printTest( \"copyEvens([2, 8, 4], 2) \u2192 [2, 8]\", copyEvens({2, 8, 4}, 2), {2, 8} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > copyEndy"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "We\u02bcll say that a positive int n is \"endy\" if it is in the range 0..10 or 90..100\n", "(inclusive). Given an array of positive ints, return a new array of length\n", "\"count\" containing the first endy numbers from the original array. Decompose out\n", "a separate isEndy(int n) method to test if a number is endy. The original array\n", "will contain at least \"count\" endy numbers.\n", "\n", "copyEndy([9, 11, 90, 22, 6], 2) \u2192 [9, 90]\n", "copyEndy([9, 11, 90, 22, 6], 3) \u2192 [9, 90, 6]\n", "copyEndy([12, 1, 1, 13, 0, 20], 2) \u2192 [1, 1]\n", "*/\n", "\n", "std::vector<int> copyEndy(vector<int> nums, int count) {\n", "    return vector<int>{};\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"copyEndy([9, 11, 90, 22, 6], 2) \u2192 [9, 90]\", copyEndy({9, 11, 90, 22, 6}, 2), {9, 90} );\n", "printTest( \"copyEndy([9, 11, 90, 22, 6], 3) \u2192 [9, 90, 6]\", copyEndy({9, 11, 90, 22, 6}, 3), {9, 90, 6} );\n", "printTest( \"copyEndy([12, 1, 1, 13, 0, 20], 2) \u2192 [1, 1]\", copyEndy({12, 1, 1, 13, 0, 20}, 2), {1, 1} );\n", "printTest( \"copyEndy([12, 1, 1, 13, 0, 20], 3) \u2192 [1, 1, 0]\", copyEndy({12, 1, 1, 13, 0, 20}, 3), {1, 1, 0} );\n", "printTest( \"copyEndy([0], 1) \u2192 [0]\", copyEndy({0}, 1), {0} );\n", "printTest( \"copyEndy([10, 11, 90], 2) \u2192 [10, 90]\", copyEndy({10, 11, 90}, 2), {10, 90} );\n", "printTest( \"copyEndy([90, 22, 100], 2) \u2192 [90, 100]\", copyEndy({90, 22, 100}, 2), {90, 100} );\n", "printTest( \"copyEndy([12, 11, 10, 89, 101, 4], 1) \u2192 [10]\", copyEndy({12, 11, 10, 89, 101, 4}, 1), {10} );\n", "printTest( \"copyEndy([13, 2, 2, 0], 2) \u2192 [2, 2]\", copyEndy({13, 2, 2, 0}, 2), {2, 2} );\n", "printTest( \"copyEndy([13, 2, 2, 0], 3) \u2192 [2, 2, 0]\", copyEndy({13, 2, 2, 0}, 3), {2, 2, 0} );\n", "printTest( \"copyEndy([13, 2, 13, 2, 0, 30], 2) \u2192 [2, 2]\", copyEndy({13, 2, 13, 2, 0, 30}, 2), {2, 2} );\n", "printTest( \"copyEndy([13, 2, 13, 2, 0, 30], 3) \u2192 [2, 2, 0]\", copyEndy({13, 2, 13, 2, 0, 30}, 3), {2, 2, 0} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > matchUp"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given 2 arrays that are the same length containing strings, compare the 1st\n", "string in one array to the 1st string in the other array, the 2nd to the 2nd and\n", "so on. Count the number of times that the 2 strings are non-empty and start with\n", "the same char. The strings may be any length, including 0.\n", "\n", "matchUp([\"aa\", \"bb\", \"cc\"], [\"aaa\", \"xx\", \"bb\"]) \u2192 1\n", "matchUp([\"aa\", \"bb\", \"cc\"], [\"aaa\", \"b\", \"bb\"]) \u2192 2\n", "matchUp([\"aa\", \"bb\", \"cc\"], [\"\", \"\", \"ccc\"]) \u2192 1\n", "*/\n", "\n", "int matchUp(vector<string> a, vector<string> b) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"matchUp([\\\"aa\\\", \\\"bb\\\", \\\"cc\\\"], [\\\"aaa\\\", \\\"xx\\\", \\\"bb\\\"]) \u2192 1\", matchUp({\"aa\", \"bb\", \"cc\"}, {\"aaa\", \"xx\", \"bb\"}), 1 );\n", "printTest( \"matchUp([\\\"aa\\\", \\\"bb\\\", \\\"cc\\\"], [\\\"aaa\\\", \\\"b\\\", \\\"bb\\\"]) \u2192 2\", matchUp({\"aa\", \"bb\", \"cc\"}, {\"aaa\", \"b\", \"bb\"}), 2 );\n", "printTest( \"matchUp([\\\"aa\\\", \\\"bb\\\", \\\"cc\\\"], [\\\"\\\", \\\"\\\", \\\"ccc\\\"]) \u2192 1\", matchUp({\"aa\", \"bb\", \"cc\"}, {\"\", \"\", \"ccc\"}), 1 );\n", "printTest( \"matchUp([\\\"\\\", \\\"\\\", \\\"ccc\\\"], [\\\"aa\\\", \\\"bb\\\", \\\"cc\\\"]) \u2192 1\", matchUp({\"\", \"\", \"ccc\"}, {\"aa\", \"bb\", \"cc\"}), 1 );\n", "printTest( \"matchUp([\\\"\\\", \\\"\\\", \\\"\\\"], [\\\"\\\", \\\"bb\\\", \\\"cc\\\"]) \u2192 0\", matchUp({\"\", \"\", \"\"}, {\"\", \"bb\", \"cc\"}), 0 );\n", "printTest( \"matchUp([\\\"aa\\\", \\\"bb\\\", \\\"cc\\\"], [\\\"\\\", \\\"\\\", \\\"\\\"]) \u2192 0\", matchUp({\"aa\", \"bb\", \"cc\"}, {\"\", \"\", \"\"}), 0 );\n", "printTest( \"matchUp([\\\"aa\\\", \\\"\\\", \\\"ccc\\\"], [\\\"\\\", \\\"bb\\\", \\\"cc\\\"]) \u2192 1\", matchUp({\"aa\", \"\", \"ccc\"}, {\"\", \"bb\", \"cc\"}), 1 );\n", "printTest( \"matchUp([\\\"x\\\", \\\"y\\\", \\\"z\\\"], [\\\"y\\\", \\\"z\\\", \\\"x\\\"]) \u2192 0\", matchUp({\"x\", \"y\", \"z\"}, {\"y\", \"z\", \"x\"}), 0 );\n", "printTest( \"matchUp([\\\"\\\", \\\"y\\\", \\\"z\\\"], [\\\"\\\", \\\"y\\\", \\\"x\\\"]) \u2192 1\", matchUp({\"\", \"y\", \"z\"}, {\"\", \"y\", \"x\"}), 1 );\n", "printTest( \"matchUp([\\\"x\\\", \\\"y\\\", \\\"z\\\"], [\\\"xx\\\", \\\"yyy\\\", \\\"zzz\\\"]) \u2192 3\", matchUp({\"x\", \"y\", \"z\"}, {\"xx\", \"yyy\", \"zzz\"}), 3 );\n", "printTest( \"matchUp([\\\"x\\\", \\\"y\\\", \\\"z\\\"], [\\\"xx\\\", \\\"yyy\\\", \\\"\\\"]) \u2192 2\", matchUp({\"x\", \"y\", \"z\"}, {\"xx\", \"yyy\", \"\"}), 2 );\n", "printTest( \"matchUp([\\\"b\\\", \\\"x\\\", \\\"y\\\", \\\"z\\\"], [\\\"a\\\", \\\"xx\\\", \\\"yyy\\\", \\\"zzz\\\"]) \u2192 3\", matchUp({\"b\", \"x\", \"y\", \"z\"}, {\"a\", \"xx\", \"yyy\", \"zzz\"}), 3 );\n", "printTest( \"matchUp([\\\"aaa\\\", \\\"bb\\\", \\\"c\\\"], [\\\"aaa\\\", \\\"xx\\\", \\\"bb\\\"]) \u2192 1\", matchUp({\"aaa\", \"bb\", \"c\"}, {\"aaa\", \"xx\", \"bb\"}), 1 );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > scoreUp"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "The \"key\" array is an array containing the correct answers to an exam, like\n", "{\"a\", \"a\", \"b\", \"b\"}. the \"answers\" array contains a student\u02bcs answers, with \"?\"\n", "representing a question left blank. The two arrays are not empty and are the\n", "same length. Return the score for this array of answers, giving +4 for each\n", "correct answer, -1 for each incorrect answer, and +0 for each blank answer.\n", "\n", "scoreUp([\"a\", \"a\", \"b\", \"b\"], [\"a\", \"c\", \"b\", \"c\"]) \u2192 6\n", "scoreUp([\"a\", \"a\", \"b\", \"b\"], [\"a\", \"a\", \"b\", \"c\"]) \u2192 11\n", "scoreUp([\"a\", \"a\", \"b\", \"b\"], [\"a\", \"a\", \"b\", \"b\"]) \u2192 16\n", "*/\n", "\n", "int scoreUp(vector<string> key, vector<string> answers) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\"], [\\\"a\\\", \\\"c\\\", \\\"b\\\", \\\"c\\\"]) \u2192 6\", scoreUp({\"a\", \"a\", \"b\", \"b\"}, {\"a\", \"c\", \"b\", \"c\"}), 6 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\"], [\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"c\\\"]) \u2192 11\", scoreUp({\"a\", \"a\", \"b\", \"b\"}, {\"a\", \"a\", \"b\", \"c\"}), 11 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\"], [\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\"]) \u2192 16\", scoreUp({\"a\", \"a\", \"b\", \"b\"}, {\"a\", \"a\", \"b\", \"b\"}), 16 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\"], [\\\"?\\\", \\\"c\\\", \\\"b\\\", \\\"?\\\"]) \u2192 3\", scoreUp({\"a\", \"a\", \"b\", \"b\"}, {\"?\", \"c\", \"b\", \"?\"}), 3 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\"], [\\\"?\\\", \\\"c\\\", \\\"?\\\", \\\"?\\\"]) \u2192 -1\", scoreUp({\"a\", \"a\", \"b\", \"b\"}, {\"?\", \"c\", \"?\", \"?\"}), -1 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\"], [\\\"c\\\", \\\"?\\\", \\\"b\\\", \\\"b\\\"]) \u2192 7\", scoreUp({\"a\", \"a\", \"b\", \"b\"}, {\"c\", \"?\", \"b\", \"b\"}), 7 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\"], [\\\"c\\\", \\\"?\\\", \\\"b\\\", \\\"?\\\"]) \u2192 3\", scoreUp({\"a\", \"a\", \"b\", \"b\"}, {\"c\", \"?\", \"b\", \"?\"}), 3 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"b\\\", \\\"c\\\"], [\\\"a\\\", \\\"c\\\", \\\"b\\\"]) \u2192 2\", scoreUp({\"a\", \"b\", \"c\"}, {\"a\", \"c\", \"b\"}), 2 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\", \\\"c\\\"], [\\\"a\\\", \\\"c\\\", \\\"a\\\", \\\"c\\\", \\\"a\\\", \\\"c\\\"]) \u2192 4\", scoreUp({\"a\", \"a\", \"b\", \"b\", \"c\", \"c\"}, {\"a\", \"c\", \"a\", \"c\", \"a\", \"c\"}), 4 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\", \\\"c\\\"], [\\\"a\\\", \\\"c\\\", \\\"?\\\", \\\"?\\\", \\\"a\\\", \\\"c\\\"]) \u2192 6\", scoreUp({\"a\", \"a\", \"b\", \"b\", \"c\", \"c\"}, {\"a\", \"c\", \"?\", \"?\", \"a\", \"c\"}), 6 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\", \\\"c\\\"], [\\\"a\\\", \\\"c\\\", \\\"?\\\", \\\"?\\\", \\\"c\\\", \\\"c\\\"]) \u2192 11\", scoreUp({\"a\", \"a\", \"b\", \"b\", \"c\", \"c\"}, {\"a\", \"c\", \"?\", \"?\", \"c\", \"c\"}), 11 );\n", "printTest( \"scoreUp([\\\"a\\\", \\\"b\\\", \\\"c\\\"], [\\\"a\\\", \\\"b\\\", \\\"c\\\"]) \u2192 12\", scoreUp({\"a\", \"b\", \"c\"}, {\"a\", \"b\", \"c\"}), 12 );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > wordsWithout"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of strings, return a new array without the strings that are equal\n", "to the target string. One approach is to count the occurrences of the target\n", "string, make a new array of the correct length, and then copy over the correct\n", "strings.\n", "\n", "wordsWithout([\"a\", \"b\", \"c\", \"a\"], \"a\") \u2192 [\"b\", \"c\"]\n", "wordsWithout([\"a\", \"b\", \"c\", \"a\"], \"b\") \u2192 [\"a\", \"c\", \"a\"]\n", "wordsWithout([\"a\", \"b\", \"c\", \"a\"], \"c\") \u2192 [\"a\", \"b\", \"a\"]\n", "*/\n", "\n", "std::vector<string> wordsWithout(vector<string> words, string target) {\n", "    return new vector<string>{};\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"wordsWithout([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"a\\\"], \\\"a\\\") \u2192 [\\\"b\\\", \\\"c\\\"]\", wordsWithout({\"a\", \"b\", \"c\", \"a\"}, \"a\"), {\"b\", \"c\"} );\n", "printTest( \"wordsWithout([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"a\\\"], \\\"b\\\") \u2192 [\\\"a\\\", \\\"c\\\", \\\"a\\\"]\", wordsWithout({\"a\", \"b\", \"c\", \"a\"}, \"b\"), {\"a\", \"c\", \"a\"} );\n", "printTest( \"wordsWithout([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"a\\\"], \\\"c\\\") \u2192 [\\\"a\\\", \\\"b\\\", \\\"a\\\"]\", wordsWithout({\"a\", \"b\", \"c\", \"a\"}, \"c\"), {\"a\", \"b\", \"a\"} );\n", "printTest( \"wordsWithout([\\\"b\\\", \\\"c\\\", \\\"a\\\", \\\"a\\\"], \\\"b\\\") \u2192 [\\\"c\\\", \\\"a\\\", \\\"a\\\"]\", wordsWithout({\"b\", \"c\", \"a\", \"a\"}, \"b\"), {\"c\", \"a\", \"a\"} );\n", "printTest( \"wordsWithout([\\\"xx\\\", \\\"yyy\\\", \\\"x\\\", \\\"yy\\\", \\\"x\\\"], \\\"x\\\") \u2192 [\\\"xx\\\", \\\"yyy\\\", \\\"yy\\\"]\", wordsWithout({\"xx\", \"yyy\", \"x\", \"yy\", \"x\"}, \"x\"), {\"xx\", \"yyy\", \"yy\"} );\n", "printTest( \"wordsWithout([\\\"xx\\\", \\\"yyy\\\", \\\"x\\\", \\\"yy\\\", \\\"x\\\"], \\\"yy\\\") \u2192 [\\\"xx\\\", \\\"yyy\\\", \\\"x\\\", \\\"x\\\"]\", wordsWithout({\"xx\", \"yyy\", \"x\", \"yy\", \"x\"}, \"yy\"), {\"xx\", \"yyy\", \"x\", \"x\"} );\n", "printTest( \"wordsWithout([\\\"aa\\\", \\\"ab\\\", \\\"ac\\\", \\\"aa\\\"], \\\"aa\\\") \u2192 [\\\"ab\\\", \\\"ac\\\"]\", wordsWithout({\"aa\", \"ab\", \"ac\", \"aa\"}, \"aa\"), {\"ab\", \"ac\"} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > scoresSpecial"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given two arrays, A and B, of non-negative int scores. A \"special\" score is one\n", "which is a multiple of 10, such as 40 or 90. Return the sum of largest special\n", "score in A and the largest special score in B. To practice decomposition, write\n", "a separate helper method which finds the largest special score in an array.\n", "Write your helper method after your scoresSpecial() method in the JavaBat text\n", "area.\n", "\n", "scoresSpecial([12, 10, 4], [2, 20, 30]) \u2192 40\n", "scoresSpecial([20, 10, 4], [2, 20, 10]) \u2192 40\n", "scoresSpecial([12, 11, 4], [2, 20, 31]) \u2192 20\n", "*/\n", "\n", "int scoresSpecial(vector<int> a, vector<int> b) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"scoresSpecial([12, 10, 4], [2, 20, 30]) \u2192 40\", scoresSpecial({12, 10, 4}, {2, 20, 30}), 40 );\n", "printTest( \"scoresSpecial([20, 10, 4], [2, 20, 10]) \u2192 40\", scoresSpecial({20, 10, 4}, {2, 20, 10}), 40 );\n", "printTest( \"scoresSpecial([12, 11, 4], [2, 20, 31]) \u2192 20\", scoresSpecial({12, 11, 4}, {2, 20, 31}), 20 );\n", "printTest( \"scoresSpecial([1, 20, 2, 50], [3, 4, 5]) \u2192 50\", scoresSpecial({1, 20, 2, 50}, {3, 4, 5}), 50 );\n", "printTest( \"scoresSpecial([3, 4, 5], [1, 50, 2, 20]) \u2192 50\", scoresSpecial({3, 4, 5}, {1, 50, 2, 20}), 50 );\n", "printTest( \"scoresSpecial([10, 4, 20, 30], [20]) \u2192 50\", scoresSpecial({10, 4, 20, 30}, {20}), 50 );\n", "printTest( \"scoresSpecial([10, 4, 20, 30], [20]) \u2192 50\", scoresSpecial({10, 4, 20, 30}, {20}), 50 );\n", "printTest( \"scoresSpecial([10, 4, 20, 30], [3, 20, 99]) \u2192 50\", scoresSpecial({10, 4, 20, 30}, {3, 20, 99}), 50 );\n", "printTest( \"scoresSpecial([10, 4, 20, 30], [30, 20, 99]) \u2192 60\", scoresSpecial({10, 4, 20, 30}, {30, 20, 99}), 60 );\n", "printTest( \"scoresSpecial([], [2]) \u2192 0\", scoresSpecial({}, {2}), 0 );\n", "printTest( \"scoresSpecial([], [20]) \u2192 20\", scoresSpecial({}, {20}), 20 );\n", "printTest( \"scoresSpecial([14, 10, 4], [4, 20, 30]) \u2192 40\", scoresSpecial({14, 10, 4}, {4, 20, 30}), 40 );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > sumHeights"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "We have an array of heights, representing the altitude along a walking trail.\n", "Given start/end indexes into the array, return the sum of the changes for a walk\n", "beginning at the start index and ending at the end index. For example, with the\n", "heights {5, 3, 6, 7, 2} and start=2, end=4 yields a sum of 1 + 5 = 6. The start\n", "end end index will both be valid indexes into the array with start <= end.\n", "\n", "sumHeights([5, 3, 6, 7, 2], 2, 4) \u2192 6\n", "sumHeights([5, 3, 6, 7, 2], 0, 1) \u2192 2\n", "sumHeights([5, 3, 6, 7, 2], 0, 4) \u2192 11\n", "*/\n", "\n", "int sumHeights(vector<int> heights, int start, int end) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"sumHeights([5, 3, 6, 7, 2], 2, 4) \u2192 6\", sumHeights({5, 3, 6, 7, 2}, 2, 4), 6 );\n", "printTest( \"sumHeights([5, 3, 6, 7, 2], 0, 1) \u2192 2\", sumHeights({5, 3, 6, 7, 2}, 0, 1), 2 );\n", "printTest( \"sumHeights([5, 3, 6, 7, 2], 0, 4) \u2192 11\", sumHeights({5, 3, 6, 7, 2}, 0, 4), 11 );\n", "printTest( \"sumHeights([5, 3, 6, 7, 2], 1, 1) \u2192 0\", sumHeights({5, 3, 6, 7, 2}, 1, 1), 0 );\n", "printTest( \"sumHeights([1, 2, 3, 4, 5, 4, 3, 2, 10], 0, 3) \u2192 3\", sumHeights({1, 2, 3, 4, 5, 4, 3, 2, 10}, 0, 3), 3 );\n", "printTest( \"sumHeights([1, 2, 3, 4, 5, 4, 3, 2, 10], 4, 8) \u2192 11\", sumHeights({1, 2, 3, 4, 5, 4, 3, 2, 10}, 4, 8), 11 );\n", "printTest( \"sumHeights([1, 2, 3, 4, 5, 4, 3, 2, 10], 7, 8) \u2192 8\", sumHeights({1, 2, 3, 4, 5, 4, 3, 2, 10}, 7, 8), 8 );\n", "printTest( \"sumHeights([1, 2, 3, 4, 5, 4, 3, 2, 10], 8, 8) \u2192 0\", sumHeights({1, 2, 3, 4, 5, 4, 3, 2, 10}, 8, 8), 0 );\n", "printTest( \"sumHeights([1, 2, 3, 4, 5, 4, 3, 2, 10], 2, 2) \u2192 0\", sumHeights({1, 2, 3, 4, 5, 4, 3, 2, 10}, 2, 2), 0 );\n", "printTest( \"sumHeights([1, 2, 3, 4, 5, 4, 3, 2, 10], 3, 6) \u2192 3\", sumHeights({1, 2, 3, 4, 5, 4, 3, 2, 10}, 3, 6), 3 );\n", "printTest( \"sumHeights([10, 8, 7, 7, 7, 6, 7], 1, 4) \u2192 1\", sumHeights({10, 8, 7, 7, 7, 6, 7}, 1, 4), 1 );\n", "printTest( \"sumHeights([10, 8, 7, 7, 7, 6, 7], 1, 5) \u2192 2\", sumHeights({10, 8, 7, 7, 7, 6, 7}, 1, 5), 2 );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > sumHeights2"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "(A variation on the sumHeights problem.) We have an array of heights,\n", "representing the altitude along a walking trail. Given start/end indexes into\n", "the array, return the sum of the changes for a walk beginning at the start index\n", "and ending at the end index, however increases in height count double. For\n", "example, with the heights {5, 3, 6, 7, 2} and start=2, end=4 yields a sum of 1*2\n", "+ 5 = 7. The start end end index will both be valid indexes into the array with\n", "start <= end.\n", "\n", "sumHeights2([5, 3, 6, 7, 2], 2, 4) \u2192 7\n", "sumHeights2([5, 3, 6, 7, 2], 0, 1) \u2192 2\n", "sumHeights2([5, 3, 6, 7, 2], 0, 4) \u2192 15\n", "*/\n", "\n", "int sumHeights2(vector<int> heights, int start, int end) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"sumHeights2([5, 3, 6, 7, 2], 2, 4) \u2192 7\", sumHeights2({5, 3, 6, 7, 2}, 2, 4), 7 );\n", "printTest( \"sumHeights2([5, 3, 6, 7, 2], 0, 1) \u2192 2\", sumHeights2({5, 3, 6, 7, 2}, 0, 1), 2 );\n", "printTest( \"sumHeights2([5, 3, 6, 7, 2], 0, 4) \u2192 15\", sumHeights2({5, 3, 6, 7, 2}, 0, 4), 15 );\n", "printTest( \"sumHeights2([5, 3, 6, 7, 2], 1, 1) \u2192 0\", sumHeights2({5, 3, 6, 7, 2}, 1, 1), 0 );\n", "printTest( \"sumHeights2([1, 2, 3, 4, 5, 4, 3, 2, 10], 0, 3) \u2192 6\", sumHeights2({1, 2, 3, 4, 5, 4, 3, 2, 10}, 0, 3), 6 );\n", "printTest( \"sumHeights2([1, 2, 3, 4, 5, 4, 3, 2, 10], 4, 8) \u2192 19\", sumHeights2({1, 2, 3, 4, 5, 4, 3, 2, 10}, 4, 8), 19 );\n", "printTest( \"sumHeights2([1, 2, 3, 4, 5, 4, 3, 2, 10], 7, 8) \u2192 16\", sumHeights2({1, 2, 3, 4, 5, 4, 3, 2, 10}, 7, 8), 16 );\n", "printTest( \"sumHeights2([1, 2, 3, 4, 5, 4, 3, 2, 10], 8, 8) \u2192 0\", sumHeights2({1, 2, 3, 4, 5, 4, 3, 2, 10}, 8, 8), 0 );\n", "printTest( \"sumHeights2([1, 2, 3, 4, 5, 4, 3, 2, 10], 2, 2) \u2192 0\", sumHeights2({1, 2, 3, 4, 5, 4, 3, 2, 10}, 2, 2), 0 );\n", "printTest( \"sumHeights2([1, 2, 3, 4, 5, 4, 3, 2, 10], 3, 6) \u2192 4\", sumHeights2({1, 2, 3, 4, 5, 4, 3, 2, 10}, 3, 6), 4 );\n", "printTest( \"sumHeights2([10, 8, 7, 7, 7, 6, 7], 1, 4) \u2192 1\", sumHeights2({10, 8, 7, 7, 7, 6, 7}, 1, 4), 1 );\n", "printTest( \"sumHeights2([10, 8, 7, 7, 7, 6, 7], 1, 5) \u2192 2\", sumHeights2({10, 8, 7, 7, 7, 6, 7}, 1, 5), 2 );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > bigHeights"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "(A variation on the sumHeights problem.) We have an array of heights,\n", "representing the altitude along a walking trail. Given start/end indexes into\n", "the array, return the number of \"big\" steps for a walk starting at the start\n", "index and ending at the end index. We\u02bcll say that  step is big if it is 5 or\n", "more up or down. The start end end index will both be valid indexes into the\n", "array with start <= end.\n", "\n", "bigHeights([5, 3, 6, 7, 2], 2, 4) \u2192 1\n", "bigHeights([5, 3, 6, 7, 2], 0, 1) \u2192 0\n", "bigHeights([5, 3, 6, 7, 2], 0, 4) \u2192 1\n", "*/\n", "\n", "int bigHeights(vector<int> heights, int start, int end) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"bigHeights([5, 3, 6, 7, 2], 2, 4) \u2192 1\", bigHeights({5, 3, 6, 7, 2}, 2, 4), 1 );\n", "printTest( \"bigHeights([5, 3, 6, 7, 2], 0, 1) \u2192 0\", bigHeights({5, 3, 6, 7, 2}, 0, 1), 0 );\n", "printTest( \"bigHeights([5, 3, 6, 7, 2], 0, 4) \u2192 1\", bigHeights({5, 3, 6, 7, 2}, 0, 4), 1 );\n", "printTest( \"bigHeights([5, 3, 6, 7, 3], 0, 4) \u2192 0\", bigHeights({5, 3, 6, 7, 3}, 0, 4), 0 );\n", "printTest( \"bigHeights([5, 3, 6, 7, 2], 1, 1) \u2192 0\", bigHeights({5, 3, 6, 7, 2}, 1, 1), 0 );\n", "printTest( \"bigHeights([5, 13, 6, 7, 2], 1, 2) \u2192 1\", bigHeights({5, 13, 6, 7, 2}, 1, 2), 1 );\n", "printTest( \"bigHeights([5, 13, 6, 7, 2], 0, 2) \u2192 2\", bigHeights({5, 13, 6, 7, 2}, 0, 2), 2 );\n", "printTest( \"bigHeights([5, 13, 6, 7, 2], 1, 4) \u2192 2\", bigHeights({5, 13, 6, 7, 2}, 1, 4), 2 );\n", "printTest( \"bigHeights([5, 13, 6, 7, 2], 0, 4) \u2192 3\", bigHeights({5, 13, 6, 7, 2}, 0, 4), 3 );\n", "printTest( \"bigHeights([5, 13, 6, 7, 2], 0, 3) \u2192 2\", bigHeights({5, 13, 6, 7, 2}, 0, 3), 2 );\n", "printTest( \"bigHeights([1, 2, 3, 4, 5, 4, 3, 2, 10], 0, 3) \u2192 0\", bigHeights({1, 2, 3, 4, 5, 4, 3, 2, 10}, 0, 3), 0 );\n", "printTest( \"bigHeights([1, 2, 3, 4, 5, 4, 3, 2, 10], 4, 8) \u2192 1\", bigHeights({1, 2, 3, 4, 5, 4, 3, 2, 10}, 4, 8), 1 );\n", "printTest( \"bigHeights([1, 2, 3, 14, 5, 4, 3, 2, 10], 0, 3) \u2192 1\", bigHeights({1, 2, 3, 14, 5, 4, 3, 2, 10}, 0, 3), 1 );\n", "printTest( \"bigHeights([1, 2, 3, 14, 5, 4, 3, 2, 10], 7, 8) \u2192 1\", bigHeights({1, 2, 3, 14, 5, 4, 3, 2, 10}, 7, 8), 1 );\n", "printTest( \"bigHeights([1, 2, 3, 14, 5, 4, 3, 2, 10], 3, 8) \u2192 2\", bigHeights({1, 2, 3, 14, 5, 4, 3, 2, 10}, 3, 8), 2 );\n", "printTest( \"bigHeights([1, 2, 3, 14, 5, 4, 3, 2, 10], 2, 8) \u2192 3\", bigHeights({1, 2, 3, 14, 5, 4, 3, 2, 10}, 2, 8), 3 );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > userCompare"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "We have data for two users, A and B, each with a String name and an int id. The\n", "goal is to order the users such as for sorting. Return -1 if A comes before B, 1\n", "if A comes after B, and 0 if they are the same. Order first by the string names,\n", "and then by the id numbers if the names are the same. Note: with Strings\n", "str1.compareTo(str2) returns an int value which is negative/0/positive to\n", "indicate how str1 is ordered to str2 (the value is not limited to -1/0/1). (On\n", "the AP, there would be two User objects, but here the code simply takes the two\n", "strings and two ints directly. The code logic is the same.)\n", "\n", "userCompare(\"bb\", 1, \"zz\", 2) \u2192 -1\n", "userCompare(\"bb\", 1, \"aa\", 2) \u2192 1\n", "userCompare(\"bb\", 1, \"bb\", 1) \u2192 0\n", "*/\n", "\n", "int userCompare(string aName, int aId, string bName, int bId) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"userCompare(\\\"bb\\\", 1, \\\"zz\\\", 2) \u2192 -1\", userCompare(\"bb\", 1, \"zz\", 2), -1 );\n", "printTest( \"userCompare(\\\"bb\\\", 1, \\\"aa\\\", 2) \u2192 1\", userCompare(\"bb\", 1, \"aa\", 2), 1 );\n", "printTest( \"userCompare(\\\"bb\\\", 1, \\\"bb\\\", 1) \u2192 0\", userCompare(\"bb\", 1, \"bb\", 1), 0 );\n", "printTest( \"userCompare(\\\"bb\\\", 5, \\\"bb\\\", 1) \u2192 1\", userCompare(\"bb\", 5, \"bb\", 1), 1 );\n", "printTest( \"userCompare(\\\"bb\\\", 5, \\\"bb\\\", 10) \u2192 -1\", userCompare(\"bb\", 5, \"bb\", 10), -1 );\n", "printTest( \"userCompare(\\\"adam\\\", 1, \\\"bob\\\", 2) \u2192 -1\", userCompare(\"adam\", 1, \"bob\", 2), -1 );\n", "printTest( \"userCompare(\\\"bob\\\", 1, \\\"bob\\\", 2) \u2192 -1\", userCompare(\"bob\", 1, \"bob\", 2), -1 );\n", "printTest( \"userCompare(\\\"bzb\\\", 1, \\\"bob\\\", 2) \u2192 1\", userCompare(\"bzb\", 1, \"bob\", 2), 1 );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > mergeTwo"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Start with two arrays of strings, A and B, each with its elements in\n", "alphabetical order and without duplicates. Return a new array containing the\n", "first N elements from the two arrays. The result array should be in alphabetical\n", "order and without duplicates. A and B will both have a length which is N or\n", "more. The best \"linear\" solution makes a single pass over A and B, taking\n", "advantage of the fact that they are in alphabetical order, copying elements\n", "directly to the new array.\n", "\n", "mergeTwo([\"a\", \"c\", \"z\"], [\"b\", \"f\", \"z\"], 3) \u2192 [\"a\", \"b\", \"c\"]\n", "mergeTwo([\"a\", \"c\", \"z\"], [\"c\", \"f\", \"z\"], 3) \u2192 [\"a\", \"c\", \"f\"]\n", "mergeTwo([\"f\", \"g\", \"z\"], [\"c\", \"f\", \"g\"], 3) \u2192 [\"c\", \"f\", \"g\"]\n", "*/\n", "\n", "std::vector<string> mergeTwo(vector<string> a, vector<string> b, int n) {\n", "    return new vector<string>{};\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"mergeTwo([\\\"a\\\", \\\"c\\\", \\\"z\\\"], [\\\"b\\\", \\\"f\\\", \\\"z\\\"], 3) \u2192 [\\\"a\\\", \\\"b\\\", \\\"c\\\"]\", mergeTwo({\"a\", \"c\", \"z\"}, {\"b\", \"f\", \"z\"}, 3), {\"a\", \"b\", \"c\"} );\n", "printTest( \"mergeTwo([\\\"a\\\", \\\"c\\\", \\\"z\\\"], [\\\"c\\\", \\\"f\\\", \\\"z\\\"], 3) \u2192 [\\\"a\\\", \\\"c\\\", \\\"f\\\"]\", mergeTwo({\"a\", \"c\", \"z\"}, {\"c\", \"f\", \"z\"}, 3), {\"a\", \"c\", \"f\"} );\n", "printTest( \"mergeTwo([\\\"f\\\", \\\"g\\\", \\\"z\\\"], [\\\"c\\\", \\\"f\\\", \\\"g\\\"], 3) \u2192 [\\\"c\\\", \\\"f\\\", \\\"g\\\"]\", mergeTwo({\"f\", \"g\", \"z\"}, {\"c\", \"f\", \"g\"}, 3), {\"c\", \"f\", \"g\"} );\n", "printTest( \"mergeTwo([\\\"a\\\", \\\"c\\\", \\\"z\\\"], [\\\"a\\\", \\\"c\\\", \\\"z\\\"], 3) \u2192 [\\\"a\\\", \\\"c\\\", \\\"z\\\"]\", mergeTwo({\"a\", \"c\", \"z\"}, {\"a\", \"c\", \"z\"}, 3), {\"a\", \"c\", \"z\"} );\n", "printTest( \"mergeTwo([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"z\\\"], [\\\"a\\\", \\\"c\\\", \\\"z\\\"], 3) \u2192 [\\\"a\\\", \\\"b\\\", \\\"c\\\"]\", mergeTwo({\"a\", \"b\", \"c\", \"z\"}, {\"a\", \"c\", \"z\"}, 3), {\"a\", \"b\", \"c\"} );\n", "printTest( \"mergeTwo([\\\"a\\\", \\\"c\\\", \\\"z\\\"], [\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"z\\\"], 3) \u2192 [\\\"a\\\", \\\"b\\\", \\\"c\\\"]\", mergeTwo({\"a\", \"c\", \"z\"}, {\"a\", \"b\", \"c\", \"z\"}, 3), {\"a\", \"b\", \"c\"} );\n", "printTest( \"mergeTwo([\\\"a\\\", \\\"c\\\", \\\"z\\\"], [\\\"a\\\", \\\"c\\\", \\\"z\\\"], 2) \u2192 [\\\"a\\\", \\\"c\\\"]\", mergeTwo({\"a\", \"c\", \"z\"}, {\"a\", \"c\", \"z\"}, 2), {\"a\", \"c\"} );\n", "printTest( \"mergeTwo([\\\"a\\\", \\\"c\\\", \\\"z\\\"], [\\\"a\\\", \\\"c\\\", \\\"y\\\", \\\"z\\\"], 3) \u2192 [\\\"a\\\", \\\"c\\\", \\\"y\\\"]\", mergeTwo({\"a\", \"c\", \"z\"}, {\"a\", \"c\", \"y\", \"z\"}, 3), {\"a\", \"c\", \"y\"} );\n", "printTest( \"mergeTwo([\\\"x\\\", \\\"y\\\", \\\"z\\\"], [\\\"a\\\", \\\"b\\\", \\\"z\\\"], 3) \u2192 [\\\"a\\\", \\\"b\\\", \\\"x\\\"]\", mergeTwo({\"x\", \"y\", \"z\"}, {\"a\", \"b\", \"z\"}, 3), {\"a\", \"b\", \"x\"} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# AP-1 > commonTwo"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Start with two arrays of strings, a and b, each in alphabetical order, possibly\n", "with duplicates. Return the count of the number of strings which appear in both\n", "arrays. The best \"linear\" solution makes a single pass over both arrays, taking\n", "advantage of the fact that they are in alphabetical order.\n", "\n", "commonTwo([\"a\", \"c\", \"x\"], [\"b\", \"c\", \"d\", \"x\"]) \u2192 2\n", "commonTwo([\"a\", \"c\", \"x\"], [\"a\", \"b\", \"c\", \"x\", \"z\"]) \u2192 3\n", "commonTwo([\"a\", \"b\", \"c\"], [\"a\", \"b\", \"c\"]) \u2192 3\n", "*/\n", "\n", "int commonTwo(vector<string> a, vector<string> b) {\n", "    return 0;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"commonTwo([\\\"a\\\", \\\"c\\\", \\\"x\\\"], [\\\"b\\\", \\\"c\\\", \\\"d\\\", \\\"x\\\"]) \u2192 2\", commonTwo({\"a\", \"c\", \"x\"}, {\"b\", \"c\", \"d\", \"x\"}), 2 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"c\\\", \\\"x\\\"], [\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"x\\\", \\\"z\\\"]) \u2192 3\", commonTwo({\"a\", \"c\", \"x\"}, {\"a\", \"b\", \"c\", \"x\", \"z\"}), 3 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"b\\\", \\\"c\\\"], [\\\"a\\\", \\\"b\\\", \\\"c\\\"]) \u2192 3\", commonTwo({\"a\", \"b\", \"c\"}, {\"a\", \"b\", \"c\"}), 3 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"], [\\\"a\\\", \\\"b\\\", \\\"c\\\"]) \u2192 3\", commonTwo({\"a\", \"a\", \"b\", \"b\", \"c\"}, {\"a\", \"b\", \"c\"}), 3 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"], [\\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"]) \u2192 3\", commonTwo({\"a\", \"a\", \"b\", \"b\", \"c\"}, {\"a\", \"b\", \"b\", \"b\", \"c\"}), 3 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"], [\\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\", \\\"c\\\"]) \u2192 3\", commonTwo({\"a\", \"a\", \"b\", \"b\", \"c\"}, {\"a\", \"b\", \"b\", \"c\", \"c\"}), 3 );\n", "printTest( \"commonTwo([\\\"b\\\", \\\"b\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"], [\\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"]) \u2192 2\", commonTwo({\"b\", \"b\", \"b\", \"b\", \"c\"}, {\"a\", \"b\", \"b\", \"b\", \"c\"}), 2 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"c\\\", \\\"d\\\"], [\\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\", \\\"d\\\", \\\"d\\\"]) \u2192 4\", commonTwo({\"a\", \"b\", \"c\", \"c\", \"d\"}, {\"a\", \"b\", \"b\", \"c\", \"d\", \"d\"}), 4 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"], [\\\"b\\\", \\\"b\\\", \\\"b\\\"]) \u2192 1\", commonTwo({\"a\", \"a\", \"b\", \"b\", \"c\"}, {\"b\", \"b\", \"b\"}), 1 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"], [\\\"c\\\", \\\"c\\\"]) \u2192 1\", commonTwo({\"a\", \"a\", \"b\", \"b\", \"c\"}, {\"c\", \"c\"}), 1 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"], [\\\"b\\\", \\\"b\\\", \\\"b\\\", \\\"x\\\"]) \u2192 1\", commonTwo({\"a\", \"a\", \"b\", \"b\", \"c\"}, {\"b\", \"b\", \"b\", \"x\"}), 1 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"c\\\"], [\\\"b\\\", \\\"b\\\"]) \u2192 1\", commonTwo({\"a\", \"a\", \"b\", \"b\", \"c\"}, {\"b\", \"b\"}), 1 );\n", "printTest( \"commonTwo([\\\"a\\\"], [\\\"a\\\", \\\"b\\\"]) \u2192 1\", commonTwo({\"a\"}, {\"a\", \"b\"}), 1 );\n", "printTest( \"commonTwo([\\\"a\\\"], [\\\"b\\\"]) \u2192 0\", commonTwo({\"a\"}, {\"b\"}), 0 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"a\\\"], [\\\"b\\\", \\\"b\\\"]) \u2192 0\", commonTwo({\"a\", \"a\"}, {\"b\", \"b\"}), 0 );\n", "printTest( \"commonTwo([\\\"a\\\", \\\"b\\\"], [\\\"a\\\", \\\"b\\\"]) \u2192 2\", commonTwo({\"a\", \"b\"}, {\"a\", \"b\"}), 2 );"]}
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}