7 replies to this topic

[flamereaper]

Ok. i am in need of some more help from the all knowning legion of the forums.

Learning java in computing atm. And as part of our project we had to remake a Tower of hanoi solver in Java. A simple program that with a bit of work i was able to translate from the BASIC that we already had done before.

But heres my problem. Solving 10 rings takes 1023 moves, works just fine, but when i try 11 it takes more moves and during the console tracing back which rings to move where, i get a huge list of the following.

at hanoiSolver.part1(hanoiSolver.java:60)
at hanoiSolver.part2(hanoiSolver.java:71)

Both of these lines in the java are calls for the part2 function.

I was told the problem may be that java has run out of memory and so wont trace back anymore. Another said that with this many moves, the code runs soo many iterations, that maybe java just stops running them properly.

Can any one tell me why this happens, and if they know, How to stop it happening, so that it traces all the instructions back as it should?


The whole .java code can be found here. >> http://www.yousendit.com/transfer.php?acti...1D6261C6B2BA2F7 <<


Thanks a bunch all.

[birdbrain24]

I would really like to help but i ain't bothered to learn Java yet sorry i will tell my friend to see if he can help you he knows Java and he is the one the does all my Java for me!

[rc69]

Bird, if you can't be bothered to help, the please don't bother posting.

Flame, there are two things i'd do differently here:
1. Use a scanner rather than bufferedreader. But that's personal preference.
2. Unfortunately it's been to long since i've solved this, so i don't remember exactly how i did it. What i did remember is nothing like what you provided. I don't know where you came up with that solution, but mine looked more like the following (it is in C, so you'll just have to translate a bit).

void move(int n, char src, char dst)
{
		/* moved disk n from peg src to peg dst */
}

void hanoi(int n, char src, char dst, char tmp)
{
		if (n == 0)
				return;

		hanoi(n-1, src, tmp, dst);
		move(n, src, dst);
		hanoi(n-1, tmp, dst, src);
}

[MetalSkin]

If your still having problems I'll try and have a gander at this tonight mate (which is in about 8 to 10 hours from now).

[flamereaper]

Yeah we got the algorithm from our teacher, he just had a sheet with the logic flow on it and we had to turn it into code. Originaly it was done in BASIC, now were converting it to JAVA, so i have no idea if theres a quicker way out there than the one we are using, but oh well.

as for the C code, i have no idea, it looks very short to me and i dont really know C so i wouldnt know where to start.

thanks for the help. look forward to seeing if metalSkin cna come up with anything.

[MetalSkin]

I was going to look at it now but my partner is giving me that look (the look that says I had better spend some time with her if I ever want to be able to use the computer again ).

I've got a problem with vista at the moment so later tonight I'll boot up my lappy and have a gander for you mate. Hopefully I'll be able to give you an answer then. Sorry for the delay, just been a big day at the office

:edit:

Okay, the problem is because your using recursion in the logic. Each time you call a method your using the stack, and by using recursion your hammering the stack. I changed the code to print how many moves would be required and it said 2047 moves. It crashes on my system on move 1268.

Now the error your getting is really:

Exception in thread "main" java.lang.StackOverflowError
		at sun.nio.cs.SingleByteEncoder.encodeArrayLoop(SingleByteEncoder.java:91)
		at sun.nio.cs.SingleByteEncoder.encodeLoop(SingleByteEncoder.java:130)
		at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:544)
		at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:252)
		at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:106)
		at java.io.OutputStreamWriter.write(OutputStreamWriter.java:190)
		at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:111)
		at java.io.PrintStream.write(PrintStream.java:476)
		at java.io.PrintStream.print(PrintStream.java:619)
		at java.io.PrintStream.println(PrintStream.java:756)
		at javaapplicationtest.Main.part2(Main.java:84)

The important part is the first one, which is the StackOverflowError. This means you've exceeded the stack via your recursion. The reason why you get the last line repeated for part1() and part2() is because the Exception when thrown is showing a complete stackTrace, and you guessed it, there's a lot of em to print!

The solution is either to remove the dependence on recursion or to increase the stack. If at the command prompt you type in:

java -X

you will get a listing of the non-standard options for the java command. The one your interested in is:

java -Xss<size>

This lets you increase the size of the stack. I think the default size is 256K. So you can try and increase it when you run your program. I tried it on my system and found using the setting of:

java -Xss1m <classname>

Worked a treat. The 1m means 1 meg. Note however I'm running a 64bit version of the JVM and while I doubt there are differences, you just never know.

Now to simplify the code you could use the logic by rc69. That seems to use common logic on the net after doing a quick google. I'm familiar with the Tower of Hanoi puzzle but never looked at the algorithms used in solving it.

I did however find this http://www.cut-the-k...nce/hanoi.shtml which has a good discussion about the maths involved, talks about the recursion issue and some links to the maths on different algorithms to solve the problem.

Overall there is nothing wrong with your code at all, it's just that as you add more to move you increase the amount of recursion by a substantial amount.

Hope that helps mate

Edited by MetalSkin, 13 July 2007 - 06:52 AM.

[flamereaper]

Brilliant, thanks metal skin. No problems on the delay, just glad you could heglp.

Ive had a look at at the momment my maths skills and time dont allow me to look at any other algorithm for now. So for the time being the stack size works just fine Big thanks for that. Ill haev to look at the other ways of doing it aty some other time.


thnkas again all.

[rc69]

flamereaper, on Jul 13 2007, 01:51 AM, said:

as for the C code, i have no idea, it looks very short to me and i dont really know C so i wouldnt know where to start.

You know Java? Then you know C. The problem here lies in coming up with the move function. I didn't take a good enough look at your code to understand it before, but it looks like this would be a nice alternative.

/**
***Hanoi Solver in Java
**/

import java.lang.Math.*;
import java.io.*;

public class hanoiSolver {
		private int moveNum=0;
	public static void main(String[] args) {
		init();
	}
	
	public static void init(){
		int totalRings = 3;
		System.out.println("How many rings do you want me to solve? ");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			totalRings =  new Integer(br.readLine()).intValue();
		}catch (IOException ioe) {
			System.out.println("IO error trying to read your number.");
			System.exit(1);
		}
		if (checkTotal(totalRings)){
			hanoi(totalRings, 0, 1, 2);
		} else {
			System.out.println("\n\n\n");
			init();
		}
	}
	
	public static boolean checkTotal(int n){
		double totalMoves = (Math.pow(2,n)) - 1;
		System.out.println("tMoves: " + totalMoves);
		if(totalMoves > 1000){
			String choice = "";
			System.out.println("Solving will require over 1000 moves.\n\nDo you wish to continue? (y/n)  :  ");
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try {
				choice = br.readLine();
			}catch (IOException ioe) {
				System.out.println("IO error trying to read your choice.");
				System.exit(1);
			}
			boolean ch = choice.equalsIgnoreCase("y");
			return (ch);
		} else {
			return (true);
		}
	}
	
	public static void hanoi(int n, int src, double dst, double tmp){
		if (n == 0)
			return;

		hanoi(n-1, src, tmp, dst);
		move(n, src, dst);
		hanoi(n-1, tmp, dst, src);
	}
	
	public static void move(int n, int src, double dst){
		System.out.println("Move number: " + (moveNum++) + " Move ring " + n + " in direction " + Integer.toString(d) + ".");
		}
}

I'd test it, but my laptop (dev comp) is sorta out of the way at the moment, so i can't.

I do realize you have the stack size increase working, but i believe if you get this working your teacher will be a bit happier

Edited by rc69, 13 July 2007 - 02:33 PM.