Thread: Removal of gotos

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    39

    Smile Removal of gotos

    Finally back at looking through code...I am trying to eliminate the gotos in the sudoku function below:


    I have eliminated simple gotos before...

    Code:
    double sum = 0.0;
         
      int x = 1;
      repeat: sum += 1.0 / x++;
    
      if (x <= N)
        goto repeat;
    
      printf("The sum of the first %d reciprocals is %lf\n", N, sum);
    
    Removal:
    
    double sum = 0.0;
         
     int x = 1;
     do
     {
            sum += 1.0 / x;
            x++;
     } while (x <= N);
     printf("The sum of the first %d reciprocals is %lf\n", N, sum);
    Now, I am trying to eliminate the 4 goto statments without using breaks or continues...

    Code:
    bool sudoku_solver(int sudoku[][9], int& diff_single, int& diff_line, int& diff_row, int& diff_block) 
    {
    	bool empty_fields = true;
        bool operation_done;
        int counter;
    	int empty_fields_counter;
    	int sdk_to_solve [9][9];
    
    	diff_single = 0;
    	diff_line = 0;
    	diff_row = 0;
    	diff_block = 0;
    	
    	int sudoku_bool[9][9][10];
    
    	for (int n = 0; n < 9; n++) {
    		for (int m = 0; m < 9; m++) {
    			for (int p = 0; p < 10; p++) {
    				sudoku_bool[n][m][p] = true;
    			}
    		}
    	}
    	
    	for (int m = 0; m < 9; m++) {
    		for (int n = 0; n < 9; n++) {
    			sdk_to_solve[m][n] = sudoku[m][n];
    		}
    	}
    	
    	//main solver
    	while (empty_fields) {
    		operation_done = false;
    		//Scanning
    		for (int n = 0; n < 9; n++) {
    			for (int m = 0; m < 9; m++) {
    				if (sdk_to_solve[m][n] != NULL) {
    					for (int i = 0; i < 10; i++) {
    						sudoku_bool[m][n][i] = false;
    					}
    					for (int i = 0; i < 9; i++) {
    						sudoku_bool[m][i][sdk_to_solve[m][n]] = false;
    						sudoku_bool[i][n][sdk_to_solve[m][n]] = false;
    					}
    					for (int k = 0; k < 3; k++) {
    						for (int l = 0; l < 3; l++) {
    							sudoku_bool[(3 * (m / 3)) + l][(3 * (n / 3)) + k][sdk_to_solve[m][n]] = false;
    						}
    					}
    				}
    			}
    		}
    		//analyze scanned pattern 
    		//single field defined value?
    		for (int m = 0; m < 9; m++) {
    			for (int n = 0; n < 9; n++) {
    				int counter = 0;
    				int last_true;
    				for (int num = 1; num < 10; num++) {
    					if (sudoku_bool[m][n][num]) {
    					   counter++;
    					   last_true = num;
    					}
    				}
    				if (counter == 1) {
    					sdk_to_solve[m][n] = last_true;
    					operation_done = true;
    					diff_single++;
    				}
    			}
    		}
    		
    		if (operation_done) {
    			goto field_counter;   //eliminate me!!!
    		}
    		
    		//Column defined field?
    		for (int num = 1; num < 10; num++) {
    			for (int m = 0; m < 9; m++) {
    				int counter = 0;
    				int last_field;
    				for (int n = 0; n < 9; n++) {
    					if (sudoku_bool[m][n][num]) {
    						counter++;
    						last_field = n;
    					}
    				}
    				if (counter == 1) {
    					sdk_to_solve[m][last_field] = num;
    					operation_done = true;
    					diff_line++;
    				}
    			}
    		}
    		if (operation_done) {
    			goto field_counter;   //eliminate me
    		}
    		
    		//Row defined field?
    		for (int num = 1; num < 10; num++) {
    			for (int n = 0; n < 9; n++) {
    				int counter = 0;
    				int last_field;
    				for (int m = 0; m < 9; m++) {
    					if (sudoku_bool[m][n][num]) {
    						counter++;
    						last_field = m;
    					}
    				}
    				if (counter == 1) {
    					sdk_to_solve[last_field][n] = num;
    					operation_done = true;
    					diff_row++;
    				}
    			}
    		}
    		if (operation_done) {
    			goto field_counter;  //eliminate me
    		}
    		//block defined field?
    		for (int num = 1; num < 10; num++) {
    			for (int block_row = 0; block_row < 9; block_row += 3) {
    				for (int block_line = 0; block_line < 9; block_line += 3) {
    					counter = 0;
    					int last_line;
    					int last_row;
    					for (int inblock_row = 0; inblock_row < 3; inblock_row++) {
    						for (int inblock_line = 0; inblock_line < 3; inblock_line++) {
    							if (sudoku_bool[block_row + inblock_row][block_line + inblock_line][num]) {
    								counter++;
    								last_row = block_row + inblock_row;
    								last_line = block_line + inblock_line;
    							}
    						}
    					}
    					if (counter == 1) {
    						sdk_to_solve[last_row][last_line] = num;
    						operation_done = true;
    						diff_block++;
    					}
    				}
    			}
    		}
    		if (operation_done) {
    			goto field_counter;   //eliminate me
    		}
    		
    		field_counter:
    		empty_fields_counter = 0;
    		for (int m = 0; m < 9; m++) {
    			for (int n = 0; n < 9; n++) {
    				if (sdk_to_solve[m][n] == NULL) {
    					empty_fields_counter++;
    				}
    			}
    		}
    		if (empty_fields_counter == 0) {
    			empty_fields = false;
    		}
    		if (empty_fields_counter != 0 && !operation_done) {
    			return false;
    		}
    	}
    	return true;
    }
    Any ideas or suggestions on how to do this...flags, what?

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I'd probably start from breaking things into functions of their own.

    E.g my own Sudoku solving loop looks like this:

    Code:
    bool SudokuGenerator::solve_()
    {
        do {
            while (find_single_candidates_() || find_hidden_single_());
    
        } while (found_count < 81 && (
             find_locked_candidates_() ||
             find_naked_pair_() ||
             ... ));
        return found_count == 81;
    }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    2,675

  4. #4
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    What's wrong with breaks & continues?
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  5. #5
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    Quote Originally Posted by cpjust View Post
    What's wrong with breaks & continues?
    nothing.

    I use them all the time in my code. everyone says they're just "pretty wrappers for goto", but isn't that actually the BEST reason to use them? so you don't have to use goto. there often isn't a better way to leave a loop or bypass the remainder of the loop, and they fill that role quite nicely.

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    In this case they don't seem to be good, and the gotos can be replaced with nested ifs:

    Code:
    while some condition:
        do something
        if not done: 
            do something
            if not done: 
                 do something
                 ...
        work done at the end of the iteration
    Simply mechanically avoiding the goto won't improve the code much (the gotos all go forward to the same place anyway). Breaking it into more manageable bits might do a lot (you'll also have more options to provide a goto-less structure).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Naturally the best way to be rid of gotos is to not put them in there in the first place!

    I thoroughly agree with anon here. The first step to eliminate those gotos must be to break it down into sub-functions. Do that first!

    Re the whole "not using break" thing: It is a ridiculous double-standard. Such people can't do without them in switch statements, but wont put them in loops, which makes no sense at all. It's making up rules of your own just to give yourself an excuse to not bother with structured programming, that you've made it too hard for yourself on purpose. If you wont use a break in a loop then I forbid you to use one in a switch statement.

    A quote from the legendary Zahlman of Gamedev.net to ponder:
    There is no meaningful sense in which break and continue are "gotos" but the ends of for loops, ends of while loops, function calls and returns (explicit or implicit) are not.
    Last edited by iMalc; 03-03-2010 at 12:34 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    By the same measure, if you've only introduced the need for `break' or `continue' because you've nested control structures you're essentially giving yourself an excuse not to rewrite the code.

    Such people can't do [...] no sense at all.
    I don't use `break' or `continue' at all. Coding under that implication I produce better code.

    I think the problem is making up rules for the sake of having rules. Their doesn't seem to be a need for a rationale behind them. (See not allowing templates in an embedded environment.)

    Soma

  9. #9
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by phantomotap View Post
    I don't use `break' or `continue' at all. Coding under that implication I produce better code.
    So you don't use switch statements?
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    What? What does that have to do with using `break' or `continue'? What do they have to do with `switch'? Are you making some indirect association? ('break' -> `goto' <- 'case acase:')

    [Edit]

    I've got it now. You asked that because of the common "rule" that every `case' block must end with a `break'. It is a stupid rule and has nothing to do with the standard.

    [/Edit]

    Whatever.

    If the situation is best illustrated by a `switch' statement, I naturally use a `switch' statement, but you'll have to explain how that necessitates `break' or `continue'. I've managed without them for some time.

    Actually, come to think on it, most of my code is "library level" where a `switch' statement wouldn't be allowed for mechanical reasons (For example, in template code where you'd have to use a different construct simple because the `case' labels must be integer like.) or design reasons. (The related values are not constant/literal expressions.) Considering that, I suppose it would be safe to say I don't use `switch' statements.

    Soma
    Last edited by phantomotap; 03-04-2010 at 12:57 AM.

  11. #11
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    Quote Originally Posted by phantomotap View Post
    O_o

    What? What does that have to do with using `break' or `continue'?
    Switch's have cases which use "break." That's all he meant.

    The main reason goto's are bad is because they produce spaghetti code. "break" and "continue" do not produce spaghetti code. They are quite uniform and generally not too hard to follow. Using a few here and there (such as for/while/if statements, switch case/break is perfectly fine) is fine (even using a small amount of goto's under certain circumstances has been argued, even though I've never encountered them).
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  12. #12
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Switch's have cases which use "break." That's all he meant.
    I don't know why he said it, but the association is too strong in the minds of most programmers. I blame the bogus "rule".

    "`if' statements have cases which use "break"."

    Hear? The association sounds silly. One doesn't necessitate the other. If you want to use `break' fine, but don't assume you need to because of a rule or because that's the way you first "see" it.

    The main reason goto's are bad is because they produce spaghetti code.
    Except where they don't. I use `goto' (and its "big brothers": `setjmp'/`longjmp') in virtually every "library level" function in C. (I hate C.) I dare you to try your hand at solid and structured source cleaning up of a dozen resources in the face of a dozen exit points without using `goto' in C.

    "break" and "continue" do not produce spaghetti code.
    Except where they do. If you care to search the Dev-C++ forum you'll find anecdotal "proof". A user had argued the same statement with me and Clifford, another regular. The source he posted as proof was a horrible mess of nesting and fake control structures solving the "N-Queen" problem. If you find it you'll find the companion source written by Clifford.

    Source is written for people. (That's probably a quote.) Source is written by people. (Which is plainly obvious.) It is the programmers writing the source that are responsible for "spaghetti" code. Programming is great like that; you can write crap source in any language using any construct.

    Soma

  13. #13
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Certainty a determined programmer does not need goto to produce spaghetti code.

    The thing about break and continue, is that often getting rid of them does not make the code any better. Often it just adds extra variables.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  14. #14
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    In any case, The OP's problem is simple. Instead of:
    Code:
    if (operation_done) {
        goto field_counter;   //eliminate me
    }
    code_segment();
    field_counter:
    general_code();
    Do:
    Code:
    if(!operation_done)
    {
        code_segment();
    }
    general_code();
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by phantomotap
    Source is written for people. (That's probably a quote.)
    If you do want a quote along those lines, Abelson and Sussman's "programs must be written for people to read, and only incidentally for machines to execute" might qualify.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. strlwr() and delimiter removal
    By kryptkat in forum C++ Programming
    Replies: 14
    Last Post: 12-29-2009, 10:53 AM
  2. GoTo's?
    By Neo1 in forum C++ Programming
    Replies: 4
    Last Post: 07-09-2007, 03:24 AM
  3. linux removal
    By MadCow257 in forum Tech Board
    Replies: 2
    Last Post: 03-24-2006, 09:48 AM
  4. Deleting object after list removal (C++ visual studio)
    By RancidWannaRiot in forum Windows Programming
    Replies: 2
    Last Post: 10-20-2005, 06:06 PM