Looking for a C++/Java tutor

L

Ludic

2[H]4U
Joined
Jun 10, 2004
Messages
2,218
I'm taking a Data Structures and Algorithms class this semester in C++/Java at SUNYIT, and since it's my first semester at this school, I got into the section with the worst programming teacher in the world. Since the section with the good programming teacher conflicts with another class I have to take, I have to try and stick it through with this professor. Just for reference, I have a 3.73 GPA thus far, and usually don't have problems with my classes.

I guess my main issue at this point is that although I understand the concepts mostly, implementing the concepts is becoming an issue. For example, we're supposed to write a program that uses stacks to traverse a maze. I'm afraid to look at any maze programs online because I don't want to be accused of plagerism, and the professor has only briefly discussed what a stack is and how to manipulate it.

If you can help me pass this class, I would be most thankful. If you are in the Central New York area and can meet me in person, that would be even better. I'm willing to pay a reasonable tutor fee. Private message me or reply if you can help me out. Thanks.
 
A stack is a data structure wherein items are put in and taken off in reverse order (aka FILO, First in, last out). *edit to clarify a bit* Common stack operations are push (put an item on top), pop (take an item from the top), and clear (clears the stack). Peek is also a useful method (views the top item without removing it)

How might this be useful to navigate a maze? It allows you to backtrack by using the stack to hold alternatives to the currently selected path.

Hopefully that's enough to get you started... if you need more specifics I'll try to help w/out giving the answer away ;).
 
Thanks for the reply.

While I understand that whole concept of the stack, my issue with this programming assignment has nothing to do with the stack itself.

I guess I might as well put the specifics of what he's looking for here:

The maze is loaded from a .txt file.
Example:
Code: 
//maze.txt
7    //number of rows
12  //number of cols

111111111111
000100100001
101101101101
100000100101
111101111101
100000000000
111111111111
1's are walls, 0's aren't.

He'll also be using his own maze files to test the program when we submit it. The program must be able oto handle at least 2 different mazes. He also wants us to use 5 different classes for the program, which I think is overkill, because it could probably be done with just 5 methods inside one class.

I've never been taught how to input something from file into a program before. I do know how to output to file however.

He wants a graphic interface. I've never done a GUI before, although I do have some experience with applets.

He also says linked lists may help in the implementation. I'm not exactly sure how that is. I do know what is linked list is and I know how to use pointers.

I guess the starting point for me is to figure out how to input the file. And then create a two-dimensional array for the maze. From there, then I'd have to create a stack for the "rat" and initialize it to maze[0][0]; Once I initialize the stack, then I could call a direction method (which he wants as a seperate class) and use it to determine which of the three possible directions the rat could go in. IN the case shown above, I'd have to figure out how to get the rat to start at 0,1

Also, I'd like to mention that I'm a Computer Information System major, and not a Computer Science or Software Engineering major. Databases are more my speed. lol
 
Quick question... in what language will you be doing this project ;). That makes a huge difference in helping you get files into the app. I'm guessing if he wants a GUI he wants you to use java and swing, but I could be wrong >.>
 
There is no requirement for what language, we could do it in COBOL if we really wanted to. But seeing as every programming class I've taken was in Java, I figured I should do it in Java. A lot of the teaching is in C++, but the class is a lot about concepts, and little about implementation.
 
Then let's start with line reading and array creation.

Here's the java tutorial on file reading: http://java.sun.com/docs/books/tutorial/essential/io/filestreams.html

You need to consider how you tell if a line is good, junk, or what.

Creating the array is trivial once you have the file input portion working.

After that, you need to begin by finding a starting point, and figuring out how to move. The technique you are using is called backtracking. Is that enough to get you pointed in the right direction for now?
 
Ludic said:
There is no requirement for what language, we could do it in COBOL if we really wanted to. But seeing as every programming class I've taken was in Java, I figured I should do it in Java. A lot of the teaching is in C++, but the class is a lot about concepts, and little about implementation.
Click to expand...

Lol, use Visual Studio.Net and C++ to create a nice GUI in 15 minutes :)

I guess if your using Java, your assignment can't be an applet because it needs to load the text file...So in Java..will you create like a C++ exe to launch the Java app?
 
{NcsO}ReichstaG said:
Lol, use Visual Studio.Net and C++ to create a nice GUI in 15 minutes :)

I guess if your using Java, your assignment can't be an applet because it needs to load the text file...So in Java..will you create like a C++ exe to launch the Java app?
Click to expand...

I have Visual Studio.NET installed, but I haven't a clue how to use it. And it seems that everything BUT the C++ compiler works on it. I haven't figured it out. I use NetBeans for my Java.
 
Tawnos said:
Then let's start with line reading and array creation.

Here's the java tutorial on file reading: http://java.sun.com/docs/books/tutorial/essential/io/filestreams.html

You need to consider how you tell if a line is good, junk, or what.

Creating the array is trivial once you have the file input portion working.

After that, you need to begin by finding a starting point, and figuring out how to move. The technique you are using is called backtracking. Is that enough to get you pointed in the right direction for now?
Click to expand...

Sorry, I just saw this post. I'm reading now and attempting to start a build.
 
the 2-dimensional array would be the maze
find a zero on the "outside wall" of the array and run Depth First Search until you come to another 0 on the outside wall. Backtracking will allow you to find the path that your "rat" took in the maze.
(depth first search will have to be modified to work with 2d arrays... trees would work better for this i think)

Initializing array:
if you are guaranteed to get the maze.txt file in the format you have shown. I would read the 2nd line and the 3rd line and initialize an array of arrays with that many elements. Each element in the array would then be an array with 3rd line # of elements. Each element in these arrays would be 0 or 1. Read in line char by char and put into the the "row" array until you have read as many lines as the 3rd number in maze.txt said.

Search:
Search row 1, row n, column 1, column n until a 0 is found. That would be your starting point. From that point, run a Depth First search would be the one that uses a stack (is stack FILO?), if stack is FIFO then use Breadth First Search.

GUI's are something I'm starting to play around with, but I don't think it should be to bad... unless you have to show the rat actually moving.

Reminds me of AI and mazes...

Disclaimer: i might be talking out of my ass here... and not seeing an easier solution..
 
Code: 
File inputFile = new File("C:\\maze.txt");
        BufferedReader myInput = new BufferedReader(new FileReader(inputFile));
        LineNumberReader myLineNumber = new LineNumberReader(myInput);
        
        int myLine = myLineNumber.getLineNumber();
        System.out.println(myLine);
        
        myLineNumber.setLineNumber(1); //sets line number to 1
        int mazeRow = myInput.read(); //reads first character of the line
        System.out.println(mazeRow);
        
        if (mazeRow < 1) {
            System.out.println("The number of rows read from the file is invalid. Now exiting.");
            System.exit(0);
        }//end of if statement to check to make sure rows is positive
        
        myLineNumber.setLineNumber(2); //sets line number to 2
        int mazeCol = myInput.read(); //reads first character of the line
        System.out.println(mazeCol);
        
        if (mazeCol < 1) {
            System.out.println("The number of columns read from the file is invalid. Now exiting.");
            System.exit(0);
        }//end of if statement to check for positive columns

Problem is right now the print out of the rows and cols say that there are 47 of each. This is going a lot more slowly than I had hoped. The Docs made me think it read it as an int, but maybe it's reading as a char?
 
You're calling read on the BufferedReader object myInput. Which is still set to the beginning of the file, so

int mazeRow = myInput.read() //reads '/'
and
int mazeCol = myInput.read() //reads '/'

the '/' character has an integer value of 47
 
Just copy existing code that works, modify it slightly, and voila - it's yours :D

Just remove any comments that has the orignal author's name in it and you're set bro !!
 
I had to do something like this in my sophmore data structures class. I still have my book and I believe it explains stacks using the maze problem as an example. (I can check when i get home.) Assume you are familiar with basic programming logic I might could scan the pages and send em to you. Its really pretty easy once you get it laid out in you're head as it being a serious of choices.

Check if you can move. If not and move count < 1 return done or failed. If so move one position. push that move onto the stack. Check if you can move if not and move count is > 1 pop last move off the stack (think of it as taking a step back) and loop over... in a large circle that will likely drive you nuts if you have any fence post errors :-p

Anywho LMK if you want those pages.
 
LordBritish said:
Just copy existing code that works, modify it slightly, and voila - it's yours :D

Just remove any comments that has the orignal author's name in it and you're set bro !!
Click to expand...

I'm seriously afraid of being accused of academic dishonesty for something like this.
 
justin82 said:
I had to do something like this in my sophmore data structures class. I still have my book and I believe it explains stacks using the maze problem as an example. (I can check when i get home.) Assume you are familiar with basic programming logic I might could scan the pages and send em to you. Its really pretty easy once you get it laid out in you're head as it being a serious of choices.

Check if you can move. If not and move count < 1 return done or failed. If so move one position. push that move onto the stack. Check if you can move if not and move count is > 1 pop last move off the stack (think of it as taking a step back) and loop over... in a large circle that will likely drive you nuts if you have any fence post errors :-p

Anywho LMK if you want those pages.
Click to expand...

Yes, I'd love to see those pages. Thanks in advance. BTW, this is a sophomore data structures class. I've already taken the junior OOP class... You'd think this would be easier.
 
MovieMan80 said:
You're calling read on the BufferedReader object myInput. Which is still set to the beginning of the file, so

int mazeRow = myInput.read() //reads '/'
and
int mazeCol = myInput.read() //reads '/'

the '/' character has an integer value of 47
Click to expand...

So how do I tell it to go to line 2 and then line 3? I thought that's what the myInput.setLineNumber() was doing.

Thanks for your help
 
Some thoughts:

Javadoc is your FRIEND. If you're doing anything with java, use this tool. It provides you with invaluable information so you're not scrounging around trying to write your own functions to do something when it may have been already implemented for you.

javadoc 1.4.2: http://java.sun.com/j2se/1.4.2/docs/api/index.html
or the 1.5 flavor: http://java.sun.com/j2se/1.5.0/docs/api/index.html

Specifically, you'll want to look at the BufferedReader class.

For input, it seems like you have most of that down. If you want to read the first char of a line, just do a BufferedReader#readLine() then do a charAt(0) on that String. String also has substring for getting, well, getting a substring.

Now on to the meat of the program - the actual algorithm. Mazes aren't too bad. Think about if you had a lot of time and just wanted to brute force your way through a maze. Eventually most people come up with the idea of hugging a wall...the left or the right...until they find the exit. However, you also have a way of encoding state (a stack). So think about it this way...every time you come to an intersection and make a choice, record that choice on the stack. when you come back to that intersection you'll know where you've been. You can do it that way, or you could simply record every position that you've been to on a stack, and when you reach a dead end start popping until you can move in a direction you haven't been. The two approaches I've outlined are essentially the same, they just differ in implementation.

As far as a GUI, why not just output the maze to the console with some marker denoting where the "rat" is at the current step, and then pressing enter to move to the next step or something simple like that. Don't waste a lot of time on the GUI at first until you have a solid algorithm, you just need enough of a GUI to see that your algorithm is working solid. Once that happens you can delve into whatever you want to use (Swing, etc.).

As for using a couple of classes....why not? It's a good OOP practice. Think about a class for the maze, a class for the rat, perhaps a class that would read in the maze, and your main class to glue it all together.

Hope that helped.
 
Well, this is where I am currently. Although this method of inputting from file works for the sample file, the substring method won't work for every file he might throw at it.

Code: 
/*  ****NAME OMITTED****
 *  CS 240
 *  Maze Project
 */

package maze;
import java.io.*;


public class Main {
    
    static int [] [] maze;
    
    public static void main (String [] args) throws IOException {

        File inputFile = new File("C:\\maze.txt");
        BufferedReader myInput = new BufferedReader(new FileReader(inputFile));
        LineNumberReader myLineNumber = new LineNumberReader(myInput);
        
        int myLine = myLineNumber.getLineNumber(); //to determine what the first line number is, 0 or 1
        System.out.println(myLine); // print out the result
        
        //myLineNumber.setLineNumber(1); //sets line number to 1
        
        myInput.readLine(); //reads first line        
        String mazeRow = myInput.readLine(); //reads the second line first 
        System.out.println(mazeRow); //print out for verification
        int mazeRowInt = Integer.parseInt(mazeRow.substring(0,1));
        System.out.println(mazeRowInt);
        
        if (mazeRowInt < 1) {
            System.out.println("The number of rows read from the file is invalid. Now exiting.");
            System.exit(0);
        }//end of if statement to check to make sure rows is positive
        
        myLineNumber.setLineNumber(2); //sets line number to 2
        String mazeCol = myInput.readLine(); //reads first character of the line
        System.out.println(mazeCol);
        int mazeColInt = Integer.parseInt(mazeCol.substring(0,2));
        System.out.println(mazeColInt); //print out for verification
        
        if (mazeColInt < 1) {
            System.out.println("The number of columns read from the file is invalid. Now exiting.");
            System.exit(0);
        }//end of if statement to check for positive columns
        
        for (int i = 0; i < mazeColInt; i++) {
            for (int j = 0; j < mazeRowInt; j++) {
                maze[j][i] = Integer.parseInt(myInput.readLine().substring(i,i+1));
            }
        }
        
        
        
        
                
    }
    
         
  
}
 
If you examine closely the documentation for LineNumberReader you will see that it says "Note however, that setLineNumber(int) does not actually change the current position in the stream; it only changes the value that will be returned by getLineNumber()". (http://java.sun.com/j2se/1.4.2/docs/api/java/io/LineNumberReader.html). This is why javadoc is your friend.

I suggest removing all that code since it's not really doing anything.

And you're right that the substring method won't work for everything he might throw at you. You'll need a smarter way of reading multi-digit numbers (i.e. anything larger than 9). How about a while loop testing charAt from 0 until you find a character that isn't between '0' and '9'? Then use substring....well I hope you get the point.

Also, I would recommend thinking about making a Maze class that has the int[][] array as a protected/private member...then making some functions like isWall(int x, int y) to test if a certain coord is a wall. Also you could make the Maze class constructor take that String representation of the maze that you read from the file along with the rows/cols and parse it in the constructor rather than in the main class, which helps you modularize and clean up a little bit.

Anyways, you're def. on the right track. keep going.
 
He beat me to it, I was going to say toss out all the LineReader stuff. You're not using it since you're using BufferedReader.

Everytime you call the readLine method on a BufferedReader it reads the next line, so the first time you call it you're reading "//maze.txt" second time you read "7 //number of rows" etc. etc.

So knowing that take a look at your nested loops. There's two things wrong with it. The first is that you're calling the readLine method row*col times, so you're reading a line, then taking a one character substring then calling readLine again, (But the next time you call readLine it reads in the next line in the file, not the next character). You want to read the line only once for each row. (hint: i times not j times.)

Second thing that's wrong with it is you never initialize your array, so you have maze defined as a two-dimensional array but yet you never define the dimensions.

If you don't specifically need to use integers then you can simplify things a lot by having a two-dimensional array of char. That way you can avoid the whole ParseInt thing and use the string.charAt method.
 
OK, I've got the program to create and populate the array with the file correctly. Now I need to work on getting the rat to navigate the maze.

I've created two stack objects in a new class. One to push the row locations on for successful moves, and one to push the column locations for successful moves. Is there a better way to do this? I guess since I've never attempted this before, I don't know what the most efficient design is.

I've left the LineNumberReader in for the time being, just because it isn't hurting anything and it may show the professor that I'm learning some other things as well.

Code: 
package maze;
import java.io.*;


public class Main {
        
    public static void main (String [] args) throws IOException {

        File inputFile = new File("C:\\maze.txt");
        BufferedReader myInput = new BufferedReader(new FileReader(inputFile));
        LineNumberReader myLineNumber = new LineNumberReader(myInput);
        
        int myLine = myLineNumber.getLineNumber(); //to determine what the first line number is, 0 or 1
        System.out.println(myLine); // print out the result
        
        myLineNumber.setLineNumber(1); //sets line number to 1
        
        myInput.readLine(); //reads first line        
        String mazeRow = myInput.readLine(); //reads the second line first 
        System.out.println(mazeRow); //print out for verification
        String [] rowSplit = mazeRow.split("\t"); //splits the string at first TAB
        System.out.println(rowSplit[0]); //for verification
        Integer tempRow = new Integer(rowSplit[0]); //changes String to Integer
        int mazeRowInt = tempRow.intValue(); //converts Integer to int
        System.out.println(mazeRowInt); //for verification
        
        if (mazeRowInt < 1) {
            System.out.println("The number of rows read from the file is invalid. Now exiting.");
            System.exit(0);
        }//end of if statement to check to make sure rows is positive
        
        String mazeCol = myInput.readLine(); //reads first character of the line
        System.out.println(mazeCol); //print out for verification
        String [] colSplit = mazeCol.split("\t"); //splits the String at first TAB
        System.out.println(colSplit[0]); //for verification
        Integer tempCol = new Integer(colSplit[0]); //changes string to integer
        int mazeColInt = tempCol.intValue();// converts Integer to int
        System.out.println(mazeColInt); //print out for verification
        
        if (mazeColInt < 1) {
            System.out.println("The number of columns read from the file is invalid. Now exiting.");
            System.exit(0);
        }//end of if statement to check for positive columns
        
        Maze myMaze = new Maze(mazeRowInt, mazeColInt);
            //Calls custom class to create a new Maze
        
        for (int j = 0; j < mazeRowInt; j++) {
            String myRow = myInput.readLine();
            for (int i = 0; i < mazeColInt; i++) {
                System.out.println("j= "+j+", i= "+i); //for debugging
                System.out.println(Integer.parseInt(myRow.substring(i,i+1))); //for debugging
                myMaze.addToMaze(j, i, Integer.parseInt(myRow.substring(i,i+1)));
                    //Calls the mutator and inserts the values into the maze array
            }
        }  
        
        
    }
    
         
  
}
Code: 
package maze;

public class Maze {
    
    private int [] [] maze;
    /** Creates a new instance of createMaze */
    public Maze() {
        
    }
    
    public Maze(int mazeRow, int mazeCol) {
        maze = new int[mazeRow][mazeCol];
    }
    
    public void addToMaze(int mazeRow, int mazeCol, int value) {
        maze[mazeRow][mazeCol] = value;
    }
    
    public int [] [] printMaze() {
        return maze;
    }
}


Thanks again for any and all help.
 
I'm really really tired right now, so I'm not going to look through that code, but here's how I think of that problem.

Find the start on left column.
While I'm not at the right column, see if a move up down left or right is valid, push and recurse.
Definition of recursive: see recursive.
When I've made it to the right column, print stack in reverse order. That's the solution.
 
Unfortunately I don't have time to look at the code, but generally I try to say stay away from multiple stacks unless you have a good reason. (Towers of Hanoi problem uses three stacks...)

What I would do is create an object that has several variables in it, that way your row and columns will always match up.

Then find a starting location and a starting direction, say 0,0 and North. Then every move you'll be pushing all three onto the stack at the same time. Every time the rat steps forward you push the previous location and direction on the stack, then when you hit a dead end, you go back a step and change directions.
 
Movieman... how do you propose to keep track of which paths have been taken?
 
Ok, that code you posted to read in the maze rows/cols from the file is pretty roundabout. I know you're still learning, but think about not reading in the whole line, converting it to an Integer, then an integer. There is a much easier way. Try looking at Integer.parseInt(String).

Also the reading in of the maze data could be better...instead of reading in the whole line at the beginning then calling substring on that line, why not just read in one character at a time?

Finally, about the maze...why not make a Position or Coordinate class that has two members - row and col....then you can use one stack that holds these classes. As for your algorithm, just try all possible paths and whenever you move put that position on the stack. If you reach a dead end, pop off the stack (re-trace your steps) until you find another path to take. Once you get to the end you can just print the contents of the stack.
 
generelz said:
Ok, that code you posted to read in the maze rows/cols from the file is pretty roundabout. I know you're still learning, but think about not reading in the whole line, converting it to an Integer, then an integer. There is a much easier way. Try looking at Integer.parseInt(String).

Also the reading in of the maze data could be better...instead of reading in the whole line at the beginning then calling substring on that line, why not just read in one character at a time?
Click to expand...

The only reason I'm converting it twice like that, and reading the maze like that is because that's what the professor showed me during his office hours. I think he's lacking as a professor, but I try to play his game while I'm in his class.
 
are you sure you're not supposed to use a queue instead of a stack?
i had a problem exactly like this, and a queue solves it.


this is the psuedo code for the algorithm:


you need a datatype for the spaces of the maze.

class point
{
int row;
int col;
list<pair<int, int> history;
};

starting at the startpoint,
start loop
enqueue each nonwall point adjacent to currentpoint
dequeue the first element
if we are at the end of the maze, use the history of the currentpoint for our solution
repeat loop
if our queue size ever reaches zero, that means we have exhausted all possible searches.


hope this helps.
 
I'd like to thank you all again for your help. But as much as I understand the concept of what I'm attempting to do, I can not figure out how to implement what I've designed conceptually. I'm still willing to pay a tutor to take time to talk with me and walk me through an example where I can implement the concepts. The implementation just hasn't "clicked" in my head, and once I do it correctly, I'll be able to recreate it, especially having working code to reference in my archive. (Obviously, I save all of my source code from every programming class)

If anyone is willing to take the time to go over this with me for a negotiable sum, please PM me. Thanks.
 
topoftheworld said:
are you sure you're not supposed to use a queue instead of a stack?
i had a problem exactly like this, and a queue solves it.


this is the psuedo code for the algorithm:


you need a datatype for the spaces of the maze.

class point
{
int row;
int col;
list<pair<int, int> history;
};

starting at the startpoint,
start loop
enqueue each nonwall point adjacent to currentpoint
dequeue the first element
if we are at the end of the maze, use the history of the currentpoint for our solution
repeat loop
if our queue size ever reaches zero, that means we have exhausted all possible searches.


hope this helps.
Click to expand...

I just saw this. Are you referring to a linked list?

The program requirements specifically say to use a stack.
 
I'll try to explain what I meant by using one stack. (Sorry had a busy weekend and couldn't post earlier)

At any given time you know where you are and the direction your heading. So for simplicity sake you start at A2 and you're pointed East. Try turning left (facing North) and check the square ahead of you (so check A1) it's full so that won't work. So turn right (face East again) and check the square ahead of you. it's empty so take a step forward, Push A2East onto the stack, and your current position is B2East. Turn left, check the square head of you, blocked so turn right, check square, it's open. push B2East onto stack and update current position to C2East, Check north, blocked, check East, blocked, check south, blocked. Uh oh, all three ways are blocked so you're at a dead end. So pop the previous position off the stack and put it back into the current location, so now you're back at B2East, but you've already checked north and east, so check south, it's open, push B2South onto stack and make B3South the current location. Turn left, check C3, blocked. turn right, check B4, open, so push B3South onto stack and make B4South current. And so on and so forth.

x ABCDE
1: 111111111111
2: 000100100001
3: 101101101101
4: 100000100101
5: 111101111101

The real trick to this is remembering where you have been and which direction you need to turn. In my example I used North South East West, but it could just as easily be done using Left, Straight, Right. Turn left justafter you take a step forward and turn right after every failure or step back.

There is an actual term for this algorithm but for the life of me I can't remember it, it's something like color trees or gray trees or color graphs.
 
You must log in or register to reply here.
Back
Top