Rough Book

Last week I was solving a problem at work that required the use of a Generic (n-ary) Tree. An n-ary tree is a tree where node can have between 0 and n children. There is a special case of n-ary trees where each node can have at most n nodes (k-ary tree). This implementation focuses on the most general case, where any node can have between 0 and n children. Java doesn’t have a Tree or Tree Node data structure. I couldn’t find any third-party implementations either (like in commons-lang). So I decided to write my own.
Read more…

A few days before I left India, I started writing a brainfuck interpreter in bAdkOde. I finished implemented all the instructions, excepting for looping. I actually finished the code (and fixed all bugs) while I was in the air, flying from Dubai to Los Angeles. Emirates Airlines has power-plugs for your laptop on the seat. It’s pretty sweet!

An interesting thing I noticed was that I couldn’t perfectly emulate the input instruction. I’m feeding the brainfuck code to the interpreter from STDIN and so that might be the problem. I’ve noticed that brainfuck interpreters written in brainfuck have the same problem. You have to specify program input before hand. This is what I’ve decided to do. You write brainfuck code, and then mark the end of program code by an exclamation mark. After the exclamation mark, you provide any input, and then mark the end of input by another exclamation mark. Programs that do not have any input end with two exclamation marks. After I finished writing the interpreter, I commented it. While I was doing this, I noticed a lack of labels in bAdkOde. So, I decided to update the interpreter to include them. Speaking of which, I really ought to rewrite the interpreter sometime…

Anyway, here is the code to the interpreter. I’m providing a link to it, because the commented version is rather large. But here’s the expanded (without labels or macros), unformatted version:

>3a>1b{!b?b>b[a)b-91b{=b+1[b>1b}+91b-93b{=b-1[b>1b}+93b(b+1a-33b}>0[a+1a>2b>a[b>1b{!b?b>b[a+1a-33b}>1b>a[b>0a>[aa>ab{=a>1a>[ab>3a{![a)a>[aa-62a{=a+1b-30000b)a>ba{+b>1b>[bb)b>0b-1b>0a}{-a+30000b)b>0a}(b(a+62a}+62a-60a{=a-1b)a>1a>[aa-ab>ba{-b>1a>[aa+30000a>ab)b>0b>0a-1a}{+a>1a>[aa+ab)b>0a-1a}(b(a+60a}+60a-43a{=a+1[b+43a}+43a-45a{=a-1[b+45a}+45a-46a{=a"[b+46a}+46a-44a{=a)a>2a>[aa>[a[b>2a+1[a(a+44a}+44a-91a{=a(a)b)a>[bb{=b>0b>1[b{![b(a+1a)a>[aa)a-91a{=a+1[a>1a}+91a-93a{=a-1[a>1a}+93a(a}(a-1a)a>1b}(a(b)a+91a}+91a-93a{=a(a)b)a>[bb{!b>0b>0[b-1[b{![b(a-1a)a>[aa)a-91a{=a+1[a>1a}+91a-93a{=a-1[a>1a}+93a(a}>0b}(a(b)a+93a}+93a(a+1a}>1a>0b}{!b"85"110"109"97"116"99"104"101"100"32"98"114"97"99"107"101"116"115>0b}

Also, this is additional proof for Turing Completeness. Yes, I’m a nerd!

Happy New Year! Well, this year is already starting off pretty well because of:

Aparna

I wonder what this decade (alright, I know it technically starts in 2011, but still) is going to be like. I hope there’s better music for one. At any rate, a whole set of new experiences and new memories; the last one wasn’t short on that! Here’s to another great decade!

Note: This post shows up on December 31^st because it isn’t New Year’s yet in Arizona (and this blog runs on MST)! I’m in India right now and it’s January 1^st, 2010 here.

…within the span of a few minutes, Beck implied that there are no quality medical schools in India; implied that medical care in India is a shoddy imitation of real health care; implied that the entire nation is an undeveloped backwater without even so much as indoor plumbing; and compared the Ganges River, a holy body of water for one of the world’s oldest and largest religions, to a disease…

I guess the only reason Glenn Beck is popular is because there is apparently a marketable-segment of idiots in America. You know, the morons that watch Fox News and actually believe what they hear. Glenn Beck, you are an asshole. You are an ignorant bigot and a douchebag. There are a few people that I know, that oppose the health reform. But the strange thing is that they have rather valid arguments, and even though I may not agree with them, I find them rather intelligent and well thought-out. I mean, Mr. Beck. I realize that by being an ignorant douchebag it’s beyond you to form coherent arguments but seriously… do you have to stoop to the level of offending an entire nation? Or what about the entire community of Indian-Americans?

Usually when people make arguments or counter-arguments about a topic, they usually know what they’re talking about because they’ve researched the topic thoroughly. Oh wait. That’s only if they have a proper show that actually discusses political topics with valid arguments instead of gleefully bending over for the lunatic far-right and being their sockpuppet. Hell, I probably shouldn’t blame you. You are making money after all, even if you have to sell your soul for it. No, your show is a circus and your arguments are bullshit. Even still, I find it appalling that you would denigrate an entire nation and community. You may not think much about Indian doctors, but they seem to be a successful and well-respected bunch in India, with a large number of satisfied customers. In one fell swoop you’ve insulted the cultural and religious sentiments of Indians, you’ve made light of the sweat, blood, and tears of her doctors that strive to serve their nation (and who have migrated to other nations, including *gasp* the United States and serve Americans), and you’ve implied that India is some backwater country without any sort of facilities. Sure, India is no United States and it has a long way to go, and even though you may have the right to say whatever the hell you want, it’s really, really bad form to make fun of a country and her people. You xenophobic, ignorant, douchebag. I find it surprising that even you would stoop this low for ratings.

You sir, are an asshole.

She said, “Yes”. Although I guess it was never in doubt that she would say anything else (being a semi-arranged marriage and all), it still feels nice . The official engagement ceremony was today. It was a traditional Nair engagement ceremony (known as a nischayam – literally translated, “decision”) where both families express their consent to the alliance and inform everyone in attendance of the same. I don’t have pictures of the ceremony on me; I’m waiting on the CD of photos from the photographers. This picture is from when I first gave her the ring.

In my previous post, I suggested that bAdkOde might be Turing Complete by writing a quine. One of the ways to actually prove Turing Completeness is to try and write an interpreter for another Turing-Complete language in bAdkOde. Another approach involves providing a direct translation from another Turing-Complete language into bAdkOde. Here, I prove the Turing Completeness of bAdkOde by providing a direct translation from Brainfuck into bAdkOde.
Read more…

On the bAdkOde project page, I mentioned that I didn’t know whether bAdkOde is Turing Complete (although I suspected it). I also mentioned that if I was able to write a quine in bAdkOde, then it would probably mean that it is Turing Complete. I was able to write one after going through this excellent quine tutorial by Dave Cope.
Read more…

December 19^th, 2000 was a Tuesday. It was the day I enlisted into the Arizona Army National Guard. Today, 9 years later, I’m finishing up my service. From my very first days at C Btry, 1/180^th FA, a tour in Iraq, and all the way to E^co 29^th BSB, it’s been quite a ride. I didn’t reenlist because I want to concentrate of my career, and frequent deployments would put me at a serious disadvantage in my field. This is not to say that I’m not torn by my decision. Part of me wants to stay in. Part of me will always want to be in the Army. It has been an amazing 9 years for me. Being part of the Army has given me discipline and confidence and has taught me the meaning of honor, duty, loyalty, and courage. I think I was a good soldier and as an NCO I think I did my best to take care of the soldiers under me. Along the way, I also made some wonderful friends who might as well be family now. The kind of camaraderie that forms when you serve with people in a combat zone cannot be put into words.

Looking back I think I can say that I’m satisfied with my career. I still remember coming in as a 19-year old Private… I knew that I at least wanted to make Sergeant before I got out, and I’m glad that I was able to achieve that. Being able to wear the uniform is something amazing. You are a part of something larger than yourself. It’s hard to put into words… I just know that it’s something that I will miss terribly.

I can’t say that I’ve looked forward to this day (although my family has). 9 years is a long time to serve and after doing something for so long, it becomes a very integral part of you and your identity. I guess I will always be a soldier and a veteran; I have earned that right. But I know I’ll always be looking back at my Army years fondly, half-wishing I was still wearing the uniform and still serving the nation.

Go Army! HOOAH!

In any science fiction story I’ve read (or science fiction movie or TV show that I’ve seen) that talks about death of the Sun. I’ve always heard references to Earth’s sun “going nova”. I’ve read about this even in Asimov’s stories. In most cases, they’re talking about a supernova. But here’s the thing. The Sun is not going to blow up. Even if the writers were talking about an actual nova, they’re still wrong. Here’s why:

Our Sun is a yellow dwarf star (more precisely known as a G-type main-sequence star), and doesn’t have enough mass to undergo a supernova explosion (type IIa). You need a star that’s at least nine times the Sun’s mass for a supernova explosion. If we’re simply looking at a nova (type Ia), then the Sun doesn’t have a companion to draw matter from when it turns into a white dwarf. So no matter which way you look at it, the Sun is not going to blow up. It’s just going to be really, big and red and will eat the Earth. Unless the Earth moves outward due to the Sun losing mass. Finally the Sun with eject its outer layers and turn into a white dwarf. See? No blowing up. I don’t know why some science fiction authors still talk about the Sun “going nova”. Maybe it’s because it sounds more dramatic.

If anyone has read a science fiction story (or seen a science fiction movie or TV show) that talked about the death of the Sun/Earth and did so realistically, then let me know.

I was talking to my CSE 200 (my first CS class at ASU) professor Richard Whitehouse about bAdkOde and he (rightly) pointed out that it didn’t have an explicit selection statement. He also said that unless I wanted it to be really ugly I’d need to have a selection statement. However, since I was going for ugly I figured that I’d just emulate the operation of an if and an if-else with the existing while statement.

If you know assembly, then you know that a while is simply a set of statements wrapped with a conditional branch at the top and a backwards branch at the bottom (or in other words, an if with a goto at the end. A do-while is simply a set of statements with a conditional branch (at the bottom) that branches to the top of the loop. In fact, in assembly programming there really aren’t any for loops or while loops. These keywords are simply abstractions and syntactic sugar. In bAdkOde, you can implement an if with the existing while statement if you explicitly make it break out of the loop. For example, let’s say that we want to check whether the user entered the character “0″:

?a
-48a
# print a line break
"10
# if a is zero
{=a
 # print the string "zero"
 "122"101"114"111"10
 # set the a register to a non-zero value so that we can break out of the loop
 >1a
}

I knew there was a way to implement an if-else with just while statements but I didn’t remember exactly how. Then my friend and co-worker Juan reminded me that I needed two variables. In our case, we need to use two registers:

?a
-48a
# copy the value of a into b
>ab
"10
# if a is zero
{=a
 # print the string "zero"
 "122"101"114"111"10
 # set the a register to a non-zero value so that we can break out of the loop
 >1a
}
# if the top loop failed, it means that b (which holds the same value as a) is
# non-zero and so we can enter this block.
# if the top loop was successful, it means that b (which holds the same value
# as a) is zero and so we won't enter this block. Hence, the second block acts
# as an 'else'
{!b
 # print the string "non-zero"
 "110"111"110"45"122"101"114"111"10
 # zero out the b register
 >0b
}

Yes, quite ugly. But that’s what I’m going for!