cpp-codingbat-15-Map-2.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": ["# Map-2 > word0"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of strings, return a Map<String, Integer> containing a key for\n", "every different string in the array, always with the value 0. For example the\n", "string \"hello\" makes the pair \"hello\":0. We\u02bcll do more complicated counting\n", "later, but for this problem the value is simply 0.\n", "\n", "word0([\"a\", \"b\", \"a\", \"b\"]) \u2192 {\"a\": 0, \"b\": 0}\n", "word0([\"a\", \"b\", \"a\", \"c\", \"b\"]) \u2192 {\"a\": 0, \"b\": 0, \"c\": 0}\n", "word0([\"c\", \"b\", \"a\"]) \u2192 {\"a\": 0, \"b\": 0, \"c\": 0}\n", "*/\n", "\n", "Map<string, int> word0(vector<string> strings) {\n", "    return null;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"word0([\\\"a\\\", \\\"b\\\", \\\"a\\\", \\\"b\\\"]) \u2192 {\\\"a\\\": 0, \\\"b\\\": 0}\", word0({\"a\", \"b\", \"a\", \"b\"}), {\"a\": 0, \"b\": 0} );\n", "printTest( \"word0([\\\"a\\\", \\\"b\\\", \\\"a\\\", \\\"c\\\", \\\"b\\\"]) \u2192 {\\\"a\\\": 0, \\\"b\\\": 0, \\\"c\\\": 0}\", word0({\"a\", \"b\", \"a\", \"c\", \"b\"}), {\"a\": 0, \"b\": 0, \"c\": 0} );\n", "printTest( \"word0([\\\"c\\\", \\\"b\\\", \\\"a\\\"]) \u2192 {\\\"a\\\": 0, \\\"b\\\": 0, \\\"c\\\": 0}\", word0({\"c\", \"b\", \"a\"}), {\"a\": 0, \"b\": 0, \"c\": 0} );\n", "printTest( \"word0([\\\"c\\\", \\\"c\\\", \\\"c\\\", \\\"c\\\"]) \u2192 {\\\"c\\\": 0}\", word0({\"c\", \"c\", \"c\", \"c\"}), {\"c\": 0} );\n", "printTest( \"word0([]) \u2192 {}\", word0({}), {} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Map-2 > wordLen"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of strings, return a Map<String, Integer> containing a key for\n", "every different string in the array, and the value is that string\u02bcs length.\n", "\n", "wordLen([\"a\", \"bb\", \"a\", \"bb\"]) \u2192 {\"bb\": 2, \"a\": 1}\n", "wordLen([\"this\", \"and\", \"that\", \"and\"]) \u2192 {\"that\": 4, \"and\": 3, \"this\": 4}\n", "wordLen([\"code\", \"code\", \"code\", \"bug\"]) \u2192 {\"code\": 4, \"bug\": 3}\n", "*/\n", "\n", "Map<string, int> wordLen(vector<string> strings) {\n", "    return null;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"wordLen([\\\"a\\\", \\\"bb\\\", \\\"a\\\", \\\"bb\\\"]) \u2192 {\\\"bb\\\": 2, \\\"a\\\": 1}\", wordLen({\"a\", \"bb\", \"a\", \"bb\"}), {\"bb\": 2, \"a\": 1} );\n", "printTest( \"wordLen([\\\"this\\\", \\\"and\\\", \\\"that\\\", \\\"and\\\"]) \u2192 {\\\"that\\\": 4, \\\"and\\\": 3, \\\"this\\\": 4}\", wordLen({\"this\", \"and\", \"that\", \"and\"}), {\"that\": 4, \"and\": 3, \"this\": 4} );\n", "printTest( \"wordLen([\\\"code\\\", \\\"code\\\", \\\"code\\\", \\\"bug\\\"]) \u2192 {\\\"code\\\": 4, \\\"bug\\\": 3}\", wordLen({\"code\", \"code\", \"code\", \"bug\"}), {\"code\": 4, \"bug\": 3} );\n", "printTest( \"wordLen([]) \u2192 {}\", wordLen({}), {} );\n", "printTest( \"wordLen([\\\"z\\\"]) \u2192 {\\\"z\\\": 1}\", wordLen({\"z\"}), {\"z\": 1} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Map-2 > pairs"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of non-empty strings, create and return a Map<String, String> as\n", "follows: for each string add its first character as a key with its last\n", "character as the value.\n", "\n", "pairs([\"code\", \"bug\"]) \u2192 {\"b\": \"g\", \"c\": \"e\"}\n", "pairs([\"man\", \"moon\", \"main\"]) \u2192 {\"m\": \"n\"}\n", "pairs([\"man\", \"moon\", \"good\", \"night\"]) \u2192 {\"g\": \"d\", \"m\": \"n\", \"n\": \"t\"}\n", "*/\n", "\n", "Map<string, string> pairs(vector<string> strings) {\n", "    return null;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"pairs([\\\"code\\\", \\\"bug\\\"]) \u2192 {\\\"b\\\": \\\"g\\\", \\\"c\\\": \\\"e\\\"}\", pairs({\"code\", \"bug\"}), {\"b\": \"g\", \"c\": \"e\"} );\n", "printTest( \"pairs([\\\"man\\\", \\\"moon\\\", \\\"main\\\"]) \u2192 {\\\"m\\\": \\\"n\\\"}\", pairs({\"man\", \"moon\", \"main\"}), {\"m\": \"n\"} );\n", "printTest( \"pairs([\\\"man\\\", \\\"moon\\\", \\\"good\\\", \\\"night\\\"]) \u2192 {\\\"g\\\": \\\"d\\\", \\\"m\\\": \\\"n\\\", \\\"n\\\": \\\"t\\\"}\", pairs({\"man\", \"moon\", \"good\", \"night\"}), {\"g\": \"d\", \"m\": \"n\", \"n\": \"t\"} );\n", "printTest( \"pairs([]) \u2192 {}\", pairs({}), {} );\n", "printTest( \"pairs([\\\"a\\\", \\\"b\\\"]) \u2192 {\\\"a\\\": \\\"a\\\", \\\"b\\\": \\\"b\\\"}\", pairs({\"a\", \"b\"}), {\"a\": \"a\", \"b\": \"b\"} );\n", "printTest( \"pairs([\\\"are\\\", \\\"codes\\\", \\\"and\\\", \\\"cods\\\"]) \u2192 {\\\"a\\\": \\\"d\\\", \\\"c\\\": \\\"s\\\"}\", pairs({\"are\", \"codes\", \"and\", \"cods\"}), {\"a\": \"d\", \"c\": \"s\"} );\n", "printTest( \"pairs([\\\"apple\\\", \\\"banana\\\", \\\"tea\\\", \\\"coffee\\\"]) \u2192 {\\\"a\\\": \\\"e\\\", \\\"b\\\": \\\"a\\\", \\\"c\\\": \\\"e\\\", \\\"t\\\": \\\"a\\\"}\", pairs({\"apple\", \"banana\", \"tea\", \"coffee\"}), {\"a\": \"e\", \"b\": \"a\", \"c\": \"e\", \"t\": \"a\"} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Map-2 > wordCount"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "The classic word-count algorithm: given an array of strings, return a\n", "Map<String, Integer> with a key for each different string, with the value the\n", "number of times that string appears in the array.\n", "\n", "wordCount([\"a\", \"b\", \"a\", \"c\", \"b\"]) \u2192 {\"a\": 2, \"b\": 2, \"c\": 1}\n", "wordCount([\"c\", \"b\", \"a\"]) \u2192 {\"a\": 1, \"b\": 1, \"c\": 1}\n", "wordCount([\"c\", \"c\", \"c\", \"c\"]) \u2192 {\"c\": 4}\n", "*/\n", "\n", "Map<string, int> wordCount(vector<string> strings) {\n", "    return null;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"wordCount([\\\"a\\\", \\\"b\\\", \\\"a\\\", \\\"c\\\", \\\"b\\\"]) \u2192 {\\\"a\\\": 2, \\\"b\\\": 2, \\\"c\\\": 1}\", wordCount({\"a\", \"b\", \"a\", \"c\", \"b\"}), {\"a\": 2, \"b\": 2, \"c\": 1} );\n", "printTest( \"wordCount([\\\"c\\\", \\\"b\\\", \\\"a\\\"]) \u2192 {\\\"a\\\": 1, \\\"b\\\": 1, \\\"c\\\": 1}\", wordCount({\"c\", \"b\", \"a\"}), {\"a\": 1, \"b\": 1, \"c\": 1} );\n", "printTest( \"wordCount([\\\"c\\\", \\\"c\\\", \\\"c\\\", \\\"c\\\"]) \u2192 {\\\"c\\\": 4}\", wordCount({\"c\", \"c\", \"c\", \"c\"}), {\"c\": 4} );\n", "printTest( \"wordCount([]) \u2192 {}\", wordCount({}), {} );\n", "printTest( \"wordCount([\\\"this\\\", \\\"and\\\", \\\"this\\\", \\\"\\\"]) \u2192 {\\\"\\\": 1, \\\"and\\\": 1, \\\"this\\\": 2}\", wordCount({\"this\", \"and\", \"this\", \"\"}), {\"\": 1, \"and\": 1, \"this\": 2} );\n", "printTest( \"wordCount([\\\"x\\\", \\\"y\\\", \\\"x\\\", \\\"Y\\\", \\\"X\\\"]) \u2192 {\\\"x\\\": 2, \\\"X\\\": 1, \\\"y\\\": 1, \\\"Y\\\": 1}\", wordCount({\"x\", \"y\", \"x\", \"Y\", \"X\"}), {\"x\": 2, \"X\": 1, \"y\": 1, \"Y\": 1} );\n", "printTest( \"wordCount([\\\"123\\\", \\\"0\\\", \\\"123\\\", \\\"1\\\"]) \u2192 {\\\"0\\\": 1, \\\"1\\\": 1, \\\"123\\\": 2}\", wordCount({\"123\", \"0\", \"123\", \"1\"}), {\"0\": 1, \"1\": 1, \"123\": 2} );\n", "printTest( \"wordCount([\\\"d\\\", \\\"a\\\", \\\"e\\\", \\\"d\\\", \\\"a\\\", \\\"d\\\", \\\"b\\\", \\\"b\\\", \\\"z\\\", \\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"z\\\", \\\"x\\\", \\\"b\\\", \\\"f\\\", \\\"x\\\", \\\"two\\\", \\\"b\\\", \\\"one\\\", \\\"two\\\"]) \u2192 {\\\"a\\\": 4, \\\"b\\\": 5, \\\"d\\\": 3, \\\"e\\\": 1, \\\"f\\\": 1, \\\"one\\\": 1, \\\"x\\\": 2, \\\"z\\\": 2, \\\"two\\\": 2}\", wordCount({\"d\", \"a\", \"e\", \"d\", \"a\", \"d\", \"b\", \"b\", \"z\", \"a\", \"a\", \"b\", \"z\", \"x\", \"b\", \"f\", \"x\", \"two\", \"b\", \"one\", \"two\"}), {\"a\": 4, \"b\": 5, \"d\": 3, \"e\": 1, \"f\": 1, \"one\": 1, \"x\": 2, \"z\": 2, \"two\": 2} );\n", "printTest( \"wordCount([\\\"apple\\\", \\\"banana\\\", \\\"apple\\\", \\\"apple\\\", \\\"tea\\\", \\\"coffee\\\", \\\"banana\\\"]) \u2192 {\\\"banana\\\": 2, \\\"apple\\\": 3, \\\"tea\\\": 1, \\\"coffee\\\": 1}\", wordCount({\"apple\", \"banana\", \"apple\", \"apple\", \"tea\", \"coffee\", \"banana\"}), {\"banana\": 2, \"apple\": 3, \"tea\": 1, \"coffee\": 1} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Map-2 > firstChar"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of non-empty strings, return a Map<String, String> with a key for\n", "every different first character seen, with the value of all the strings starting\n", "with that character appended together in the order they appear in the array.\n", "\n", "firstChar([\"salt\", \"tea\", \"soda\", \"toast\"]) \u2192 {\"s\": \"saltsoda\", \"t\": \"teatoast\"}\n", "firstChar([\"aa\", \"bb\", \"cc\", \"aAA\", \"cCC\", \"d\"]) \u2192 {\"a\": \"aaaAA\", \"b\": \"bb\",\n", "\"c\": \"cccCC\", \"d\": \"d\"}\n", "firstChar([]) \u2192 {}\n", "*/\n", "\n", "Map<string, string> firstChar(vector<string> strings) {\n", "    return null;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"firstChar([\\\"salt\\\", \\\"tea\\\", \\\"soda\\\", \\\"toast\\\"]) \u2192 {\\\"s\\\": \\\"saltsoda\\\", \\\"t\\\": \\\"teatoast\\\"}\", firstChar({\"salt\", \"tea\", \"soda\", \"toast\"}), {\"s\": \"saltsoda\", \"t\": \"teatoast\"} );\n", "printTest( \"firstChar([\\\"aa\\\", \\\"bb\\\", \\\"cc\\\", \\\"aAA\\\", \\\"cCC\\\", \\\"d\\\"]) \u2192 {\\\"a\\\": \\\"aaaAA\\\", \\\"b\\\": \\\"bb\\\", \\\"c\\\": \\\"cccCC\\\", \\\"d\\\": \\\"d\\\"}\", firstChar({\"aa\", \"bb\", \"cc\", \"aAA\", \"cCC\", \"d\"}), {\"a\": \"aaaAA\", \"b\": \"bb\", \"c\": \"cccCC\", \"d\": \"d\"} );\n", "printTest( \"firstChar([]) \u2192 {}\", firstChar({}), {} );\n", "printTest( \"firstChar([\\\"apple\\\", \\\"bells\\\", \\\"salt\\\", \\\"aardvark\\\", \\\"bells\\\", \\\"sun\\\", \\\"zen\\\", \\\"bells\\\"]) \u2192 {\\\"a\\\": \\\"appleaardvark\\\", \\\"b\\\": \\\"bellsbellsbells\\\", \\\"s\\\": \\\"saltsun\\\", \\\"z\\\": \\\"zen\\\"}\", firstChar({\"apple\", \"bells\", \"salt\", \"aardvark\", \"bells\", \"sun\", \"zen\", \"bells\"}), {\"a\": \"appleaardvark\", \"b\": \"bellsbellsbells\", \"s\": \"saltsun\", \"z\": \"zen\"} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Map-2 > wordAppend"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Loop over the given array of strings to build a result string like this: when a\n", "string appears the 2nd, 4th, 6th, etc. time in the array, append the string to\n", "the result. Return the empty string if no string appears a 2nd time.\n", "\n", "wordAppend([\"a\", \"b\", \"a\"]) \u2192 \"a\"\n", "wordAppend([\"a\", \"b\", \"a\", \"c\", \"a\", \"d\", \"a\"]) \u2192 \"aa\"\n", "wordAppend([\"a\", \"\", \"a\"]) \u2192 \"a\"\n", "*/\n", "\n", "string wordAppend(vector<string> strings) {\n", "    return \"\";\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"wordAppend([\\\"a\\\", \\\"b\\\", \\\"a\\\"]) \u2192 \\\"a\\\"\", wordAppend({\"a\", \"b\", \"a\"}), \"a\" );\n", "printTest( \"wordAppend([\\\"a\\\", \\\"b\\\", \\\"a\\\", \\\"c\\\", \\\"a\\\", \\\"d\\\", \\\"a\\\"]) \u2192 \\\"aa\\\"\", wordAppend({\"a\", \"b\", \"a\", \"c\", \"a\", \"d\", \"a\"}), \"aa\" );\n", "printTest( \"wordAppend([\\\"a\\\", \\\"\\\", \\\"a\\\"]) \u2192 \\\"a\\\"\", wordAppend({\"a\", \"\", \"a\"}), \"a\" );\n", "printTest( \"wordAppend([]) \u2192 \\\"\\\"\", wordAppend({}), \"\" );\n", "printTest( \"wordAppend([\\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"a\\\", \\\"a\\\"]) \u2192 \\\"ba\\\"\", wordAppend({\"a\", \"b\", \"b\", \"a\", \"a\"}), \"ba\" );\n", "printTest( \"wordAppend([\\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"b\\\", \\\"a\\\", \\\"c\\\", \\\"a\\\", \\\"a\\\"]) \u2192 \\\"baa\\\"\", wordAppend({\"a\", \"b\", \"b\", \"b\", \"a\", \"c\", \"a\", \"a\"}), \"baa\" );\n", "printTest( \"wordAppend([\\\"a\\\", \\\"b\\\", \\\"b\\\", \\\"b\\\", \\\"a\\\", \\\"c\\\", \\\"a\\\", \\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"a\\\"]) \u2192 \\\"baaba\\\"\", wordAppend({\"a\", \"b\", \"b\", \"b\", \"a\", \"c\", \"a\", \"a\", \"a\", \"b\", \"a\"}), \"baaba\" );\n", "printTest( \"wordAppend([\\\"not\\\", \\\"and\\\", \\\"or\\\", \\\"and\\\", \\\"this\\\", \\\"and\\\", \\\"or\\\", \\\"that\\\", \\\"not\\\"]) \u2192 \\\"andornot\\\"\", wordAppend({\"not\", \"and\", \"or\", \"and\", \"this\", \"and\", \"or\", \"that\", \"not\"}), \"andornot\" );\n", "printTest( \"wordAppend([\\\"a\\\", \\\"b\\\", \\\"c\\\"]) \u2192 \\\"\\\"\", wordAppend({\"a\", \"b\", \"c\"}), \"\" );\n", "printTest( \"wordAppend([\\\"this\\\", \\\"or\\\", \\\"that\\\", \\\"and\\\", \\\"this\\\", \\\"and\\\", \\\"that\\\"]) \u2192 \\\"thisandthat\\\"\", wordAppend({\"this\", \"or\", \"that\", \"and\", \"this\", \"and\", \"that\"}), \"thisandthat\" );\n", "printTest( \"wordAppend([\\\"xx\\\", \\\"xx\\\", \\\"yy\\\", \\\"xx\\\", \\\"zz\\\", \\\"yy\\\", \\\"zz\\\", \\\"xx\\\"]) \u2192 \\\"xxyyzzxx\\\"\", wordAppend({\"xx\", \"xx\", \"yy\", \"xx\", \"zz\", \"yy\", \"zz\", \"xx\"}), \"xxyyzzxx\" );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Map-2 > wordMultiple"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "Given an array of strings, return a Map<String, Boolean> where each different\n", "string is a key and its value is true if that string appears 2 or more times in\n", "the array.\n", "\n", "wordMultiple([\"a\", \"b\", \"a\", \"c\", \"b\"]) \u2192 {\"a\": true, \"b\": true, \"c\": false}\n", "wordMultiple([\"c\", \"b\", \"a\"]) \u2192 {\"a\": false, \"b\": false, \"c\": false}\n", "wordMultiple([\"c\", \"c\", \"c\", \"c\"]) \u2192 {\"c\": true}\n", "*/\n", "\n", "Map<string, Boolean> wordMultiple(vector<string> strings) {\n", "    return null;\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"wordMultiple([\\\"a\\\", \\\"b\\\", \\\"a\\\", \\\"c\\\", \\\"b\\\"]) \u2192 {\\\"a\\\": true, \\\"b\\\": true, \\\"c\\\": false}\", wordMultiple({\"a\", \"b\", \"a\", \"c\", \"b\"}), {\"a\": true, \"b\": true, \"c\": false} );\n", "printTest( \"wordMultiple([\\\"c\\\", \\\"b\\\", \\\"a\\\"]) \u2192 {\\\"a\\\": false, \\\"b\\\": false, \\\"c\\\": false}\", wordMultiple({\"c\", \"b\", \"a\"}), {\"a\": false, \"b\": false, \"c\": false} );\n", "printTest( \"wordMultiple([\\\"c\\\", \\\"c\\\", \\\"c\\\", \\\"c\\\"]) \u2192 {\\\"c\\\": true}\", wordMultiple({\"c\", \"c\", \"c\", \"c\"}), {\"c\": true} );\n", "printTest( \"wordMultiple([]) \u2192 {}\", wordMultiple({}), {} );\n", "printTest( \"wordMultiple([\\\"this\\\", \\\"and\\\", \\\"this\\\"]) \u2192 {\\\"and\\\": false, \\\"this\\\": true}\", wordMultiple({\"this\", \"and\", \"this\"}), {\"and\": false, \"this\": true} );\n", "printTest( \"wordMultiple([\\\"d\\\", \\\"a\\\", \\\"e\\\", \\\"d\\\", \\\"a\\\", \\\"d\\\", \\\"b\\\", \\\"b\\\", \\\"z\\\", \\\"a\\\", \\\"a\\\", \\\"b\\\", \\\"z\\\", \\\"x\\\"]) \u2192 {\\\"a\\\": true, \\\"b\\\": true, \\\"d\\\": true, \\\"e\\\": false, \\\"x\\\": false, \\\"z\\\": true}\", wordMultiple({\"d\", \"a\", \"e\", \"d\", \"a\", \"d\", \"b\", \"b\", \"z\", \"a\", \"a\", \"b\", \"z\", \"x\"}), {\"a\": true, \"b\": true, \"d\": true, \"e\": false, \"x\": false, \"z\": true} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Map-2 > allSwap"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "We\u02bcll say that 2 strings \"match\" if they are non-empty and their first chars are\n", "the same. Loop over and then return the given array of non-empty strings as\n", "follows: if a string matches an earlier string in the array, swap the 2 strings\n", "in the array. When a position in the array has been swapped, it no longer\n", "matches anything. Using a map, this can be solved making just one pass over the\n", "array. More difficult than it looks.\n", "\n", "allSwap([\"ab\", \"ac\"]) \u2192 [\"ac\", \"ab\"]\n", "allSwap([\"ax\", \"bx\", \"cx\", \"cy\", \"by\", \"ay\", \"aaa\", \"azz\"]) \u2192 [\"ay\", \"by\", \"cy\",\n", "\"cx\", \"bx\", \"ax\", \"azz\", \"aaa\"]\n", "allSwap([\"ax\", \"bx\", \"ay\", \"by\", \"ai\", \"aj\", \"bx\", \"by\"]) \u2192 [\"ay\", \"by\", \"ax\",\n", "\"bx\", \"aj\", \"ai\", \"by\", \"bx\"]\n", "*/\n", "\n", "std::vector<string> allSwap(vector<string> strings) {\n", "    return new vector<string>{};\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"allSwap([\\\"ab\\\", \\\"ac\\\"]) \u2192 [\\\"ac\\\", \\\"ab\\\"]\", allSwap({\"ab\", \"ac\"}), {\"ac\", \"ab\"} );\n", "printTest( \"allSwap([\\\"ax\\\", \\\"bx\\\", \\\"cx\\\", \\\"cy\\\", \\\"by\\\", \\\"ay\\\", \\\"aaa\\\", \\\"azz\\\"]) \u2192 [\\\"ay\\\", \\\"by\\\", \\\"cy\\\", \\\"cx\\\", \\\"bx\\\", \\\"ax\\\", \\\"azz\\\", \\\"aaa\\\"]\", allSwap({\"ax\", \"bx\", \"cx\", \"cy\", \"by\", \"ay\", \"aaa\", \"azz\"}), {\"ay\", \"by\", \"cy\", \"cx\", \"bx\", \"ax\", \"azz\", \"aaa\"} );\n", "printTest( \"allSwap([\\\"ax\\\", \\\"bx\\\", \\\"ay\\\", \\\"by\\\", \\\"ai\\\", \\\"aj\\\", \\\"bx\\\", \\\"by\\\"]) \u2192 [\\\"ay\\\", \\\"by\\\", \\\"ax\\\", \\\"bx\\\", \\\"aj\\\", \\\"ai\\\", \\\"by\\\", \\\"bx\\\"]\", allSwap({\"ax\", \"bx\", \"ay\", \"by\", \"ai\", \"aj\", \"bx\", \"by\"}), {\"ay\", \"by\", \"ax\", \"bx\", \"aj\", \"ai\", \"by\", \"bx\"} );\n", "printTest( \"allSwap([\\\"ax\\\", \\\"bx\\\", \\\"cx\\\", \\\"ay\\\", \\\"cy\\\", \\\"aaa\\\", \\\"abb\\\"]) \u2192 [\\\"ay\\\", \\\"bx\\\", \\\"cy\\\", \\\"ax\\\", \\\"cx\\\", \\\"abb\\\", \\\"aaa\\\"]\", allSwap({\"ax\", \"bx\", \"cx\", \"ay\", \"cy\", \"aaa\", \"abb\"}), {\"ay\", \"bx\", \"cy\", \"ax\", \"cx\", \"abb\", \"aaa\"} );\n", "printTest( \"allSwap([\\\"easy\\\", \\\"does\\\", \\\"it\\\", \\\"every\\\", \\\"ice\\\", \\\"eaten\\\"]) \u2192 [\\\"every\\\", \\\"does\\\", \\\"ice\\\", \\\"easy\\\", \\\"it\\\", \\\"eaten\\\"]\", allSwap({\"easy\", \"does\", \"it\", \"every\", \"ice\", \"eaten\"}), {\"every\", \"does\", \"ice\", \"easy\", \"it\", \"eaten\"} );\n", "printTest( \"allSwap([\\\"list\\\", \\\"of\\\", \\\"words\\\", \\\"swims\\\", \\\"over\\\", \\\"lily\\\", \\\"water\\\", \\\"wait\\\"]) \u2192 [\\\"lily\\\", \\\"over\\\", \\\"water\\\", \\\"swims\\\", \\\"of\\\", \\\"list\\\", \\\"words\\\", \\\"wait\\\"]\", allSwap({\"list\", \"of\", \"words\", \"swims\", \"over\", \"lily\", \"water\", \"wait\"}), {\"lily\", \"over\", \"water\", \"swims\", \"of\", \"list\", \"words\", \"wait\"} );\n", "printTest( \"allSwap([\\\"4\\\", \\\"8\\\", \\\"15\\\", \\\"16\\\", \\\"23\\\", \\\"42\\\"]) \u2192 [\\\"42\\\", \\\"8\\\", \\\"16\\\", \\\"15\\\", \\\"23\\\", \\\"4\\\"]\", allSwap({\"4\", \"8\", \"15\", \"16\", \"23\", \"42\"}), {\"42\", \"8\", \"16\", \"15\", \"23\", \"4\"} );\n", "printTest( \"allSwap([\\\"aaa\\\"]) \u2192 [\\\"aaa\\\"]\", allSwap({\"aaa\"}), {\"aaa\"} );\n", "printTest( \"allSwap([]) \u2192 []\", allSwap({}), {} );\n", "printTest( \"allSwap([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"xx\\\", \\\"yy\\\", \\\"zz\\\"]) \u2192 [\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"xx\\\", \\\"yy\\\", \\\"zz\\\"]\", allSwap({\"a\", \"b\", \"c\", \"xx\", \"yy\", \"zz\"}), {\"a\", \"b\", \"c\", \"xx\", \"yy\", \"zz\"} );"]},
{"cell_type": "markdown", "metadata": {}, "source": ["# Map-2 > firstSwap"]},
{"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["/*\n", "We\u02bcll say that 2 strings \"match\" if they are non-empty and their first chars are\n", "the same. Loop over and then return the given array of non-empty strings as\n", "follows: if a string matches an earlier string in the array, swap the 2 strings\n", "in the array. A particular first char can only cause 1 swap, so once a char has\n", "caused a swap, its later swaps are disabled. Using a map, this can be solved\n", "making just one pass over the array. More difficult than it looks.\n", "\n", "firstSwap([\"ab\", \"ac\"]) \u2192 [\"ac\", \"ab\"]\n", "firstSwap([\"ax\", \"bx\", \"cx\", \"cy\", \"by\", \"ay\", \"aaa\", \"azz\"]) \u2192 [\"ay\", \"by\",\n", "\"cy\", \"cx\", \"bx\", \"ax\", \"aaa\", \"azz\"]\n", "firstSwap([\"ax\", \"bx\", \"ay\", \"by\", \"ai\", \"aj\", \"bx\", \"by\"]) \u2192 [\"ay\", \"by\", \"ax\",\n", "\"bx\", \"ai\", \"aj\", \"bx\", \"by\"]\n", "*/\n", "\n", "std::vector<string> firstSwap(vector<string> strings) {\n", "    return new vector<string>{};\n", "}\n", "\n", "\n", "// tests:\n", "printTest( \"firstSwap([\\\"ab\\\", \\\"ac\\\"]) \u2192 [\\\"ac\\\", \\\"ab\\\"]\", firstSwap({\"ab\", \"ac\"}), {\"ac\", \"ab\"} );\n", "printTest( \"firstSwap([\\\"ax\\\", \\\"bx\\\", \\\"cx\\\", \\\"cy\\\", \\\"by\\\", \\\"ay\\\", \\\"aaa\\\", \\\"azz\\\"]) \u2192 [\\\"ay\\\", \\\"by\\\", \\\"cy\\\", \\\"cx\\\", \\\"bx\\\", \\\"ax\\\", \\\"aaa\\\", \\\"azz\\\"]\", firstSwap({\"ax\", \"bx\", \"cx\", \"cy\", \"by\", \"ay\", \"aaa\", \"azz\"}), {\"ay\", \"by\", \"cy\", \"cx\", \"bx\", \"ax\", \"aaa\", \"azz\"} );\n", "printTest( \"firstSwap([\\\"ax\\\", \\\"bx\\\", \\\"ay\\\", \\\"by\\\", \\\"ai\\\", \\\"aj\\\", \\\"bx\\\", \\\"by\\\"]) \u2192 [\\\"ay\\\", \\\"by\\\", \\\"ax\\\", \\\"bx\\\", \\\"ai\\\", \\\"aj\\\", \\\"bx\\\", \\\"by\\\"]\", firstSwap({\"ax\", \"bx\", \"ay\", \"by\", \"ai\", \"aj\", \"bx\", \"by\"}), {\"ay\", \"by\", \"ax\", \"bx\", \"ai\", \"aj\", \"bx\", \"by\"} );\n", "printTest( \"firstSwap([\\\"ax\\\", \\\"bx\\\", \\\"cx\\\", \\\"ay\\\", \\\"cy\\\", \\\"aaa\\\", \\\"abb\\\"]) \u2192 [\\\"ay\\\", \\\"bx\\\", \\\"cy\\\", \\\"ax\\\", \\\"cx\\\", \\\"aaa\\\", \\\"abb\\\"]\", firstSwap({\"ax\", \"bx\", \"cx\", \"ay\", \"cy\", \"aaa\", \"abb\"}), {\"ay\", \"bx\", \"cy\", \"ax\", \"cx\", \"aaa\", \"abb\"} );\n", "printTest( \"firstSwap([\\\"easy\\\", \\\"does\\\", \\\"it\\\", \\\"every\\\", \\\"ice\\\", \\\"eaten\\\"]) \u2192 [\\\"every\\\", \\\"does\\\", \\\"ice\\\", \\\"easy\\\", \\\"it\\\", \\\"eaten\\\"]\", firstSwap({\"easy\", \"does\", \"it\", \"every\", \"ice\", \"eaten\"}), {\"every\", \"does\", \"ice\", \"easy\", \"it\", \"eaten\"} );\n", "printTest( \"firstSwap([\\\"list\\\", \\\"of\\\", \\\"words\\\", \\\"swims\\\", \\\"over\\\", \\\"lily\\\", \\\"water\\\", \\\"wait\\\"]) \u2192 [\\\"lily\\\", \\\"over\\\", \\\"water\\\", \\\"swims\\\", \\\"of\\\", \\\"list\\\", \\\"words\\\", \\\"wait\\\"]\", firstSwap({\"list\", \"of\", \"words\", \"swims\", \"over\", \"lily\", \"water\", \"wait\"}), {\"lily\", \"over\", \"water\", \"swims\", \"of\", \"list\", \"words\", \"wait\"} );\n", "printTest( \"firstSwap([\\\"4\\\", \\\"8\\\", \\\"15\\\", \\\"16\\\", \\\"23\\\", \\\"42\\\"]) \u2192 [\\\"42\\\", \\\"8\\\", \\\"16\\\", \\\"15\\\", \\\"23\\\", \\\"4\\\"]\", firstSwap({\"4\", \"8\", \"15\", \"16\", \"23\", \"42\"}), {\"42\", \"8\", \"16\", \"15\", \"23\", \"4\"} );\n", "printTest( \"firstSwap([\\\"aaa\\\"]) \u2192 [\\\"aaa\\\"]\", firstSwap({\"aaa\"}), {\"aaa\"} );\n", "printTest( \"firstSwap([]) \u2192 []\", firstSwap({}), {} );\n", "printTest( \"firstSwap([\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"xx\\\", \\\"yy\\\", \\\"zz\\\"]) \u2192 [\\\"a\\\", \\\"b\\\", \\\"c\\\", \\\"xx\\\", \\\"yy\\\", \\\"zz\\\"]\", firstSwap({\"a\", \"b\", \"c\", \"xx\", \"yy\", \"zz\"}), {\"a\", \"b\", \"c\", \"xx\", \"yy\", \"zz\"} );"]}
 ],
 "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
}