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
Dave Taylor has been hacking shell scripts on UNIX and Linux systems for a really long time. He's the author of Learning Unix for Mac OS X and Wicked Cool Shell Scripts. You can find him on Twitter as @DaveTaylor, and you can reach him through his tech Q&A site: Ask Dave Taylor.
