What is the best way to store temporary selected characters and their insertion order?

Question

I'm developing word game similar to word mole. I'm having a hard time determining how to store temporary selected character (and in turn will changed into word).

Here's the situations. Say, I have the following character:

  0  1  2  3
  -----------
0|o  b  o  s
1|s  f  r  h
2|t  n  e  z
3|r  b  d  i

I store all this information in arrayed char named playCharacter and I also created another arrayed char named markedCharacter with default value for each array item is ' '.

In my opinion, every time I select each cell, say cell[1,0], I set markedCharacter[1,0] = 'b' an so on, until I'm done with current word.

My question is, how do I store the step information? for example, if I choose to play bored, I'll be marking:

markedCharacter[1,0] = 'b'
markedCharacter[2,0] = 'o'
markedCharacter[2,1] = 'r'
markedCharacter[2,2] = 'e'
markedCharacter[2,3] = 'd'

Do I need another array? if so, what data should I store in it?

UPDATE

In turn, I'll want to use this markedCharacter as a way to check:

• if certain move are valid (eg, do they marked within an already marked neighbor cell?)
• if stored word are valid or not (this part is already covered)
• I don't need to do undo operation

Answer 1

TL;DR

A simple List<int> is enough to store all the information you need. Read on for the details.

Context

I'll drop in a little trick here then. Are you aware that when working with 2D matrices there's a way to index them with a single number, instead of having to provide a (x,y) pair?

For instance, where is the letter d in the following matrix?

  | 0 1 2
--|-------
0 | a b c  
1 | d e f

Using the usual (x,y) notation the answer would be (0,1) - the letter d can be found on the first column of the second row (remember, zero based indexes).

But you could also index your matrix like this:

a b c    =>    0 1 2
d e f          3 4 5

In which case the answer would simply be (3) - the letter d is the fourth element in the matrix starting from the top and to the right (once again, zero based).

Conversion

You can convert from a (X,Y) pair to a simple (index) by doing:

int index = x  + y * width

And you can convert an (index) back to a (X,Y) pair by doing:

int x = index % width;
int y = index / width; // Note: Integer division (truncate)

Where width is simply the width of the matrix.

Here's two simple methods to do this:

int encode(int x, int y, int width) 
{ 
    return x + y * width; 
}

void decode(int index, int width, out int x, out in y)
{
    x = index % width;
    y = index / width;
}

And how to use them:

int width = 3;

// Encode (1,2)
int index = encode(1, 2, width);

// Decode
int x, y;
decode(index, width, out x, out y);

Answer

On to your question. Using this little encoding you can store a sequence as simply as:

List<int> sequence = new List<int>();

• The order in which you store elements in the list becomes the order in which the letters were selected.
• It's easy to check for duplicates or collisions. Just do a List.Contains or List.Find.
• Undoing is simply a matter of removing the last index from the list.
• Starting a new sequence is as simple as calling List.Clear.
• You can check which letter corresponds to any element in the sequence by doing board.GetLetterAt(index % board.Width, index / board.Width).
• Just repeat the previous line for each element in the sequence to reconstruct the word.

And to answer your specific example, if you chose to play bored, that would be stored as:

sequence.Clear();
sequence.Add(new []{encode(1,0), encode(2,0), encode(2,1), encode(2,2), encode(2,3)});

Answer 2

Why not create a Sequence object that is a list of marked words in the order they were chosen?

Something like this..

class Sequence {
  List<Letter> letters;
  int index = 0;

  public void addLetter(char letter, Point position) {
    letters.add(new Letter(letter, position, index++);
  }    

  public boolean checkIfThereIsAMatchInThisLevel(List<string> words) {
    return words.contains(letters);
  }

  /* OTHER COOL AND USEFUL METHODS HERE */
}

class Letter 
  char letter;
  Point position; // Just a struct/class with x,y values stored.
  int index;

  //Constructor omitted
}

Then you can just create a new object or reset it, or whatever floats your boat, when a new sequence is created/finished etc.

I hope I understood your question correctly!