CS106B Assessment 2

Initial comments…

This brings me up to lecture 5 and 6, maybe 7 and 8.  Like the previous lectures, it seems some of the Stanford classes have changed or been depreciated so the example code was throwing errors.  I finally found this https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1162/lecture-videos-2008.shtml which says “Please note that the Stanford C++ library has changed somewhat since 2008, so when Julie talks about various library classes or their functions, some of the names or behavior may be different now. We’re sorry for the inconvenience. In general the concepts are the same even if a function’s name may have changed slightly over the years. ”  No kidding.  Not to worry, there are many ways to accomplish the same task.

I felt really stupid trying to do this assessment at the start.  I got the general idea of what the (random writer)  program should do and how but I could not translate that into a mathematical function, despite looking at many examples of pre-existing code. For each char, I could easily create a frequency table, but how to track what comes next.  How to build a mapping for each and every combination of characters (and what comes next) for a, aa, 00, 11, kk, c9, aaa, aaaa, aaaaa..zzzzzzzzzz???

The URS.

  1. Random Writer Program the 2017 handout is helpful http://web.stanford.edu/class/cs106b/assn/serafini.pdf  Began 15/09/2017 – Finished 20/09/2017
  2. Maze creation and solving program.  Began 25/09/2017 – Finished NEVER
  • 7 days to program

Program Setup

The Random Writer Program

  1. Try out the demo program to get a feel for thins,
  2. Review Standford’s provided classes
  3. Design a data structure
  4. Implement analysis of the source text
  5. Implement the random generation

The Maze creation and solving program

Using a bunch of container classes, Stack, Queue, Vector, Set, Maze and more to generate a perfect maze and solve it using a bread-first search.

  1. Try out the demo
  2. Get familiar with the provided classes
  3. Conceptualize the generation algorithm
  4. Generate the maze
  5. Conceptualize the solve algorithm
  6. Solve the maze.

Creating the Program Including Beta Testing

Random Writer

The first thing I hit a brick all with was the 2008 Stanford classes don’t do what the 2017 ones do.  Gotta love a lack of backwards compatibility.

  • void ReadFile(ifstream &inSourceText, Map &mapping); // variant on lecture 6 live coding example does not work as not enough arguments in Map.
    void ReadFile(ifstream &in, Map<int, string=””> &m); // works so now i need to see how to change the example function to get int and string in (though string was always the key!)</int,>

The hardest bit of this, I hope is figuring out the math and how to store the file input.  As far as I can tell, a Markov lvl 1 looks at the most popular character and then does stuff.  A level 2, would use “at” as the start text if that was the most popular series of double chars.  How to store all this in a single map or do we make 10, based on 1 char, 2 char, 3 char etc?  How is the random text created after the seed?  Random section based on the 2nd to 26th most popular sequences?  Once the seed is set, look at the next char(s) and based on the frequency of what has come after that in the past, chuck down some text? So, if after at, an e came, are we now looking at what comes after te?  So a n would have us looking at en?
After lots of head scratching and scribbling, the answer began to dawn on me.  Analyze the file AFTER getting the Markov value.  Start the output with a random n characters.  For the next char, look at the two chars in the (tracker)stack and use the size of the key value entry as the random generation (eg if size 10, chose a random position between 0-9 in the length of the map value.  Output that and add it to the (tracker)stack.  Nah, stack no good for this.  Map and Vector can do all I need. This is despite he handout saying the assessment would give the programmer practice using set, stack, queue, map and vector classes.

cs106b_assessment2_rw

t Trying to visualize what the code should do…

Here I worked through some existing code (I seem to do that maybe too much?) to figure out what was happening where.

I manged to create the DetermineSeed and SpitOutRandomText() functions from scratch as well as the so yay me.  Here’s what the demo program and my own program both spit out…

cs106B_randomwriter_possiblyfinished

cs106B_randomwriter_possiblyfinished

In the end, the code was fairly simple and used maps, vectors and lots of loops.

int main() {
setConsoleSize(800, 600);
setConsoleWindowTitle(“Random Writer – brought to you by the Markov Model”);
cout << “This program takes a source file and generates up to 2000 characters of randomised text in the style of the source file.\n” << endl;
promptUserForFile(inSourceText, “Enter filename containing source text: “, “File does not exist, try again:”);
SelectModel();
BuildMapKeyEntries (iMarkov_kOrder);
DetermineSeed();
SpitOutRandomText();
return 0;
}

Maze Solver

A specific class Maze is provided in the resource directory for this assessment.  In 2017 I needed to comment out genlib.h and add using namespace std.  The following text book, Chapter 7  http://www.cas.mcmaster.ca/~qiao/courses/cs2so3/textbook/ProgAbs.pdf details recursively solving a maze.  However the assessment says to use the breadth-first search method.

So, the maze.h says “Usage: Maze m(10, 20, true);”.  I use the following code “Usage: Maze m(10, 20, true);’ and the compiler says “undefined reference to Maze::Maze(int, int, bool)”.  I change things to Maze::Maze and get a “cannot call constructor ‘Maze::Maze’ directly [ f-permissive] for a function-style case, remove the redundant ‘::Maze].  So I remove that and get the undefined reference. I have included maze.h.  Argh!

Maze m(); allows the code to run.  When then adding m(MAZE_ROWS, MAZE_COLS, true); a “too many arguments to function Maze m() declared here” is thrown.  Given I am following the directions in the header file and errors are being thrown, I’m not even getting off the mark.  Some web searching indicates the maze.h might not be compatible with Stanford’s current libraries.  If so, it looks like I’ll not be doing part two of this (unless I figure out how to create my own base grid/2 dimensional array which is not the point as this assessment is supposed to expose me to the joys of ADT’s).  The final assessment of CS106B is called “Pathfinder” and appears to be an advanced version of a maze solver – eg, find the shorted path between two points (presumably recursively).  I expect if Maze Solver can be worked out, then I Pathfinder is easier than if I need to skip this section. I found an (open source) 2011 set of Standford’s C++ libs that included maze.h, however thaey do not work on Windows systems.  After some further investigation, I declared this assessment dead.

There’s a great explanation of generating the maze at this page: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap

Following declaring part two dead, I spent the next weeks and a half trying to get maze.h to be happy and searching for ways to create mazes in such a way that I could then program an automatic solution.

The Shipped Program

Part 1 was fine.  Part 2 was impossible as the libraries were out of date.

Program Modifications / Extensions

None

Summary

Annoying/disappointing that the maze class was not functional with current C++ libraries.  I thought this sort of stuff was supposed to be backwards compatible.

How would I make the maze if the 2 dimensional array graphical element was able to be created:

  • Start bottom left.
  • Has cell been visited?
  • >>No.  Good.  Move to an adjoining cell.  If visited, remove the wall between the previous cell and the one I’m currently in.  Repeat for all the other cells.
  • >> if visited, then do nothing besides look at another cell.
  • What this should do is remove the wall only between a visited and non visited cell which should create a maze.

Lessons Learned

Porting old code into newer versions of a programming language can be difficult / tedious.