crossword-like game algorithm in C#

Question

I'm doing a crossword game for my uni assignment. Almost done, but here is a problem that I can't solve it.

We need to load a csv file which contains a completed crossword game, but we need to do some validation to make sure the crossword file is valid.

The constraints are:

Words cannot be repeated.
Words can be placed horizontally but only run left to right.
Words can be placed vertically but only run high to low.
A horizontal word must intersect one or more vertical words.
A vertical word must intersect one or more horizontal words.
Each word must be delimited by spaces or the grid edge.

I've done all constraints above, but i'm stuck at here

You can only have one group of connected words, That is, a group of connected words cannot be disconnected from another group of connected words.

Part of the crossword file is like this: (I can't upload images because lack of reputation)

R   O   B   E   R   T           
        I                       
J   I   L   L                   
E       L           J   O   H   N
S                           A   
S       M   A   R   Y       R   
I       A       O           R   
C       R       G   A   R   Y

.......

What i've done relate to this so far:

A class named Crozzle represents this crossword file. One of the property is public List CrozzleWords, which contains all the word in the file.
A class name WordInCrozzle represents every single word in Crozzle. Every word has an attribute to record the intersection's position. e.g. the word 'ROBERT' has an intersection with the word 'BILL' the intersection's position is (int)[0,3], the letter at intersection is 'B'.
The word in WordInCrozzle class has another property named Direction, which represent the direction of the word, can be either vertically or horizontally.

Here is my solution:

public bool ContainsOneGroup()
    {
        bool flag = true;

        // a temp crozzle word list
        List<WordInCrozzle> tempWords = _crozzle.CrozzleWords;

        // start from the first item in wordlist, whatever which word is using
        WordInCrozzle word = tempWords[0];
        if (word.IntersectionPosition.Count > 0)
        {
            // step1. get a word randomly 'Word'  OK -- WordInCrozzle word = tempWords[0];
            // step2. get wordInCrozzle List  OK -- List<WordInCrozzle> tempWords = _crozzle.CrozzleWords;
            // step3. find the intersection position(s) of the word 'Word' and store it to a temp list 'positionOfIntersection'  OK -- List<int[]> positionOfIntersection = word.IntersectionPosition;

            List<int[]> positionOfIntersection = word.IntersectionPosition;

            // remove the first word
            tempWords.Remove(word);
            //crozzleBackup.CrozzleWords.Remove(word);

            // step4. if can grab an intersection position from 'positionOfIntersection' (means any)
            while (positionOfIntersection.Any())
            {
                foreach (WordInCrozzle w in tempWords)
                {
                    for (int i = 0; i < w.IntersectionPosition.Count; i++)
                    {
                        if (ArraysEqual(w.IntersectionPosition[i], positionOfIntersection[0]))
                        {
                            w.IntersectionPosition.Remove(positionOfIntersection[0]);
                            positionOfIntersection.Remove(positionOfIntersection[0]);
                            //tempWords.CrozzleWords[i].IntersectionPosition.Remove(w.IntersectionPosition[i]);
                            if (w.IntersectionPosition.Count > 0)
                            {
                                // store the positionOfIntersections, if this is null, and still have word in tempWords, means there are more than one group of words
                                positionOfIntersection.AddRange(w.IntersectionPosition);

                            }
                            // after get the position, remove the word
                            tempWords.Remove(w);
                        }
                    }
                }
            }
            // step9. if there is no more intersection position left, and no word in wordInCrozzle List, means only one group in the crozzle
            //          Otherwise, more than one group of word
            if (tempWords.Any())
            {
                _errors.Add(new Error(ErrorType.CrozzleError, "More than one group of connected words found"));
                flag = false;
            }
        }
        else
        {
            _errors.Add(new Error(ErrorType.CrozzleError, "More than one group of connected words found")); // if there is no intersection in a word, means there must more than one group of words
            flag = false;
        }
        return flag;
    }

But when I run it, I've got a 'System.InvalidOperationException', it tells me I can't modify the tempWords when i'm doing foreach.

Anybody can tell me how to do that? or is there any algorithm to figure out is there only one group of words in the crossword file?

score 4 · Answer 1 · edited May 23 '17 at 11:58

4

As the exception is saying you can't modify a list which implements IEnumerable whilst looping through it. A solution would be to create a separate list and add all the items you would like to remove. When you finish looping then remove each item in the new list from the original list.

You can also traverse the original loop backwards as per (plus some other options): How to remove elements from a generic list while iterating over it?

edited May 23 '17 at 11:58

Community

1
1

answered Aug 26 '14 at 12:11

Lee

586
3
5

I considered that, but here is the problem: I need to remove the word and the intersection position immediately when i found any word that across with other, otherwise the loop will be infinite loop. – Alex Aug 26 '14 at 12:18

score 3 · Accepted Answer · answered Aug 26 '14 at 12:18

3

You aren't allowed to remove an element from an array while you enumerate it. What I usually do is just make a copy of the array and enumerate over that:

foreach (WordInCrozzle w in tempWords.ToArray())
{
    ...
    tempWords.Remove(w);
}

answered Aug 26 '14 at 12:18

Weyland Yutani

4,682
1
22
28

score 0 · Answer 3 · answered Sep 07 '14 at 08:25

My algorithm for this constraint

You can only have one group of connected words, That is, a group of connected words cannot be disconnected from another group of connected words.

is:

Take first word and put it to collection of "connected words".
Go through all remaining words and if some of them connected with "connected words" -> put it to "connected words" too.
Do 2nd step while you put at least one word to "connected words".
When the loop is finished -> If there are still remaining words that were not put to "connected words" it means that you have several groups.

crossword-like game algorithm in C#

3 Answers3