Dreamer of Worlds

Algorithms: Prime Number Revisited, The Sieve of Eratosthenes

2013-11-30T12:28:00.002-05:00

The last time we played with prime numbers, we created an algorithm that would start with the first prime as a seed, and then discover each subsequent prime in the sequence by testing it against all known primes. The problem with this algorithm is that although it works, it needs a large number of computations once the prime list gets high enough.

What if we could eliminate many of those computations, and use a boolean array to immediately tell if a number was prime or not?

The good news is, we can. And this method has been known since the time of the ancient Greeks. It's easy enough to do by hand, but when working with very large numbers, computers can do a much faster job than a human. The method is known as the Sieve of Eratosthenes.

In order to use the method, you must first have a target. Let's say that you want to find all the prime numbers up to 10. You start by making a list of all numbers from 2 to 10.

2, 3, 4, 5, 6, 7, 8, 9, 10

The first number on your list is 2, and that's because 2 is the first prime number. I will underline it to mark it as prime.

2, 3, 4, 5, 6, 7, 8, 9, 10

From here, you cross off all the numbers that are multiples of 2.

2, 3, 4, 5, 6, 7, 8, 9, 10

The next number that is not crossed off is the next prime in the series, which is 3. We underline 3 to mark it as prime, and cross off the multiples of 3.

2, 3, 4, 5, 6, 7, 8, 9, 10

The next number not crossed off is 5, which is prime. We repeat the process with 7, and we are left with our list of primes.

2, 3, 4, 5, 6, 7, 8, 9, 10

The algorithm is straightforward, with a base case and a finite number of steps. We can easily code this to accept a target number, generate an array of the numbers between 2 and the target, and then run the sieve method on the list to generate all primes. We can even optimize it so that we are not working with a number type at all, but rather a boolean type using a hash-table.

In my implementation, I create a hash-table as a simple array of booleans. The index of the array represents the actual number. If the value is true, then the number is prime. If the value is false, then the number is non-prime. Once the hash-table has computed, the algorithm will walk the table and add each prime to a list of numbers, returning it to the calling method.



        static List<int> SieveOfEratosthenes_Full(int x)

        {

            //The sieve will generate a list of primes between 0 and x.



            //Array of booleans to determine whether or not a given index is a prime number.

            //For example, primes[2] == true because 2 is a prime number while primes[4] == false because 4 is not prime.

            bool[] sieve = new bool[(int)(x + 1.0)];



            //Seed the starting values. 0 and 1 are not considered prime and are seeded as false.

            sieve[0] = false;

            sieve[1] = false;



            //2 is the first prime number and is seeded as true. Each number after 2 is considered prime until ruled out by the sieve

            //and is seeded as true.

            for (int y = 2; y <= x; y++)

                sieve[y] = true;



            //The algorithm walks the array. If the number is prime, then all multiples of that number are marked as false.

            //The algorithm continues ruling out numbers based on their status as a multiple of a prime.

            //The algorithm starts at 2, the first prime.

            for (int y = 2; y <= x; y++)

                if (sieve[y])

                    for (int z = 2 * y; z <= x; z += y)

                        sieve[z] = false;



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



            for (int y = 2; y < sieve.Length; y++)

                if (sieve[y])

                    primes.Add(y);



            return primes;

        }

The algorithm is in place and runs quite fast. While discussing ways to improve it, several programmers suggested to only test odd numbers as we know all even numbers except 2 are non-prime. By using a hash-table with no gaps, we would cut the physical memory required down by half.

The second implementation I came up with does just that. Simple formulas will convert a number to an index and back again. The hash-table holds all odd values from 3 to the target number. The issue with the implementation is that the code becomes more complex. Even with comments, it's not immediately clear why some of the in-line calculations are happening.

static List<int> SieveOfEratosthenes_Odd(int x)

{

//The sieve will generate a list of primes between 3 and x, only odd numbers.

bool[] sieve = new bool[(int)(Math.Ceiling(x / 2.0) - 1)];

for (int z = 0; z < sieve.Length; z++)

sieve[z] = true;

            //The sieve only needs the odd numbers from 3 to x. The prime's index in the sieve is: Math.floor(n / 2) - 1

//The index can be converted to the prime it represents by the formula: index * 2 + 3

for (int z = 0; z < sieve.Length; z++)

if (sieve[z])

{

int number = z * 2 + 3;

//When incrementing, only investigate the odd numbers.

for (int y = 3 * number; y <= x; y += (2 * number))

sieve[(int)Math.Floor(y / 2.0) - 1] = false;

}

//Create the list of primes. Seed with 2 and pull the odd primes from the sieve.

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

primes.Add(2);

for (int z = 0; z < sieve.Length; z++)

if (sieve[(int)z])

//The index can be converted to the prime it represents by the formula: index * 2 + 3

primes.Add(z * 2 + 3);

return primes;

}

The first implementation is much easier to read and follow than the second. The second implementation uses half the memory, but an array of over 2,000,000 boolean values still takes up less space than the average video or music file. The footprint is theoretically 1.9MB for the full hash implementation and 0.95MB for the odds-only implementation. What about speed? I ran a simple test harness to determine the time used to run both implementations. The speed saved by only testing odd numbers is then lost during the additional calculations. Here are results from a few runs:

The odds-only implementation saves a small fraction of the time. In one case above, it even took longer than the full implementation. Unless processing speed and memory footprint of the hash-table are tight constraints, I'd opt to use the full implementation as it would be easier to read and maintain in a team-environment.

Algorithms: Prime Numbers and Prime Factorizations

2013-07-19T21:19:00.001-04:00

EDITED: Removed a bug discovered by a reader regarding very large prime numbers. Any input over 1,000,000 will take a while to run.

I was recently introduced to Project Euler. This site contains many problems for programmers to test both their math skills and coding skills. One of the problems dealt with finding the largest prime factor of a very large number. I enjoyed this problem, and decided to make a small program in C# to find the prime factorization of ANY number between 2 and 9,223,372,036,854,775,807 (the highest value stored in long). The speed for the high end isn't great and would be improved if the program used an existing list of prime numbers. The program does just fine for reasonable input values, however, and the algorithm is a good tool for those wishing to have a quick prime factorization tool.

I broke the problem down into two parts. The first part is how to generate a sequence of prime numbers. The second part is finding the prime factorization using the list. Since my program does not know what the highest prime number is until the process is completed, I only generate new prime numbers as factorization candidate as needed.

Generating a sequence of primes is the first step. A prime number, be definition, is only divisible by 1 and itself. It has no other factors. All non-prime numbers can be broken out into a factorization of primes. For example, 10 is not prime as it is divisible by 1, 2, and 5. The prime factorization of 10 is 2 * 5. Since all non-prime numbers have a prime factorization, any non-prime number that is a factor of another number ensures that the primes in the prime factorization of the lower number are also factors of the higher number. For example, 10 is a factor of 20 and 10 is not prime. Since the prime factorization of 10 is 2 * 5, we know that 2 and 5 are both factors of 20. Using these deductions, we can generate a list of primes merely by testing numbers against all known primes that are lower than the given number.

I wrote a method that does exactly that. Given a list, it will populate that list with the next prime number in the sequence. See the code below, the method is named generateNextPrime. It takes in a list as the only . argument. The only prime number that is hard-coded is 2. When an empty list is passed in, 2 is seeded as the first prime. All subsequent primes in the list are discovered. When the list is not empty, the method determines the last prime in the list and then starts at the very next number. For example, if the list contains { 2 }, then the method will start searching for the next prime at 3. The method compares the number to all discovered primes. Since 2 is greater than the square root of 3, we know that 3 is prime. The list now contains { 2, 3 } as prime numbers. The next time the method is invoked, it will start at 4. 2 is a factor of 4, so 4 is not prime and is not added to the list. The method then moves to 5. Both 2 and 3 are not factors of 5, so we add 5 to the list as prime. The list now contains { 2, 3, 5 }.

This method is known as trial division. It is a lot of work if done by hand, but computers are great at doing monotonous, high-volume calculations like this quickly.

The next part of the problem is to find the prime factorization of a given number. I used trial division again to accomplish this. A list is generated that contains prime numbers to use as candidate factors. A second list is used to store numbers that are actual prime factors of the target. A prime number is generated, in sequence, one at a time and tested against the target. When a prime factor is found, the target is reduced by dividing it by the given factor and the factor is added to the list of prime factors. The prime is checked again to see if it appears in the prime factorization multiple times (such 20, which has a prime factorization of 2 * 2 * 5). Each time the target is reduced as a prime factor is found, and when the prime fails as a candidate, the program generates the next prime in sequence to test as a prime factor candidate.

Here are some screenshots of the console program in action, using inputs 10, 20, 65, and 1,234,567,890

The code, with comments:



    class Program

    {

        static void Main(string[] args)

        {

            //The target number to generate a prime factorization for.

            long target;



            //List to store the prime factors of the target.

            List<long> primeFactorList = new List<long>();



            //List to store all primes. Generated as needed.

            List<long> candidateList = new List<long>();



            //Seed the candidateList with 2 as the first prime.

            generateNextPrime(candidateList);



            //Get the target number.

            Console.Write("Please enter a number to generate a prime factorization for: ");

            string userInput = Console.ReadLine();



            //Validate input is a valid long number. If not, get new input.

            while (long.TryParse(userInput, out target) == false || target < 2)

            {

                Console.Write("\nPlease enter a positive number greater than 1: ");

                userInput = Console.ReadLine();

            }



            //Main while loop. Once the target is 1, we know that we have found all the prime factors.

            while (target > 1)

            {

                //The value of the index at the last prime discovered in our candidate list.

                int lastIndex = candidateList.Count - 1;



                Console.WriteLine("\nChecking against prime number " + candidateList[lastIndex]);



                if (target % candidateList[lastIndex] == 0)

                {

                    //Our target is divisible by the prime number candidate. Add this to the prime factorization list and reduce

                    //our target by dividing it by this prime factor.

                    target = target / candidateList[lastIndex];

                    primeFactorList.Add(candidateList[lastIndex]);

                    Console.WriteLine("\nPrime number " + candidateList[lastIndex] + " added as a prime factor.");

                }

                else

                {

                    //Our target was not divisible by the current prime number candidate. Find the next prime candidate to test.

                    generateNextPrime(candidateList);

                }

            }



            //All prime factors have been found by this point in the program. Now we just need to output the prime factorization.

            if (primeFactorList.Count == 1)

            {

                //1 prime factor.

                Console.WriteLine("\nThe number is prime.");

            }

else
{
//Multiple prime factors
Console.Write("\nThe prime factors are: ");
foreach (long primeFactor in primeFactorList)
{
Console.Write(primeFactor);
if (primeFactor < primeFactorList[primeFactorList.Count - 1]) Console.Write(" * ");
}

}




            Console.Write("\n\nPlease press any key to close...");

            Console.ReadKey();

        }



        static private void generateNextPrime(List<long> primeList)

        {

            //This method will generate the next prime number in the sequence of all primes stored in primeList. The method uses trial division by comparing

            //the candidate number to all previous primes.



            //If the list is empty, seed it with 2 as the first prime in the sequence.

            if (primeList.Count == 0)

            {

                primeList.Add(2);

                return;

            }



            //Find the last prime in the discovered sequence. Start looking for a new prime at the very next number.

            long lastPrime = primeList[primeList.Count - 1] + 1;

            bool foundPrime = false;



            //Loop until the next prime is found.

            while (foundPrime == false)

            {

                bool notPrime = false;



                //Compare the candidate number to all previous discovered primes. If the candidate is not divisible by any of the primes, then its prime factorization

                //will be 1 and itself, which means it is indeed prime.

                for (int x = 0; x < primeList.Count; x++)

                {

                    if (lastPrime % primeList[x] == 0)

                    {

                        //This number is divisible by a previously discovered prime number. It is not prime.

                        notPrime = true;

                        continue;

                    }

                }



                if (notPrime == false)

                {

                    //The number is prime. Add it to the prime list and flag the while loop to stop.

                    foundPrime = true;

                    primeList.Add(lastPrime);

                }

                else

                {

                    //The number was not prime. Try the next number.

                    lastPrime++;

                }

            }

        }

    }

Project Examples: 3D Lightsaber Model

2013-02-24T10:53:00.000-05:00

I apologize to anyone who wants to read this blog regularly as I have not had time to update it with a proper coding post in a few weeks. I am in the home stretch of my undergraduate work. All of my classes will be completed by the end of the spring term. Once that is done, I have two projects to complete for my degree, which will both be games. I am excited and cannot wait to complete them.

In the meantime, I wanted to show off a small project I did this week for a 3D modeling class. We are using Maya 2011 for the class. The project was to model a weapon using primitive polygon modeling. Since primitive polygons are great for modeling man-made objects, and since natural curvatures take a lot more time, I decided to model a lightsaber from the Star Wars series. Bonus points to anyone who can guess which movie and hilt I used as reference, but please note that some of the finer details are missing from the model.

The next stage of this modeling project will be to work on textures, modeling a character to use the weapon, and then finally to animate the scene. I'm not an artist, but I'm happy on how this one turned out.

Miscellaneous: Videogame Violence: A Second Look from the Perspective of the Gaming Culture

2013-02-14T20:43:00.003-05:00

I was going through some old files on my PC to decide what needs to be moved to archive and off my main hard drive. I found this while looking through some of the folders. It was a fun little positional essay I wrote concerning videogame violence for one of my composition classes. I thought I'd repost it here for fun:

Videogame Violence: A Second Look from the Perspective of the Gaming Culture

The party of warriors crashed through the underbrush into the clearing. An elf, tall and lean, was carrying an ornate golden bow. A man, strong and fearless, was sporting armor and broadsword that seemed more decorative than functional. And a dwarf, stout and sturdy, yelled a battle-cry through his thick beard, swinging his large axe in wide arcs. In front of the trio was a clearing in the dense forest where five goblins had set up a small camp. The fire in the center was burning bright, and the goblins scrambled to pick up their own crude weapons for the coming fight. The elf, man and dwarf made short work of the group of goblins, their weapons hewing through flesh and bone. The corpses lay in a pile, and the trio began looking through the camp for anything valuable. They would carry the spoils with them, food and healing herbs, to the next small camp only a short walk ahead. Perhaps there they would find a weapon better than what they currently possessed; A bow that made its bearer shoot faster and farther or a sword with cryptic runes that would slowly heal its bearer’s wounds. They would continue this pattern throughout the night. They would never tire, for these three were not living in the conventional sense, but in the virtual sense. They were avatars, or a virtual representation of a person, for a popular game known in gaming culture as an “MMORPG,” or, “Massively Multiplayer-Online Role-Playing Game.” When the users who created them would log off the virtual world, they would not move. Their world would persist, but they would wait motionless and lifeless where they stood until their user logged back on for more carnage and mayhem. The world of fantasy violence awaits.

Since their humble inception, videogames have become a significant part of American culture. The stereotypical gamer, anti-social and brooding, has been portrayed in the media in a negative light for many years. Only recently has some of the stigma of playing videogames lifted as they have become more mainstream and widely accepted by society. Some of the stigma still lingers, however. Images still haunt communities around Littleton, Colorado and Paducah, Kentucky, famous for their school shooting incidents. Various psychologists perform studies on videogames and their effects on children and their conclusions are often the subject of talk of parents. When looked at by other professionals who are self-professed “gamers,’ the results of these studies are sometimes interpreted very differently. Videogames have been unfairly criticized and vilified for a number of societal problems and incidents due to various misconceptions about gaming culture. Often, benefits from playing videogames are not studied or overlooked. Stereotypes concerning people who play videogames devoutly are often false and results from studies on videogames can often be seen as skewed by the media.

Concern over videogame violence can be seen as far back as the 1970s with an obscure arcade cabinet game called Death Race. Like all early videogames, the graphics were crude and left a lot to the imagination. A block was to represent the car, and the player earned points for running down stick-figures scattered in the road. The stick-figures were to represent “Gremlins,” but this style of graphic violence caused the game to be banned in some areas of the country (Kushner, 2003, p. 79). Even with very little graphical detail, and a small set of instructions that clearly stated the car was not running over people but rather monsters, society let their imagination run wild. Unfortunately, they overreacted and assumed the worst. Children would be corrupted and tempted to run down pedestrians in real-life.

The controversy in Death Race was the first major issue to strike the burgeoning industry concerning violence. Videogames were a brand-new medium, captivating the minds of many computer enthusiasts at the time. By the time the first videogames were shown to the public, society did not know how to react. Chaplin and Ruby write in their 2005 book Smartbomb: The Quest for Art, Entertainment, and Big Bucks in the Videogame Revolution, “Considering that most people in America had never seen a computer in 1962, to actually be able to play with one – to control a visual representation on screen – left them speechless” (p. 46). The backlash to videogames in the early years is easy to understand since many in the general public, in fact, did not understand videogames or computers. One of the very first videogames, Spacewar, was discontinued from mass-production due to general confusion from the large instruction manual that came with it. This was something that very few people had seen or even thought of. The games were created by brilliant programmers working in labs at MIT or Berkeley on the very first computer systems available to the academic and business world. They viewed the programs they created as a way to expand their problem-solving skills. They were pioneers in an industry that did not yet exist and were misunderstood by the general public.

Videogames gradually gained acceptance and popularity in American culture. The industry crashed and recovered in the 1980s. A Japanese company called Nintendo succeeded in gaining a large share of the market and producing a game console that was affordable enough to be placed in many homes. Many programmers and computer enthusiasts challenged themselves to create games on their own systems, inspired by games and characters such as Mario. Two of these enthusiasts were John Carmack and John Romero, founders of id software and creators of several violent games such as Wolfenstein, Doom, and Quake. These games would go on to be linked to the tragic school shooting incidents that took place in Littleton, Colorado and Peducah, Kentucky.

The two teen shooters from the Columbine shootings were said to be warped by their favorite music and their favorite game, Doom. Doom was shown in a negative light in the media, portrayed as sick fantasy and ultra violent. Today, many writers look back on the incident as an example of how an industry is portrayed when conclusions are rushed. Fantasy violence was not new and had existed before in other forms of media and imagination. Kushner, an American writer and Journalist, stated in his book Masters of Doom:

Violent fantasy, of course, had an ancient history. Readers had been fascinated by the gore in Beowulf for over a thousand years (“The demon clutched a sleeping thane in his swift assault, tore him in pieces, bit through the bones, gulped the blood, and gobbled the flesh”). Kids played cops and robbers, brandishing their guns and flying backwards in imagined bursts of blood. (2003, p. 79)

Had the shooting incidents not occurred, the fantasy violence in games such as Doom may have been overlooked or unnoticed. The outrage over the incidents fueled public rage and led to a scramble to make sense out of a senseless act. It is argued that the music and videogames that these teens played were the scapegoat for the incidents because they had not yet reached mainstream acceptance. Doom was distributed not through retailers, but freely through the internet. The new forms of metal played by acts such as Nine Inch Nails and Marilyn Manson were demonized and also associated with the same games. Kushner explained that Trent Reznor of Nine Inch Nails had agreed to record music for Carmack’s next violent game, titled Quake (2003, p. 213).

Some proponents of the videogame industry view fantasy violence as essential for a child’s normal development, teaching him or her to be able to distinguish fantasy from reality much better than a child who has not had any experience with fantasy violence. Charles Herold, a writer for the New York Times and videogame critic, challenged parents to attend a boxing match with their child and watch as the crowd cheers and a man is beaten until he can no longer compete. He stated, “Perhaps then people will realize that an animated spear is better than a real fist and they will e-mail me with their gratitude for luring the world away from true violence. They are most welcome” (2005, para. 21). It’s true that sporting events today are not the same violent spectacles the Romans put on for their public, but real violence in sports can still have an effect on a child. A favorite star gets physical with another player, and a child may assume that this sort of physicality is acceptable. A child who plays a violent game will know the level of violence on screen is fantasy and is not acceptable in the real world.

Studies on how videogames affect children are numerous. One of the most active in the field of study is Anderson, a PhD and journalist for the American Psychological Association. His report on violent videogame studies state that children who routinely play violent videogames are subject to a moderate but predictable rise in aggressive behavior and thought (2003, para. 4). A moderate increase in aggression may serve as proof to some that videogames are responsible for all aggressive behavior. The very same conclusion was drawn in the past when studying the effects of contact sports on college and high school students. Goleman, a journalist for the New York Times, wrote in 1985, “Since football athletes might be more aggressive to start with, the telling point in this research is that, as the season goes on, these athletes grow more hostile and aggressive, and remain so in the off-season. That result was not found with swimmers” (para. 12). Aggressive behavior in individuals has always been present, and experts and researchers will continue to do studies on activities and other areas of our culture that contribute to aggressiveness. Videogames were not the first scapegoat of aggressive behavior, and will not be the last. Organized sports such as football and hockey are an accepted part of modern culture and serve many benefits to the players. These sports are not banned because of an increase in aggressive behavior in the participants. Videogames, similarly, have many benefits not reported in the aggression studies.

Skills that can benefit from videogames vary. Some, in common with organized sports, let the player build upon his teamwork skills. Others are not readily apparent but are now being studied, such as the effects of the player’s problem solving and critical thinking skills. Young, an American journalist, studied research by Steinkuehler. Young reported on Steinkuehler’s argument, “’People were actually—no kidding—gathering data on things like the game monster's behavior, putting it in an Excel spreadsheet, and building little mathematical models to try to beat the monster,’ she told me recently. The game teaches complex problem solving and collaborative learning, Ms. Steinkuehler argues” (2010, para. 4). If these studies continue and are able to ascend to the same level as the aggression studies, many may see all the benefits that videogames may offer and stop focusing on just the behavioral studies that indicate videogames instill aggressive behavior and anti-social tendencies in players.

As a testament to the skills that videogames can teach and hone, the government has been using videogames extensively. In the mid 1990s, when Senator Lieberman and President Clinton were calling for regulation of the videogame industry due to its violence, the military had licensed the Doom engine built by Carmack, and built a new version called Marine Doom. This version of the game was used to teach soldiers teamwork in an urban combat environment since eight players were able to cooperatively conquer the many levels (Kushner, 2003, pp. 193-194). More recently, the armed forces have released their own game series entitled America’s Army. The games can be downloaded and played for free from the web-site www.americasarmy.com. Inside the games, the player must go through virtual boot camp that includes conquering an obstacle course, learning basic and advanced rifle skills, and even sit inside a virtual classroom to learn other vital areas of warfare, such as combat first aid. Once the player finished boot camp, he is allowed to play with others on various locations that pit two squads against each other, much like war games played at real boot camps. The game is hugely popular and is widely known to be one of the Army’s best recruitment tools. From within the game, the player can request to have information on joining the armed forces sent to his address or be contacted directly by a real recruiter over the phone.

Videogames have slowly been becoming accepted as part of mainstream culture over its history. The violence in videogames has often been cited as a societal problem that contributes to delinquency and violent behavior in youths. In much the same way the music industry and motion picture industry were targeted years before, videogames became a scapegoat for the public and for politicians. With the help of greater societal acceptance and studies that reveal benefits from videogames, the industry is slowly shedding the stigma associated with fantasy violence and aggressive behavior. Even the government uses videogames as a training and recruitment tool for the military. The next time a zombie is shown being dismembered on a television or computer monitor, remember that violence is not the cause for societal behavioral problems and that the game may be teaching the player critical thinking and problem solving skills. He must figure out a way past all obstacles whether they are a part of the environment or a monster standing in his way to the goal. He may be working as part of a larger group, tackling a large obstacle that he would not be able to handle on his own. His culture is not one of endless violence, but of teamwork, problem solving, and critical thinking. The violence depicted is no different than the popular violence in major motion pictures, television, and sports. Videogames will receive fair judgment once all of society is able to participate and understand the concepts and challenges behind their design.

References

Anderson, C. A. (2003, October). Violent videogames: Myths, facts, and unanswered questions. American Psychological Association. Retrieved April 12, 2010 from: http://www.apa.org/about/psa/2003/10/anderson.aspx

Chaplin, H. & Ruby, A. (2005). Smartbomb: The quest for art, entertainment, and big bucks in the videogame revolution. Chapel Hill, North Carolina: Algonquin Books of Chapel Hill.

Goleman, D. (1985, August 13). Brutal sports and brutal fans. The New York Times. Retrieved April 18, 2010 from: http://www.nytimes.com/1985/08/13/science/brutal-sports-and-brutal-fans.html

Herold, C. (2005, March 24). Fighting on the screen, out of harm’s way. The New York Times. Retrieved April 12, 2010 from: http://www.nytimes.com/2005/03/24/technology/circuits/24game.html

Kushner, D. (2003). Masters of doom: How two guys created and empire and transformed pop culture. New York: Random House.

Young, J. (2010, January 24). Five teaching tips for professors—from video games. The Chronicle of Higher Education. Retrieved April 19, 2010 from: http://chronicle.com.bakerezproxy.palnet.info/article/5-Lessons-Professors-Can-Le/63708/

Algorithms: Replace all ' ' characters in a string with "%20"

2013-02-11T21:59:00.000-05:00

In McDowell's (2012) Cracking the Coding Interview, we arrive at problem 1.4.

1.4 - Write a method to replace all spaces in a string with "%20". You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: If implementing in Java, please use a character array so that you can perform this operation in place.)

EXAMPLE

Input: "Mr John Smith "

Output: "Mr%20John%20Smith"

This problem was pretty straightforward, and I'd like to alter it a bit. I am not going to assume that the string has enough spaces at the end, because somewhere down the line, some engineer will not read the documentation and toss in a string with no trailing spaces. Since I assumed that there were trailing spaces, that's a nice crash that was unanticipated. Instead, my method will trim any space characters that are leading or trailing the string. That way, we are sure that every string that is passed to this method DOES NOT have enough space to store the extra characters. Every string is passed through the Trim() method to be equal. We can avoid having to throw an exception when we have some strings with trailing spaces and some strings without.

The original problem was also pretty clear that in-place operations are preferred. I wrote my method in C#. This means that the strings are immutable, and I cannot swap characters in place. Instead, I tried to do the next best thing. Convert the string to a character array, swap the characters in place in that array, then convert the array back into a string. I understand that new memory is allocated for the character array, and then memory is allocated again for the new string, so the method isn't quite as in-place as it would be in Java, but that's OK for the exercise.

The first thing I do (after the Trim()) is to count the number of spaces in the string. For each space, we need two more empty characters added to the string to make sure there is enough room to store all the "%20"'s. After that is done, we convert the string to a character array.

From here, we begin moving characters from the end of the original string to the end of the lengthened string. For all non-space characters, it's a simple move. When we get to a space character, we replace it with "%20". In either case, we decrement our indices carefully until we get to the beginning of the string. From here, we cast the array back into a string and store it as the original variable, which is passed back to the caller as it was given as reference.

My goal for this method was not the shortest code, but the shortest time complexity. The time complexity is O(n), which means it will scale well when given large strings. Somehow, I have a feeling somebody will try to pass in a string that contains the entire manuscript of "War and Peace" so that they have an HTML version whenever they feel the need to read the classic...

Here is the code:



//Brandon Theolet

//

//1.4 Write a method to replace all spaces in a string with '%20'. If implementing in Java, please use a character array so that you can perform this operation in place (McDowell, 2012).

//

//McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions. Palo Alto, CA: Career Cup, LLC.



using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;



namespace Problem1_4

{

    class Program

    {

        static void Main(string[] args)

        {

            //Get a string from the user.

            string myString;



            Console.Clear();

            Console.Out.Write("Please enter a string: ");

            myString = Console.In.ReadLine();



            //Call the method and display a before and after

            //comparison showing the transformation.

            Console.Clear();

            Console.Out.WriteLine("Given string:\t\t\"" + myString + "\"");

            insertHTMLSpaces(ref myString);

            Console.Out.WriteLine("\nTransformed string:\t\"" + myString + "\"\n");

          

            //Pause to display results before closing.

            Console.Out.Write("Please press any key to exit...");

            Console.ReadKey();

        }



        static void insertHTMLSpaces(ref string myString)

        {

            //The original problem has been modifed for

            //this exercise. It stated that we can assume

            //there is enough space at the end of the

            //string to insert the characters. Instead,

            //we are not assuming there are enough spaces

            //to do the in-place operations. This means we

            //have to create the space first. For every

            //space present in the string, we need to add

            //two more.

          

            //If extra spaces were given at the beginning or end, remove them.

            myString = myString.Trim();



            //The true length of the string.

            int stringLength = myString.Length;



            if (stringLength < 1) return;



            for (int myIndex = 0; myIndex < stringLength; myIndex++)

            {

                //Add additional spaces for in-place operations.

                if (myString[myIndex] == ' ') myString += "  ";

            }



            //The last character index in the lengthened string.

            int lastCharIndex = myString.Length - 1;



            //The last character from the original string.

            int partitionIndex = stringLength - 1;



            //Convert the string to a char array for in-place swaps.

            char[] myCharArray = myString.ToCharArray();



            while (partitionIndex >= 0)

            {

                if (myString[partitionIndex] != ' ')

                {

                    //Character at partitionIndex is not a space.

                    //Move it to the rear of the string.

                    myCharArray[lastCharIndex] = myCharArray[partitionIndex];

                    lastCharIndex--;

                    partitionIndex--;

                }

                else

                {

                    //Char at partitionIndex is a space. Replace

                    //it as neccessary.

                    myCharArray[lastCharIndex] = '0';

                    myCharArray[--lastCharIndex] = '2';

                    myCharArray[--lastCharIndex] = '%';

                    lastCharIndex--;

                    partitionIndex--;

                }

            }



            //Allocate the transformed string back to the original

            //variable since it was passed by reference.

            myString = new string(myCharArray);



            //O(n) time complexity, in-place swaps in the char array,

            //method ensures there is enough memory to insert extra

            //characters. Return control to caller.

            return;

        }

    }

}

Here are some screen shots of the program in action:

Reference:

McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions. Palo Alto, CA: Career Cup, LLC.

There is a Fine Line Between Learning and Failure

2013-02-05T18:22:00.001-05:00

I was talking with some of my fellow students today and the discussion turned to academic projects. Which academic projects had us learn the most?

Most of the examples that I heard were projects that were overly easy. Very little thought process was put in place for these. The student was able to complete it way ahead of the deadline by applying an established design principle or design pattern. Basically, a problem was given to a student who already knew the answer.

This isn't learning. This is merely practice.

Problems like these definitely have their place in a college curriculum. Practice is essential to hone any skill and keep it sharp. Major League ballplayers don't stop hitting balls in batting practice once they've learned the exact technique their hitting coaches want them to learn. Likewise, programmers shouldn't stop applying existing design patterns to new problems that merit the pattern once they've learned it.

Practicing skills was not the topic of the original question. We asked which project had us learn the most. My answer was a project that I came very close to failing. Some of the guys in the conversation had the same class and the same project, and they shuddered at the thought of it. Many of them had failed that project in at least one requirement of the assignment.

What was the project? It was in a class called Game Console Development and involved writing a working video game in the XNA 4.0 framework that would run on both a PC and an X-Box 360. The course itself was six weeks long, with five weeks given to the project, full of all the standard reading and assignments given in any college course.

This project was not a greenfield project. A greenfield project, for those not familiar with the term, is a code project created from scratch. Those projects tend to be easier for college undergrads because that individual has no questions about the framework because he or she wrote all of it. This project used the XNA 4.0 framework, which is vast and documented (quite well) over at the MSDN web-site. Not only did we have to contend with this framework that was brand new to most of us, but we were also given another framework inside of that one to build around.

Because of the length of the course, our instructor wanted us to spend most of our time on programming game logic and not setting up an infrastructure to display menus and options and load the game assets. At first, this was a welcome blessing. The menu system seemed easy enough to understand with the example code at first glance.

Then we were asked to change it. Because we couldn't leave the default settings for these menus in place since they had nothing to do with our game. The blessing quickly became a curse.

If you would like to check out the code in question, titled Game State Management Example, it is available for everyone here.

Now, looking at this production quality code, written by some great software developers who are loads smarter than I am, made me feel inferior. Not only had I never written anything close to this elegant, beautiful sample framework, but at first I couldn't tell you what many of the lines actually did. It was all Greek to me. I got the overall picture, but instead of using this framework as a black box, I was expected to open it up and tinker with the fragile components. What does this do? I had no idea where to start. Changing some of the code often left me with a bunch of code that no longer compiled.

Now, compare this to the projects discussed earlier, where the students had a clear idea of what was needed and knew every line of code by heart because they authored it. Those projects were practice, and this was learning.

I knew what the results of the sample were. I had run the code on both my PC and X-Box 360. There was an abstract data type that defined what a screen was, and then there were classes that used these defined screen properties to define specific types of screens. That much was clear. I could also find the one screen that proudly displayed the message, "Game code goes here..." So, my game would be coded there, but for the rest of it...I had no idea.

I wanted to be angry with my instructor for working up the assignment this way. Why would he give us code that was so advanced compared to our study of .NET and C# that we would have no idea how to work with it? I tried to bring this up to him as politely as I could, and he gave me an answer. His answer was so important to how things actually worked, and I felt like an idiot for not realizing it.

My instructor, Andy Dunn, formerly of Microsoft and now senior game programmer extraordinaire at Exato Game Studios, told me that rarely in the real world would I be implementing code from scratch. More likely, I will debug, maintain, and add to existing code much like we were doing in this assignment. I was floored, like a boxer who is staring at the stadium lights and can't find the will or energy to stand back up for another round. I was ready to tell myself that if I couldn't understand this, then I shouldn't be in software development.

Good thing I didn't listen to myself about quitting.

There was a lot of trial and error. There was a lot of back-and-forth discussion about the fine details of the framework with Andy. And there was a lot of frustration. But, I ended the course with a passing project. I had not been able to implement all of the features that I wanted to, but I was able to implement all of the features required for the assignment and then some. I was also able to secure some positive feedback from Andy, who told me it looked very polished, you know, for a student project.

I came very close to failing this project because I was ready to quit. I was frustrated with not knowing how all of this code worked. To me, it was pure voodoo. The Microsoft team that wrote it was using arcane PC wizardry to get XNA and .NET to do things I had never been exposed to. I saw little value in using this framework as a foundation for my game, until my mentor stepped in and got me to do it. I forced myself to continue failing at this project until I got it working.

And then I no longer felt like a failure, but rather like a ragged and tattered survivalist who was lost at sea. The design patterns and challenges about sorting small arrays and comparing drop-down list items and writing classes to do binary arithmetic were simply the kiddie-pool. I now saw the actual danger of the open sea and how easy it was to get swept away and drown. To avoid drowning, I would need to be able to dive into huge waves and swim for my life by picking through unfamiliar code and somehow making it work.

Microsoft Research published a paper on some of the skills that fresh graduates lack upon obtaining their first software developer position. Not surprisingly, working on a team with a large established code base was one of the top issues highlighted in the paper. I still feel inferior when comparing myself to some of the best that Microsoft has to offer, but I feel a bit better after reading that new hires in that company experienced some of the same problems that I did on my academic project.

What did I learn during this course? I learned that existing codebases take a lot of time to get familiar with when they are new to you. I learned that trial and error does not mean I'm a total idiot. I learned that three years of study lets me get out of the kiddie pool and see firsthand how much knowledge is actually present in the software development industry. But, the most important lesson of all, I learned that there is a fine line between learning and failure.

Algorithms: Determine if Two Strings Are Permutations of Each Other

2013-02-05T11:00:00.004-05:00

In McDowell's (2012) set of problems, we come across problem 1.3: Given two strings, write a method to decide if one is a permutation of the other. If two strings are permutations, then they will have the same characters. Given "ABCDEF" and "FEDCBA", we can determine that these strings are permutations. They contain the same characters, just in different orders.

To go about solving this problem, I decided to use a similar approach to previous string algorithm problems and use an array to produce behavior that is similar to a hash table. An array is declared with spots equal to the number of possible characters. In extended ASCII, this is 256. My array has indices from 0 to 255.

There are two basic checks that I came up with to determine if the strings are permutations. The first is to check the length. If the strings are not the same length, they cannot be permutations. Next, I simply count the characters in each string. If the counts do not match, the strings are not permutations.

I did the counts by first adding the counts from the first string to the count array, and then subtracting the counts from the second string from the count array. At this point, each index in the count array should be 0. If any spot does not equal 0, then the strings are not permutations.

Here is the complete source code. I've written this one in C# in order to brush up on the basic syntax instead of C++.



//Author: Brandon Theolet

//

//McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions (5th ed.). Palo Alto, CA: Career Cup, LLC.

//Problem 1-3: Given two strings, write a method to decide if one is a permutation of the other.



using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;



namespace Problem1_3

{

    class Problem1_3

    {

        static void Main(string[] args)

        {

            //Testing harness. Prompts the user for two strings

            //and invokes the method that compares for permuatations.



            string myString1, myString2;



            Console.Clear();

            Console.Out.Write("Please enter any string: ");

            myString1 = Console.In.ReadLine();



            Console.Out.Write("Please enter another string: ");

            myString2 = Console.In.ReadLine();



            if (isPermutation(myString1, myString2)) Console.Out.WriteLine("These strings are permutations.\n");

            else Console.Out.WriteLine("These strings are not permutations.\n");



            Console.Out.Write("Please press enter to continue...");

            Console.In.ReadLine();

        }



        static private bool isPermutation(string myString1, string myString2)

        {

            //If the strings are different lengths, they are not

            //permutations.

            if (myString1.Length != myString2.Length) return false;



            //Create an array to count the number of each specific

            //character in the strings.

            int[] characterCount = new int[256];

            int charIndex;



            //Populate the array with default value 0.

            for (int index = 0; index < 256; index++)

            {

                characterCount[index] = 0;

            }



            //Count the number of each character in the first

            //string. Add the count to the array.

            foreach (char myChar in myString1.ToCharArray())

            {

                charIndex = (int)myChar;

                characterCount[charIndex]++;

            }



            //Count the number of each character in the second

            //string. Subtract the count from the array.

            foreach (char myChar in myString2.ToCharArray())

            {

                charIndex = (int)myChar;

                characterCount[charIndex]--;

            }



            //If the strings are permutations, then each character

            //would be added to our character count array and then

            //subtracted. If all values in this array are not 0

            //then the strings are not permutations of each other.

            for (int index = 0; index < 256; index++)

            {

                if (characterCount[index] != 0) return false;

            }



            //The strings are permutations of each other.

            return true;

        }

    }

}

Reference:

McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions (5th ed.). Palo Alto, CA: Career Cup, LLC.

Project Examples: Sudoku Solver with a GUI

2013-01-18T17:55:00.000-05:00

Phase two of the Sudoku project is completed. The solver now has its own GUI, or graphical user interface. The interface was created in Adobe Flash and the Sudoku solver algorithm I wrote in C++ was ported to Actionscript 3.0. If you would like to see the C++ application in action, or view the source code for that application, the posts are available here:

Project Examples: A Sudoku Solver Implementation

Code Examples: SudokuPuzzle.h and SudokuPuzzle.cpp

Some minor changes were made to the code in order to accommodate the new input system. The grid that exists in the GUI is separate from the Sudoku puzzle that exists in memory as it was written for the C++ command-line application. There are simple methods in the Actionscript code that syncs the grid with the puzzle in memory.

The interface is very simple. Click on any box to enter a number. The solver will only accept valid entries. If an entry is not valid, the puzzle will not accept it. Any box that you click on will generate a list of valid candidates to assist the solver.

There are limitations that were carried over from the C++ code to the Actionscript version. For starters, if the solver is executed with too few given clues, then the solver has the potential to run for hours. I've added a check to the solver. If there are too many potential solutions, the solver will stop running and allow the user to keep editing the puzzle.

I've had successful test cases where 17 clues were given and over 4,000 solutions were found. The solver did not stop. In a case where 16 clues were given, and this was a very poorly designed puzzle, the solver stopped immediately.

This tool was designed to assist players in completing difficult Sudoku puzzles that are well-designed. Poorly designed puzzles may be unsolvable or contain too many potential solutions in order to let the solver generate them in a reasonable amount time (less than 3 minutes). If a poorly designed puzzle is entered, do not expect a solution to be found.

Please, feel free to test the new GUI for Sudoku Master. Still on my wish list is an algorithm that will generate new puzzles for users to try and solve, and the ability to save and load puzzles. For now, the existing framework will do for a small applet that will assist in solving puzzles.

Code Examples: SudokuPuzzle.h and SudokuPuzzle.cpp

2013-01-13T14:00:00.004-05:00

My latest project, a command-line interface Sudoku solver, used the class SudokuPuzzle. Here is the source code for the header file and implementation file for SudokuPuzzle. The class will be re-used in a project that creates a GUI (graphical user interface) for the solver and adds new features, such as the ability to save and load puzzles.

SudokuPuzzle.h


#ifndef SudokuPuzzle_Header
#define SudokuPuzzle_Header

#include <vector>

using namespace std;

class SudokuPuzzle
{
public:

    //Default constructor.
    SudokuPuzzle();

    //Returns a list of candidate values for a spot at (x, y).
    void getPossibleValuesAt(int possibleSolutions[], int x, int y);

    //Returns the number of possible candidates at (x, y).
    int getNumberOfPossibleValuesAt(int x, int y);

    //Attempts to add a number to (x, y). As long as the number
    //is a valid candidate, the method returns true.
    bool addNumberAt(int addNumber, int x, int y);

    //Removes a number at (x, y)
    void removeNumberAt(int x, int y);

    //Resets the puzzle grid and solution list.
    void newPuzzle();

    //Prints the puzzle.
    void printPuzzle();

    //Returns a vector container of all the possible solutions
    //found for the current puzzle.
    void solvePuzzle();

    //Determines whether or not the current puzzle is solved.
    bool isSolved();

    //Copies the puzzle into newPuzzle with a deep copy of the
    //grid.
    void copyPuzzle(SudokuPuzzle &newPuzzle);

    //Shows a solution in the list of solutions at the
    //specified index.
    void showSolution(int index);

    //Returns a solution in the list of solutions at the
    //specified index.
    SudokuPuzzle getSolution(int index);

    //Returns the number of solutions in the list of solutions.
    int getNumberOfSolutionsFound();

private:

    //Two-dimensional grid to store the puzzle.
    int myGrid[9][9];

    //Dynamically expanding vector to store all possible solutions
    //to the puzzle. Most puzzles only have 1 solution, but poorly
    //designed puzzles may have many.
    vector<SudokuPuzzle> possibleSolutions;
};

#endif

SudokuPuzzle.cpp


#include <iostream>
#include <cmath>
#include <vector>
#include "SudokuPuzzle.h"

using namespace std;

SudokuPuzzle::SudokuPuzzle()
{
    //Default constructor. This constructor creates an empty Sudoku grid.

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            myGrid[x][y] = 0;
        }
    }
}

void SudokuPuzzle::getPossibleValuesAt(int possibleSolutions[], int x, int y)
{
    //This function will use the array possibleSolutions as a hash table to
    //determine the value of all candidates for the Sudoku grid at (x, y).
    //The hash table is then used by the calling method to determine which
    //candidates are allowed for that spot.

    for (int index = 0; index < 9; index++)
    {
        possibleSolutions[index] = 1;
    }

    for (int xPos = 0; xPos < 9; xPos++)
    {
        if (xPos != x && myGrid[xPos][y] > 0) possibleSolutions[myGrid[xPos][y] - 1] = 0;
    }

    for (int yPos = 0; yPos < 9; yPos++)
    {
        if (yPos != y && myGrid[x][yPos] > 0) possibleSolutions[myGrid[x][yPos] - 1] = 0;
    }

    int xGroup = floor((double)(x / 3));
    int yGroup = floor((double)(y / 3));
    
    for (int xPos = 0 + (3 * xGroup); xPos < 3 + (3 * xGroup); xPos++)
    {
        for (int yPos = 0 + (3 * yGroup); yPos < 3 + (3 * yGroup); yPos++)
        {
            if (yPos != y && xPos != x && myGrid[xPos][yPos] > 0) possibleSolutions[myGrid[xPos][yPos] - 1] = 0;
        }
    }

    return;
}

int SudokuPuzzle::getNumberOfPossibleValuesAt(int x, int y)
{
    //This function will return the number of candidates available
    //for the Sudoku grid at (x, y).

    if (myGrid[x][y] != 0) return 0;

    int possibleSolutions[9];

    getPossibleValuesAt(possibleSolutions, x, y);

    int candidateCount = 0;

    for (int x = 0; x < 9; x++)
    {
        if (possibleSolutions[x] == 1) candidateCount++;
    }

    return candidateCount;
}

bool SudokuPuzzle::addNumberAt(int addNumber, int x, int y)
{
    //This function will put in addNumber in the grid at (x, y) as long
    //as addNumber is a valid candidate for that spot. A boolean is returned
    //so the caller knows whether or not the number was successfully added.

    if (addNumber == 0) return true;

    if (myGrid[x][y] != 0) 
    {
        cout << "The spot at (" << x << "," << y << ") is currently occupied.\n\n";
        system("PAUSE");
        return false;
    }

    int possibleSolutions[9];

    getPossibleValuesAt(possibleSolutions, x, y);

    if (possibleSolutions[addNumber - 1] == 0)
    {
        cout << addNumber << " is not a valid candidate for (" << x << "," << y << ").\n\n";
        system("PAUSE");
        return false;
    }

    myGrid[x][y] = addNumber;
    return true;
}

void SudokuPuzzle::removeNumberAt(int x, int y)
{
    //Remove one number.

    myGrid[x][y] = 0;
}

void SudokuPuzzle::newPuzzle()
{
    //Clears the grid.

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            myGrid[x][y] = 0;
        }
    }
}

void SudokuPuzzle::printPuzzle()
{
    //Display the puzzle for implementation
    //in a command-line environment.

    cout << "\t0 1 2  3 4 5  6 7 8\n\n";

    for (int y = 0; y < 9; y++)
    {
        cout << y << "\t";

        for (int x = 0; x < 9; x++)
        {
            cout << myGrid[x][y] << " ";
            if (x == 2 || x == 5) cout << " ";
        }

        if (y == 2 || y == 5 || y == 8) cout << "\n\n";
        else cout << "\n";
    }
}

bool SudokuPuzzle::isSolved()
{
    //Determine if all spots are filled with valid candidates.

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            if (myGrid[x][y] == 0) return false;
        }
    }

    return true;
}

void SudokuPuzzle::solvePuzzle()
{
    //The puzzle solving algorithm. The algorithm scans each spot
    //and starts with the spot that has the lowest number of 
    //possible candidates. Each candidate is tried one at a time
    //and the rest of the spots are filled in the same manner.
    //If a spot is found that is not yet filled, but there are no
    //valid candidates, then the puzzle is unsolvable and a new
    //candidate is tried in a previous spot.

    int candidateX, candidateY, candidateNumber = 100, tempCandidate;
    int candidateList[9];

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            if (myGrid[x][y] == 0)
            {
                tempCandidate = getNumberOfPossibleValuesAt(x, y);

                if (tempCandidate < candidateNumber)
                {
                    candidateNumber = tempCandidate;
                    candidateX = x;
                    candidateY = y;
                    getPossibleValuesAt(candidateList, x, y);
                }
            }
        }
    }

    //All candidates have been determine for (candidateX, candidateY) where
    //that spot has the least amount of candidates. Loop through those candidates
    //and attempt to solve the next resulting puzzle.

    for (int index = 0; index < 9; index++)
    {
        if (candidateList[index] == 1)
        {
            addNumberAt(index + 1, candidateX, candidateY);

            if (isSolved()) 
            {
                SudokuPuzzle tempPuzzle;
                copyPuzzle(tempPuzzle);
                possibleSolutions.push_back(tempPuzzle);
            }
            else solvePuzzle();
            
            removeNumberAt(candidateX, candidateY);
        }
    }
}

void SudokuPuzzle::copyPuzzle(SudokuPuzzle &newPuzzle)
{
    //Deep copy the grid into newPuzzle.

    for (int x = 0; x < 9; x++)
    {
        for (int y = 0; y < 9; y++)
        {
            newPuzzle.addNumberAt(myGrid[x][y], x, y);
        }
    }
}

void SudokuPuzzle::showSolution(int index)
{
    //Show the solution in possibleSolutions at the specified index.
    
    if (index < 0 || index >= possibleSolutions.size()) return;

    possibleSolutions[index].printPuzzle();
}

SudokuPuzzle SudokuPuzzle::getSolution(int index)
{
    //Return the solution in possibleSolutions at the specified index.

    if (index < 0 || index >= possibleSolutions.size())
    {
        SudokuPuzzle newPuzzle;
        return newPuzzle;
    }
        
    return possibleSolutions[index];
}

int SudokuPuzzle::getNumberOfSolutionsFound()
{
    //Return the number of solutions in possibleSolutions.

    return possibleSolutions.size();
}

Project Examples: A Sudoku Solver Implementation

2013-01-13T13:49:00.001-05:00

While on vacation in Florida, I got a bit restless during some downtime and broke out Visual Studio in order to see if there was anything I wanted to try and program. One of the ideas that came up was a Sudoku solver.

The project took a day or so to code. The goals of this implementation were, to establish a proof-of-concept:

1. Store a Sudoku puzzle in computer memory.

2. Access the Sudoku puzzle and display it on the screen.

3. Create and implement an algorithm to solve a Sudoku puzzle that a user inputs.

These goals were all met with the project. The implementation was written in C++ and uses a command-line interface to interact with the user.

In order to show off what this implementation can do, I took some screenshots. The puzzle used in this example is located here: http://www.sudoku.ws/extreme-20.htm

Here is what the user sees when the program is started. There is a blank Sudoku grid and a menu of options. The user can input a puzzle either 1 number at a time, or iterate through each spot and input the entire puzzle. I prefer option 1 to enter my puzzles.

When option 1 is selected, you are prompted to enter a value for each spot at (x, y) on the coordinate system. At any time, the user may stop entering new numbers, which will take him back to the main menu.

Here is my screen after I finished entering the puzzle. The puzzle values are displayed along with the main menu. From here, if we were trying to solve the puzzle manually, we can use option 4 to view a list of candidate numbers for a certain spot.

In this screen, I elected to view the candidate list for spot (1,1) on the Sudoku grid. The program calculates the valid candidates and returns the list for display. This information is helpful for those trying to manually solve the puzzle.

Finally, the option that is the backbone of the entire project, is the automated solver. I selected the automated solver and it returned 1 solution. This solution matches exactly with the posted solution on the web-site that provided the test puzzles. If there were more than 1 solution, the user has the option of viewing them 1 at a time in a slide-show format. At any time, the user may select the solution he wishes to do more work with and that puzzle is then brought back to the main menu. This feature should be of help to Sudoku puzzle designers as they can see how removing numbers from the puzzle impacts the candidate lists for each spot.

The command line implementation utilizes a greedy algorithm and recursion to solve the puzzle. The first thing the solver does is scan the grid to determine which spot has the least amount of valid candidate numbers. From here, the solver simply inputs the first candidate and then repeats the process. When a puzzle becomes unsolvable, where an empty spot has no valid candidates, control is simply returned to a previous spot, and the next valid candidate is attempted. The algorithm has O(n ^ 2) time complexity due to the nested loops within each recursive call, but there is an upper limit since each Sudoku puzzle has, at maximum, 81 empty slots.

If you would like to try out the solver, I have uploaded it to Google Drive. Simply download the Sudoku solver and run it on your PC.

The next stage of this project is to implement the SudokuPuzzle class in a Windows form application that will allow us to create a GUI (graphical user interface) in order to allow easier puzzle input. I would also like the option to save and load puzzles for the application.

If you would like to see the source code for the SudokuPuzzle class, it is available here. The class contains the solver method.

Algorithms: Reverse a String when Given a Pointer to the First Character

2012-12-30T21:31:00.003-05:00

First, my code. Then, the explanation.

void reverse(char* str)
{    
    if (str == NULL || *str == '\0') return;

    char *tail = str;

    while (*tail != '\0')
    {
        tail++;
    }

    char tempChar;
    tail--;

    while (str < tail)
    {
        tempChar = *tail;
        *tail = *str;
        *str = tempChar;
        str++;
        tail--;
    }

    return;
}

What does the above function do? Well, if you paid attention to the title, or if you can read C++, this should be fairly obvious.

The method in question is called reverse and passed to the method is the sole pointer to a string. This method assumes that the string in question will be a basic ASCII string that is null terminated. In fact, that what '\0' represents. The null terminator.

Where are the comments? Well, since the code is fairly simple, and after reading a blog essay by Steve Yegge, the comments were left out. The essay in question is here: Portrait of a N00b. I'll forgive the perceived insult because Steve Yegge is right: I'm a n00b. Besides, had I documented the method with enough comments to double the line-count, I wouldn't be able to write a descriptive blog post about my thought process going into the method, now, would I?

The original problem once again comes from McDowell (2012).

Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string.

Now, that question seems pretty straightforward. The author's solution given in the book is a little different from mine in trivial items. The logic is exactly the same. That made me very proud, until Mr. Yegge reminded me that I am still a n00b at programming compared to a two-decade veteran who has worked for Amazon and Google. Again, not insulted, but now blissfully aware of how much harder I need to study outside of and in addition to my core classes at Baker College if I ever hope of landing an offer with one of the Big Four.

Had this been an actual interview question, I would have asked a few questions before coding this. Because these questions are from an interview preparation book, I can not unfortunately ask any questions, but only make assertions. From the problem, the string is known to be null-terminated. What I did not know was what encodings this method should handle. My assertion was the string would be a basic ASCII string and not Unicode. I would have also asked if I was allowed to declare additional pointers and variables within the method. My assertion was that I was allowed to. The reason I would have asked this question is that I've seen message board postings with a similar problem that gives the same method signature, but adds the qualifier that no additional pointers or variables may be declared. This solution came together in ten minutes, and was tested in two. Had this been an actual interview, I would have been able to write it, test it, and explain what I was doing within the confines of the interview. If I was not able to declare any local pointers or temporary variables, this would have taken much longer and probably would have overran the time constraints of said interview.

Starting off, the first line of code is just basic optimization. If we were given a pointer that points to NOTHING, or to a null-terminator character itself, it means we have no string to work with. Nothing more is needed, so we return the control to the calling method. The method signature also states we return nothing, hence no error code such as "return 1;".

Yes, Mr. Yegge, I am a two-year old explaining how this big scary programming world works so that I know I understand it. At least I'm following one of your blogging rules, which is write a blog. :D

The next line declares a new pointer called tail and sets it to the address of the same starting character pointed to by str. So far, the time complexity of the method is O(1).

From here, we need to increment the tail pointer in order to find the null-terminator character. After that, we decrement the tail pointer so that it points to the last non-terminator character in the string. This loop changes the method time complexity to O(n) where n is the number of characters in our string. I saw no reason to limit how large the string can be that is passed. If I had, I would have kept track of how many times we incremented the tail pointer and then checked to see if the string fell into the confines of our arbitrary limit.

Now that the tail is found, we simply switch the first character, pointed to by str, and the last character, pointed to by tail. Now, we increment str and decrement tail, so that they both move toward the middle of the string, and swap each character again. We keep doing this until str and tail are at the same memory address or have passed each other. This means that the entire string is now reversed.

The overall time complexity of the method reduces to O(n). This means it scales linearly as the number of characters in the string gets larger. I see no way to make this O(1) constant time. If any industry veteran out there is reading this and knows a trick to do so, please feel free to share. I love it when n00bs like me are mentored.

The code I provided is my own code. It is not elegant, but simply straightforward. I chose to implement a "quick and dirty" solution rather than trying to hack the compiler to achieve the fastest possible run time. Depending on the project, "quick and dirty" may have saved the company some money by not devoting days to optimizing something that shouldn't break the overall project.

If this does break the project, then methinks I'm doomed...

Reference:

McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions (5th ed.). Career Cup: Palo Alto.

Algorithms: Design an Algorithm to Determine if there are Repeating Characters in a String

2012-12-20T11:13:00.000-05:00

Lately, I've been practicing coding techniques by taking a look at different coding problems available for those preparing for computer science positions. The practice problem I worked on today involves both algorithm design and coding. The problem comes from Gayle Laakmann McDowell's Cracking the Coding Interview.

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

The first thing I did was start thinking about possible ways to solve this. For the example, I am using C++. C and C++ recognize a string as an array of characters. If I was given this problem as part of an interview, I would ask if the string would be passed in ASCII or in another format. For this example I am assuming that all characters are ASCII.

My first algorithm is a straightforward, brute force approach. Basically, we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2) because of the nested loop.

bool noRepeatingCharacters(string myString)
{
    for (int x = 0; x < myString.length(); x++)
    {
        for (int y = 0; y < myString.length(); y++)
        {
            if (myString[x] == myString[y] && x != y) return false;
        }
    }
    return true;
}

This code is very simple, but there are some problems. First, comparisons are repeated. Let's say we have a string of five characters, and the string is "ABCDE". On the first iteration, we will compare A to B, then to C, then to D, then to E. On the second iteration, we will compare B to A, then to C, then to D, then to D. Do you see how the comparison between A and B is repeated on the second iteration?

We can optimize this code a bit by altering the loops so that each character is only compared to every character AFTER it. This would mean that once A is compared to all the other characters, the other characters never compare themselves to A again.

bool noRepeatingCharacters(string myString)
{
    for (int x = 0; x < myString.length() - 1; x++)
    {
        for (int y = x + 1; y < myString.length(); y++)
        {
            if (myString[x] == myString[y]) return false;
        }
    }
    return true;
}

This code is a bit better than the previous code since we avoid repeated comparisons. The number of comparisons made with a string with n characters is (n - 1) + (n - 2) + (n - 3) + ... + (1). With a string of 5 characters, this would mean 10 comparisons, or 4 + 3 + 2 + 1. This algorithm works if I am not allowed to use any additional data structures.

I came up with another solution that is even faster, but it is only faster at the expense of memory. By using an additional data structure, we can speed up comparisons. How? By using a hash table. Each character can be cast to an integer in order to determine its ASCII value. We can use that integer as a hash key inside an array that serves as a hash table. The array itself can be made up of boolean values for quick comparisons.

bool noRepeatingCharacters(string myString)
{
    /*
    This is a hash table algorithm. This will speed up comparison times by

    using a 128 slot hash table based on the ASCII encoding of each char
    in the string. The index number matches the ASCII decimal value. If a
    character is in the string, then its ASCII slot is marked true. If 
    another character collides with that slot, then the function returns
    false. If no collisions are detected, the function returns true.
    
    The hash table uses more memory than the brute force algorithm, but
    comparison time is drastically improved.
    */

    bool myHashTable[256] = {false};
    int myIndex;

    for (int x = 0; x < myString.length(); x++)
    {
        myIndex = int(myString[x]);
        if (myHashTable[myIndex]) return false;
        else myHashTable[myIndex] = true;
    }
    return true;
}

This is much better than the brute force algorithm. The time complexity for comparisons becomes O(n). The memory requirements for the hash table is constant. As long as memory is not a concern, this algorithm will give us a much better comparison time.

In order to validate that both algorithms work correctly, I wrote a short testing method that will take in a user-defined string, determine if there are repeating characters in the string, and then pause to show the results. Here is the full code for the exercise:

//Cracking the Coding Interview
//Chapter 1: Problem 1
//
//Design an algorithm to determine if a string has all unique characters. 
//What if you cannot use additional data structures?
//
//Solution by Brandon Theolet
//December 20, 2012

#include <iostream>
#include <string>

using namespace std;

bool noRepeatingCharacters(string myString);

void main()
{
    //Method to test the algorithm.

    string myString;
    cout << "Please enter any phrase: ";
    cin >> myString;
    cout << "\n";
    if (noRepeatingCharacters(myString)) cout << "There are no repeating characters in this string.\n\n";
    else cout << "There are repeating characters in this string.\n\n";
    system("pause");
}

bool noRepeatingCharacters(string myString)
{
    /*
    This is a hash table algorithm. This will speed up comparison times by
    using a 256 slot hash table based on the ASCII encoding of each char
    in the string. The index number matches the ASCII decimal value. If a
    character is in the string, then its ASCII slot is marked true. If 
    another character collides with that slot, then the function returns
    false. If no collisions are detected, the function returns true.
    
    The hash table uses more memory than the brute force algorithm, but
    comparison time is drastically improved.
    */

    bool myHashTable[256] = {false};
    int myIndex;

    for (int x = 0; x < myString.length(); x++)
    {
        myIndex = int(myString[x]);
        if (myHashTable[myIndex]) return false;
        else myHashTable[myIndex] = true;
    }
    return true;
}

/*

bool noRepeatingCharacters(string myString)
{
    //This is a brute force implementation that uses no additional data structures.
    //Instead, two loops will iterate through the string and compare all chars
    //to every other char in the string AFTER the starting char. This is to avoid
    //repeating comparisons. If a match is found, the function returns false. If
    //the entire string is compared and no matches were found, the function returns
    //true.


    for (int x = 0; x < myString.length() - 1; x++)
    {
        for (int y = x + 1; y < myString.length(); y++)
        {
            if (myString[x] == myString[y]) return false;
        }
    }
    return true;
}

*/

Update: The author of the text proposed another solution that I had not considered with this problem. The solution involved first sorting the string. A well-implemented quicksort algorithm would sort the string in O(n log n) time on average. For comparisons of unique characters, the ordering of the string does not need to be preserved. Once the string is sorted, we can simple iterate through the sorted string, starting at the first character, and comparing this character to the character in the next index. If any neighboring characters are equal, we have non-unique characters in the string.

Another point the author made that I did not consider in my solution involved optimization. If we assume that the ASCII encoding was used to pass the string, then at most there can be 256 characters, which is one unique character for every possibly ASCII character. Thus, if we pass in a string with more than 256 characters, we can assume that at least one is repeated and then return an appropriate value from the function. This optimization would involve O(1) time, or constant time, for strings that were longer than 256 characters. Improving on this idea, I imagine we could also involve error checking where we would throw an error if we received an empty string.

Game Design: Static vs. Random Content

2012-11-23T11:27:00.004-05:00

Looking through GameFAQS.com today got me thinking about static content and random content. In terms of game design, what are they?

Static content never changes in a game, no matter how many times it is played. It can be a level design, enemy placement, or a puzzle. Most games released in the past typically use static content. Static content still makes up a large majority of games released today.

Random content is procedurally generated based on some input seed. Computers cannot generate truly random numbers, but can come close enough by taking an input value that is hard to control, such as the time of day down to the second, and using it to generate a predictable value based on a random number generation algorithm. This means a game can change the content it presents based on any number of input values. Level designs can change, enemy placement can change, and even the starting state of a puzzle can change.

Both methodologies have advantages and disadvantages. Replay value of a game is one area that is affected by the choice of using static content or random content. For illustration purposes, let's take a look at Resident Evil, originally released on the PSX in 1997. The game state is the same each time it is played. Each item and enemy is in the same spot each time it is played. Each time the game is played, it becomes easier for the player to plan and map out his approach since he knows what to expect. When using randomized content, such as the case in Diablo, released for the PC in 1996, this is not the case. Diablo features randomized dungeon layout, randomized enemy locations, and randomized item placement and drops. Each time the player plays through this game, he is limited in planning his approach. He can set up his character for different possibilities, but does not know the absolute layout of the dungeon or the absolute enemy positioning. Even though games like Diablo feature randomized level layouts and enemy positioning, the game still gets easier each time it is played. The player does not know the absolute enemy positions, but he should get a general idea of the general enemies he will face in each area of the game. The Butcher, for example, is a boss character that is always found on the second level of the Cathedral. As we discussed earlier, randomized content is not truly randomized but rather procedurally generated by a computer in order to appear random.

Some games attempted to blur the line between static content and random content. Resident Evil 3 was the first Resident Evil game to feature variable enemy placement and item placement in a static world. Some puzzles could also have different starting states, requiring game guides to determine multiple solutions for the player seeking assistance. Unfortunately, Resident Evil 3 only included two or three states or locations for puzzles and items that featured random placement. After two or three plays, the player would likely see all configurations for each design.

Some independent games, such as Dwarf Fortress, like to be as random as possible. Upon setting up a game in Dwarf Fortress, the game prompts the player to generate a new world. Dwarf Fortress uses various algorithms to model terrain and then flesh out multiple generations of history for this world. Races rise and fall, erosion and weather changes the landscape, and characters end up migrating to end up in a different area of the world than when they started. Once this world generation is completed, it is open for the player to explore however he wishes. There is very little guidance and limitless options about where to travel, where to build, and who to talk to. The downside of this level of randomness is the lack of structure to the game. Many players are put off by the lack of guidance and abandon the game due to this. Imagine spending five hours building a character in Adventure Mode and then running across an enemy that is far too strong. The character is now dead, and in Dwarf Fortress, death is permanent. This level of freedom and unpredictability appeals to a niche genre of gamers, but is not for everybody.

When designing a game, you need to be aware of your audience. You also need to be aware of your game genre. Some genres do not require any sort of randomized content. Sports games should have schedules and rosters that mimic the real world. They should not be jumbled up as this can lead to clustering of star players on few teams, lending those teams an unfair advantage, and an unrealistic schedule. This may put off a large number of fans that would prefer to play a game this is closer to their actual sport. RPGs on the other hand lend themselves well to randomly generated content. Many RPG fans enjoy games that offer a high degree of replayability. This does not mean that RPGs should all be randomized, though. Replayability can still be offered through branching storylines that requires many playthroughs before the player is able to see all options.

The real challenge for determining whether to use static content or randomized content comes in determining what your target audience wants and striking a balance between fun and difficulty. Games that are randomized to a high degree are usually more difficult than games that feature static content. The player is not able to plan a specific approach since level design and enemy placement is not static. The player also has no ideas which item he will find or need for specific areas, or if his character is even strong enough to survive an area. Guides written for randomized content will be vague when compared to guides written for games with static content.

Static content versus random content is an important design decision. It affects many facets of game, from replayability to difficulty to target audience. The choice needs to be made at the design stage in order to get the team on the same page. Static content is easier to develop and implement, but may be harder to change. Once the static content is implemented into a game, changing it would mean a new design for the entire area. Randomized content is harder to develop, but once fully implemented can be easily changed by changing specific inputs. Games that use both need to be designed very carefully in order to prevent static events from being broken by randomized content.

In terms of game design, I believe a mix is best for most games that have the option to implement either. Good games feature guidance that is appropriate for the target audience. If the target audience is sandbox gamers, then very little guidance is needed. If the target audience is young children, then a high level of guidance needs to be implemented.

The only area of game design where I like to seen purely randomized content is concerning game puzzles. Most RPGs, shooters, and action and adventure titles feature them. Most of them are static, and are easily solved with the assistance of a game guide. I believe puzzles should be designed better than bring key A to lock B. A puzzle should be self-contained and started in a randomized initial state. Take the example of the "Lights-Out!" inspired door lock from Resident Evil. The puzzle has the player hit buttons on a 3 by 3 keypad. Each time a button is hit, its state is switched from lit to blacked out or vice versa. All surrounding buttons are also switched, similar to the children's puzzle game "Lights-Out!". The puzzle is solved the same way each time. If the player found a note earlier in the game, the key code to solve the puzzle is given. This puzzle can be initialized to a random starting state each time the game is played, and the note can be generated to give a solution to each generated puzzle. This would prevent players from being able to breeze through the puzzle without finding the note or at least taking time to think about their moves before touching the key pad. Guides would also be unable to assist the player by providing the definitive answer. Instead, guides would need to switch to teaching the players how to think and solve the puzzle for themselves. If this turns off too many players, then the game designer may need to revisit including puzzles in the game in the first place.

Project Examples: SWF Illustrating the Star, Starfield, and MessageBoxManager Classes

2012-11-22T11:22:00.002-05:00

Here is an extremely early build for the game engine for Salvager: A Dredger's Tale. This build uses the Star, Starfield, and MessageBoxManager classes discussed and shared in previous posts. This build merely moves the game camera down and then creates a new message on the screen every few seconds. This is a build illustrating how to use the MessageBoxManager to show the main title and how to use the Star and Starfield classes to create a simple animated background.

Related posts:

Code Examples: MessageBoxManager Class

2012-11-22T10:52:00.003-05:00

This example code for Actionscript 3.0 is the class I wrote titled MessageBoxManager. The description for this example is in this post: Flash Game Programming: Treating Game Messages Similarly to Particles with a Life Timer .

If you would like to see this class used in a small project, go here: Project Examples: SWF Illustrating the Star, Starfield, and MessageBoxManager Classes.

package {

   import flash.display.*;
   import flash.text.*;
   import flash.events.*;


   public class MessageBoxManager extends MovieClip {

       //This variable keeps track of how long the message is displayed.
       private var displayTimer: int;
       //This variable keeps track of how long since the message was created.
       private var timeSinceCreated: int;
       //A text field container to hold the messages.
       private var thisTextField:TextField;
       //A TextFormat object to alter the appearance of the text as needed.
       private var thisTextFormat:TextFormat;
       //A Boolean variable to notate if the message should not dissapear in a few seconds.
       private var permaDisplay: Boolean;

       public function MessageBoxManager() {

           //Constructor function to initialize the variables.
           thisTextField = new TextField();
           thisTextFormat = new TextFormat();
           permaDisplay = false;
           thisTextField.border = true;
           thisTextField.borderColor = 0x00FF00;
           thisTextField.width = 630;
           thisTextField.height = 100;
           thisTextField.alpha = 0;
           thisTextField.textColor = 0x00FF00;
           thisTextField.embedFonts = true;
           displayTimer = 0;
           thisTextField.x = 5;
           thisTextField.y = 10;
           thisTextField.alpha = 0;

           //When this object is added to the stage by the parent class, call the function
           //that draws the text box on the screen.
           this.addEventListener(Event.ADDED_TO_STAGE, DrawMessageBox);

       }

       public function DrawMessageBox(event:Event){

           //This object has been added to the stage by the parent.

           //Remove the event listener.
           this.removeEventListener(Event.ADDED_TO_STAGE, DrawMessageBox);

           //Draw the message box on the stage.
           parent.addChild(thisTextField);
       }

       public function addNewMessage(myMessage:String, size:int, font:String, seconds:int, alignment:String, permaDisplay:Boolean) {

           //Add a new message to the text box.

           //Set the display timer for the number of frames to show the message.
           this.displayTimer = 60 * seconds;
           this.timeSinceCreated = 0;

           //Determine which alignment to use. The parent class uses string constants to pass this
           //information quickly and easily.
           switch (alignment) {
               case "center": thisTextFormat.align = TextFormatAlign.CENTER; break;
               case "left": thisTextFormat.align = TextFormatAlign.LEFT; break;
               case "right": thisTextFormat.align = TextFormatAlign.RIGHT; break;
               case "justify": thisTextFormat.align = TextFormatAlign.JUSTIFY; break;
           }

           //Set the permanent display option if the message needs to stay on the screen.
           this.permaDisplay = permaDisplay;

           //Set the font. The parent class uses string constants to pass in the embedded font
           //quickly and easily.
           thisTextFormat.font = font;

           //Set the size.
           thisTextFormat.size = size;

           //Set the format properties to the text.
           thisTextField.defaultTextFormat = thisTextFormat;

           //Add the text to the text box and end the line with a newline character.
           thisTextField.appendText(myMessage + "\n");
       }

       public function clearMessages() {
           //Clear the text box.
           thisTextField.text = "";
           this.permaDisplay = false;
       }

       public function updateMessages() {

           //This function is called every frame.

           //Decrement the displayTimer variable.
           displayTimer--;
           timeSinceCreated++;

           //Set the limits for each timer variable.
           if (displayTimer < 0) {displayTimer = 0;}
           if (timeSinceCreated > 60) {timeSinceCreated = 60;}

           //If permaDisplay is true, give 1 second of life.
           if (permaDisplay == true) {displayTimer = 60;}

           //Determine the visibility of the text box. If the text box has less than 1 second
           //to live, gradully fade it out.
           if (timeSinceCreated < 60) {thisTextField.alpha = timeSinceCreated / 60;}
           else {thisTextField.alpha = displayTimer / 60;}
       }
   }

}

Code Examples: Starfield and Star Classes

2012-11-22T10:20:00.003-05:00

This code example contains the full Actionscript 3.0 code for the Starfield and Star classes discussed in this post: Flash Game Programming: Adding objects to the main stage from a child object.

If you would like to see these classes used in a small project, go here: Project Examples: SWF Illustrating the Star, Starfield, and MessageBoxManager Classes.

The Starfield class:

package
{

    import flash.display.*;
    import flash.events.*;

    public class Starfield extends MovieClip
    {
        //This class manages all of the Star objects displayed on the game screen.

        //Array to hold the Star objects.
        private var myStarfield:Array = new Array;
        //Integer to notate the number of Star objects to create.
        private var numberOfStars:int;

        public function Starfield(numberOfStars: int)
        {
            //Constructor initializes the class and waits for the object to be drawn on the main stage.
            this.numberOfStars = numberOfStars;
            this.addEventListener(Event.ADDED_TO_STAGE, DrawStarfield);
        }

        public function DrawStarfield(myEvent: Event): void
        {
            //The Starfield object has been added to the stage by its parent. We now create and draw
            //the Star objects.

            //Remove the event listener.
            this.removeEventListener(Event.ADDED_TO_STAGE, DrawStarfield);

            //Temporary variables to create and display the Star objects.
            var thisIndex:int;
            var thisStar:Star;

            //Loop to iterate the creation and display of each Star object.
            for (thisIndex = 0; thisIndex < numberOfStars; thisIndex++)
            {
                //Create a new Star object.
                thisStar = new Star(Math.random() * 640,Math.random() * 480, Math.random() * 3 + 1);

                //Add the Star object to the parent's stage.
                parent.addChild(thisStar);

                //Add the Star object to the reference array for the Starfield object.
                myStarfield.push(thisStar);
            }
        }

        public function UpdateStarField(cameraX:int, cameraY:int) {

            //Update all stars being managed by the object based on the change in game camera position.

            //Temporary variables to point to each Star object and update it.
            var thisIndex:int;
            var thisStar:Star;

            //Loop to access each Star object in the reference array.
            for (thisIndex = 0; thisIndex < myStarfield.length; thisIndex++)
            {
                //Point to the Star object in the reference array indicated by thisIndex.
                thisStar = myStarfield[thisIndex];

                //Update the Star object's position based on the change in the game camera and the Star object's layer.
                thisStar.x = thisStar.x - (cameraX / thisStar.getZDistance);
                thisStar.y = thisStar.y - (cameraY / thisStar.getZDistance);

                //If the Star object goes off screen, recycle it by wrapping it on the screen.
                if (thisStar.x > 640) {thisStar.x = 0;}
                if (thisStar.x < 0) {thisStar.x = 640;}
                if (thisStar.y > 480) {thisStar.y = 0;}
                if (thisStar.y < 0) {thisStar.y = 480;}
            }
        }
    }

}

The Star class:

package
{

    import flash.display.*;

    public class Star extends MovieClip
    {
        //This class defines the properties of a Star object used to make the scrolling background
        //on the main stage.

        //Integer to determine which layer of the background the Star object is in.
        private var zDistance:int;

        public function Star(xPos: int, yPos: int, zDistance: int)
        {
            //Constructor to initialize the Star object.

            this.x = xPos;
            this.y = yPos;
            this.alpha = .25 * (4 - zDistance);
            this.zDistance = zDistance;
        }

        public function get getZDistance():int {

            //This get function returns the integer variable zDistance. We use it to determine
            //which layer the Star object is in. The layer determines the brightness of the star
            //and how fast it will scroll as the game camera changes positions.

            return this.zDistance;
        }
    }

}

Flash Game Programming: Treating Game Messages Similarly to Particles with a Life Timer

2012-11-21T19:30:00.003-05:00

I love particle engines. We can accomplish so many interesting graphical effects using particles with relatively minimal code. This is because the class definition for the behavior of a particle is minimal but we leverage the power of object oriented design principles to create a complex system. The behavior of any one particle is easy to predict, but the behavior of hundreds of these objects acting at the same time is difficult to predict.

On the other hand, we can also use design patterns similar to particle engines to create a remarkably simple device to manage lots of data.One element that is present in most particle designs is a timer that keeps track of how long a particle has to live before it is released from memory. I will use this design technique in order to simplify the adding and removing of game messages in the game engine for Salvager: A Dredger's Tale.

In the game, one of my classes that I created manages in-game messages. The title of the class is MessageBoxManager. The class holds a standard text-box, a TextFormat object alter the appearance of the text, a variable to keep track of how long the message should be displayed if on a timer, a variable to keep track of how long since the message was created, and a Boolean flag that marks whether or not the message box should acknowledge the timer and just stay visible until the player wishes to close the messages.

What use is this class? In order to script in-game events, one of the issues that needs to be dealt with is to create a mechanism to easily display game messages. These messages can be hints, data from the game engine such as damage dealt on each successful hit, or even dialogue from a non-player character. This mechanism will accept strings that need to be displayed to the player and put them in the game environment on the stage.

The last post outlined how to add display objects to the main stage from a class that is a child of the class that directly references the stage. I have used a similar technique here. The constructor initializes the variables and sets an event listener to execute a method as soon as the object is added to the stage. The main class adds the object to the stage, and the method within the child class executes to add all relevant display objects to the stage by referencing its parent. I know that sounds confusing, so check out my previous post for clarification on how to do this and why we have to do this: Flash Game Programming: Adding objects to the main stage from a child object.

The class creates a text box and edits the display attributes in order to make it match the game content. The visual style is simple retro-style vector graphics. Everything is typically green or white on a black background. A method is created in order to accept a string and then append this string to the text box. We also accept various arguments to this method. One such argument is the number of seconds that the message box should be displayed for. For most quick messages, 3 seconds is the standard time. Since the project is set to run in the Flash environment at 60 fps, we simply assign the timer variable the argument value multiplied by 60.

How do we get the message box to go away without losing any data contained within? The Flash environment makes this very easy. Every display object has an alpha property which determines transparency. This value can be any value from 0 to 1. 0 means the object is entirely transparent and 1 means the object is entirely opaque. I treat the message box like one big particle here. On every frame, when the method that handles updating the message box is called, we set the alpha property of the message box itself. I use a simple formula.

          displayTimer--;

          thisTextField.alpha = displayTimer / 60;

What happens here? We set the alpha property of the text box based on how long the display timer has left. Remember, when we created a message, we passed in a value that told the manager how long we wanted it to be visible by. If the value passed was 3 seconds, then timeToLive was set to 180. Since 180 divided by 60 is 3, the alpha property of the box is set to 1. That means it is opaque. Every frame, that variable is decreased by 1. For two seconds, the box is completely opaque. Then, during the last second that it's to be shown, the box slowly fades until it becomes invisible on the main stage. For example, let's say that timeToLive is equal to 30 frames. It has half a second to live. It will also be at half transparency, since 30 divided by 60 is one half. The alpha property will always be set to 1 if the value of timeToLive divided by 60 is 1 or greater than 1. Once we get below 1 second of life left, it will start to fade as the alpha property is set to the appropriate decimal between 0 and 1.

Notice how easy this technique is. We don't add a new text box each time we create a message. We also don't have to worry about removing old text boxes from the stage and deallocating the memory. The text box inside the manager class is added once and only once. It is never removed. We simple remove it from sight, but the other display properties such as the text inside that container as well as the on-screen position do not change.

When we have an event, such as the player pressing the console key to bring up a history of recent messages, we can set the Boolean flag to display the message box constantly to true. Here, we simply have to add an additional line of code.

            if (permaDisplay) {displayTimer = 60;}

Each frame, the timer will be given 1 second to live. This will keep the alpha property of the text box at 1. We have to make sure that this line comes after the line that decrements the displayTimer variable so that the alpha property of the text box is always set to 1. One the flag is set back to false, the message box will fade out over the course of 1 second.

The full code to the MessageBoxManager class is posted here: Code Examples: MessageBoxManager Class.

Flash Game Programming: Adding objects to the main stage from a child object.

2012-11-20T21:59:00.000-05:00

When it comes to object oriented design principles, Flash and Actionscript 3.0 do things a little differently. My current project, Salvager: A Dredger's Tale, ran into an early hurdle. While trying to keep true to the object oriented design principle of encapsulation, I discovered that adding items to the stage became a bit convoluted when trying to do so from a child of the parent class where the stage was instantiated.

Most of the rendering is being done through Actionscript classes rather than animated MovieClip objects. I still use MovieClip objects as the containers for my classes, but most of them have no graphics. The reason is that MovieClips are easily linked to ActionScript classes and provide easy access from within the Flash IDE.

In the IDE, the stage is linked to its own ActionScript 3.0 file. This main class instantiates the other classes I've written. From the main class, adding a display object to the stage is as easy as using the addChild function. Trying to add an object from a child class was a bit of a challenge.

For this example, I will use my classes Star and Starfield. Star is a MovieClip that contains a 1 frame graphic of a star. The MovieClip is linked to an ActionScript file. The Star definition includes the x position of the object, the y position of the object, and an integer from 1 through 3 to notate the depth layer. Starfield is a class that was designed to manage all the Star objects on the main stage that will make up the background. There are 300 Star objects on the main stage, and using Starfield as a manager class to update all of them during gameplay keeps the main class neat and tidy.

When Starfield is instantiated, it creates 300 Star objects. Their position on the screen is set. Their brightness is determined by their depth layer. A depth layer of 1 will be closer to the camera than depth layer 3, and thus brighter. When the game camera moves during gameplay, the Star objects in depth layer 1 will also scroll faster than those in depth layer 3. The objects were originally created in the constructor method for Starfield. I then tried to add them to main stage by using this line.

        parent.addChild(thisStar);

It seemed simple. Starfield is a child of the main class. In the line of code, "parent" references the main class and the addChild() method should push the object pointed to by thisStar onto the stage to display it. The compiler did not like the code.

It turns out that one of the peculiarities of Flash is that an object does not know it has a parent until the object itself has been added to the stage as a display object. Starfield is a manager class and is not a display object by itself, but it is the container for which all the Star objects are held, and those Star objects are display objects.

The workaround for this hurdle is actually quite simple. From the main class, we instantiate the Starfield class and then add that class to the stage.

This is the variable declaration in the main class.

        private var gameStarField:Starfield;

And this is where we instantiate it and add it to the stage.

            gameStarField = new Starfield(300);
           addChild(gameStarField);

But that means we cannot create and draw the Star objects in the Starfield constructor because the constructor must finish executing before Starfield is added to the stage from the main class. To solve this problem, we need to take out all the code from the Starfield constructor and replace it with an event.

        public function Starfield(numberOfStars: int)
       {
           //Constructor initializes the class and waits for the object to be drawn on the main stage.
           this.numberOfStars = numberOfStars;
           this.addEventListener(Event.ADDED_TO_STAGE, DrawStarfield);
       }

The event listener waits until the Starfield object myStarfield is added to the stage in the main program. Once it has been added to the stage, the function CreateStarfield() is called from within the Starfield object. This enables us to now create the number of Star objects we need and then push them onto the main stage so that they are now displayed.

        public function DrawStarfield(myEvent: Event): void
       {
           //The Starfield object has been added to the stage by its parent. We now create and draw
           //the Star objects.

           //Remove the event listener.
           this.removeEventListener(Event.ADDED_TO_STAGE, DrawStarfield);

           //Temporary variables to create and display the Star objects.
           var thisIndex:int;
           var thisStar:Star;

           //Loop to iterate the creation and display of each Star object.
           for (thisIndex = 0; thisIndex < numberOfStars; thisIndex++)
           {
               //Create a new Star object.
               thisStar = new Star(Math.random() * 640,Math.random() * 480, Math.random() * 3 + 1);

               //Add the Star object to the parent's stage.
               parent.addChild(thisStar);

               //Add the Star object to the reference array for the Starfield object.
               myStarfield.push(thisStar);
           }
       }

Presto! We can now instantiate the Starfield object myStarfield, add it the stage, and immediately have a method executed that creates all the Star objects and pushes them to the main stage from inside a child object of the main class. Don't forget to remove the event listener once the appropriate method is called. Also don't forget to import the proper package in order to use the ADDED_TO_STAGE event.

If you would like to see the full Actionscript 3.0 code for both the Starfield and the Star classes, they are available here: Code Examples: Starfield and Star Classes.

Prototypes and RetroVector Games

2012-11-19T11:01:00.000-05:00

I keep coming across game development pieces and advice columns that state students need to be creating prototypes for games. A writer writes, a developer develops. I have not been following this advice as closely as I should have been.

I am in my senior year of my undergraduate career. Soon I will have the choice of continuing my education or trying to secure a job. If securing a job is anything like securing an internship, then I have a lot of competition from highly regarded universities and experienced developers who have been laid off. In order to be able to compete, I need a portfolio of projects.

Thus far, I have two working projects. One is an XNA project called KLAX'D and is outlined below. The second is a Flash project and is an Asteroids clone. I named it Salvager as the goal of the game is not just survival, but also to break down space debris and collect the pieces once it is safe to do so. This project was a three week part-time endeavor, and I am not happy with the results. If you would like to play this rushed prototype version, you can find it at Kongregate.com: http://www.kongregate.com/games/theo20185/salvager

Since I am not happy with the results of Salvager, I have decided to start fresh on that same project. It will remain a Flash project. I am changing the art style to mimic old school vector arcade platforms. These were the games that drew everything out in monochrome lines. There were even some 3D titles that displayed everything in wireframe.

Why the choice of vector graphics? The reasoning is simple. I am studying to be a game programmer. I am not studying to be a game artist. Using vector graphics will allow me to quickly create needed assets for prototype projects and use them as placeholders. It will also allow me to draw sprites or object wire frame models without embarrassing myself among the artistic side of the industry. My pixel art and textures leave a lot to be desired. Since I have opted to go lean on graphics and focus on programming, I have decided to brand my games using the name RetroVector Games.

What plans do I have for the full version of Salvager? First, I am programming a 2D engine in Flash that will allow me to script enemy behavior and add events and objects to certain spots in the game world. The player will no longer be confined to a small box, but will be able to travel the galaxy in an open-world environment. The new working title for this project is "Salvager: A Dredger's Tale". Yes, this is an homage to classic games such as A Bard's Tale. I want an adventure-style shooter that keeps the mechanics shown in the Salvager prototype and adds new features such as NPC interactions, an upgradeable player ship, and scripted enemies. You can only shoot so many pieces of non-sentient space debris before you go looking for something more challenging.

I've already started on the game engine. In Flash, I've grouped my files into three main folders. Thus far, we have fonts that are embedded into the project, graphics, and classes. I've created blank movie clips and stuck them into the classes folder for easy access to the ActionScript definitions of these objects through the Flash IDE.

Thus far, I have a definition for a game camera, a star, a star field manager, and a message manager. Later in this week, I will make posts concerning these game components and how I've implemented them.

Here's to an official brand for my student game projects! Salvager: A Dredger's Tale will be the first project from RetroVector games. All RetroVector branded games will be projects that are not academic assignments.

Project Examples: Klax'D

2012-02-18T20:00:00.002-05:00

It's been more than a month since my last post. I have been extremely busy with college assignments. I thought today was a great day to update my blog. I am pleased to announce my first XNA Game Studio project was turned in for grading, and I would like to share it with all of you as well. The link to the file is included at the end of this post.

Klax was released in 1989 by Dave Akers and Mark Stephen Pierce. It is an action-puzzle game. My first XNA Game Studio project is a version of this game and I titled it Klax'D in homage to the original.

The game world consists of a conveyor belt, a paddle at the end of this belt, and a drop zone. The conveyor belt has five lanes. Bricks spawn at one end of the belt and move towards the end. The player can choose to catch these on his paddle or let them fall into the drop zone. The paddle can stack up to five bricks. The player can either drop the bottom brick or put the bottom brick at the top of the stack. If he drops the brick, it falls into an appropriate lane in the drop zone. The drop zone is able to hold 5 stacks of bricks. Each stack can hold 5 bricks. If a brick falls onto a stack that is full, it's game over. The player can remove bricks from the drop zone by matching like-colors. If three or more bricks with the same color form a line in any direction (vertical, horizontal, or diagonal) then those bricks are removed from the drop zone.

It's a simple game and a good one to code for a starter project. I will not share the source code for this project since I can get in trouble with the school for that, but I will be more than happy to share the finished compiled project. This game requires the appropriate .NET and XNA frameworks, which are included in the file if you don't already have them. The game will run on any Windows computer with a graphics card that is capable of rendering DX9 or higher. Please note this project is not digitally signed, so you should see a message asking if you trust the content of the file during the installation. If you are not comfortable with this, then do not install the game. There is no malware included in this file.

If you have an XNA Creator's Club membership, you can also run this project on your Xbox 360 through XNA Connect. If you want the Xbox version to try on your own console, send me an email and I will send you the .ccgame file to unpack to your Xbox.

Some of the features we focused on for this assignment were using the XNA framework to access the GPU, inclusion of very simple shaders, basic game loop architecture within the XNA framework, and using an established code base and building a game on top of that (for this project, we were given the Game State Management Sample code from the Microsoft Developer Network and used that as the starting framework). I built this game using one 3D model and added additional methods to the Screen class in the GSMS from MSDN.

Please download Klax'D from this link.

What is Dreamer of Worlds?

2012-01-02T19:27:00.001-05:00

This is the first post for my blog, "Dreamer of Worlds." This blog will chronicle my journey as I study the art of game design and development.

I am a student at Baker College in Michigan. Baker is the state's largest private college. I am a BCS candidate with a concentration in Game Software Development. I am in my junior year as of this post. I have 100 credit hours completed of the 181 credit hour program with a cumulative GPA of 3.96 on a 4.0 scale.

I've found college to be a challenge. I juggle my classwork with a full time job at North American Bancard and with my two-month old daughter Amelia. I've learned a lot during these past two years, both in and out of the classroom. I hope that I am honing my time management skills to an extent where they will be useful outside of school.

This blog is meant to be an outlet for my thoughts on game design and game development as well as a platform to show off some of my work as I progress through the last two years of my undergraduate degree.

If you are a game designer/developer, or a student planning on entering the game industry, please feel free to send me an email or follow the blog. I'll be sure to return the favor.

-Theo20185