{"id":141,"date":"2014-08-12T12:56:50","date_gmt":"2014-08-12T19:56:50","guid":{"rendered":"http:\/\/willclausen.com\/?p=141"},"modified":"2014-08-12T12:56:50","modified_gmt":"2014-08-12T19:56:50","slug":"programming-praxis-feb-15-2011","status":"publish","type":"post","link":"http:\/\/willclausen.com\/?p=141","title":{"rendered":"Programming Praxis: Feb 15, 2011"},"content":{"rendered":"<p>Below is my solution to the Programming Praxis problem from Feb. 15, 2011. The problem came from Google Code Jam Qualification Round Africa 2010. For more info, check <a href=\"http:\/\/programmingpraxis.com\/2011\/02\/15\/google-code-jam-qualification-round-africa-2010\/\">this link<\/a>.<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\r\n\/\/ Author: William Clausen\r\n\/\/ Date: Aug. 11, 2014\r\n\/\/ Descpription: This file solves the programming praxis problem from\r\n\/\/ Feb. 15, 2011\r\n\r\n#include &lt;vector&gt;\r\n#include &lt;iostream&gt;\r\n#include &lt;unordered_map&gt;\r\n\r\nusing namespace std;\r\n\r\n\/\/ Problem 1: Given a target number, C, determine if a set of +integers contains\r\n\/\/ two integers that sum to the target.\r\n\r\n\/\/ This function returns two positive integers representing the indices of the\r\n\/\/ integers in the set whose sum is the target\r\nvector&lt;int&gt; storeCredit(int credit, vector&lt;int&gt; itemPrices) {\r\n\t\/\/ Create result array to return. Populate it with -1's to represent\r\n\t\/\/ failed state\r\n\tvector&lt;int&gt; result (2, -1);\r\n\r\n\t\/\/ Loop through the items to determine if a solution exists.\r\n\tfor (int i = 0; i &lt; itemPrices.size(); ++i) {\r\n\t\tfor (int j = i+1; j &lt; itemPrices.size(); ++j) {\r\n\t\t\tif (itemPrices&#x5B;i] + itemPrices&#x5B;j] == credit) {\r\n\t\t\t\tresult&#x5B;0] = i+1;\r\n\t\t\t\tresult&#x5B;1] = j+1;\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\r\n\treturn result;\r\n}\r\n\r\n\/\/ Problem 2: Given a list of separated words, reverse the order of the words.\r\n\r\nstring reverseWordList(string message) {\r\n\t\/\/ It will be helpful to split the message into strings representing\r\n\t\/\/ words\r\n\tstring result;\r\n\tstring copy(message);\r\n\tint wordEnd = message.length() - 1;\r\n\r\n\t\/\/ Loop through the list looking for spaces denoting breaks between words.\r\n\twhile (copy.find_last_of(' ') != string::npos) {\r\n\t\tint wordStart = copy.find_last_of(' ') + 1;\r\n\t\tresult.append(copy.substr(wordStart, wordEnd));\r\n\t\tresult.push_back(' ');\r\n\t\twordEnd = wordStart - 1;\r\n\t\tcopy = copy.substr(0, wordEnd);\r\n\t\t--wordEnd;\r\n\t}\r\n\r\n\t\/\/ We left the first word because there are no spaces after it, so\r\n\t\/\/ add the first word to the end of the result string.\r\n\tresult.append(copy);\r\n\r\n\treturn result;\r\n}\r\n\r\n\/\/ Problem 3: Write a function that takes in a string message and outputs the\r\n\/\/ appropriate T9 keypresses for that message\r\n\r\n\/\/ For simplicity, typedef the map type\r\ntypedef unordered_map&lt;char, int&gt; letterMap;\r\n\r\nbool sameButton(int first, int second) {\r\n\t\/\/ Break down the numbers to a single digit, then compare the digits\r\n\twhile (first &gt; 10) {\r\n\t\tfirst \/= 10;\r\n\t}\r\n\r\n\twhile (second &gt; 10) {\r\n\t\tsecond \/= 10;\r\n\t}\r\n\r\n\treturn first == second;\r\n}\r\n\r\nvector&lt;int&gt; t9Converter(string message) {\r\n\tvector&lt;int&gt; result;\r\n\r\n\t\/\/ Just some input checking to start\r\n\tif (message.length() == 0) {\r\n\t\treturn result;\r\n\t}\r\n\t\/\/ First, we need an unordered map for the mapping of numbers to letters\r\n\t\/\/ according to T9 standards.\r\n\tletterMap map ( {{'a', 2}, {'b', 22}, {'c', 222},\r\n\t\t            {'d', 3}, {'e', 33}, {'f', 333},\r\n\t\t            {'g', 4}, {'h', 44}, {'i', 444},\r\n\t\t            {'j', 5}, {'k', 55}, {'l', 555},\r\n\t\t            {'m', 6}, {'n', 66}, {'o', 666},\r\n\t\t            {'p', 7}, {'q', 77}, {'r', 777}, {'s', 7777},\r\n\t\t            {'t', 8}, {'u', 88}, {'v', 888},\r\n\t\t            {'w', 9}, {'x', 99}, {'y', 999}, {'z', 9999},\r\n\t\t            {' ', 0}} );\r\n\r\n\t\/\/ So that we don't have to call empty all the time...\r\n\tresult.push_back(map&#x5B;message&#x5B;0]]);\r\n\r\n\tfor (int i = 1; i &lt; message.length(); ++i) {\r\n\t\tint nextNum = map&#x5B;message&#x5B;i]];\r\n\r\n\t\tif (sameButton(result&#x5B;i-1], nextNum) &amp;&amp; nextNum != 0) {\r\n\t\t\t\/\/ Add a space, denoted by a -1\r\n\t\t\tresult.push_back(-1);\r\n\t\t}\r\n\r\n\t\tresult.push_back(nextNum);\r\n\t}\r\n\r\n\treturn result;\r\n}\r\n\r\n<\/pre>\n<p>And here are some tests I did to make sure everything worked properly.<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\r\n\/\/ Test the solutions\r\n\r\n\/\/ Test problem 1\r\nvoid testProblem1() {\r\n\t\/\/ First example\r\n\tint credit = 100;\r\n\tvector&lt;int&gt; itemPrices = {5, 75, 25};\r\n\r\n\tvector&lt;int&gt; answer = storeCredit(credit, itemPrices);\r\n\r\n\tcerr &lt;&lt; &quot;Answer for first test case for store credit problem: &quot;;\r\n\tcout &lt;&lt; answer&#x5B;0] &lt;&lt; &quot;,&quot; &lt;&lt; answer&#x5B;1];\r\n\tcout &lt;&lt; &quot;\\n&quot;;\r\n\r\n\t\/\/ Second example\r\n\tcredit = 200;\r\n\titemPrices = {150, 24, 79, 50, 88, 345, 3};\r\n\r\n\tanswer = storeCredit(credit, itemPrices);\r\n\r\n\tcout &lt;&lt; &quot;Answer for second test case for store credit problem: &quot;;\r\n\tcout &lt;&lt; answer&#x5B;0] &lt;&lt; &quot;,&quot; &lt;&lt; answer&#x5B;1];\r\n\tcout &lt;&lt; &quot;\\n&quot;;\r\n\r\n\t\/\/ Third example\r\n\tcredit = 8;\r\n\titemPrices = {2, 1, 9, 4, 4, 56, 90, 3};\r\n\r\n\tanswer = storeCredit(credit, itemPrices);\r\n\r\n\tcout &lt;&lt; &quot;Answer for third test case for store credit problem: &quot;;\r\n\tcout &lt;&lt; answer&#x5B;0] &lt;&lt; &quot;,&quot; &lt;&lt; answer&#x5B;1];\r\n\tcout &lt;&lt; &quot;\\n&quot;;\r\n}\r\n\r\n\/\/ Test problem 2\r\nvoid testProblem2() {\r\n\tstring input = &quot;this is a test&quot;;\r\n\tstring output = reverseWordList(input);\r\n\r\n\tcout &lt;&lt; &quot;input: &quot; &lt;&lt; input &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;output: &quot; &lt;&lt; output &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;\\n&quot;;\r\n\r\n\tinput = &quot;foobar&quot;;\r\n\toutput = reverseWordList(input);\r\n\r\n\tcout &lt;&lt; &quot;input: &quot; &lt;&lt; input &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;output: &quot; &lt;&lt; output &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;\\n&quot;;\r\n\r\n\tinput = &quot;all your base&quot;;\r\n\toutput = reverseWordList(input);\r\n\r\n\tcout &lt;&lt; &quot;input: &quot; &lt;&lt; input &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;output: &quot; &lt;&lt; output &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;\\n&quot;;\r\n}\r\n\r\n\/\/ Helper function for printing vectors for problem 3\r\nvoid printT9(vector&lt;int&gt; t9Message) {\r\n\tfor (int i = 0; i &lt; t9Message.size(); ++i) {\r\n\t\tif (t9Message&#x5B;i] == -1) {\r\n\t\t\tcout &lt;&lt; &quot; &quot;;\r\n\t\t}\r\n\t\telse {\r\n\t\t\tcout &lt;&lt; t9Message&#x5B;i];\t\t\t\r\n\t\t}\r\n\t}\r\n\tcout &lt;&lt; &quot;\\n&quot;;\r\n}\r\n\r\n\/\/ Test problem 3\r\nvoid testProblem3() {\r\n\tstring input = &quot;hi&quot;;\r\n\tvector&lt;int&gt; t9Message = t9Converter(input);\r\n\r\n\tcout &lt;&lt; &quot;input: &quot; &lt;&lt; input &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;output: &quot;;\r\n\tprintT9(t9Message);\r\n\r\n\tinput = &quot;yes&quot;;\r\n\tt9Message = t9Converter(input);\r\n\r\n\tcout &lt;&lt; &quot;input: &quot; &lt;&lt; input &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;output: &quot;;\r\n\tprintT9(t9Message);\r\n\r\n\tinput = &quot;foo  bar&quot;;\r\n\tt9Message = t9Converter(input);\r\n\r\n\tcout &lt;&lt; &quot;input: &quot; &lt;&lt; input &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;output: &quot;;\r\n\tprintT9(t9Message);\r\n\r\n\tinput = &quot;hello world&quot;;\r\n\tt9Message = t9Converter(input);\r\n\r\n\tcout &lt;&lt; &quot;input: &quot; &lt;&lt; input &lt;&lt; &quot;\\n&quot;;\r\n\tcout &lt;&lt; &quot;output: &quot;;\r\n\tprintT9(t9Message);\r\n}\r\n\r\n\/\/ For testing purposes\r\nint main() {\r\n\ttestProblem1();\r\n\ttestProblem2();\r\n\ttestProblem3();\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Below is my solution to the Programming Praxis problem from Feb. 15, 2011. The problem came from Google Code Jam Qualification Round Africa 2010. For more info, check this link. \/\/ Author: William Clausen \/\/ Date: Aug. 11, 2014 \/\/ Descpription: This file solves the programming praxis problem from \/\/ Feb. 15, 2011 #include &lt;vector&gt; [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[38,11,40,39,41],"class_list":["post-141","post","type-post","status-publish","format-standard","hentry","category-programming-praxis","tag-google-code-jam","tag-programming-praxis-2","tag-reverse-words","tag-store-credit","tag-t9-spelling"],"_links":{"self":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/141","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=141"}],"version-history":[{"count":1,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/141\/revisions"}],"predecessor-version":[{"id":142,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/141\/revisions\/142"}],"wp:attachment":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=141"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=141"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=141"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}