/* ////////////////////////////////////////////////////////////////////////////// * * Template version history * 1.0: intitial version * 1.1: comments changed from // to star slash as QT creator can fold the latter * 1.2: standardized formatting and cleaned up code (including removing test/debug code) * Recursive Functions * * Program contains a number of warmup excercises for Assignment 2 of the 2008 CS106B Stanford subject as well as sample code that may * or may not be implimented within the code below. * * Several functions have been placed in and associated files for "something to do" * * The "meat" of the program is the code for the assessed part of the Assignment: * -12 Steps to Recursive Enlightenment ( not all my own code) * -for Ruler of the World (mostly my own code) * -Every Vote Counts (mostly NOT my code) * -Every Vote Counts * -Recursive Puzzle * -Stock Cutting * * * Paul Yeatman * 20171204 * * Version Notes: * Initial version (v1.0) * v1.1 - change "if else" in main to "switch", sent binary and ruleroftheworld functions to *.h files (the *.h combined with *.cpp seems wonky but the files are in the stanflib dir) * The code is not standardised - some has arrVector, iInt etc while some just has names. * v1.2 - added arr to arrays, i to its, s to string etc. Removed pseudocode and test comments * * /////////////////////////////////////////////////////////////////////////////// */ /* My own libraries (or at the very least, pointers to exported cpp files that are used by main)*/ #include "binary.h" #include "ruleroftheworld.h" /*Stanford Libs*/ #include "console.h" #include "gwindow.h" #include "gobjects.h" #include "simpio.h" #include "strlib.h" #include "filelib.h" #include "vector.h" #include "lexicon.h" //#include "dawglexicon.h" /*Standard C++*/ #include #include #include #include #include using namespace std; /* ////////////////////////////////////////////////////////////////////////////// * * Constants should be declared here * * /////////////////////////////////////////////////////////////////////////////// */ const string LEXICON = "HangmanLexicon.txt"; const string VOTINGBLOCKS = "4blockstest.txt"; // "4blockstest.txt", "testdata.txt"; // "VotingBlocks.txt"; // numbers obtained from https://www.archives.gov/federal-register/electoral-college/allocation.html TotalVotes should be 538 const string sINPUT_DETAILS1 = "Enter...\n\"0\" for Binary calculation, \n\"1\" for Subset Data Entry: "; const string sINPUT_DETAILS2 = "\"2\" for Anagram (permutation) search (!!!NOTE 5 char words and up only!!!): \n\"3\" for Keypad Mnemonics (!!!NOTE - this outputs ALL combinations!!!)\n\"4\" for ACTUAL ASSIGNMENT SOLUTIONS: "; const string sINPUT_DETAILS3 = "Enter...\n\"0\" for 12 Steps to Recursive Enlightenment, \n\"1\" for Ruler of the World: "; const string sINPUT_DETAILS4 = "\"2\" for Every Vote Counts: \n\"3\" for Mobile Phone Mind Reading: \n\"4\" for A Recursive Puzzle: \n\"5\" for Stock Cutting: "; const string sBLANK = ""; const string sBINARY_PROMPT = "Enter base 10 number to convert to binary: "; const string sMOBILE_PREDICTIVE = "Enter a keypad sequence: "; const int iSMALL_STRIDE = 1; const int iLARGE_STRIDE = 2; const int iWINDOW_HEIGHT = 290; const int iWINDOW_WIDTH = 550; const int iLABEL_Y_OFFSET = 15; // offset for program purpose label const int iLABEL_X_OFFSET = 110; // offset for program purpose label const double dLINE_OFFSET = 15; // movedup 2px so we can see the line (for testing) const double dMIN_WIDTH = 3; // when to kill off the DrawRuler recursion const double dMIN_HEIGHT = 10; // when to kill off the DrawRuler recursion // Keypad conversion for MobilePhoneMindReading /* I plan to build array to iterate over aspart of the int to string conversion * Or should we convert the int sequence to text immediately and then do our interation? * alternately, could enter nubmers into an array. each int would correspond to the array of string segments cell ref... */ const string CONVERT_sKEYZERO = "0"; const string CONVERT_sKEYONE = "1"; const string CONVERT_sKEYTWO = "ABC"; const string CONVERT_sKEYTHREE = "DEF"; const string CONVERT_sKEYFOUR = "GHI"; const string CONVERT_sKEYFIVE = "JKL"; const string CONVERT_sKEYSIX = "MNO"; const string CONVERT_sKEYSEVEN = "PWRS"; const string CONVERT_sKEYEIGHT = "TUV"; const string CONVERT_sKEYNINE = "WXYZ"; const string sALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // this is for iteration of "prefix" and then whatever might be a word in the lexicon /* Recursive Puzzle * Constants for it */ const int iRECURSIVE_TARGET = 0; /* StockCuttingConstants */ const string sSTOCK_CUTTING = "Enter the length of the provided pipes: "; /* Recursive Puzzle * Variables for it */ int iComparisonValue; int iSourceCellValue; /* ////////////////////////////////////////////////////////////////////////////// * * Variiables should be declared here * * /////////////////////////////////////////////////////////////////////////////// */ int iEnteredNumber; Vector arrNums; // the vector to hold the values we plan on running the recursive function through int iTarget; int iSumSoFar = 0; // base case result // DawgLexicon lex; Lexicon lex; int iNumStairsTracker = 0; // for recursion trouble shooting /grocking Lexicon lexMobileMindReading; Vector arrKeypadMindReading; /* !! The convention is supposedly adding an i at the start of ints, d for double, * s for string etc. That causes a lot of work if at some time we want to change * the into to a double and we have placed the variable name iNumber multiple times * in the code with and want to change it to a double. dNumber. We could cast it to * a double, but it would be easier to * not put the lower character i,d etc in front. * * If I want to make the code easier to read, the i, d, s etc is the way to go. */ /* ////////////////////////////////////////////////////////////////////////////// * * Typedef section. Create an alias name for another data type. * * /////////////////////////////////////////////////////////////////////////////// */ template inline string stringify(const T& input); // typedef vector Coordinates; // this gived vector the name of Coordinates. Used for collecting the mouse click points /* ////////////////////////////////////////////////////////////////////////////// * * Function Prototypes are declare here here, alternately, just whack all the * methods main calls before main! * * Practically, it's good to list them all at the top, so you do not have to work * out where to place it in the list of functions that are written in the program. * Alternately, put the FP's after Main. * * /////////////////////////////////////////////////////////////////////////////// */ int EnterChoice (string string1, string string2); int EnterChoiceAssign3(); int SeekInput(string sPrompt); void SubsetSum(); void ExhaustiveAltRecSum(Vector &nums, int iIndex, int iSumSoFar, int iTarget); bool RecSum(Vector &nums, int iIndex, int iSumSoFar, int iTarget); bool AltRecSum(Vector &nums, int iIndex, int iSumSoFar, int iTarget); void RecSubsets(string soFar, string theRest); void ListSubsets(string str); bool CanMakeSum(Vector &nums, int iTargetSum); void ListPermuations(string s); void RecPermuteExhaustive( string sSoFar, string sTheRest); //mnemonics fuctions void ListMnemonicsFunction(); void ListMnemonics (string str); // H17S handout solutuions void RecursiveMnemonics(string sBLANK, string str); // called by the ListMneminics wrapper function string DigitLetters(char ch); //When using DawgLexicon.h... /* bool IsAnagram(string sSoFar, string sTheRest, DawgLexicon &lex); void RecPermute(string sCurrent, string sOther, DawgLexicon &lex); bool IsAnagramWord(string s, DawgLexicon &lex); */ //When using lexicon.h... bool IsAnagram(string sSoFar, string sTheRest, Lexicon &lex); void RecPermute(string sCurrent, string sOther, Lexicon &lex); bool IsAnagramWord(string s, Lexicon &lex); void CreateLexiconAnagramSearch(); // Assignment 3 Code void Assignment3Code(); int CountWays(int iNumStairs); int RecCountWays (int iNumStairs); // from https://github.com/dsbmac/ProfessionalDevelopment/blob/master/Stanford-CS106B/Assignment%203%20Recursion/Assignment%203%20Recursion/Stairs.cpp void TwelveStepsToRecursiveEnlightenment(); void RulersOfTheWorld(); void EveryVoteCounts(); Vector arrVotingBlocks; Vector arrVotingBlocksToInt; // capital V for Standford vector //int CountCriticalVotes(Vector & blocks, int blockIndex); // wrapper in required prototype form //void CountCriticalVotes(Vector blocks, int blockIndex, int iCandidate1, int iCandidate2, int &iCriticalOutcomes, int iTotalOutcomes); // the next two lines replace the above two lines and is based on code shown at https://github.com/brianjscoles/CS106b-solutions/blob/master/3%20-%20Recursion%20Exercises/3%20-%20vote%20cointing.cpp int CountCriticalVotes(Vector & arrBlocks, int iBlockIndex); void CountCriticalVotesRecursion(Vector arrBlocks, int iKeyblock, int iAlice, int iBob, int &iCritical_outcomes, int &iTotal_outcomes); // FOR MOBILEPHONEMINDREADING void MobilePhoneMindReading(); void ListCompletions(string sDigits, Lexicon & lex); //the required prototype for mobilephone...takes the int to string conversion and outputs all occurancesin the lexicon string RecursiveKeypadMnemonics(string sPrefix, string sRest, Lexicon lex); //, Lexicon & lex); //string ConvertDigitsToLetters(int iEnteredNumber); // converts Mobile keypad entry to string (recursively) void printValidWords(string sPprefix, Lexicon &lex, string sAlpha); string RecursiveWordsStartingWithThePrefix(string sPrefix, string sRrest, Lexicon &lex); void WordsContainingPrefix(string sPrefix, Lexicon &lex); string sNonConstAlpha = sALPHA; Vector arrPrefixedWords; // create array. lexocon it and then check for match? // FOR A RECURSIVEPUZZLE void ARecursivePuzzle(); bool Solvable(int iStart, Vector & arrSquares); // wrapper bool RecursionSolvable(int iStartCellToLookIn, Vector & arrSquares, Vector arrVisitedCell, int iStartCellValue); // recursive function // FOR STOCKCUTTING void StockCutting(); int SeekInput(string sPrompt); int CutStock(Vector & arrRequests, int iStockLength); // wrapper int SmallestAnswer(Vector > & arrSmallestSolution); void RecursiveCutStock(Vector arrRequests, Vector > arrCurrentSolution, Vector > & arrSmallestSolution, int iStockLength); bool PipeLeft(int iRequestedPiece, Vector arrCurrentSolution, int iStockLength); void SetUpWindow (GWindow &gw); /* ////////////////////////////////////////////////////////////////////////////// * * DataStructure struct ScoreStats () * * This contains the structure of the data read from he file containing scores * * /////////////////////////////////////////////////////////////////////////////// */ /* ////////////////////////////////////////////////////////////////////////////// * * function ReadFile (string filename) * Usage: ReadFile(the name of the file); * -------------------------------------- * This read a file line by line and calculates some statistics: * min, average and max score. * The calcs are done in memory. * The scores in the file range from 0 to 100. * * /////////////////////////////////////////////////////////////////////////////// */ /* ////////////////////////////////////////////////////////////////////////////// * * function DisplayStats () * Usage: DisplayStats(); * -------------------------------------- * This spits out the values in memory * * /////////////////////////////////////////////////////////////////////////////// */// /* ////////////////////////////////////////////////////////////////////////////// * * Main Program * * Provides options of what sectuion of the program runs: * * - Binary warmup, * - subset sum warmup * - Anagram search warmup * - key pad mnemonics warmup * - The assessed sectuion of the program * - 1: 12 steps to recursive enlightment (90 my own code) * - 2: Ruler of the world (95% my own code) * - 3: Every vote counts (50% my own code) * - 4: Mobile phone mind reading (100% my own code) * - 5: Stock Cutting (25% my own code) * * /////////////////////////////////////////////////////////////////////////////// */ int main() { setConsoleWindowTitle("CS106B Assessment 3 - Recursion, or how to make things interesting."); EnterChoice(sINPUT_DETAILS1, sINPUT_DETAILS2); while (true) { switch(iEnteredNumber) { case 0: SeekInput(sBINARY_PROMPT); PrintInBinary(iEnteredNumber); cout << endl << "Print in Binary ended."; EnterChoice(sINPUT_DETAILS1, sINPUT_DETAILS2); break; case 1: SubsetSum(); CanMakeSum(arrNums, iTarget); if (CanMakeSum(arrNums, iTarget) == true) cout << "This is solvable.\n"; if (CanMakeSum(arrNums, iTarget) == false) cout << "This is NOT solvable.\n"; EnterChoice(sINPUT_DETAILS1, sINPUT_DETAILS2); break; case 2: CreateLexiconAnagramSearch(); EnterChoice(sINPUT_DETAILS1, sINPUT_DETAILS2); break; case 3: ListMnemonicsFunction(); EnterChoice(sINPUT_DETAILS1, sINPUT_DETAILS2); break; case 4: Assignment3Code(); EnterChoice(sINPUT_DETAILS1, sINPUT_DETAILS2); break; default: cout << "Error: enter a valid selection" << endl; EnterChoice(sINPUT_DETAILS1, sINPUT_DETAILS2); break; } } return 0; } /* ////////////////////////////////////////////////////////////////////////////// * * Function's follow - these should all be listed in the * Function Prototype section towards the top * * /////////////////////////////////////////////////////////////////////////////// */ /* ////////////////////////////////////////////////////////////////////////////// * * Function EnterChoice * Usage: EnterChoice (string1, string2); * ________________________ * A standardised function to seek input by sending the CONSTANT strings to the function * where the strings explain what NUMERICAL input is sought to access what option of * the program. * The input integer is the send back to main in order for processing. * * /////////////////////////////////////////////////////////////////////////////// */ int EnterChoice (string string1, string string2) { cout << string1 << endl; // make sure only characters are entered cout << string2; iEnteredNumber = getInteger(); cout << "You Entered " << iEnteredNumber << endl; return iEnteredNumber; } /* ////////////////////////////////////////////////////////////////////////////// * * Function SeekInput * Usage: SeekInput (string to display at prompt); * ________________________ * A standardised function to seek input by sending a single CONSTANT string to the function * where the strings explain what NUMERICAL input is sought to access what option of * the program. * The input integer is the send back to main in order for processing. * * /////////////////////////////////////////////////////////////////////////////// */ int SeekInput (string sPrompt){ cout << sPrompt; // make sure only character are entered iEnteredNumber = getInteger(); return iEnteredNumber; } /* ////////////////////////////////////////////////////////////////////////////// * * Function SubsetSum * Usage: SubsetSum (); * ________________________ * Builds an array of values from user entered data * * /////////////////////////////////////////////////////////////////////////////// */ void SubsetSum (){ cout << "Enter first number: "; // make sure only character are entered // Good code would loop this until sentinal value entered. int iEnteredNumber = getInteger(); arrNums.push_back(iEnteredNumber); cout << "Enter second number: "; iEnteredNumber = getInteger(); arrNums.push_back(iEnteredNumber); cout << "Enter third number: "; iEnteredNumber = getInteger(); arrNums.push_back(iEnteredNumber); cout << "Enter forth number: "; iEnteredNumber = getInteger(); arrNums.push_back(iEnteredNumber); cout << "Enter fifth number: "; iEnteredNumber = getInteger(); arrNums.push_back(iEnteredNumber); cout << "Enter the target number: "; iTarget = getInteger(); string str = arrNums.toString(); cout << "Guts of the arrNums vector: " << str << endl; cout << "Target Number: " << iTarget << endl; } /* ////////////////////////////////////////////////////////////////////////////// * * Function RecSubsets * Usage: RecSubsets(string of soFar, string of theRest); * ________________________ * This recusion explores all possible solutions * * /////////////////////////////////////////////////////////////////////////////// */ void RecSubsets(string sSoFar, string sTheRest) { if (sTheRest == "") { cout << sSoFar << endl; } else { RecSubsets(sSoFar + sTheRest[0], sTheRest.substr(1)); RecSubsets(sSoFar, sTheRest.substr(1)); } } /* ////////////////////////////////////////////////////////////////////////////// * * Function ListSubsets * Usage: ListSubsets(thje string to permutate); * ________________________ * Used with RecSubsets recursion * * /////////////////////////////////////////////////////////////////////////////// */ void ListSubsets(string sStr) { RecSubsets("", sStr); } /* ////////////////////////////////////////////////////////////////////////////// * * Function RecSum * Usage: RecSum(nums, iIndex+1, iSumSoFar, iTarget); for example * ________________________ * This In-out pattern is commonly used for any sort of subset/power-set exploration * * /////////////////////////////////////////////////////////////////////////////// */ bool RecSum(Vector &arrNums, int iIndex, int iSumSoFar, int iTarget) { if (iSumSoFar == iTarget) return true; // success base case if (iIndex == arrNums.size()) return false; // failure base case // recursive case, try next element both in and out of the sum return RecSum(arrNums, iIndex+1, iSumSoFar, iTarget) || RecSum(arrNums, iIndex+1, iSumSoFar+arrNums[iIndex], iTarget); } /* ////////////////////////////////////////////////////////////////////////////// * * Function RecPermuteExhaustive * Usage: RecPermuteExhaustive(sSoFar + sTheRest[i], sTheRest.substr(0,1)+sTheRest.substr(i+1)); for example * ________________________ * Permuation function that is exhaustive (as opposed to the IsAnagram function) * cycles through all possibilities. * * /////////////////////////////////////////////////////////////////////////////// */ void RecPermuteExhaustive(string sSoFar, string sTheRest) { if (sTheRest == "") { cout << sSoFar << endl; } else { for (int i = 0; i < sTheRest.length(); i++) { RecPermuteExhaustive(sSoFar + sTheRest[i], sTheRest.substr(0,1)+sTheRest.substr(i+1)); } } } /* ////////////////////////////////////////////////////////////////////////////// * * Function ExhaustiveAltRecSum * Usage: ExhaustiveAltRecSum(the vector, int iIndex, iSumSoFar, iTarget); * ________________________ * EXHAUSTIVE (RECURSIVE) PERMUTATION RECUSION * This recursion is exhaustive as it cycles through all possible combinations. * Compare to the BACKTRACKING as small mods are made to this to get that. * * Exhaustive recursion is resource expensive as it looks at everything (obvioulsy) * * /////////////////////////////////////////////////////////////////////////////// */ void ExhaustiveAltRecSum(Vector &arrNums, int iIndex, int iSumSoFar, int iTarget) { if (iSumSoFar == iTarget) // success base case { cout << iSumSoFar << endl; } else { for (int i = iIndex; i < arrNums.size(); i++) // for all avail choices, try one choice { RecSum(arrNums, i+1, iSumSoFar+arrNums[i], iTarget); //if it works, you are done, else unmake choice and try next one. } } } /* ////////////////////////////////////////////////////////////////////////////// * * Function AltRecSum * Usage: AltRecSum(the vector, int iIndex, iSumSoFar, iTarget); * ________________________ * BACKTRACKING RECUSION * This recursion chooses an element at each call and tries it both in and out * This is a choose one of the remaining pattern, useful for permutations */ bool AltRecSum(Vector &arrNums, int iIndex, int iSumSoFar, int iTarget) { if (iSumSoFar == iTarget) return true; // success base case. So "if (no more choices), return (conf is goal state) for (int i = iIndex; i < arrNums.size(); i++) // for (all avail choices,) try one choice { if (RecSum(arrNums, i+1, iSumSoFar+arrNums[i], iTarget)) //if it works, you are done, else unmake choice and try next one. return true; } return false; // exhausted all choices? returns this which says "solution not found" } /* ////////////////////////////////////////////////////////////////////////////// * * Function CanMakeSum * Usage: CanMakeSum(vector of nums, iTargetSum); * ________________________ * given a vector of numbers and a target sum, report whether any subset of the numbers * in the array sum to that target. This is just a wrapper for the recursive function * RecSum (or a call AltRecSum for the same result) * * /////////////////////////////////////////////////////////////////////////////// */ bool CanMakeSum(Vector &arrNums, int iTargetSum) { return RecSum(arrNums, 0, 0, iTargetSum); } /* ////////////////////////////////////////////////////////////////////////////// * * Function IsAnagram * Usage: IsAnagram(string sSoFar, string sTheRest, Lexicon); * ________________________ * IsAnagram function from Lecture 10 ~30mins. * bool IsAnagram(string sSoFar, string sTheRest, DawgLexicon &lex * * This looks for the first occurence only and returns it via * if (lex.contains(sSoFar)) cout << sSoFar << endl; * Lecure 10, ~35mins summarises this * * /////////////////////////////////////////////////////////////////////////////// */ bool IsAnagram(string sSoFar, string sTheRest, Lexicon &lex) { if (sTheRest == "") { if (lex.contains(sSoFar)) cout << sSoFar << endl; return lex.contains(sSoFar); // check the header file } else { for (int i = 0; i < (sTheRest.length()); i++) { string sNext = sSoFar + sTheRest[i]; string sRemaining = sTheRest.substr(0, i) + sTheRest.substr(i + 1); if (IsAnagram(sNext, sRemaining, lex)) return true; } } return false; } /* ////////////////////////////////////////////////////////////////////////////// * * Function ListSubsets * Usage: CreateLexiconAnagramSearch(); * ________________________ * Searches a lexicon (or dawglexicon) for a specicic string contained * in the IsAnagramWord) * * /////////////////////////////////////////////////////////////////////////////// */ void CreateLexiconAnagramSearch() { // DawgLexicon lex(LEXICON); Lexicon lex(LEXICON); //while (true) // this gets the function stuck in this call time. would need a sentinal value to break out cout << "?"; string s = getLine(); cout << IsAnagramWord(s, lex) << endl; //} } /* ////////////////////////////////////////////////////////////////////////////// * * Function ListPermuations * Usage: ListPermuations(string s) * ________________________ * Wrapper function * * /////////////////////////////////////////////////////////////////////////////// */ void ListPermuations(string s) { IsAnagram("", s, lex); } /* ////////////////////////////////////////////////////////////////////////////// * * Function IsAnagramWord * Usage: IsAnagramWord(string s, Lexicon); * ________________________ * Wrapper function * * /////////////////////////////////////////////////////////////////////////////// */ // bool IsAnagramWord(string s, DawgLexicon &lex) { bool IsAnagramWord(string s, Lexicon &lex) { return IsAnagram("", s, lex); } // ////////////////////////////////////////////////////////////////////////////////////////// // MNEMONICS FUNCTIONS // ////////////////////////////////////////////////////////////////////////////////////////// /* ////////////////////////////////////////////////////////////////////////////// * * Function ListMnemonicsFunction * Usage ListMnemonicsFunction(); * ________________________ * This is the 'main' for the ListMnemonics(str) function * and it seeks the input. * This function lists all the mnemonics for the string of * digits stored in the string str. The correspondance between * digits and letters id the same as that on the standard * telephone keypad. The implimentations at this level is a * simple wrapper function that provides the arguments * necessay information * * /////////////////////////////////////////////////////////////////////////////// */ void ListMnemonicsFunction() { int iKeypad = SeekInput("Enter keypad sequence: "); cout << iKeypad << " is what you just entered." << endl; //run stringify..to produce //string sIntToString = (iEnteredNumber); // cout << sIntToString << "stringified int \n"; // ListMnemonics(sIntToString); cout << "\nListMnemonicsFunction ended\n"; } /* ////////////////////////////////////////////////////////////////////////////// * * Function ListMnemonics * Usage ListMnemonics(str); * ________________________ * Wrapper function * * /////////////////////////////////////////////////////////////////////////////// */ void ListMnemonics(string str) { RecursiveMnemonics("", str); } /* ////////////////////////////////////////////////////////////////////////////// * * Function RecursiveMnemonics * Usage: RecursiveMnemonics(prefix, rest); * ________________________ * This function does all the real work for ListMnemonics and * implements a more general problem with a recursive solution * that is easier to see. The call to RecursiveMnemonics generates * all mnemonics for the digits in the string prefixed by the * mnemonic string in the prefix. As the recursion proceeds, the rest * string ets shorter and the prefix string gets longer * * /////////////////////////////////////////////////////////////////////////////// */ void RecursiveMnemonics(string sPrefix, string sRest) { if (sRest.length() == 0) { cout << sPrefix << " "; //endl; } else { string sOptions = DigitLetters(sRest[0]); for (int i = 0; i < sOptions.length(); i++) { RecursiveMnemonics(sPrefix + sOptions[i], sRest.substr(1)); } } } /* ////////////////////////////////////////////////////////////////////////////// * * Function DigitLetters * Usage: digits = DigitLetters(ch); * ________________________ * This function returns a string consisting of the legal * substititutions for a given digit chracter. Note that 0 * and 1 are handled by just leaving the digit in it position * * /////////////////////////////////////////////////////////////////////////////// */ string DigitLetters(char ch) { switch (ch) { case '0': return (CONVERT_sKEYZERO); case '1': return (CONVERT_sKEYONE); case '2': return (CONVERT_sKEYTWO); case '3': return (CONVERT_sKEYTHREE); case '4': return (CONVERT_sKEYFOUR); case '5': return (CONVERT_sKEYFIVE); case '6': return (CONVERT_sKEYSIX); case '7': return (CONVERT_sKEYSEVEN); case '8': return (CONVERT_sKEYEIGHT); case '9': return (CONVERT_sKEYNINE); default: cout << "ERROR! Illegal digit"; } return "Something went wrong"; } // ////////////////////////////////////////////////////////////////////////////////////////// // // ASSIGNMENT 3 ASSESSED CODE // // ////////////////////////////////////////////////////////////////////////////////////////// /* ////////////////////////////////////////////////////////////////////////////// * * Function Assignment3Code * Usage: Assignment3Code(); * ________________________ * This is the 'main' for the assessed assignment 3 code * * /////////////////////////////////////////////////////////////////////////////// */ void Assignment3Code() { cout << "whack in Assignment 3 functions called etc...\n"; EnterChoice(sINPUT_DETAILS3, sINPUT_DETAILS4); if (iEnteredNumber == 0) TwelveStepsToRecursiveEnlightenment(); else if (iEnteredNumber == 1) RulersOfTheWorld(); else if (iEnteredNumber == 2) EveryVoteCounts(); else if (iEnteredNumber == 3) MobilePhoneMindReading(); else if (iEnteredNumber == 4) ARecursivePuzzle(); else if (iEnteredNumber == 5) StockCutting(); } /* Assignment 3 Part 1 * * NOTE: If this were production code, I'd probably put each project in a header file so the "main" program is not as cluttered/long */ /* ////////////////////////////////////////////////////////////////////////////// * * Function TwelveStepsToRecursiveEnlightenment * Usage: TwelveStepsToRecursiveEnlightenment(); * ________________________ * This is the 'main' for the TwelveStepsToRecursiveEnlightenment code * * /////////////////////////////////////////////////////////////////////////////// */ void TwelveStepsToRecursiveEnlightenment() { cout << "How many stairs does Billy need to climb? "; iEnteredNumber = getInteger(); if (iEnteredNumber == 0) cout << "No stairs needed to climb, so program ended."; // NOTE! I have not bothered with error checking. Get integer does it anyway. else if (iEnteredNumber == 1) cout << "One stair cannot be climbed with a large stride, only a small stride (or half a large stride)."; else { cout << "Billy can climb the stairs " << RecCountWays(iEnteredNumber) << " different ways. (sent from the recursive function)\n"; } Assignment3Code(); // so program loops back to a prompt. } /* ////////////////////////////////////////////////////////////////////////////// * * Function CountWays * Usage: CountWays(int numStairs); * ________________________ * Wrapper for the 12 steps to Recursive Enlightenment * * /////////////////////////////////////////////////////////////////////////////// */ int CountWays(int numStairs) { return numStairs; } /* ////////////////////////////////////////////////////////////////////////////// * * Function RecCountWays * Usage: RecCountWays (int numStairs * ________________________ * This is the recursive function "borrowed" from the follwing webpage: * https://github.com/dsbmac/ProfessionalDevelopment/blob/master/Stanford-CS106B/Assignment%203%20Recursion/Assignment%203%20Recursion/Stairs.cpp * I can see what it does after the if and what happens in the return * However, I cannot fathom how it works or how it keeps track of the numbmer it reports as numStairs at the end of the recursiion * * /////////////////////////////////////////////////////////////////////////////// */ int RecCountWays (int iNumStairs) { if (iNumStairs <= 3) return iNumStairs; else { //create two branches and substract large and small steps respectively iNumStairsTracker ++; return RecCountWays(iNumStairs-iLARGE_STRIDE) + RecCountWays(iNumStairs-iSMALL_STRIDE); } } /* Assignment 3 Part 2 */ /* ////////////////////////////////////////////////////////////////////////////// * * Function RulersOfTheWorld * Usage: RulersOfTheWorld(); * ________________________ * This is the 'main' for the RulersOfTheWorld code * * 1. Takes in w and h if a rectange from user. * 2. Line drawn along bottom of rectangle (so in a gwindow) * 3. Middle line in center of rectangle (so w/2) and is as high as rectange (so h). * 4. Next we half the height of h and draw line in the middle of the "new" smaller * rectangle. 3 and 4 then repeat until we stop at some arbitary point. Say if w < 1 * * Working as of 20171019 13:11. Code for lines hald borrowed. Underlying ideas * for the recursion are mine so progress made. * * ////////////////////////////////////////////////////////////////////////////// */ void RulersOfTheWorld() { cout << "RulersOfTheWorld launched. " << endl; cout << "Enter rectangle height (max 250): "; // not bothering with bounds checking at this stage double h = getInteger(); cout << "Enter rectangle width(max 500): "; // not bothering with bounds checking at this stage double w = getInteger(); //Opens Graphics window AFTER collecting input GWindow gw(iWINDOW_WIDTH, iWINDOW_HEIGHT); // creates graphics window an sets size. Tried intialising it under variables but an error happened down here. SetUpWindow(gw); double dX0 = (gw.getWidth() / 2) - (w / 2); // middle of screen minus half the input width so the line centres in the window. !! OFF TO THE LEFT A LITTLE BIT !! double dY0 = gw.getHeight() - dLINE_OFFSET; double dX1 = dX0 + w; double dY1 = dY0; gw.add(new GLine(dX0, dY0, dX1, dY1)); // this is the bottom line of the "ruler" NOTICE: no need for rectangle. DrawRuler (gw, dX0, dY0, w, h, dMIN_HEIGHT); // this is the recursive function - packaged into ruleroftheworld.h Assignment3Code(); // so program loops back to a prompt. } /* Assignment 3 Part 3 */ /* ////////////////////////////////////////////////////////////////////////////// * * Function EveryVoteCounts * Usage: EveryVoteCounts(); * ________________________ * This is the 'main' for the EveryVoteCountscode * * Examines a subset and builds on the subset warmup solution * * 1. Build a coalition - choose a subset and sum it * 2. Determine which target block is necessary and sufficient to reach a majority * >> needs to add housekeeping and counting * >> adapting the warmup code should do the job (H18-assignRec.pdf) * * 3. add up total votes, divide by 2 and times by 51/100 to get the dMajorityVote vote. * 4. Assign on set of votes to CandidateA, the other set to CandidateB * 5. If one index (the last one chosen) gives CandidateA or B >= the dMajorityVote, then that block is critical. * * ////////////////////////////////////////////////////////////////////////////// */ void EveryVoteCounts() { cout << "EveryVoteCounts launched\n";\ // read the text file into a vVotingBlocks. ifstream inVotingBlocks; openFile(inVotingBlocks, VOTINGBLOCKS); // open file readEntireFile(inVotingBlocks, arrVotingBlocks); // read contents into an array /* pretty much the code here http://www.geeksforgeeks.org/converting-strings-numbers-cc/ */ for (int i = 0; i < arrVotingBlocks.size(); i++) { string s = arrVotingBlocks[i]; // object from the class stringstream stringstream geek(s); // stream it to the integer x int x = 0; geek >> x; // Now the variable x holds the value represented by the string // cout << "Value of x for i = " << i << " is: " << x; arrVotingBlocksToInt.push_back(x); } int iTotalVotes = 0; for (int i = 0; i < arrVotingBlocksToInt.size(); i++) { iTotalVotes = iTotalVotes + arrVotingBlocksToInt[i]; // arrVotingBlocksToInt == blocks // cout << "Total Votes = " << iTotalVotes << ","; } for(int i = 0; i < arrVotingBlocksToInt.size(); i++){ int critical_outcomes = CountCriticalVotes(arrVotingBlocksToInt, i); } /* The commented out content was going to be my trackers, and the code would see if the abs majority was exceeded at the end of each block cout << "Total Votes = " << iTotalVotes << "."; double dAbsoluteMajority = (iTotalVotes * 0.51); cout << "Absolute Majority = " << dAbsoluteMajority << "," << endl; blocks = vVotingBlocks.size(); // not right. how to declare? int blockIndex = 0; int arrazysize = arrVotingBlocksToInt.size(); cout << arrazysize << " is the arraysize" << endl; for(int i = 0; i < arrVotingBlocksToInt.size(); i++){ int critical_outcomes = CountCriticalVotes(arrVotingBlocksToInt, i); // points to the wrapper - critical outcomesis zero everywhere int arrazysize = arrVotingBlocksToInt.size(); cout << arrazysize << " is the arraysize" << endl; cout << critical_outcomes << " equals critical_outcomes" << endl; // critical outcomesis zero everywhere } CountCriticalVotes(arrVotingBlocksToInt, blockIndex, dAbsoluteMajority); */ Assignment3Code(); } /* ////////////////////////////////////////////////////////////////////////////// * * Function CountCriticalVotes * Usage: CountCriticalVotes(Vector, iIndex); * ________________________ * Wrapper Function * From https://github.com/brianjscoles/CS106b-solutions/blob/master/3%20-%20Recursion%20Exercises/3%20-%20vote%20cointing.cpp * * ////////////////////////////////////////////////////////////////////////////// */ int CountCriticalVotes(Vector & arrBlocks, int iBlockIndex){ int iKeyblock = arrBlocks[iBlockIndex]; Vector arrBlockscopy = arrBlocks; arrBlockscopy.remove(iBlockIndex); int iAlice = 0; int iBob = 0; int iCritical_outcomes = 0; int iTotal_outcomes = 0; CountCriticalVotesRecursion(arrBlockscopy, iKeyblock, iAlice, iBob, iCritical_outcomes, iTotal_outcomes); cout << "The block of " << iKeyblock << " is critical in " << iCritical_outcomes << " of " << iTotal_outcomes << " possible outcomes." << endl; return iCritical_outcomes; } /* ////////////////////////////////////////////////////////////////////////////// * * Function CountCriticalVotes * Usage: CountCriticalVotesRecursion(arrblocks, iKeyblock, iAlice, iBob, iCritical_outcomes, iTotal_outcomes); * ________________________ * Sent to function * 1. Vector of block vote counts * 2. index within that vector * 3. Number of election outcomes in which the block at the gven index is a critical vote * eg {4, 2, 7, 4} represents a viting syste, with four blocks of 17 total votes * a majority of 9 votes is required to win. * if block insex is , the fucntuion counts the critical votes for the last block * if block 0 and 1 vote for Alice and 2 for Bob, the last one (3) is critical * if block 9 votes for Alice and 1 and 2 for Bob, the last block is irrelevant. * THE LAST block is critical in 2 of the 8 solutions. * A 2 block vote at index 1 has the same count of critical votes * A 7 block vote has 6 critical votes * Possible electiuon outcomesin remaining blocks = N-1 * There are 2(exp)N-1 diff possibilities. * * ////////////////////////////////////////////////////////////////////////////// */ void CountCriticalVotesRecursion(Vector arrBlocks, int iKeyblock, int iAlice, int iBob, int &iCritical_outcomes, int &iTotal_outcomes) /* * blocks contains the list of votes per array ref * keyblock is what? the total? * Alice is the running vote total for her * Bob is the running vote total for hi, * Criticaloutcome goes up when Either Alice or Bob gets an absolute majority from the last lots of votes in the next block examined) * Total outcomes would be the tracker that goes up once an entire permutation exploration has occurred and we shunt back to the base case. Each time the recursion goes around, this goes up 1. */ { if(arrBlocks.size()==0){ if(abs(iAlice-iBob)<=iKeyblock) iCritical_outcomes++; iTotal_outcomes++; } else { int iNext_block = arrBlocks[0]; arrBlocks.remove(0); CountCriticalVotesRecursion(arrBlocks, iKeyblock, iAlice + iNext_block, iBob, iCritical_outcomes, iTotal_outcomes); // if alice and the next block gives her the win, it is critical CountCriticalVotesRecursion(arrBlocks, iKeyblock, iAlice, iBob + iNext_block, iCritical_outcomes, iTotal_outcomes); // if bob and the next block gives himr the win, it is critical } } /* Assignment 3 Part 4 */ /* ////////////////////////////////////////////////////////////////////////////// * * Function MobilePhoneMindReading * Usage: MobilePhoneMindReading(); * ________________________ * An implimentation of predictive text which is seen these days on smart phones * mostly. * * 1. Takes a keypad input (as a single string of numbers) and converts to mapped letters * >> Key 1: 1 * >> Key 2: A B C * >> Key 3: D E F * >> Key 4: G H I * >> Key 5: J K L * >> Key 6: M N O * >> Key 7: P Q R S * >> Key 8: T U V * >> Key 9: W X Y Z * >> Key 0: 0 * * Converting the key (number) input to text is done recursively * * 2. Looks up the output from the number to text conversion and determines if the key presses can create any * equal size or greater word. This word is then output to the screen. * * >> an vector would be created where cell 0 represents key 0, cell 1 = key 1 etc. * >> so cell 1 = 0 * >> ...cell 2 = ABC. The lexicon seach then iterates over the contents of cell 2>>A...B...C... * * ////////////////////////////////////////////////////////////////////////////// */ void MobilePhoneMindReading() { int iKeypad = SeekInput(sMOBILE_PREDICTIVE); cout << iKeypad << " is what you just entered." << endl; //run stringify..to produce string sIntToString = stringify(iKeypad); // string sTest = "73647"; /* creates lexion from a CONSTANT file name */ Lexicon lexMobileMindReading(LEXICON); ListCompletions(sIntToString, lexMobileMindReading); ListCompletions(sIntToString, lexMobileMindReading); // this takes an age to run (I'm sure it was faster before I cleaned up the code) cout << "The keypad predictions are...\n"; for (int i = 0; i < arrPrefixedWords.size(); i++) { string sFoo = arrPrefixedWords[i]; //cout << "sfoo tracker " << sFoo << "..."; if (lexMobileMindReading.contains(sFoo)) { cout << sFoo << " "; } } cout << endl; Assignment3Code(); } /* ////////////////////////////////////////////////////////////////////////////// * * Function ListCompletions * Usage ListCompletions(string, Lexicon); * ________________________ * This function lists all the mnemonics for the string of * digits stored in the string str. The correspondance between * digits and letters id the same as that on the standard * telephone keypad. The implimentations at this level is a * simple wrapper function that provides the arguments * necessary for the recursive call * * NO CHANGE TO LISTMNEMONICS, could modify so we could send the function name as a constant and not repeat code * * /////////////////////////////////////////////////////////////////////////////// */ void ListCompletions(string str, Lexicon & lex) { string sPrefix = RecursiveKeypadMnemonics("", str, lex);//, lex); } /* * Function RecursiveKeypadMnemonics * Usage: RecursiveKeypadMnemonics(prefix, rest, lex); * ________________________ * This function does all the real work for ListMnemonics and * implements a more general problem with a recursive solution * that is easier to see. The call to RecursiveKeypadMnemonics generates * all mnemonics for the digits in the string prefixed by the * mnemonic string in the prefix. As the recursion proceeds, the rest * string gets shorter and the prefix string gets longer */ string RecursiveKeypadMnemonics(string sPrefix, string sRest, Lexicon lex) { if (sRest.length() == 0) { arrKeypadMindReading.add(sPrefix); if (lex.containsPrefix(sPrefix)) // lex.contains(prefix) is CONTAINS WORD SPECIFICALLY. Use this to stop goign down deadends... WordsContainingPrefix(sPrefix, lex); return sPrefix; } else { string options = DigitLetters(sRest[0]); for (int i = 0; i < options.length(); i++) RecursiveKeypadMnemonics(sPrefix + options[i], sRest.substr(1), lex); return options; } } /* ////////////////////////////////////////////////////////////////////////////// * * Function WordsContainingPrefix * Usage: WordsContainingPrefix(str, Lexicon); * ________________________ * Looks for the prefix as part of the recursive investigation * * /////////////////////////////////////////////////////////////////////////////// */ void WordsContainingPrefix(string sPrefix, Lexicon &lex) { if ((lex.containsPrefix(sPrefix)))// && (lex.contains(prefix))) { arrPrefixedWords.add(sPrefix); for (int i = 0; i < sALPHA.size(); i++) { WordsContainingPrefix(sPrefix + sNonConstAlpha.at(i), lex); } } } /* Assignment 3 Part 5 */ /* //////////////////////////////////////////////////////////////////////////////// * * A Recursive Puzzle * * From a starting position of Vector[0], see if we can get to the final position * which ALWAYS has the value of 0 and there is ALWAYS only a single cell with the * value of zero AND that's awalys in the vector.size() -1 positon (Not that we need * to check for that if we know the targert value is always 0 * * Paul Yeatman * 20171120 * * Version Notes: * Initial version (v2.0) * Total rewrite using newly concocted logic * * /////////////////////////////////////////////////////////////////////////////// */ /* //////////////////////////////////////////////////////////////////////////////// * Function ARecursivePuzzle * Usage: ARecursivePuzzle(); * ________________________ * This is the 'main' for the ARecursivePuzzle code * * /////////////////////////////////////////////////////////////////////////////// */ void ARecursivePuzzle() { // Test array creation cout << "ARecursiveFunction launched\n"; Vector arrRecursivePuzzle; Vector arrRecursivePuzzle1; Vector arrRecursivePuzzle2; Vector arrRecursivePuzzle3; Vector arrRecursivePuzzle4; Vector arrRecursivePuzzle5; Vector arrRecursivePuzzle6; Vector arrRecursivePuzzle7; arrRecursivePuzzle += 1,0; string sArrayCreated = " 1, 0 is solvable.";// 1,0 = solvable, 2,0 not solvable arrRecursivePuzzle1 +=2,0; string sArrayCreated1 = " 2,0 is not solvable.";// 1,0 = solvable, 2,0 not solvable arrRecursivePuzzle2 += 3,1,2,3,0; string sArrayCreated2 = " 3,1,2,3,0 is not solvable.";// this creates a 5 cell non solvable array arrRecursivePuzzle3 += 3,6,4,1,3,4,2,5,3,0; string sArrayCreated3 = " 3,6,4,1,3,4,2,5,3,0 is solvable.";// this creates a 10 cell solvable array arrRecursivePuzzle4 += 2,1,1,0; string sArrayCreated4 = " 2,1,1,0 is solvable.";// this creates a 4 cell solvable array arrRecursivePuzzle5 += 2,1,3,3,1,2,0; string sArrayCreated5 = " 2,1,3,3,1,2,0 is solvable.";// this creates a 4 cell solvable array arrRecursivePuzzle6 += 3,3,2,2,0; string sArrayCreated6 = " 3,3,2,2,0 is solvable";// this creates a 5 cell solvable array arrRecursivePuzzle7 += 3,6,4,1,3,5,2,5,3,0; string sArrayCreated7 = " 3,6,4,1,3,5,2,5,3,0 is not solvable";// this creates a 10 cell solvable array // duplicated code to test all the created arrays from above cout << "The created array has the following elements:" << sArrayCreated << endl; int iSourceCellRef = 0; // needs to be intialised to have a size? //cout << "Solvable(iSourceCellRef, arrRecursivePuzzle) run" << endl; if (Solvable(iSourceCellRef, arrRecursivePuzzle) == true) { cout << "*********THIS IS SOLVABLE*********\n" << endl; } else { cout << "*********THIS IS NOT SOLVABLE*********\n" << endl; } cout << "The created array has the following elements:" << sArrayCreated1 << endl; iSourceCellRef = 0; // needs to be intialised to have a size? if (Solvable(iSourceCellRef, arrRecursivePuzzle1) == true) { cout << "*********THIS IS SOLVABLE*********\n" << endl; } else { cout << "*********THIS IS NOT SOLVABLE*********\n" << endl; } cout << "The created array has the following elements:" << sArrayCreated2 << endl; iSourceCellRef = 0; // needs to be intialised to have a size? if (Solvable(iSourceCellRef, arrRecursivePuzzle2) == true) { cout << "*********THIS IS SOLVABLE*********\n" << endl; } else { cout << "*********THIS IS NOT SOLVABLE*********\n" << endl; } cout << "The created array has the following elements:" << sArrayCreated3 << endl; iSourceCellRef = 0; // needs to be intialised to have a size? if (Solvable(iSourceCellRef, arrRecursivePuzzle3) == true) { cout << "*********THIS IS SOLVABLE*********\n" << endl; } else { cout << "*********THIS IS NOT SOLVABLE*********\n" << endl; } cout << "The created array has the following elements:" << sArrayCreated4 << endl; iSourceCellRef = 0; // needs to be intialised to have a size? if (Solvable(iSourceCellRef, arrRecursivePuzzle4) == true) { cout << "*********THIS IS SOLVABLE*********\n" << endl; } else { cout << "*********THIS IS NOT SOLVABLE*********\n" << endl; } cout << "The created array has the following elements:" << sArrayCreated5 << endl; iSourceCellRef = 0; // needs to be intialised to have a size? if (Solvable(iSourceCellRef, arrRecursivePuzzle5) == true) { cout << "*********THIS IS SOLVABLE*********\n" << endl; } else { cout << "*********THIS IS NOT SOLVABLE*********\n" << endl; } cout << "The created array has the following elements:" << sArrayCreated6 << endl; iSourceCellRef = 0; // needs to be intialised to have a size? if (Solvable(iSourceCellRef, arrRecursivePuzzle6) == true) { cout << "*********THIS IS SOLVABLE*********\n" << endl; } else { cout << "*********THIS IS NOT SOLVABLE*********\n" << endl; } cout << "The created array has the following elements:" << sArrayCreated7 << endl; iSourceCellRef = 0; // needs to be intialised to have a size? if (Solvable(iSourceCellRef, arrRecursivePuzzle7) == true) { cout << "*********THIS IS SOLVABLE*********\n" << endl; } else { cout << "*********THIS IS NOT SOLVABLE*********\n" << endl; } Assignment3Code(); // so program loops back to a prompt. } /* ////////////////////////////////////////////////////////////////////////////// * * Function Solvable * Usage: Solvable(iStart, arrSquares); * ________________________ * wrapper function for bool RecursionSolvable * * /////////////////////////////////////////////////////////////////////////////// */ bool Solvable(int iStart, Vector & arrSquares) // wrapper { /* This is from https://github.com/brianjscoles/CS106b-solutions/blob/master/3%20-%20Recursion%20Exercises/5%20-%20puzzle%20solver.cpp * it sets up an array and fills every value with 0 (so each cell in a reference array is marked as not visited) */ Vector arrVisitedCell; for (int i = 0; i < arrSquares.size() ; i++) { arrVisitedCell.add(false); } int BoolSolvable = RecursionSolvable(iStart, arrSquares, arrVisitedCell, arrSquares[iStart]); return BoolSolvable; // line above could as easily be "return RecursionSolvable(start, squares, arrVisitedCell, squares[start])" } /* ////////////////////////////////////////////////////////////////////////////// * * Function RecursionSolvable * Usage: RecursionSolvable(iStartCellToLookIn, arrSquares, arrVisitedCell, iStartCellValue); * ________________________ * tracks forwards and backwards through the numbers until the last cell in the array is reached. If cannot be reached, puzzle not solvale * * /////////////////////////////////////////////////////////////////////////////// */ bool RecursionSolvable(int iStartCellToLookIn, Vector & arrSquares, Vector arrVisitedCell, int iStartCellValue) // recursive function { if (iStartCellValue == 0) { return true; } int intCellRefToLookIn = iStartCellValue + iStartCellToLookIn; if (intCellRefToLookIn >=0 && intCellRefToLookIn < arrSquares.size()) // ensure only looks within bounds of array/vector { if (arrVisitedCell[intCellRefToLookIn] == true) { return false; } if (arrVisitedCell[intCellRefToLookIn] == false) { arrVisitedCell[intCellRefToLookIn] = true; if (RecursionSolvable(intCellRefToLookIn, arrSquares, arrVisitedCell, arrSquares[intCellRefToLookIn])) { //cout << "Forwards exploration...\n"; return true; // if true, keep going forwards, else go backwards } if (RecursionSolvable(intCellRefToLookIn, arrSquares, arrVisitedCell, -arrSquares[intCellRefToLookIn])) { //cout << "Backwards exploration...\n"; return true; } } } return false; } /* Assignment 3 Part 6 */ /* ////////////////////////////////////////////////////////////////////////////// * * Function StockCutting * Usage: StockCutting(); * ________________________ * This is the 'main' for the StockCutting code * * All elements in the vector arepositive nubmers (you cannot create negative lenth pipes! * Requests for pipes longer than the starting material are not made * Only the pipes needed are shown, the combinations are not needed (knowing the combis would help * in reality) * * based heavily on https://github.com/brianjscoles/CS106b-solutions/blob/master/3%20-%20Recursion%20Exercises/6%20-%20stock%20cutting.cpp * which was used as a learning example * * /////////////////////////////////////////////////////////////////////////////// */ void StockCutting() { //int intStartingStockLength = 10; // moved to a ask user Vector arrOrder; //Vector arrOrder1; //Vector arrOrder2; //Vector arrOrder3; //Vector arrOrder4; //arrOrder += 4,3,4,1,7,8; string sArrOrder = " 4,3,4,1,7,8 = {4,4,1}, {3,7} & {8} with 2 small left over fragments.\n"; // arrOrder += 5, 5; string arrOrderStr = " 5,5 = {5,5} needs 1 pipe min."; //arrOrder +=2,0; string arrOrderStr = " 2,0 is not solvable in test config as 2 & 0 cannot reach 10 (it would use 1 pipe though).";// 1,0 = solvable, 2,0 not solvable //arrOrder += 6,1,2; string arrOrderStr = " 6, 1, 2 adds to 9 needs 1 pipe min {6, 1, 2}.";// this creates a 5 cell non solvable array //arrOrder += 6,1,5; string arrOrderStr = " 6, 1, 5 adds to 12 needs 2 pipes min {6, 1} {5} OR {6}, {5, 1}.";// this creates a 5 cell non solvable array arrOrder += 3,6,4,1,3,4,2,5,3,0; string sArrOrder = " 3,6,4,1,3,4,2,5,3,0 test 2.";// this creates a 10 cell solvable array //arrOrder5 += 2,1,1,0; string arrOrderStr4 = " 2,1,1,0 is solvable.";// this creates a 4 cell solvable array int iStartingStockLength = SeekInput(sSTOCK_CUTTING); cout << "The created array has the following elements:" << sArrOrder << endl; // Just for the heck of it emulation of green screen monitor from the 70's and 80's cout << "***********************************************************\n"; cout << "******* P I P E S I N V E N T O R Y R E Q U E S T *******\n"; cout << "***********************************************************\n"; cout << "********* I N P U T P I P E L E N G T H : " << iStartingStockLength << " *************\n"; cout << "***********************************************************\n"; cout << "********* P I P E S N E E D E D F O R J O B : " << CutStock(arrOrder, iStartingStockLength) << " *******\n"; cout << "***********************************************************\n"; } /* ////////////////////////////////////////////////////////////////////////////// * * Function CutStock * Usage: CutStock(arrRequests, iStockLength); * ________________________ * * Wrapper function for the recursion * * Creates two tracking vectors of vectors, one that holds the solution configuration and one that holds * the smallest successful configuration * * /////////////////////////////////////////////////////////////////////////////// */ int CutStock(Vector & arrRequests, int iStockLength) // wrapper { //could include error checking given we ask the user for the stocklength. Vector > arrCurrentSolution; // contains currently tested solution Vector > arrSmallestSolution; // contains smallest tested solution (is the arr.size() smaller than the current arrSmallestSolution? RecursiveCutStock(arrRequests, arrCurrentSolution, arrSmallestSolution, iStockLength); int iMinimalPipes = SmallestAnswer(arrSmallestSolution); return iMinimalPipes; } /* ////////////////////////////////////////////////////////////////////////////// * * Function SmallestAnswer * Usage: SmallestAnswer(Vector of arrSmallestSolution); * ________________________ * This outputs the configuration of pipe pieces. It's not requiredin the assignement, however the * vector exists so may as well output the sizes * * /////////////////////////////////////////////////////////////////////////////// */ int SmallestAnswer(Vector > & arrSmallestSolution) { cout << "****** P I P E S T O B E C U T A S F O L L O W S *****\n"; cout << "***********************************************************\n"; for (int i = 0; i < arrSmallestSolution.size(); i++) { for (int j = 0; j < arrSmallestSolution[i].size(); j++) { cout << "********************* PIPE " << i + 1 << ": " << arrSmallestSolution[i][j] << " ***************************\n"; } } cout << "***********************************************************\n"; return arrSmallestSolution.size(); } /* ////////////////////////////////////////////////////////////////////////////// * * Function RecursiveCutStock * Usage: RecursiveCutStock(arrRequests, Vector of arrCurrentSolution, Vector of arrSmallestSolution, iStockLength); * ________________________ * What we need: * >>combination of pipe lenths assigned to a vector (created this in arrOrder) * >>size of the pipe we have been given * * To determine... * >> how many times can we cut the pipe leaving a left over number as small as possible * >> can we cut the pipe with the currently investigated length * * What to track... n * >> How many pipes have we used * >> could track the successful combos (not required) * >> what lengths have we chopped so far (create arrays for this? use the arrays to detemine smallest array.size() which is the smallest soluton * so: -know what pipe we are cutting -know how much is left on the pipe (exceed stick legnth, go onto next pipe), new vector element * * we are modifying the copied vector by removing a tested elment from it (and adding it back if a case fails) * so, when requests gets to zero, all tests completed. base case (we are exhaustively permuting so one of these will be the smallest array). * basically, emprty vector (NO REQUESTS) is the base case. * * /////////////////////////////////////////////////////////////////////////////// */ void RecursiveCutStock(Vector arrRequests, Vector > arrCurrentSolution, Vector > & arrSmallestSolution, int iStockLength) { if (arrRequests.size() == 0) { if (arrCurrentSolution.size() < arrSmallestSolution.size() || arrSmallestSolution.size() == 0) { arrSmallestSolution = arrCurrentSolution; } } else { int iRequestedPiece = arrRequests[0]; arrRequests.remove(0); // grabs the next requested size from the copied vector and removes it from the vector for (int i = 0; i < arrCurrentSolution.size(); i++) { if (PipeLeft(iRequestedPiece, arrCurrentSolution[i], iStockLength)) { arrCurrentSolution[i].add(iRequestedPiece); RecursiveCutStock(arrRequests, arrCurrentSolution, arrSmallestSolution, iStockLength); arrCurrentSolution[i].remove(arrCurrentSolution[i].size()-1); } // the above chops the next bit of pipe off (assuming it can) } // not sure how this works but it generates a new branch if a new pipe is needed //when not base case, follow recursion Vector arrNewPipe; arrNewPipe.add(iRequestedPiece); arrCurrentSolution.add(arrNewPipe); RecursiveCutStock(arrRequests, arrCurrentSolution, arrSmallestSolution, iStockLength); } } /* ////////////////////////////////////////////////////////////////////////////// * * Function PipeLeft * Usage: PipeLeft(iRequestedPiece, Vector of arrCurrentSolution, iStockLength); * ________________________ * Determines if the existing pipe has legnth left on it, or if a new pipe length is needed * * /////////////////////////////////////////////////////////////////////////////// */ bool PipeLeft(int iRequestedPiece, Vector arrCurrentSolution, int iStockLength) { int iSumSoFar = 0; for (int i = 0; i < arrCurrentSolution.size(); i++) { iSumSoFar += arrCurrentSolution[i]; } if (iRequestedPiece + iSumSoFar <= iStockLength) return true; else return false; } /* ////////////////////////////////////////////////////////////////////////////// * * Function SetUpWindow * Usage: SetUpWindow(GWindow gw) * ________________________ * Using the Simple Project as inspiration * Sets up a graphics windows so the user can draw on it * * ////////////////////////////////////////////////////////////////////////////// */ void SetUpWindow(GWindow &gw) { gw.setColor("White"); gw.clear(); gw.setWindowTitle("RulersOfTheWorld"); gw.setColor("Black"); gw.setVisible(true); GLabel* ProgramPurpose = new GLabel ("Recursively draws the representation of a ruler."); gw.add(ProgramPurpose, (gw.getWidth()/2) - iLABEL_X_OFFSET, iLABEL_Y_OFFSET); // ideally move this 1/2 the text length to the left to centre it } /* ////////////////////////////////////////////////////////////////////////////// * * Function stringify * Usage: stringify(integer to convert); * ________________________ * stringify converts the input to a string. * * From page 729 of C++ All-In_One for dummies * * Ideally, this would be put in aheader for repeated use. * * /////////////////////////////////////////////////////////////////////////////// */ template inline string stringify(const T& input) { ostringstream StringTest; StringTest << input; return StringTest.str(); }