Tuesday, April 28, 2009

Electric Traps and a High-Tech Marker

You are lost deep in an enormous maze.

The maze is made of rooms, automatic sliding doors, and fluorescent-lit hallways. The maze is so large and uniform-looking, and your memory is so bad, that you aren't able to remember where you've been or how you got wherever you happen to be. Rooms are connected by hallways with doors at both ends. Hallways can have stairs and ladders to other stories of the maze. There is exactly one exit.

Halfway through every hallway, the walls, floor, and ceiling are lined by strange metal. Every time you step on the metal, the hairs on your arms stand up and you hear a high-pitched squealing coming from the walls. The squealing continues until you're off the metal on one side or another. If you come back to a hallway and step on the same metal a second time, you hear the squealing again, but even higher-pitched. If you step on the metal in any hallway a third time, you get electrocuted and killed. There is no way to get through a hallway without stepping on the metal.

You find in your pocket a high-tech marker that can only write on the metal walls in the hallways, and only when they're squealing. You have no other way to leave markings in the maze.

How do you find your way out alive?

Sunday, April 26, 2009

Consistent Arbitrary Colors

Mibbit gives usernames colors, i think, depending on their users' client. XChat gives everyone but me the same color. I don't like either of these choices because many usernames get the same color, and I therefore can't use color to tell who said something without reading their username.

I'd prefer it if everyone had a different color (to a reasonable extent), but still have the same color the next time they log in. Short of users assigning colors to anything, how could an IRC client accomplish this?

Wednesday, April 22, 2009

Tuesday, April 14, 2009

No Excuse for Ignorance

Java's ArrayList and Scanner classes are two that anyone writing in Java should know about, or else they're stupid.

The following two atrocities are summaries of actual code I had to review, the first at work, the second a submission in a programming competition.

What's an ArrayList?

Inexcusable ignorance:

int size = 0;

int optAIndex = -1;
if (weNeedOptA)
optAIndex = size++;

int optBIndex = -1;
if (weNeedOptB)
optBIndex = size++;

int optCIndex = -1;
if (weNeedOptC)
optCIndex = size++;

String[] options = new String[size];

if (optAIndex != -1)
options[optAIndex] = "-a";

if (optBIndex != -1)
options[optBIndex] = "-b";

if (optCIndex != -1)
options[optCIndex] = "-c";

return options;

Enlightened version:

ArrayList<String> options = new ArrayList<String>();

if (weNeedOptA)

if (weNeedOptB)

if (weNeedOptC)

return options.toArray(new String[options.size()]);

The concept that this code is accomplishing is really pretty basic: add options to an array as we need them. That's just what ArrayList's are for. The ignorant solution uses 18 lines to solve an 8-line problem, and that's the reduced version of the actual code that I've had to deal with.

The toArray(T[]) function is the hardest part of the class to learn, but even the programmers who just copy and paste code they don't understand should be able to pick up that one-liner pretty easily.

If you think you know how to program in Java and you don't know about the ArrayList class, then what you really know is how to be a pain in the neck to other programmers.

The ArrayList api consists of 3 important methods. The constructor, add(T), and toArray(T[]). Don't click on the links, just look at what I did in the example, and that's all you need to know.

Now use it!

I Can Read Numbers All by Myself!

Inexcusable ignorance:

String numberStr = "";
int nextChar = System.in.read();
while (nextChar != -1) { // check for EOF
char c = (char)nextChar;
if ('0' <= c && c <= '9') // check for whitespace
numberStr += c;
break; // end of number
nextChar = System.in.read();
int number = Integer.parseInt(numberStr);

Enlightened version:

Scanner scanner = new Scanner(System.in);
int number = scanner.nextInt();

Two lines!! The task we're trying to perform is to read a number from standard input. Really, did you not think that someone else ran into this problem before you did? The first line wraps a scanner around standard input, so you can read from it many times successively. Really the enlightened version is a 1-line solution with a line for setup.

There's another issue here as well, folks. The inexcusable ignorance can't read negative numbers. The first time through the while loop breaks because '-' is not in the range [0-9]. Then the Integer.parseInt() call will throw a NumberFormatException because numberStr is still the empty string. This was a real submission to a programming competition I helped run, and the negative number issue is the reason the participant got this question wrong.

Not only is the bad solution bulky, it's broken. Use a Scanner!

The Scanner api has lots of nice functions for you. The code below outlines what I've found to be useful constructors and methods:

// reads from a text file
Scanner file = new Scanner(new File("<filepath>"));
while (file.hasNextLine()) {
String line = file.nextLine();
// ...

// reads through a string
Scanner scanner = new Scanner("123 hello 6.67e-11");
int number = scanner.nextInt(); // 123
String token = scanner.next(); // "hello" stops at whitespace
double gravity = scanner.nextDouble(); // Newton's constant
boolean done = !scanner.hasNext(); // true

I hope you, the reader, agree that knowledge these two classes and their api's are an absolute minimum requirement for Java programmers. Please do not put the rest of us through the pain of dealing with their absence in your code.

Thursday, April 9, 2009

Interned Arrays?

Intro to String.intern()

In Java, string comparison is done with the String.equals() method as opposed to using the == operator. This is because the == operator only compares references.

String s1 = "first ";
s1 += "second"; // All these lines are to prevent Java from optimizing
String s2 = "first"; // and concatenating the literals at compile time and
s2 += " second"; // defeating the purpose of this snippet.
assert s1.equals(s2) && !(s1 == s2);

That is to say, s1 and s2 were constructed in different ways but now represent equals strings (they're both "first second".). The .equals() method knows this but the strings are at different locations in memory.

Strings in Java (unlike in C) are immutable. That is to say that once I have a reference to a String, I know that it's value will never change because it is downright impossible for me or anyone else to do so (without using reflection. that's cheating). What does this imply?

When you spell out two different literal strings in your source code that actually have the same value, Java gets smart and really only makes one string and points both references to it.

String s1 = "hello", s2 = "hello";
assert s1 == s2;

It's harmless to do so because String's are immutable. This does a few good things. It takes up less space (which many people might not care about) and it optimizes comparisons. You can see this optimization in Java's String class source code (which Sun has so generously opened):

public boolean equals(Object anObject) {
if (this == anObject) {
return true;
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) {
char v1[] = value;
char v2[] = anotherString.value;
int i = offset;
int j = anotherString.offset;
while (n-- != 0) {
if (v1[i++] != v2[j++])
return false;
return true;
return false;

You can see that a call to .equals() with the object as its own parameter will return in one comparison. But is this optimization only applicable to literal String's?

No, you can create this effect at runtime with the String.intern() method. It returns a unique reference (possibly its own) to a String with the same value as itself. If two String's have the same value, then their .intern() methods will return the same reference.

String s1 = "first ";
s1 += "second";
String s2 = "first";
s2 += " second";
assert s1 != s2;
s1 = s1.intern();
s2 = s2.intern();
assert s1 == s2;

This is done by Java managing a pool of String's that are the official intern representatives, so to speak. When you call .intern(), a match is found from pool and returned, or if there isn't one yet, then you your string goes in the pool and becomes the official intern.

The call to .intern() is potentially expensive, but the idea is to save time later during comparisons and memory usage.

Why use it?

All literal String's go into the pool:

String s1 = "first ";
s1 += "second";
s1 = s1.intern();
String literal = "first second";
assert s1 == literal;

This means that if you are using some arbitrary String constants as property keys, you can just use the equality operator instead of the .equals() method.

public static final String HEIGHT_PROPERTY = "HEIGHT_PROPERTY";

public void setProperty(String key, int value) {
this.height = value;
public void example() {
setProperty(HEIGHT_PROPERTY, 5);

When is this not the case? If you're reading property key/value pairs out of a file or from a stream, then String's are constructed from scratch and the newly created property maps don't use the same memory as your literal.

Property File:


Parsing Code:

String line = scanner.nextLine();
String[] keyAndValue = line.split("=");
String key = keyAndValue[0];
String value = keyAndValue[1];

Here, the key is equal to HEIGHT_PROPERTY according to the .equals() method, but not the == operator. Instead of changing all your code to use .equals() instead of the == operator, you can just intern the key.

String key = keyAndValue[0].intern();

Now you can still use the == operator throughout your code, and, as long as there are enough comparisons performed after the value is read from the file, you've increased performance.

Interned Arrays?

In Java, the size of an array is immutable. In order to increase the size of an array, you have to create a new one, then copy the contents into it.

Object[] objects = new Object[10];
// now we need it to be bigger
Object[] newObjects = new Object[20];
System.arraycopy(objects, 0, newObjects, 0, 10);
objects = newObjects;

This doesn't mean that arrays are themselves immutable in the same way that String's are because you can change the contents of an array. The only exception to this is, of course, zero-length arrays, who don't have any contents to change. This means that one zero-length array of a type is indistinguishable from another, leading to programmers getting smart and keeping just one zero-length array around and using it instead of creating new ones all the time.

Instead of writing this:

public Result[] getResults() {
if (resultGenerator == null)
return new Result[0];
return resultGenerator.getResults();

they write this:

private static final Result[] NO_RESULTS = new Result[0];

public Result[] getResults() {
if (resultGenerator == null)
return NO_RESULTS;
return resultGenerator.getResults();

This is a good idea, in my opinion, but also creates clutter just for the sake of efficiency. And what if another class were also storing a zero-length array of Result's? Then the purpose is partially defeated because there isn't just one instance. Is there a solution?

If the Java language 'interned' zero-length arrays, then this problem would be solved (and look much nicer).

Object[] a1 = new Object[0];
Object[] a2 = new Object[0];
assert a1 == a2; // fails :(

Currently, Java does not intern literal zero-length arrays, like the ones above. I agree that the "new" keyword looks like it should actually create something new. If, however, Java kept a special copy of zero-length arrays around for each type, it would take care of some optimizations that are ugly to write in code. The reference to the zero-length array would be inserted into the bytecode instead of the call to create a new one of length zero. It would only work for explicitly zero-length arrays. It wouldn't work for the following code.

private Object[] makeArray(int size) {
return new Object[size];
private void example() {
Object[] a1 = new Object[0];
Object[] a2 = makeArray(0);
assert a1 == a2; // hopeless

In this situation, there's no way around having two instances of zero-length arrays. Having a .intern() function on arrays would be more hassle than it's worth, because it only applies to zero-length arrays, which is a property that's usually only known at runtime.

What I'm proposing is that the code

new SomeType[0]

will never allocate memory, but will return a reference to an already existing zero-length array of type SomeType.

What do you think?

Sunday, April 5, 2009

Programming Languages Quiz

I made a little quiz covering new stuff about programming languages I learned that I thought was interesting.

It's as language-neutral as I could make it. Like you don't have to know C# specifically or anything.

It's really easy to look up the answers on the internet, so your score is only as honest as you are.

Programming Languages Quiz

I'm open for corrections or suggestions.

Saturday, April 4, 2009

Nice Guys Sleep Alone

You always loved the jerk in me and when I didn't treat you right.
You said I should change, be gentle and kind, but you really wanted to fight.
I blew you off and beat you down. It only made you want me more.
You knew I wasn't right for you, just one more thing to like me for.

Then I changed per your request, softened sweet and meek.
I served you, loved you, promised to wed you. But you just saw me as weak.
Your twisted heart's desires and your longing to pursue,
You bored of me and left me. And I'll never forgive you.

I gave you my life. The game is done.
Rejecting this mere trophy heart that you've won.
You showed me you loved me. I tried to be true.
You left me with nothing. I'll never forgive you.

If jerks you like, then jerks you'll get. You'll never be happy in life.
You love the hate and lust the fight. You'll never be anyone's wife.
I'll be the jerk you love again. You can be sure of that.
I'll win you back and catch your heart. And then I'll leave you flat.

All my devotion to you was in vain.
All the hurt I'll remit.
I'll give you your drama, abuse, and pain.
You'll beg to be mine, and I won't give you shit.