Friday, February 25, 2011

What more can you ASCII for?

Greetings

I am not the artistic type, but that does not mean that I do not appreciate art. While I do like art created by others, I sometimes wish that I too was gifted with artistic abilities. Once again, using the awesome powers of Java, I was able to realize this dream. Using simple Java code, I created an image to ASCII converter program which takes an image and outputs a text file with ASCII characters, which looks like the input image when viewed all at once. In this post I will explain the basic principle behind computer generated ASCII art, and how to implement it using Java. I will release my own code for the program that I built, the program itself and a short video of the program in action. From now on, I will release all my code under the Open Source Initiative (OSI) MIT License (MIT), because the license is clean, short and easy to understand. Before I explain the principle behind ASCII art, here are some of the ASCII art created by the program: 
That's me!!

The Simpsons are ASCIIfied!
p-51 Mustang- A classic

The principle behind ASCII art is easy to understand. An image can be thought of as an 2 dimension array with rows and columns that correspond to the width and height of the image (In reality, it is more complex than that but this is a good enough understanding for the time being). Each cell in this array holds a pixel. When all these pixels are viewed together at once, you get an image. So a 400x400 image has 400 rows and 400 columns, and has 160000 pixels. Now to convert an image to text, the program has to iterate through all the pixels, get its RGB value, convert it to its gray scale value, and append a suitable ASCII character. Java has a class called the BufferedImage class, which has the methods necessary to obtain the RGB values of a pixel. Now once the RGB values(ranging from 0 to 255) of the pixel is obtained, there is a simple formula to convert it to a gray scale value. Simply take ~30% of the Red Value,  ~59% of the Green value and ~11% of the blue value and add them up together to a value ranging from 0 to 255, 0 being the darkest and 255 being the brightest. Don't worry, the BufferedImage class has the necessary methods to obtain these values,which you can see in my annotated code posted below.This value is your gray scale value. Generally gray scale value range from 0 to 1 with decimals in between, but there is no reason for them to be between 0 and 255. You could divide it by 255 to range it from 0 to 1, but why the extra hassle? After obtaining the gray scale values, the creative part begins. As you know, some ASCII characters appear darker than the others. For example, # appears darker than 0.So what the program does is obtain the gray scale value of each pixel, and according to the value, append an ASCII character to the text file. For example, if the gray scale value is in between 180 and 200(very bright), it appends a ".", and if it is 50 and 70(very dark), it appends  a "#". Currently there are nine different ASCII characters that the program chooses from to append. However, I urge you to edit the code and experiment by adding more characters, changing the existing characters, etc. For a detailed explanation, read the comments in my code which explain the function and workings of each method. The results are stored in a file called result.txt, and when viewing the results in a text editor, choose a small bold mono-spaced font, with word wrapping DISABLED. I recommend choosing images not bigger than 600x600 as the task will become more and more resource intensive with bigger images. While the current program does have an area where the results are appended, for spectacular results, open up the result.txt file and choose the best font and size to view the art. I find that Prestige Std Elite and OCR A work really well, almost giving the illusion of colors. This program is only a test, and soon I will be releasing code to a program with better GUI, more options and ultimately more robust. But until then, here is a small video below which runs you through the code of the program and explains how the program works. 


And finally here are the links to the code of the program and the actual program and the Netbeans Project. Please go through the code, experiment with it and hope you learn something out of this.


This is not the end

Aravind Rao
                  

Sunday, February 20, 2011

Prim's Algorithm

Greetings

Sometime back, I wanted to dive into a programming topic called graph theory. Graph theory is an extremely interesting topic in the sense one needs to use their brains to solve graph problems. Also many problems, such as the traveling salesman problem have only been partially solved at yet, making it a NP hard problem. I decided to start my dive with a lesson in Prim's Algorithm. However after countless hours of scourging the web, I could not find the code, nor an explanation simple enough for me to understand the algorithm. Thanks an awesome video I found on YouTube(I don't have the link, but I find it, I will post it here) on the Prim's Algorithm I was able to write my own interpretation of the Algorithm. This code makes use of arrays and simple vectors and is extremely easy to understand. I though of posting this code because I wanted anybody else in my position to be able to understand Prim's algorithm without having to resort to complex, unnecessary code. So what is the Prim' algorithm? Ever heard of problems such as the length of road required to connect all cities? or the cabling needed to form a network of computers, but some computers acting as proxies for the others? Well for all these problems, the MST or the minimum spanning tree has to be found. Imagine a group of cities (A to E) to be the nodes in a graph. Now imagine the distance between them to be the edges in a graph. Here is a pic.
An Example Graph
So the DIRECT distance from A to B is 10, A to E is 34, etc. However what is the least length of road to be constructed so that all the cities are connected? It is certainly not 106, the sum of all the distances. It happens to be 22 or the MST of the graph of cities. Try it out. cross out the distances of 33, 34 and 17 and you should still be able to travel from any city to any other city! Solving such problems require MST which can be found using the Prim's algorithm.The code I release for Prim's algorithm will have a detailed explanation on how it works. Here is a gist: start from any node, mark it visited. Choose the shortest path from all paths available and the add the path length to your MST counter. Get the node at the other end of the chosen path and mark that visited as well. Now considering the paths from all visited nodes, choose the shortest path and mark the node on the other end as visited. Continue to do this until all nodes are visited and once done you have the MST! The Prim's algorithm is great for finding the MST, although a little bit slower than other algorithms. However it is a simple algorithm to learn and is fun to work with. Links for the code and explanation down below. Once again you are free to modify and distribute the code with proper credit given.

Link to .exe file.
Link to code.

This is not the end...

Aravind Rao

Tuesday, February 15, 2011

Java to the rescue!

Greetings

Some time back, I decided to run for the position of secretary in the student council of my school. Being a secretary appealed to me; I did not want a position that was constantly in the limelight and I enjoyed tasks such as data handling and processing (student data and volunteer info). I was subsequently elected and while reviewing the duties of  a secretary, I realized that there was no real system in place to store, view and edit member data. I found out that previous secretaries had left this responsibility to the members themselves; that is the reporting of the hours volunteered and so on. It did not seem right to me to allow volunteers to self report theirs hours. However it was seemingly the only option considering there was no concrete system in place. One of my fellow student council members had the "bright" idea to use an excel document; At 300+ members and over 100 activities per year, the excel cells to be edited would exceed 30000. There had to be another method. Finally, it was Java that came to my rescue! I decided to create a Java GUI Swing App combined with a self written text file parser. Every time a new member is added, the app creates a new text file with name, grade, etc as well as a volunteer hours summary, edited to look like a table. Adding hours to members files involves using the text file parser. which searches for special indexes and edits the file accordingly. Since the data is stored as text files, it can be printed out and handed back to members to increase transparency. I set out to code the app and in about a week finished it. It was a mad rush of coding ~ 440 lines of Java. All the codes are in a single file, though looking back in retrospect, I should have used interfaces and abstract classes for more readable code. However, it was the best I could do in a week! In any case, it helped me tremendously in processing members and their hours. I also built upon this code to build a simple payroll program for a local dentist's office. Although I cannot release that code until they allow me, here is a screen shot below:
My more complex payroll app screenshot.

As you can see, it is a pretty complex app with over 1250 lines of code. I shall be however posting links for the source code and entire project of my Student Council Secretary App as well as the .jar file. I have annotated key parts of code, but if you have any questions, please post a comment question on this post. When using the app, he member files are created in the same directory as that of the app. Like always, you can use, modify and redistribute it without any license. If you do redistribute it, It would be nice if you could add my name somewhere in the file, but if you cannot, it is not really a problem. Here are the links:
Link to download zipped Netbeans project (source code in the Hours-src-hours folder.)
Link to download .jar executable file. (Not tested on Mac, but should work. Works in Ubuntu and Windows)

This is not the end...

Aravind Rao

Wednesday, February 9, 2011

Intelligent Code

Greetings

Every problem in Computer Science can be solved by accounting for every possible permutation that the program might encounter. Naturally this is not an efficient practice, especially when  the number of possibilities can grow exponentially, reaching billions in no time. To effectively solve such problems, we need to implement  a kind of logic, based on our own thinking while problem solving. This inherent 'common sense' of humans can help create powerful algorithms to solve computer problems, without the aid of brute force. An example of such a problem is a computer game (Source .cpp, and .exe), where a computer tries to guess a users' choice within a given range. If the users' choice is >= the computers' guess, the user inputs 0. If the user's choice is < than the computer;s guess, the user inputs 1. Naturally, the computer can iterate through all numbers in the range from lowest to highest and check whether the computers' guess matches the users' choice and arrive upon the answer when the user inputs one(the users' choice will be the current computers' guess - 1). However what if the range extended from 1 to 2^10? Does it make sense to loop through all those numbers, check for user input and output the answer? This method is not time or user friendly. However, if we implement an algorithm that imitates the way we think when solving such a problem, we can arrive upon an extremely efficient solution for this problem. Consider the range 0 to 16. The user's choice is 11. Now lets add 1 to 0 and 1 to 16, to make the range 1-17. This is done because we will than have 2 nice halves of the range: 1-8 and 9-17. This idea of dividing the range into half will be central to out algorithm. You will get why I do this later. Now the computer has 1\16 or 6.25 % chance of guessing the right user's choice. If it iterated through all the values of the range and checked it against the user input, the probability of the program guessing the right choice will be increased to 6.67% -> 7.14 %...etc.(Not really, but for the time being, let us consider the case to be true). What should the program do to arrive upon the answer faster and in fewer tries? It should try to increase the probability of getting the right answer in each successful turn by a greater rate. For example in the range 1-17, the computer programs' first guess has to be (1+17)/2 = 9 or the average of the range extremes. Why? Because if the user inputs 1, the users' guess is less than 9, so it is in the range 1-8. Alternatively, if the user inputs 0, the users' guess will be greater than or equal to 9, and thus in the range 9-16. What have we achieved here? We have increased them probability of the computer guessing the right answer in the next turn to a whooping (1/8)% = 12.5%, which is the double the probability of guessing the right answer of the programs' first turn. Compare this with the 6.67% probability while iterating through all values!Now since the user's choice is 11, he will input 0, and now the computer program will carry out the same operation, although this time on a different range, that is 9-16. After this turn, the probability of guessing the answer right will increase to 25%, then to 50% and finally to 100% When it reaches 1000%, the program will have the answer! his method only works on ranges whose higher extreme can be expressed as:
Log2(Higher Extreme) = some Natural Number.
Therefore 16 works(log2(16) = 4), so does 8. 32 and 4096. The number of guesses the program will make is log2(higher Extreme). In the case of the higher Extreme being 16, the program will make 4 guesses, in the case of 32, it will make 5 guesses and so on.
I have provided the links to the source code and .exe file of this 'game'. Feel free to edit it, distribute it and use it, although with proper credit!

Link to .cpp source file.
Link to .exe playable game file.


This is not the end

Aravind Rao