Table of Contents [ Show]
Inside my Shell
To give a bit of background, I am brushing up on C and am trying to use it in ways that don't totally make sense in order to try and work out creative solutions to problems. One project that I am working on, that will be featured in a future Projects article is a command line card game.
Drawing a Dynamic Board
Printing line by line is not too difficult for the player's hand, as it just required 3 nested loops. The first to loop the rows of the cards, the second to loop through the cards in the hand, and the third to loop thought the columns making up that row of that card. While it would have been possible to print the rows for each card as a string or substring it is slightly more complicated to do this because of the variable width of the cards.
"Variable with of the card?" you ask. Yes, all cards are the same width, but by default the one-quadrant terminal that I'd want to stick this thing in is only 87 columns wide, so not all cards can be displayed at full width. Much like you do in real life, the cards must be fanned out behind one another in the interest of space. The standard assumption is that a console is 80 columns wide and so this is what I worked with. Since I don't trust my basic algebra skills, I wrote a short program to tell me the maximum width that each card can be displayed at as well as the space required to fill the remaining columns on each side with consideration for the fact that the last card is always full-width. I plugged these values into 3 arrays with the values for the number of cards left in the hand; there is no sense in having the main program calculate constants.
Significantly harder than the player's hand was the middle of the board. This requires that a variable number of cards for the second and fourth hands be printed as well as a variable number of in-play cards and spaces between them. Having the AI's hands spread to take up as much space as possible like the players hand does would have required an extra layer of conditions that would not have yeilded any real value to the player so I didn't bother fighting with that. Instead I just made the hands steadily shrink in one direction. This allowed me to just check the line number as well as how many cards each player has left and print either the correct pattern or the equivalent blank space as the hand shirks. Right in the middle I could again check the line number, print blanks where no card exists and then duplicate the behaviour of the players hand for the in-play cards less the 3 spaces on each side that are populated by the AI's hands. The top hand was the easiest since I could just replicate the shrinking hand behaviour for consistency, and then put half of the spaces on each side. I could have done these as a constant as well, but since the card width was not variable, the calculation was easy enough to do inline.
This brings me to what inspired me to document the writing of this program in the first place; the titular problem of dealing. There is a common problem in programming of trying to solve problems in the way that a human would, rather than thinking of how a computer might deal with the same problem. I fell victim to this when it came to the problem of dealing.
My Problem
When a human deals cards, we go through a process of shuffling and dealing to players in sequence, just to have the players re-sort the cards. We don't think about how inefficient this is because it is essential to fair, random dealing. At first pass I did just this. I wrote a shuffle algorithm that picked from an array of 0-51 at random, then moved all numbers larger than the picked card left by one in the array. Because the higher numbers were all pushed left they would overwrite the selection so that it couldn't be picked twice, and leave a stray copy of the highest number at the end. It ran 52 times, generating a random selection from a range that shrank once per run to leave out the duplicate at the end. Plugging the selected number on each run into a seprate array at the position equivalent to the run number yeilds a shuffled array containing each number between 0-51 once. Dealing was then as simple as putting every forth card into an array for each player. But this leaves you with 4 shuffled arrays and is what eventually placed my palm firmly on my face.
Before I got to that point, however, I had already written a quick bubble sort. For those who don't know, bubble sorts are really easy but extremely inefficient. This is because a bubble sort requires that you compare each pair of side by side items in an array, swapping them if they are out of order. Because any item can only move up to one position in sequence each time this is done and it is possible that the highest or lowest item may be on the exact opposite side, this will have to be repeated as many times as the list is long, less one. This means a maximum of n less one comparisons per run, times n less one runs, or (n-1)^2 comparisons where n is the number of items in the set. Luckily 4 sets of 13 is a very managable 574 comparisons and would have been handled in a tiny fraction of a second.