Rough Book

random musings of just another computer nerd

Tag: programming

Don’t use class literals as type-tokens

Generics were added to the Java language within J2SE 5.0, and there was much rejoicing. It was finally possible to deal with containers in a type-safe manner. Prior to the availability of generics, Java developers had to do things like this:

List people = new ArrayList();
people.add(new Person("Donkey Kong"));
people.add(new Person("Guybrush Threepwood"));

Person pirate = (Person) people.get(1);

This kind of code is very fragile since it is not easy to keep track what is inside a container. If at runtime, the object you retrieve is not of the type that you’re expecting, you can get a ClassCastException. It is also remarkably easy to pollute a container by shoving objects of different types inside there, which makes it even more difficult to keep track of the types of the objects inside. Workarounds included littering code with instanceof checks, or creating a wrapper class (for example a class called PeopleList that would delegate to an internal List instance) around the container so that you could have control over the types of objects being inserted.

When generics finally arrived, people were ecstatic because now you could do things like this:

List<Person> people = new ArrayList<Person>();
people.add(new Person("Donkey Kong"));
people.add(new Person("Guybrush Threepwood"));

Person pirate = people.get(1); //It just works!

This meant no-more ugly workarounds, which means that things are awesome! Right?

Read the rest of this entry »

How I got a medal from the Army for writing code

In 2005 my National Guard unit was deployed to Iraq as part of Operation Iraqi Freedom. My MOS (Military Occupational Specialty) in the Army was 92A, which is basically a logistics and supplies specialist. My job was to order parts for mechanics, pick them up, return old parts, manage HAZMAT, dispatch/return vehicles from missions, and handle licenses. I also did a few other things that I don’t remember right now. Anyway, at the time, the heart of this system was a tool called ULLS-G (Unit Level Logistics System – Ground). I say “at the time”, because shortly after we came back, ULLS-G was replaced by SAMS-E (Standard Army Maintenance System – Enhanced), which incidentally uses Oracle as a back-end database. Compared to SAMS-E, ULLS-G was a dinosaur. I had used it quite a bit, of course, having been in the Army for about 4 years by the time I was deployed. It was a complete pain to use it. ULLS-G was a DOS application (yes, MS-DOS) and most of the computers I used it on at the armory were only running DOS (this was circa early 2000’s so it wasn’t too uncommon to still see DOS systems around). By the time I was deployed most computers were running WinXP/2K or something like that, and so you could run ULLS-G in “MS-DOS compatibility mode”.

Read the rest of this entry »

Maintaining a sorted array in O(1)

Yesterday, I came across an interesting question on StackOverflow. The question is as follows: assuming you have a sorted array, is it possible to increment locations by 1 (one at a time) and still ensure that the array is sorted in O(1)? Assuming you are not allowed to use any other secondary data-structures, the answer is no. This becomes evident when you have repeated values. Assume a degenerate case where you have an array of identical values; let’s say [0, 0, 0, 0, 0]. If you increment the value in location 0, you now have [1, 0, 0, 0, 0]. For this array to be sorted, the value 1 must be moved to the end of the array (index 4). This will require four comparisons, which means that this will inevitably turn into an O(n) algorithm.

How can we do better?

Read the rest of this entry »

The Feast

Inspired by The Codeless Code:

The master was meditating when a priest respectfully entered his chamber. The master opened his eyes. The priest bowed respectfully and said, “Master, I would like you to look at the code of a young disciple of mine”. The master nodded and followed the priest to a computer. On the screen, was a code listing. The priest pointed to the code and said:

“My disciple created an abstract class and another class that extends the abstract class. However, he has a method that should be of use to all future derivations of the abstract class.”

The master furrowed his brow and looked at the code. “Indeed.”, he said. The priest continued, “I pointed this fact out to him and mentioned that it would be better to define it in the abstract class”. “I see; what did he say?”, asked the master.

The priest sighed and said, “He said ‘You Ain’t Gonna Need It’ and that he could simply copy the method into each new derivation when the time comes”. The master then asked the priest to bring the disciple to him at once. The priest bowed and went away to fetch the young disciple.

A few minutes later, the young disciple respectfully entered the master’s chamber. “You sent for me, master?”, he said. “Yes. I have a task for you”, said the master. The disciple bowed, indicating that he was ready to perform whatever task the master required. The master looked at the disciple and said: “Tomorrow, we will have monks visiting from a neighboring monastery. In their honor, our monastery is providing a feast for them. I need you to report to the dining hall tomorrow. The cook will give you further instructions”. The disciple bowed and left the master’s chamber.

The next morning the disciple arrived at the dining hall as he was asked. He looked around and noticed a large number of seats. He assumed, correctly, that these seats were for the visiting monks. He then noticed the monastery’s cook approaching him. The cook was holding a bowl that was filled with a white substance. As the cook got closer, the disciple realized that it was salt. Once the cook reached the disciple, he held out the bowl to him and said, “Master has asked you to give salt to any of the monks who desire it”. The disciple took the bowl and the cook left. The disciple was puzzled, but smiled thinking that this was going to be an easy task. After all, how many monks would require more salt in their food? He estimated only a few; not much more than that.

In a few minutes, the visiting monks arrived and sat at their places. Other monks from the hosting monastery brought out steaming bowls of soup for the visitors. The head visiting-monk took a spoonful of soup, sipped it and wrinkled his nose. “This soup does not have any salt!” he said, rather loudly. The disciple quickly ran up to the head visiting-monk and bowed and said “Master, I apologize that there is not enough salt in your soup, please allow me to offer you some!” The head monk nodded and the disciple quickly added salt until the monk motioned him to stop. He had barely finished when he heard another monk complaining that there was no salt in his soup either, then another, and another. Soon he was running around the hall at full speed, bringing salt to each of the visiting monks, trying his best to make sure that everyone was happy. The hall was big, and the number of visiting monks was many. When he was done, he sat down exhausted, in the corner of the hall.

He closed his eyes and tried to catch his breath. When he opened his eyes, he noticed that the next course was being brought in. “Surely the cook wouldn’t have forgotten to add salt this time!”, he thought. Unfortunately, it was not so! “There is no salt in my meal!”, thundered the head visiting-monk. The disciple got up and ran to the head monk to add salt his meal. Soon other monks started complaining and the disciple was running around the hall as he had done before, offering salt to all the visiting monks. The disciple hoped that this would be the last time he would have to do this, but alas, there were three more courses! The rest of the courses passed by in a blur for the disciple. All he could remember was that he was running around the entire hall, bringing salt to the visiting monks. The monks didn’t all finish their meals at the same time and so the later courses were continuously being brought out. Hence, he was always on his feet and didn’t get a chance to rest.

Finally, the monks stopped asking for salt and the disciple wearily went back to his corner. Dessert would be next, and there would be no need for salt then. He had barely sat down when he saw the cook approaching him. This time he had another bowl, also filled with a white substance. When the cook got close, he offered the bowl to the disciple and said a single word: “Sugar”. The disciple was almost in tears. He knew was was coming and prepared himself for the endless rushing around that he would have to do. Luckily there was only one course of dessert. When the feast was done, the disciple collapsed in the corner. He opened his eyes and noticed the cook walking towards him again. “What more will he want me to do?”, thought the disciple frantically. He noticed with some relief however, that the cook’s hands were empty. “Master will see you now”, said the cook as he got closer to the disciple. The disciple wearily got up to his feet and walked to the master’s chambers.

After a few minutes, the disciple arrived at the master’s chambers. He walked in and bowed in front of the master, his legs burning with fatigue. “How was your task?” asked the master with his eyes still closed. “It was exceedingly difficult master! There was no salt in the soup or the meals, and no sugar in the desserts! I had to run around the whole hall bringing salt and sugar to the visiting monks!”, said the disciple. “It must have been exceedingly tiring…”, said the master. “Yes, master! It was!”, said the disciple nodding his head. The master opened his eyes and said, “One could say that your task would have been much easier had the salt and sugar been added to the meals at the source, and thus before they were brought out to our honored visitors.”

In that moment, the disciple was enlightened.

Data and Code

Inspired by The Codeless Code:

A novice monk had just started learning assembly programming when he was troubled by doubt. He approached his master and asked:

“Master, how do I know which is code and which is data?”

The master who was meditating, opened his eyes, smiled, and said:

“Each is the other, yet neither is either.”

“Master, I do not understand.”, said the disciple.

The master then brought out two identical pots and said. “Take these. Fill one with the water from the lake, and fill the other with water from the stream that flows into the lake. Then bring them to me.”

The monk bowed and took the pots. He walked to the lake, which was some distance away and filled it with water from the lake. Then he walked around the side of the lake until he found the stream that fed water into the lake. He used this water to fill the second pot and then brought both pots back to his master and set them at his feet. The master looked at the pots, and then back to his disciple and said “Now go. You may come back tomorrow morning.”

The disciple came back the next morning to find his master standing with the two pots. He held up both the pots and then threw them to the opposite sides of the room. The pots smashed, and the water from both pots flowed towards the center of the room, forming a puddle.

The master then said, “Which pot contained water from the stream? Which pot contained water from the lake?” He then pointed to the growing puddle that was forming in the middle of the room. “Which part of the puddle contains water from the stream? Which part contains water from the lake?”

In that moment, the novice was enlightened.

Akṣi: Handwritten-digit-recognizing neural-network

I’ve always been interested in Neural Networks (ever since I first found out about them around 10 years ago). However, I never got a chance to learn about them or write one of my own; this is something I’ve wanted to do for some time. I got the opportunity this semester when my professor in my advanced data-structures class told us that we could pick any topic we liked, for a semester project. I thought that this would be the perfect time for me to learn about neural networks and create one of my own.

The end result was Akṣi, a neural network that recognizes hand-written digits. I’ve hosted it using Google’s App Engine. Please check it out!

CherryBlossom

I’ve created a project page for the CherryBlossom programming language. You can check it out here. The interpreter is written in perl.

Introducing CherryBlossom

Over the past month, I’ve been working on a new project. It’s called CherryBlossom, and it’s a way to write programs using haikus. Strictly speaking, CherryBlossom is a brainfuck analog. I actually spent more time writing the obligatory “Hello World” program in CherryBlossom than I did writing the interpreter for the language. The idea behind CherryBlossom is simple. Brainfuck instructions are mapped to words that convey the essence of the Brainfuck instruction. Of course, this is a little subjective and also a little abstract.

Ultimately, it serves as a way to make program code not just functional, but beautiful and artistic. Thus, we introduce a new criteria to programming. Your code must not only be elegant algorithmically, but must also be poetic and artistic (also, since program code consists of haikus, you need to represent your code in sets of 3 lines with the first and last lines having 5 syllables, and the second line 7. That is, conforming to haiku rules). CherryBlossom serves to blend the programmer and the poet into one entity (hopefully with amazing results).

Here is an example of “Hello World!” in CherryBlossom. I have opted to use a spruced up div tag instead of enclosing my beautiful poem in soulless sourcecode tags.
Read the rest of this entry »

Maven project for Generic (n-ary) Tree in Java

Guus was kind enough to make a maven project for the Generic Tree. He also fixed an error in my equals method for the GenericTreeNode (I intended to do Object.equals(Object obj) but was doing GenericTreeNode.equals(GenericTreeNode obj). Since it’s a maven project, you can easily create a jar out of it and add it as a dependency to your project. You can download the project here. Thanks Guus!

All original content on these pages is fingerprinted and certified by Digiprove
%d bloggers like this: