Dave finishes up the PAIRS concentration game, only to realize it's too hard to solve!

In my last article, I tossed away my PC card and talked about how I was a fan of the British colonial-era writer Rudyard Kipling. With that in mind, I do appreciate that you're still reading my column.

I was discussing the memory game that the British spy plays with the orphan boy Kim in the book of the same name. The game in question involves Kim being shown a tray of stones of various shapes, sizes and colors. Then it's hidden, and he has to recite as many patterns as he can recall.

The card game Concentration is clearly inspired by the same pattern memorization game, and it's considerably easier to set up: shuffle a deck of cards, place them face down in a grid, then flip pairs to find matches. In the beginning, it's just guessing, of course, but as the game proceeds, it becomes more about spatial memory than luck. Someone with an eidetic memory always will win.

Using letters makes things easy, so I suggested a row, column, notational convention like this:

    1   2   3   4   5   6   7   8   9   10  11  12  13
1: [-] [-] [-] [-] [-] [-] [-] [-] [-] [-] [-] [-] [-]
2: [-] [-] [-] [A] [-] [-] [-] [-] [-] [-] [-] [-] [-]
3: [-] [-] [-] [-] [-] [-] [-] [-] [E] [-] [-] [-] [-]
4: [-] [-] [-] [-] [-] [-] [-] [-] [-] [-] [-] [-] [Z]

You can represent uppercase letters as a shell array like this:

declare -a letters=(A B C D E F G H I J K L M N O P Q R
                    S T U V W X Y Z)

Unfortunately, Bash doesn't support multidimensional arrays, so you're going to have to represent the grid as a one-dimensional array. It's not too hard though, because the grid is straightforward. Here's an index formula if firstvalue is the first digit and rest is the remainder of the index value:

index=$(( ( ( $firstvalue - 1 ) * 13 ) + $rest ))

The letter "E" in the above grid, at 3,9, would show up in the array as ((3-1)*13)+9 or slot 35.

The script from my last article already initializes everything in sequential order and defaults to 2 * 13 slots (for simplicity in debugging). The work of the script is really in the shuffle, but it turns out that there's a pretty elegant little shuffle algorithm (shown in a kind of sloppy C for illustrative purposes) floating around the internet that can be tapped for this task:

shuffle {
   for (i = n-1; i > 0; i-) {
     int j = rand() % (i+1);
     swap( array[i], array[j]);
   }
}

Translating this into a shell script and using better variable names, here's what I created:

shuffle ()
{
   # shuffle board with $1 * 13 values

   totalvalues=$(( $1 * 13 ))

   index=$totalvalues

   while [ $index -gt 1 ] ; do

     randval=$(( ( $RANDOM % $index ) + 1 ))

     # swapping value pair

     temp=${board[$index]}
     board[$index]=${board[$randval]}
     board[$randval]=$temp

     index=$(( $index - 1 ))
   done
}

Instead of having a separate function for the value swap, I just went ahead and dropped that into the function itself. It's faster and also lets you sidestep the dereference hassle neatly.

Here's what happens when you initialize the grid, shuffle it, then display it on screen (and yes, I changed the "[]" to "<>" to make it more visually interesting):

    1   2   3   4   5   6   7   8   9   10  11  12  13
1: <V> <X> <M> <R> <C> <F> <K> <O> <U> <H>
<T> <Q> <L>
2: <A> <G> <B> <N> <J> <Y> <P> <W> <Z> <E>
<D> <I> <S>

Of course, 26 grid spots equals exactly the number of letters in the alphabet, so there are exactly zero pairs. That's not much fun as games go, but what if you request a four-line grid?

    1   2   3   4   5   6   7   8   9   10  11  12  13
1: <G> <J> <A> <K> <P> <L> <B> <O> <I> <X>
<Y> <N> <F>
2: <Y> <C> <Z> <O> <G> <D> <T> <N> <V> <D>
<H> <E> <U>
3: <W> <C> <R> <Q> <M> <B> <E> <K> <F> <I>
<T> <Q> <R>
4: <U> <Z> <P> <H> <S> <W> <L> <J> <M> <X>
<V> <S> <A>

A few pairs jump out, like 2,13 and 4,1 for the "U" values, but remember, the game is going to hide all of this, and it's your job to guess these pairs.

Ah, it's suddenly not so easy, eh?

Now that the grid is being created and shuffled correctly, the next step is to differentiate between spots that have been guessed correctly and those that are still unknown. You could do that with a parallel array, but why go through the hassle? Instead, initialize every value to have a dash as its first character and then remove it once guessed.

The display function now can test a value to see if it's a "negative" letter. If so, it'll display a "-" instead of the actual value. Now the initial grid looks like this:

    1   2   3   4   5   6   7   8   9   10  11  12  13
1: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->
2: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->
3: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->
4: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->

What about entering your guess for the location of a given pair? I'm going to make things harder by not showing the values in a grid but rather just displaying them directly.

Enter a grid value as row, col, then split it into those values and multiply it out to a unique array index. It's complicated, but if you read $slot1 and $slot2 as the input values from the user, the analysis loop is this:

row1=$( echo $slot1 | cut -c1 )
col1=$( echo $slot1 | cut -d, -f2 )
row2=$( echo $slot2 | cut -c1 )
col2=$( echo $slot2 | cut -d, -f2 )

index1=$(( ( $row1 - 1) * 13 + $col1 ))
index2=$(( ( $row2 - 1) * 13 + $col2 ))

val1=${board[$index1]}
val2=${board[$index2]}

There's a woeful lack of error-checking here, but that's something I like to add afterward, once I get the core algorithm functional.

Armed with $val1 and $val2 above, testing to see if you have a match is easy:

if [ $val1 = $val2 ] ; then
  echo "You've got a match. Nicely done!"
  board[$index1]=${val1:1:1}
  board[$index1]=${val2:1:1}
  unsolved=$(( $unsolved - 2 ))
else
  echo "No match. $row1,$col1 = ${val1:1:1} and \
       $row2,$col2 = ${val2:1:1}."
fi

Did you notice $unsolved in the matching conditional code? That's how you can keep track of whether the grid has been solved.

With all this code in place, let's give it a whirl:

Welcome to PAIRS. Your mission is to identify matching letters
in the grid. Good luck. If you give up at any point, just use
q to quit.


Enter a pair of values in row,col format : 1,1 4,1
No match, but 1,1 = P and 4,1 = A.

    1   2   3   4   5   6   7   8   9   10  11  12  13
1: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->
2: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->
3: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->
4: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->

Enter a pair of values in row,col format : 2,1 3,1
No match, but 2,1 = Z and 3,1 = B.


    1   2   3   4   5   6   7   8   9   10  11  12  13
1: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->
2: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->
3: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->
4: <-> <-> <-> <-> <-> <-> <-> <-> <-> <->
<-> <-> <->

I'm basically done with the program at this point, and I'm realizing something. This is really hard to solve as a game.

Here's an exercise for you, dear reader: this is generating 26 possible values, the letters A–Z, which requires a minimum grid of 52 slots. That's a lot! Modify it to work with single digits, and then adjust the grid dimensions appropriately. For example, 20 slots can be portrayed in a 4 x 5 grid. For sure, 19 possibilities for the match of a revealed value is a lot easier than 51 possibilities.

Have fun with this, and grab the full script below or from here. Let me know how you modify this to make it more entertaining, interesting or just make it easier!

#!/bin/sh

# PAIR - a simple matching game, implmemented as a linear array

# Usage: PAIR rowcount
#    note: rowcount must be even and specifies how many 13-slot
#    rows are created
#    the default value is 2 rows of 13 values

declare -a board
declare -a letters=(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z)
rows=4                  # default # of 13 slot rows

initialize ()
{
   # given number of rows, initialize the board with all blank values

   count=1   maxcount=$1

   while [ $count -le $maxcount ]
   do
     addon=$(( 13 * ( $count - 1 ) ))

     for slot in {1..13}
     do
       index=$(( $addon + $slot ))
       letter=$(( $index % 26 ))        # unshuffled value

       board[ $index ]="-${letters[$letter]}" # unguessed start with '-'
     done
     count=$(( $count + 1 ))
   done
}

shuffle ()
{
   # given the board[] array with $1 * 13 entries, shuffle the contents

   totalvalues=$(( $1 * 13 ))

   index=$totalvalues

   while [ $index -gt 1 ] ; do

     randval=$(( ( $RANDOM % $index ) + 1 ))

     # swapping value pair

     temp=${board[$index]}
     board[$index]=${board[$randval]}
     board[$randval]=$temp

     index=$(( $index - 1 ))
   done
}

showgrid ()
{
   # show our grid. This means we need to display $1 x 13 slots with
   # labels
   #     rows is grabbed from the global var 'rows'

   count=1

   echo "    1   2   3   4   5   6   7   8   9   10  11  12  13"

   while [ $count -le $rows ]
   do
     /bin/echo -n "$count: "
     addon=$(( 13 * ( $count -1 ) ))

     for slot in {1..13}
     do
       index=$(( $slot + $addon ))
       value=${board[$index]}
       if [ ${value:0:1} != '-' ] ; then   # matched!
         /bin/echo -n "<${board[$index]}> "
       else
         /bin/echo -n "<-> "     # still unknown
       fi
     done
     echo ""
     count=$(( $count + 1 ))
   done
             
}

##################################

if [ $# -gt 0 ] ; then
  rows=$1
fi

if [ $(( $rows % 4 )) -ne 0 ] ; then
  echo "Ooops! Please only specify a multiple of 4 as the number
of rows (4, 8, 12, etc)"
  exit 1
fi

slot1=slot2="X"                 # start with a non-empty value
unsolved=$(( $rows * 13 ))
maxvalues=$unsolved             # parameter testing

echo "Welcome to PAIRS. Your mission is to identify matching letters
in the grid."
echo "Good luck. If you give up at any point, just use q to quit."
echo ""

initialize $rows

shuffle $rows

showgrid

while [ $unsolved -gt 0 ] ; do
  echo ""
  /bin/echo -n "Enter a pair of values in row,col format : "
  read slot1 slot2

  if [ "$slot1" = "" -o "$slot2" = "" ] ; then
    echo "bye."
    exit 1
  fi

  row1=$( echo $slot1 | cut -c1 )
  col1=$( echo $slot1 | cut -d, -f2 )
  row2=$( echo $slot2 | cut -c1 )
  col2=$( echo $slot2 | cut -d, -f2 )

  index1=$(( ( $row1 - 1) * 13 + $col1 ))
  index2=$(( ( $row2 - 1) * 13 + $col2 ))

  if [ $index1 -lt 0 -o $index1 -gt $maxvalues -o $index2 -lt
 ↪0 -o $index2 -gt $maxvalues ] ; then
    echo "bad input, not a valid value"
    exit 1
  fi

  val1=${board[$index1]}
  val2=${board[$index2]}

  if [ $val1 = $val2 ] ; then
    echo "You've got a match. Nicely done!"
    board[$index1]=${val1:1:1}
    board[$index1]=${val2:1:1}
    unsolved=$(( $unsolved - 2 ))
  else
    echo "No match, but $row1,$col1 = ${val1:1:1} and $row2,$col2 =
 ↪${val2:1:1}."
  fi

  echo ""
  showgrid

done

exit 0