CS106B Assessment 4 – Boggle

November and December were busy work months.  Delivering training  in Melbourne.  Off to Perth for a week to do the same thing.  A quick stop over in Moscow for a work shindig and the usual time sinks caused by the festive season.  This brings me to January where my programming skills will have tarnished a little.  Roll along to the end of April and I’m still trying to nut this one out.  I’ve gone back to pseudo code and trying to picture everything as my head feels like it want to explode, scanner style.  Finally I had some time to revisit this in August 2018!

The aim here is to give students more practice designing and implementing recursive algorithms.

NOTE: this page is going to be fairly waffly as I’m updating it as I go with “this did not work, and this worked, and I’ll need to try this next”.  Think of it more as a diary as I develop a program.

The URS.

  1. Using the provided graphical function/class, create the classic (trademarked) game Boggle.
  • 9 days to program

Program Setup

Human player turn

  1. Entered word must be >= 4 chars
  2. Word must be in the lexicon
  3. Word cannot have already been chosen (even if alternative path to the word)
  4. Word can only be formed from the board following a “are the characters adjacent either left, right, up down or diagonally”
  5. User input is case insensitive.

If the above is false, word is rejected.  If true, score count = score count +1.  Word highlighted for (say 1 second) on the board.  USE PAUSE FUNCTION & GBOGGLE.  Score determined by word length.  1 for 4 letters, 2 for 5, 3 for 6 etc.  Word displayed on LHS of screen.  Carriage return with no input is the sentinel.

Computer (AI???) player turn

  1. search the board for all possible remaining combinations of 4 letter and above words
  2. Same deal as for Human player turn requirements.

Containsprefix will come in handy as will the recursive functions I’ve already developed (I expect).  NOTE:  for the human turn, the containsWord did the job.  Is this a program efficiency thing?

The assignment pdf says the grid class and lexicon classes will come in handy.  Given the grid class was not used in the maze solver assignment as the maze class was depreciated, I have doubts I’ll be able to even start this assignment.  As discovered in previous assignments, the lexicon.dat cannot be used so I’ll be using HangmanLexicon.txt again. This limits us to characters a minimum of 5 characters long.

Issues at the start. lexicon.h, gboggle.h both referenced genlib.h which no longer exists. I changed that to iostream.h.
Next extgraph.h did not exist. I changed that to graph.h.  This then threw a load of errors in the gboggle.h and gboggle.cpp files.

The changes to lexicon.h resulted in loads of compiler errors so I copied lexicon.h and lexcon.cpp from the first recursion assignment into the current project’s library.

Next there was no strutils.h.  Argh.  I changed this to strlib.h.

At this point, it looked like before I could get anywhere, I’d need to debug the whole of the helper functions rather than get busy with recursion.  This went into the two hard basket.

Boogle – depreciated to death?

I’ll ponder this overnight.  I may just write pseudo code here to show what I would have done had the provided graphical element worked.

Ok, new day…I jumped online to check out Stanford’s site.  Often one will find newer code.  They had the starter code for Boggle from 2017 here.

In the package were 4 cpp files, 2 header files and a text file with instructions.

I was a bit rusty on incorporating other cpp files into a program. Had I done this with C++ or was that only covered (so far) in java? The good news is that with all of these files the src directory, the bare bones program ran. Woo hoo. It looks like I can get underway.  As an aside, this means the header files binary.h and ruleroftheworld.h I developed and split off can stay in the src dir and do not need to be put in the lib directory.  Good to learn/know.

“Bare bones” program.

There was also a snazzy video regarding this assignment…

Since the 2006 assignment was written, a shuffle.h has been introduced so there’s no need to write my own shuffle algorithm.  Looking at grid.h, there is also a shuffle routine.

Creating the Program Including Beta Testing

Cube Setup, board drawing, cube shuffling.

Here I needed to use both Boggle.cpp and boggleplay,cpp to build the game and get either the random starter cubes show, or my custom text.  I started with a custom string first.

First off I used a custom string of either 16 or 25 chars.  That worked.  I needed to wrap my mind around how the string was stored and how the recursion could examine a “guess” against the letters shown.

Originally I’d converted the array of strings that Boggle.cpp created back into individual string so a random seed string could be created.  That seemed nuts to me as there should be some way to look at each position on each string in the array.  Looking through the course reader gave me the answer:  CUBES[i].at(j).  This allowed me to create a string to send to the GUI and at the same time create c vector of chars that could be shuffled.  Here I went “hmmm, we do not send the string until the shuffle, so I can create the string from the vector, or just send each element of the vector to the gui.

What caused me trouble here was trying to call anything else other than Boggle Boggle(dictionary, word);  Eg. test(word), Boggle.test(…) or Boggle::test(…) would throw compiler errors.  I was trying to see if the vector I created could be read from Boggle.cpp by Boggleplay.cpp via another function as I wanted to know if I needed to send each element into the stack (i.e. use pointers).  Something like expected unqualified ID before. or : token.  None of the existing solutions posted online seemed to be the same version of the assignment I was doing, so I would need to work things out for myself.

After about a day’s work (on and off in between non employer based study time), I finally got the grid to form without missing characters or program crashes.  However, the chars were inserted down not up.  Hahaha.

Obviously should be counting up the cols and keeping the rows constant.

This was an easy fix.

Ta da. All set for the next section.

So now I have my grid of characters (and probably a lot of double handling as I created a string (to send to the gui) and a vector (to send to the grid).

Human’s turn (excluding findings word on the board)

Here work on taking input, ensuring it is >3 chars.  Add it to the GUI.  If already present, send an error. Score words based on size. Here we are testing function.  The search is in the next milestone.

I can see the code for the scoring.   I’m pretty sure I know how to ask for some input and send it to the appropriate class (…pretty sure).

Right, I got stuck almost immediately.  checkword(string); resulted in an error despite this being a function of the boggle.h.  Using Boggle checkword(string); threw a “invalid initialization of a non-const reference of type ‘Lexicon’ from an rvalue of type lexicon” error.  Using Boggle checkword(string string); did not throw an error.  Umm.  When I send a string as a reference, the compiler says no.  When I explicitly state a string, all is well.  So, the program likes a set string, not any old string.

A search online for existing solutions was a head scratcher.  Lots of solutions.  No one seemed to do what the assignment required.  People were using boggle.cpp to seek and show input in the console instead of boggleplay.cpp.  Sure I could do it that way, though presumably I would not learn the joy of using classes properly.  Here I came up with the ideas of using the main boggle.cpp routine to decide what to do based on the length of character input.  I figured a 16 letter solution was pretty unlikely, so if a 16 or 25 char string was entered the board could be built, while if a less than 16 (but not 0) was input, the search the grid for solutions could be called.  According to Google, there were 44 English word possibilities if Qu was used.  This could be a fudge, though I felt better logic was needed.

It also looked like people were screwing around with the names and formats of the provided functions while ditching boggleplay.cpp and putting that into boggle.cpp as a function.  That’s not what the instructions say is allowed.  Perhaps that is how it was done one year, though I doubt it.  OK, some more searching shows that at least the 2013 version of the assignment seemed to not use as many files as the 2017 version.  Looks like I’m on my own figuring out this one as…

“The playOneGame function (along with any sub-functions it calls within the same file) should perform all console user interaction such as printing out the current state of the game. No other file should have cout or user/file input.”  So, somehow I have to send the user input word guess to the boggle class and get it to be a &string (and so far every combination of instructions I can think to type come back with errors).

Back to the thinking…

I rejigged the code to returns strings and not numbers to make debugging easier (eg large_game, random_game).  As I am yet to figure out how to get the boggle.cpp to so anything other than generate the game board, I coded the dictionary check from boggle.play (for the time being).

The most recent run of the program saw my test string randomised.  Argh.  Ha!  Test code was sending a specific string.

So, up until this point, 90% of the chat in this section has been about how I’ve got the GUI to work.

I finally got a call to boggle.cpp to work, however that included setting up the lexicon again in the specific function. I needed to set up another Lexicon which I expect is bad style.  I must be missing something (memory pointers? put and get functions?).

A week later I’m almost done with this section.  Scoring is setup (but buggy).  Text is sent to the GUI including a concatenated “you have found a new word ‘foo’ “.  The function’s written in boggleplay mostly and stored a dummy list of founds words and the player’s score in boggleplay.  It needs to run and store out of boggle. I can work on the recursive code, but really need my gameGrid<char> that was created earlier in boggle to be accessible from boogleplay. Perhaps it is in memory, I’m just not calling it correctly.

Okay, after a week off to think I discovered that assigning static to the variable in the class kept the variable in memory and therefore it was accessible through all instances of the class.  That meant (for starters) my gamegrid was now in memory.  Next up, I needed to create and store a grid of (correct) guesses.

Find a given word on the board

Hmm, let’s have a think.

20180125_code_thoughts

So, look in cell 0,0.  Does it equal SearchWord[0]?  If yes, good.  Does our next looked in cell match SearchWord[1]?  If the word can be found, eventually cell(x,y) would match SearchWord[Searchword,length()].  If that happens word found.  Send SearchWord int Vector . If the check is out of bounds (off the grid?) an int exception needs to be returned.  Does that mean coding the grid limits is not needed as if intException =500, skip to next cell?

Once I’d figured out most of what to do up to this point, the code was getting large thanks to comments.  I was considering starting again to develop cleaner code (or printing it all out to see how to set things out better.

This is taking an age to complete as programming requires my full attention.  The distractions of work (self study is done when I can do it) is not allowing me to get into the zone.  At any rate, I have a for loop that is the beginnings of my recursion planning.  I’m probably shooting myself in the foot by trying to work off one monitor and keeping everything in my head rather than grabbing a pen and paper (or even referring to the above image, hahaha.  yeah, perhaps I should do that).

20180227_slowly getting there

Details of recursion creation

I began to revisit assignment on 26/04/2018.  What I had in mind was code to explore all of the GameGrid for a match to SearchWord[0].  If there was a match, then the surrounding cells would be explored for a match.  If the code got to the last char in the SearchWord and the GameGrid reference matched the final char in the search word, a true would be returned and the loop would break.  A false would continue so if SearchWord[0] was in more than one location the additional references would be explored.  An ultimate result of true would mean the SearchWord could be formed from the GameGrid.

August 2018

My scribbled notes…

After about 6 months of work and non work getting in the way of working on this project, I got back into it.  Things seemed to start well then I got stuck again.

I managed to get a “search around” function working, but it looped incessantly, working on word[0]…[n].

After a day of fluffing, I decided to really go back to basics.

1. make grid
2. search and mark grid.

From there I’d create the search for word[0] and then search around, all the cells if the 1st search failed to find word[n]. I’m sure that was working in an earlier iteration of code earlier in the week, but tweaking things killed it.

I got my program to identify matches for word[0] and to correctly search around a hit. However, I could not get it to unmark a hit and continue searching in the event of an unsuccessful search (maybe remark everything as not searched, or look for marked cells and unmark of another hit found…seems a lot of work for a simple action). Presumably are recursive function could be used here. Currently my brain is fried so I’ll need to think of that again later.

All of the solutions on the Internet were nothing like how I coded my program. That might mean I’m crap, choosing a different though valid solution or other. It certainly makes trying to program myself a tad hard.

Positives so far:

  • I got the first word check to work.
  • I got the search around to work.

I appeared to get it working. It certainly returned a word found result from a valid search (i.e. “A”) though the program appeared to be doing way too much. When searching for “AEROPLANE”, my VM BSODed. It’s been doing that a lot when I use up lots of memory, so I might need to rebuild it. Anyway, once I fired up the VM again, I ditched the text outputs and ran the program with a shorted positive “ROPE”. The program crashed with an infinite loop warning.  I built a new VM.  No more crashes.

I then ran with a negative “Q”. Argh. The base case failed. Hmmm. Progress?
After some more coding I seemed to be getting somewhere…a positive word is found. An incorrect word is not found. A word with the positive chars but errors also reports word found.
Eg rope = y, beet = y, aeroplane = y, muffy = n, feet = n, AEROQPLANE = y (eh!!)

What boggles the mind is I pruned a hell of a lot of code and the function works much better even with the errors.
Some more tinkering and I got a failure case to return a fail, though now qa success case returns a fail. Argh.

Ok, after too much stuffing around I’m starting from scratch.

Take 2……………………

Getting the program setup and up to the bit where the recursion runs was quick and easy. Pleasing to see I’ve learned something. Along the way, my coding was much nicer and less convoluted. The aim here was to make any “main” sections as simple as possible with the actual hard work sent to helper functions.
http://web.stanford.edu/class/archive/cs/cs106x/cs106x.1174/assn/boggle.html = even newer assignment

After more faffing around, I grabbed a pen and paper and wrote down the code I thought would work.
After typing it out and debugging, some words would not hit the base case and still yield a positive. Clearly there was a true return where there should not be.

After a few more days of on and off coding, I got unfound words to not be found and found words to be found. Things got stuck if the found word was present further into the 16 cells of the game with multiple starting words being matches. I fixed that by changing the code to only return a true is the word[0] was a match AND the subsequent search returned a match. So. after over 8 months of playing around (haha, real world sacking / fail if this was”real” uni, I got the human search to work. I assume the computer search will be relatively easy compared to the human search, but I’m not going to hold my breath.

Once the human search appeared to be working, it would fail to find words beginning with, say R, when there were multiple R’s ont eh board and the first R gave results.  I soon figured that one our and the human recursion was finally complete.

base case found…

CS106B Boggle Base case working

CS106B Almost there

CS106B Boggle Success!

Find all the words on the board (computer’s turn)

This was far, far, far easier than trying to work out the human code.  It tool me about 2 hours to scribble out ideas and type up the code.  Rather than using a bool function, voids were (mostly) used.

Loop to play over and over again.  “Add polish”

The loop was already in place.  While developing the program, I also included the 5×5 game.  The one bug that eluded me was that now and then, pressing enter would say “it is not the computer’s turn” and send me back to the human prompt.  Pressing enter again would continue to the computer’s turn.

CS106B Boggle Working. Needs a little tweak.

I almost forgot to implement the human vs computer score check.

The Shipped Program

The shipped program is much the same as seen in the screen shot below.  I removed the highlighting for before the computer code ran and that was that – the 5×5 game shows this.

The major bug was not being able to move from a 4-5 grid or 5-4 grid game is after the first game.  Reinitializing the graphics window using close terminates the game.  This is contrary to what the Bogglegui.h says it should do. “Closes and discards the graphical window. This differs from shutdown() in that you can call close() and then call  init() again to make a new window (perhaps of a different size)  while shutdown() totally closes down the Stanford C++ graphics subsystem.”

CS106b Boggle 4×4 working game

CS106b Boggle 5×5 working game

Program Modifications / Extensions

5×5 game.

Summary

Wow.  I am not sure what I got stuck on here.  Maybe I just needed 8 months for recursion to percolate through my head.  Not having solutions online that looked anything like what I was doing may made things a tad tricky as I could not even borrow (or test) code that was not mine.  That is good.  I learned on my own (ideally I’d have mentors, but oh well)

Lessons Learned

How a static reference means the values are put in memory for use from other functions.  Very handy.

I also finally figured out what private and public functions are actually used for (and how).