C++

Forum

 
232 - Crossword Answers

Pages: 12
PureEvil75 (49)
Hello
I've trying to solve a problem called Crossword Answers on UVa
but I'm getting a wrong answer and I don't know why ?....
Please have a look on the problem here :
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=168


and here is my code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# include <iostream>
using namespace std;
int main ()
{
	char word [10][10] ;
	int helper [10][10] , set = 0 ; // helper to number the grid
	int row , col ;

	while (cin >> row)
	{
		set ++ ;
		int counter = 0 ;
		if (row == 0) // checking if the input is zero 
		{
			break;
		}
		cin >> col ;
		if (col == 0)
		{
			break;
		}
		// reading the grid elements and numbering the first row in helper
		for (int i=0 ; i<row ; i++)
		{
			for (int j=0 ; j<col ; j++)
			{
				cin >> word [i][j] ;
				if (word [i][j] != '*' && i == 0)
				{
					counter++;
					helper [i][j] = counter  ;
				}
			}
		}
		// these rules to number the rest of the grid in helper
		for (int i=1 ; i<row ; i++)
		{
			for (int j=0 ; j<col ; j++)
			{

				if (word [i][j] == '*' && word [i][j+1] != '*' && j+1 < col )
				{
					counter++ ;
					helper [i][j+1] = counter  ;
				}

				if ((word [i][j] != '*' && word [i-1][j] == '*' && word [i][j-1] != '*') || (word [i][j] != '*' && j==0 )) 
				{
					counter++ ;
					helper [i][j] = counter  ;
				}
			}
		}
		// printing the output for Across
		cout << "puzzle #"<< set << ":" << endl << "Across" << endl; 
		for (int i=0 ; i<row ; i++)
		{
			for (int j = 0 ; j<col ; j++)
			{
				if (word [i][j] != '*')
				{
					cout << helper [i][j] << "." << word [i][j] ;
					j++ ;
					while (word [i][j] != '*' && j<col)
					{
						cout << word [i][j] ;
						j++ ; 
					}
					cout << endl;
				}
			}
		}
		// printing the output for Down (printing the letters in each column till it encounters a black square , then it loops  the next column)
		cout << "Down" << endl;
		for (int i=0 ; i<col ; i++)
		{
			for (int j=0 ; j<row ; j++)
			{
				if (word [j][i] != '*')
				{
					int y = j ; // to maintain the j increment
					cout << helper [y][i] << "." << word [y][i] ;
					y++ ;
					while (word [y][i] != '*' && y<row)
					{
						cout << word [y][i] ;
						y++ ; 
					}
					cout << endl;
					break;
				}

				if (word [j][i] == '*' && word [j+1][i] != '*')
				{
					int y = j+1 ; // to maintain the j increment
					cout << helper [y][i] << "." << word [y][i] ;
					y++ ;
					while (word [y][i] != '*' && y<row)
					{
						cout << word [y][i];
						y++ ;
					}
					cout << endl;
					break;
				}

			}
		}
		// printing the rest of the Down by looping from the the second row.....and so on
		for (int i=1 ; i<row ; i++)
		{
			for (int j=0 ; j<col ; j++)
			{
				if ((word [i][j] == '*' && word [i+1][j] != '*' && i+1<row ))
				{
					int x = i ;
					x ++ ;
					cout << helper [x][j] << "." << word [x][j] ;
					x++ ;
					while (word [x][j] != '*' && x<row)
					{
						cout << word [x][j] ;
						x++ ;
					}
					cout << endl;
				}
			}
		}
		cout << endl;
	}

}



please I need help
Last edited on
ne555 (10692)
You are accessing `helper' and `word' out of bounds (loop 36)
fg109 (709)
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
		cout << "Down" << endl;
		int down [10] ;
		for (int i=0 ; i<col ; i++)
		{
			for (int j = 0 ; j<row ; j++)
			{
				if (word [j][i] != '*')
				{
					cout << helper [j][i] << "." << word [j][i] ;
					j++ ;
					while (word [j][i] != '*' && j<row)
					{
						cout << word [j][i] ;
						j++ ; 
					}
					cout << endl;
				}
				break;
			}
		}

What's line 75 supposed to do? Anyway, when you output the "Down" words, you are skipping the rest of the row.

For example, in the second example given, the word "IMPOSE" is from row 1 to row 6. Your code will go from j = 0 to j = 5 when you output it, which means you will skip words like "DO", "ENTIRE", "ROD", etc.

You are outputting the down words in incorrect order. You are outputting from top to bottom, then from left to right. The numbering scheme is from left to right, then top to bottom.

Also, maybe you should code it to take input from a file instead of the console.
Last edited on
PureEvil75 (49)
ok line 75 is a mistake

but here is sample input :
6 7
AIM*DEN
*ME*ONE
UPON*TO
SO*ERIN
*SA*OR*
IES*DEA

output is :
Across
1.AIM
4.DEN
7.ME
8.ONE
9.UPON
11.TO
12.SO
13.ERIN
15.SA
17.OR
18.IES
19.DEA
Down
1.A
2.IMPOSE
3.MEO
4.DO
5.ENTIRE
6.NEON
9.US
10.NE
14.ROD
16.AS
18.I
20.A

this is how I understand Across and down :
Across : output should be form left to right (in the same row) if a block is encountered , skip it and finish the row ....then proceed to the next row and so on....


Down : output should be from top to down (in the same column) if a block is encountered , then proceed to the next column and so on.....when the column are finished , check again by starting from the second row ....and so on

hope u got what I mean

am I correct ?
and thx a lot
Last edited on
fg109 (709)
My mistake. I didn't notice the break; in the code I pointed out. That seems to make a very inefficient loop though, with you needing to add a whole other loop after it to print out the rest of the "Down" words.

Try changing line 41 to this:
if (j+1 < col && word [i][j] == '*' && word [i][j+1] != '*')

That should take care of the out of bounds problem ne555 pointed out.

If that doesn't fix it, maybe it's because you assume the puzzle will be a maximum size of 10x10. You can try changing the code to use dynamic memory allocation.
ne555 (10692)
input
2 2
a*
*b

your output
puzzle #1:
Across
1.a
3.b
Down
1.a
3.b
¿shouldn't be 2.b ?

PureEvil75 (49)
Thanks a lot at first
commenting on nes55
I don't understand how did the counter reach 3
I debugged it I did not even see number 2 in the whole grid.......
then how did the counter reach number 3 without reaching number 2

and one more thing why is the for loop in line 36 go out of bounds
I don't understand how ?
PureEvil75 (49)
done now I can see why it is 3.b

changing line 47 to :
if ((word [i][j] != '*' && word [i-1][j] == '*' && word [i][j-1] != '*') || (word [i][j] != '*' && j==0 ))

but still why is the loop in line 36 go out of bounds ?
Last edited on
PureEvil75 (49)
NO NO WAY

consider this input case :
4 3
a e *
m * l
* n o
* m n

the output according to UVA toolkit is :
puzzle #1:
Across
1.ae
3.m
4.l
5.no
6.mn
Down
1.am
2.e
4.lon
5.nm

if this is certainly true , then I don't understand the output
here try it for yourself here : http://uvatoolkit.com/problemssolve.php
please write the word cross in the search bar and choose crossword answers......

I must understand the output in order to accept this problem

and here an other sample input :
3 3
a e *
m * l
* n o

according to uva toolkit the output is :
puzzle #1:
Across
1.ae
3.m
4.l
5.no
Down
1.am (I agree with this)
2.e (I agree with this)
4.lo (I don't agree with this)
5.n (I don't agree with this)


I think 4 and 5 need to be replaced by each other
Last edited on
PureEvil75 (49)
ok
I've modified my code to just like toolkit
the main code has been updated above

but still nothing make any sense
consider the input :
3 3
* a *
m * s
p w l

uva toolkit output is :

puzzle #1:
Across
1.a
2.m
3.s
4.pwl
Down
1.a
2.mp
3.sl
5.w


CAN anyone just answer one question ?
why 2.mp wasn't printed at first ......instead of 1.a
Last edited on
Lowest0ne (1536)
That is just the way numbers on crosswords work. Your link on your first post as the picture:
http://uva.onlinejudge.org/external/2/232img3.gif

So that is the simple answer, why do 16 before 14?

For your program, it's because of the way you do the loop:
1
2
 
for -> rows
  for -> cols


You reach (row 1, col 0) before (row 0, col 1).
PureEvil75 (49)
ok thx
I'm making a new for loop to finish the DOWN at once
PureEvil75 (49)
DONE
now all the mentioned cases are working with this code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
# include <iostream>
using namespace std;
int main ()
{
	char word [10][10] ;
	int helper [10][10] , set = 0 ; // helper to number the grid
	int row , col ;

	while (cin >> row)
	{
		set ++ ;
		int counter = 0 ;
		if (row == 0) // checking if the input is zero 
		{
			break;
		}
		cin >> col ;
		if (col == 0)
		{
			break;
		}
		// reading the grid elements and numbering the first row in helper
		for (int i=0 ; i<row ; i++)
		{
			for (int j=0 ; j<col ; j++)
			{
				cin >> word [i][j] ;
				if (word [i][j] != '*' && i == 0)
				{
					counter++;
					helper [i][j] = counter  ;
				}
			}
		}
		// these rules to number the rest of the grid in helper
		for (int i=1 ; i<row ; i++)
		{
			for (int j=0 ; j<col ; j++)
			{

				if (word [i][j] == '*' && word [i][j+1] != '*' && j+1 < col )
				{
					counter++ ;
					helper [i][j+1] = counter  ;
				}

				if ((word [i][j] != '*' && word [i-1][j] == '*' && word [i][j-1] != '*') || (word [i][j] != '*' && j==0 )) 
				{
					counter++ ;
					helper [i][j] = counter  ;
				}
			}
		}
		// printing the output for Across
		cout << "puzzle #"<< set << ":" << endl << "Across" << endl; 
		for (int i=0 ; i<row ; i++)
		{
			for (int j = 0 ; j<col ; j++)
			{
				if (word [i][j] != '*')
				{
					cout << helper [i][j] << "." << word [i][j] ;
					j++ ;
					while (word [i][j] != '*' && j<col)
					{
						cout << word [i][j] ;
						j++ ; 
					}
					cout << endl;
				}
			}
		}
		// printing the output for Down 
		cout << "Down" << endl;
		for (int j=0 ; j<row ; j++)
		{
			for (int i=0 ; i<col ; i++)
			{
				if ((word [j][i] == '*' && j == 0 && i == 0) || (word [0][i] == '*' && word [0][0] == '*' && j == 0))
				{
					continue ;
				}

				if (word [j][i] != '*' && j==0 && i == 0)
				{
					int y = j ;
					cout << helper [y][i] << "." << word [y][i] ;
					y++ ;
					while (word [y][i] != '*' && y<row)
					{
						cout << word [y][i] ;
						y++ ; 
					}
					cout << endl ;
					continue ;
				}

				if (word [j][i] == '*' && word [0][0] != '*' && word [j+1][i] != '*' && j+1<row)
				{
					int y = j+1 ;
					cout << helper [y][i] << "." << word [y][i] ;
					y++ ;
					while (word [y][i] != '*' && y<row)
					{
						cout << word [y][i] ;
						y++ ; 
					}
					cout << endl ;
					continue ;
				}
					
				if (word [j][i] != '*' && j == 0)
				{
					int y = j ; // to maintain the j increment
					cout << helper [y][i] << "." << word [y][i] ;
					y++ ;
					while (word [y][i] != '*' && y<row)
					{
						cout << word [y][i] ;
						y++ ; 
					}
					cout << endl;
				}

				if (word [j][i] != '*' && word [j-1][i] == '*' && j>0 && word [0][0] == '*')
				{
					int y = j ;
					cout << helper [y][i] << "." << word [y][i] ;
					y++ ;
					while (word [y][i] != '*' && y<row)
					{
						cout << word [y][i] ;
						y++ ; 
					}
					cout << endl;
				}

			}
		}
		cout << endl;
	}
}



I hope just it will accept on UVA
PureEvil75 (49)
WRONG ANSWER AGAIN
please any suggestions !
fg109 (709)
Puzzles are numbered in this order:

123
456
789

Not this order:

147
258
369

When printing out the answers, you are supposed to go through the list in the correct order. That way, the answers would be listed in ascending order.
PureEvil75 (49)
I don't understand !
PureEvil75 (49)
I think I Do understand you now
ok
but my code is already doin that !!
where is the wrong test case


NOW I GOT WHAT U MEAN
now I've to loop with helper instead of word
without using these stupid conditions
Last edited on
fg109 (709)
Sorry, didn't refresh the page before I posted last. LowestOne already answered and you already corrected your code.

I really have no idea what could be wrong if your code generates the same output as the UVa toolkit.

This is what I have written, though I don't have an account there so I haven't tried submitting it. Maybe it'll give you some ideas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
#include <iostream>
#include <iomanip>
#include <fstream>

using namespace std;

int main()
{
    char **squares;
    int **numbers;
    int rows, cols, puzzle = 0;
    ifstream fin("input.txt");

    if (!fin)
    {
        cout << "Error opening input.txt file.";
        return 1;
    }

    while (fin >> rows >> cols && rows > 0 && cols > 0)
    {
        squares = new char * [rows];
        numbers = new int * [rows];
        int num = 1;

        for (int i = 0; i < rows; i++)
        {
            squares[i] = new char[cols];
            numbers[i] = new int[cols];
            for (int j = 0; j < cols; j++)
            {
                fin >> squares[i][j];
                if (i == 0 && squares[i][j] != '*')
                    numbers[i][j] = num++;
                else if (i > 0 && squares[i][j] != '*' && squares[i - 1][j] == '*')
                    numbers[i][j] = num++;
                else if (j == 0 && squares[i][j] != '*')
                    numbers[i][j] = num++;
                else if (j > 0 && squares[i][j] != '*' && squares[i][j - 1] == '*')
                    numbers[i][j] = num++;
                else
                    numbers[i][j] = 0;
            }
        }

        cout << "puzzle #" << ++puzzle << ":\nAcross" << endl;

        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if ((j == 0 && squares[i][j] != '*') ||
                    (j > 0 && squares[i][j] != '*' && squares[i][j - 1] == '*'))
                {
                    cout << setw(3) << right << numbers[i][j] << ". ";
                    while (j < cols && squares[i][j] != '*')
                        cout << squares[i][j++];
                    cout << endl;
                }

        cout << "Down" << endl;

        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if ((i == 0 && squares[i][j] != '*') ||
                    (i > 0 && squares[i][j] != '*' && squares[i - 1][j] == '*'))
                {
                    cout << setw(3) << right << numbers[i][j] << ". ";
                    int i2 = i;
                    while (i2 < rows && squares[i2][j] != '*')
                        cout << squares[i2++][j];
                    cout << endl;
                }

        cout << endl;

        for (int i = 0; i < rows; i++)
        {
            delete[] squares[i];
            delete[] numbers[i];
        }
        delete[] squares;
        delete[] numbers;
    }

    fin.close();
    return 0;
}
PureEvil75 (49)
Thank u very much
but one last thing
can u make an account n uva and try to submit to see what will happen
REGARDS

and I'm not familiar with the input text file
can u modify it to input from consul
fg109 (709)
Well, I tried submitting it and looks like mine was the wrong answer as well. (Also, apparently you must use console input because file input results in a runtime error.)
Pages: 12