CS106B Assessment 3 – Recursion

Having read through the handout, this might be a cut short assessment like 2 was.  There’s external links to a couple of header files that, 10 years later, may not exist.  A quick check shows them in the starter file so if I do not have similar issues to maze.h it’ll be a good time.

The URS.

  1. Warmup by figuring out a recursive binary number generator.
  2. Warmup some more by figuring out a recursive set / permutation code analyzer.
  3. 12 Steps to Recursive Enlightenment
  4. Ruler of the World
  5. Every Vote Counts
  6. Cell phone Mind Reading
  7. Recursive Puzzle
  8. Stock Cutting

Program Setup

I did not even try to figure out the recursion.  What I did was take the provided solutions and build a working program from them.  I figured that as lectures said most recursion falls into either the subset or the permutation categories, starter tools are what I need.

Creating the Program Including Beta Testing

Warmup

I ported the binary code into binary.h.  Depending on how useful the recursion code is (I am expecting very), I’ll put all of it into a recursion.h file and call the wrapper from main.  That assumes the nitty gritty of the functions stay the same.  If not, I could always overload the function and still use the header file as the go to place for my recursive solutions.

When running through IsAnagram (Lecture 10, ~30 mins), running the code produced compiler errors.  The first one was an error when the lexicon.dat file was read.  It could not be read so I used the HangmangLexicon.txt file from CS106A Assignment 4 instead  That took care of one error.  Reading the lexicon.cpp file told me this… This is a re-implementation of Lexicon – it relied on binary file formats that were not readable by students.  Reading deeper I discovered:  The original DAWG implementation is retained as dawglexicon.h.  Using this header did not allow the reading of dat files, nor did it take care of the next error (so maybe my function is/was wrong).

Next up the lexicon header file seemed to be looking for words larger than provided:  eg “boats” threw ” *** basic_string::substr: __pos (which is 6) > this->size() (which is 5)”. Argh.  Not crusty old non working headers again.  Nope.  It was a “i = sSofar…” instead of a “i < sSofar…”  I also discovered through testing that the hangman lexicon included 5 character word and up.  Anything with 4 chars would return a bool of false.

20171011anagrams

20171011anagrams

12 Steps to Recursive Enlightenment

I figured a base case would be 2 steps.  A single large stride or two small.  The max would be numStairs * small stride and (numStairs / 2) as long as there was no remainder.  How to package the program to step through iterations of s s s, s s l, s l s, l s s, l l s etc?  When I peeked online for answers, I could see what code did, but why and how eluded me.  I wanted to understand what was going on before trying to move onto Rule of the World (and ideally, create my own recursive function that was different to the one(s) I’d peeked at.

After watching Lectures 8-10 of the “old” CS106B lectures, I moved onto the newer ones on the same subject by a newer lecturer.  The first one I saw incorporated test code into the program.  Nice.  I then figures out that before moving on.

Though I found some code online that works for the recursion, I do not know why it works.  Looking at the NumStairs return, ut looks like (in the 6 stair example), “5 + 8” is returned and mysteriously added, however I suspect that calls 10, 11, 12 and 13 were not shown, but somehow tracked and returned as the stair climb variation number.  Argh!  This bit of the assignment shall remain with the ‘borrowed’ code.

Ruler of the World

I could visualize the next task fairly well, though my graphic calls were obviously wrong.  The only things working at the start was the base line for the ruler and bit of code that drew the two smaller boxes.  It looks like I am missing a bit of code (assuming it exists) that allows me to draw into a graphical element.  It looks like the code’s taking 0,0 and drawing the origin points of the rectangle1 and rectangleLHS from there.  Why the center line is off when I call rectangle->getWidth() is perplexing.

What's not going on here that should be???

What’s not going on here that should be???

I eventually worked our I was using a getHeight when I should have been using a getWidth.  After correcting the code and removing a few small bugs and commenting out debugging helper code, I get to below.

That’s a base case and a non recursively coded “draw LLHS and RHS rectangles and show their middle with a line”…

The students in this course either have a great advantage as they can talk to class tech about this or they a re a heck of a lot faster than I am to work things out.

Not far to go if packaging the code into a recursive function works...

Not far to go if packaging the code into a recursive function works…

Trying to port this to a recursive function was not going to work as the code was too complex.  I rewrote it to entirely remove the gRect’s I’d created as the lines could be drawn knowing the values of w and h only.  There was no need to introduce rectangles to figure out widths from – here I was hoping the recursion would divide the w x h each iteration and “magically” do it’s thing.  Nah, the program got stuck in an infinite loop which would do the non base case, get to the base case and then repeat the non base case (somehow after ‘w’ getting below ‘5’ it would then be above ‘5’. Additionally, the RHS part of the graduations would only draw when the LHS code was commented out and the LHS code would sort of go nuts (that’s the technical term).

At this stage I compared my code to published code.  The way to call the recursion was thought out the correct way, but my formula was iffy (as was the published code which drew the recursive lines at the top of the rectangle and flipped the lines as well).  A little bit of tweaking and I had this done with a lot less help than part 1.

Every Vote Counts

Here I got to re-purpose code for examining subsets and for reading in text files (that way I could automatically input the data for the voting blocks).  Issue one arose soon after.  How to is a ifstream to read into an array of ints.  Seems the compiler said no,  Trying to use strol would not work when reading the array of strings.  ie:

sWorking = “20”; //&arrVotingBlocks[i]; // cannot handle anything other than a direct quote – argh!
iConverted = strtol (sWorking, &p1, 0);

It seems crazy that file reading would not have the ability to read in numbers or there was a prebuilt function to convert strings to unto in C++ and failing that, it sounds like something a first year student would be asked to do as an assignment.  Eventually I found stringstream and at the same time, found out my text file should have had an entry to a line, not have everything on the on line separated by spaces.

OK, onto the actual recursive function.  Here I decided the base case would be at least two blocks.  If block 1 assigned to Candidate A, would Block 2 make candidate A or B win?  Here we also need to know the total available votes as a win would be if ((total votes for candidate X >=  (total votes x 0.51)).  So if block 2 was above the abs majority, then that would be critical.  Back to Lecture 10 at around the 24min mark as I had my backtracking code, but not the exhaustive permutation code from which it was derived.

In the end I had no idea what was going on and “borrowed code”.  I was wondering what the point of continuing to learn to program was if I could not work out the underlying mathematics needed to produce a result.  I did discover than evern after running the program, for >24hrs, a full 51 block exploration did not produce any results.  Plenty was going on in the background, so that’s one for a super computer!

Cell phone Mind Reading

The Internet was not working at my location for this one so no peering at code (or being tempted to).

This one needed a lexicon. I’d already created that for the anagram warmup so yay there (aw, that was specific to looking for anagrams so not so much yay). The SeekInput() code I created for the choice selection part of the program I could use to grab the “key presses”. Presumably I would be able to modify the IsAnagram recursion to sort for words starting with the key presses rather than every combination of. To get things working I’d need to assign each key to a certain set of letters (much like the Soundex code from assignment 1 (aw, not so much as that was a bulk conversion, this one needed to be done piecemeal)). The assignment pdf said to look at ListMnemonics from section 3. I created my own ToString function earlier, so that might come in handy for the conversion.

I got the sample mnemonic code working and figured I’d send the output of that into an array. The array could then be iterated through the lexicon once to find matches and then twice to see if the value in the cell was a prefix of a word.  I then managed to show a “match found” output when searching the lexicon.  My code must have been REALLY bad as it took ages to a search once I got up to a 4 number entry.  I was running an exhaustive search rather than a backtracker which most likely was doing.

Expensive recursion - mobilemindreader

Expensive recursion – mobilemindreader

So, at this point I could identify if a word was match for a prefix in the lexicon and if it was not a match, I could delete it (though only a combo that did not match).  Somehow I needed to get the words that START with the prefix (inc. the prefix) out of the lexicon.  Back in 2008 there appeared to be a containsWord function for the Stanford lexicon.  Now there is not.  Maybe I should convert the lexicon to an array and then look for matches based on the lexicon matches (entered into yet another array) for tracking)). Seems like a bunch of double handling to me!  I decided to see if I could get the old DawgLexicon to do what I needed.  Nope  “does not have a containsWord”.  Argh.

Ha!  It looks like I spent 2 days on and off trying to think of a way to get the output I wanted when “lex.contains” actually did the job.  Running the program, it looked like I was getting the same output as for “lex.getPrefix” but no.  Yay there.  I managed this project all on my own!

Recursive Puzzle

Lots of scribbling on paper for this one.  I figured out I needed to start at a 1 or 2 cell array and work left and right (but not outside the bounds of the array), see if the value in the cell could advance to the target cell and match a target number. Once I got that out of the way, I needed to make it recursive.

recusivepuzzle_earlydays

Hmm, not sure the code that got me to the result above is actually any good for a recursive analysis.   It might be time to go back to the drawing board.  After playing around with the code some more, I decided to look at published versions.  The first one I found used an array to track the results, which did not follow my line of thinking at all.  Back to the back tracking lecture again.

Rather than my first idea of running from the last cell backwards, I rethought this and started at cell 0.  The goal was to get to a cell with a value of 0.  There would only ever be a single 0 value cell and it would always be in the final location.  I coded to make sure only valid array referenced were looked at and if a forwards exploration worked, keep going.  If it failed, go backwards.  It looked like I’d finally worked this one out (after weeks of on and off programming, ahhh life).  However, after some beta testing, I found that an infinite loop (recursion) could be entered with no final fail case.  That lead me to see the value of the solution I found online and ignored on purpose.  It used a “have we visited this cell before” check.

So, keep programming this, or leave as is as I know how to get it working and I’ve spent ages on it…

Many many notes and scribbled ideas on how to get this to work

20171121_a recursivepuzzle (CS106B) – keep going or continue?

OK, I could not resist having a crack at a working program.  For whatever reason a false flag was not being sent back when it was meant to be so everything but when the first cell would go off the end of the array came back as true.  Using the bool as a visited cell concept from  https://github.com/brianjscoles/CS106b-solutions/blob/master/3%20-%20Recursion%20Exercises/5%20-%20puzzle%20solver.cpp I added a check into my recursion and amazingly, after a little bit of debugging, got my own recursive code to work, yay.

Stock Cutting

The assignment says this one is tricky.    Presumably it draws upon what I am supposed to have learned in the previous exercises.  If I can grok the maths (as in what we want to the program to do), presumably this one will not take me weeks to figure out. Wikipedia has an entry on this problem.

After trying to work this out and looking at two different solutions: solution 1 and solution 2,  my head hurt and I was thinking of skipping this. However, as I’m treating this like a proper uni course I was compelled to figure it out no matter how long it took.  Not working this out will probably make subsequent assignments harder than they should be too.

Soooo, here I worked through an existing solution trying to figure out what was done.  After tweaking it, it worked though would not give the correct answer.

20171201 Almost There

Hmmm.  At least by this point I could see why an array of array was being used to track the solutions and how they were being used to assign the smallest solution.  I was a bit foggy on the actual recursion (not what it did, only how it was coded).

A ha! I’d left off the code that removes used pipe cuts from the pipe request array.  That got things working.  This solutions shows the pipes to be cut.  The assignment did not require this.  Given the array used to track what is the smallest solution has the pipe combination, it would be nuts not to spit it out at the end (which is what I would have done even if the code developed was my own.

The Shipped Program

With work and other bits of life getting in the way, the warmup took about 2 weeks of here and there attention.

20171010_recursion_warmup1a2

20171010_recursion_warmup1a2

Clearly this works, but how? Am I missing something obvious?

Clearly this works, but how? Am I missing something obvious as I don’t know why.

20171019_ruleoftheworldfinal

20171019_ruleoftheworldfinal – managed to do 80% of this without help

Mobile Phone Mind Reading Complete

Mobile Phone Mind Reading Complete – 100% me.  Phew!

CS106B – A Recursive Puzzle completed!

CS106B’sw Stock Cutting Recursion Assignment Complete

Program Modifications / Extensions

The only addition here was outputting the combination of pipe pieces to cut.  The assignment did not require it.  It’s seems amiss not to provide such information, especially as the array with the solution has the data.

Summary

Good times over all.  No old crappy header files and I got better as the tasks progressed.  Disappointing I could not debug A Recursive Puzzle.  Great I codes the Mobile Phone Mind Reader all on my own,  Not so good I needed to work through existing code for the StockCutting Solution.  At this rate I’ll be great at modifying existing code (just like I w as in my Basic 7.0 days), but be crappy at coming up with my own.

Lessons Learned

The important of reading notes in header (and associated) files as what someone tells you a library does may not be correct.

I have the general idea of how recursion works, though it’s still fairly black boxy (despite thinking about it while commuting and while dreaming).

The Code

This is a text file with the cleaned up code: The code (binary.h and ruleroftheworld.h not included).