A school-related computer game

My blog has been somewhat neglected for the past few days. I suppose one of the reasons is my work on a really big school project.

In place of a final exam, the Language Arts course at my school offers something called a Language Arts portfolio, consisting of three projects. The creative portion of the portfolio is quite free-form: you were to pick a novel and do pretty much anything you wanted on it.

For this project I chose the novel Siddhartha by Herman Hesse:

I chose to create a Java game for this assignment. The game was a sort of role-playing platformer, and in my own words, ‘a combination of Runescape and Maple Story’.

This project took up most of my time for the last week or so. Planning began about four weeks ago, and I began coding and writing the dialogs about three weeks before. I nevertheless scrambled to complete all of the graphics and put it all together on the weekend.

Unlike most Language Arts assignments, I actually quite enjoyed making this game, and I’m proud of my work. I’m going to release the game along with its source code:

siddhartha.zip (1.7 mb)

On windows, the game can be run by double-clicking game.bat. Java 1.5 or later is required to run this game.

Here’s what the game looks like:

I was given an opportunity to ‘present’ my project to the class today. The school laptop had a problem with some java dll’s, but a classmate had a working laptop so the presentation went fairly well. I discovered one or two bugs in the presentation that I never noticed when testing the game.

I also tried to get my girlfriend to playtest the game, which kind of failed miserably.

Technical details of the game

Before starting coding for the game, I searched for existing, similar, open source, java alternatives. Finding none, I was forced to make my own.

If anyone else ever wants to make a similar game, my work here might be useful. If I myself were to make something like this again in the future, I wouldn’t have to write the game from scratch again. Of course by then I would have forgotten how the code works; it would benefit me to write about it here to refer back to in the future.

The following section is probably too technical and would be only useful when trying to understand my code. Anyways.

The game is written in about 1300 lines of Java code (although about 60% of it was configuration so only about 600 lines of it was game logic). The images are mostly drawn in MS-Paint, since I’m not very skilled at using Photoshop. I only used Photoshop to change all of the white pixels to transparent pixels (impossible in MS-Paint).

I chose JGame for the game engine. This is a decent game engine, although I think it’s a bit buggy and very unprofessional (the sample games look like they’re from the 1980’s). It’s backed by OpenGL, not because the game uses any OpenGL features, but because the non-OpenGL version of the library has a certain bug in one of its functions that I wasn’t sure how to circumvent.

This particular bug was about the setBGImage() function, which seemed to not work on the JRE version of JGame. I asked a question on Stack Overflow, but didn’t really get an answer.

The most complicated portions of the game was handling transitions between maps, and handling dialogs. The handling of maps was done completely in Java code, while the dialogs were handled in an ad-hoc scripting language I created for this purpose.

To transition between maps, I had the idea of a portal, which would activate at certain points and replace the existing map (and all its objects) with a new map, and adjust the game state accordingly. In essence, a portal has a one-way connection to another portal. To make such a connection, a portal keeps a reference to its connecting portal, so that it can change the game accordingly when needed.

The portal has an off state, an on state (when the player is touching the portal), and an active state (when the transition between maps is taking place). If a portal has a connecting portal, it is ‘activated’ when the up key is pressed, otherwise it cannot be activated.

A map in the game takes up exactly one screen, has one background image, can have multiple portals, and at most one NPC (non player character). There are 28 maps in this game (some sharing the same background).

A NPC is a character in the game that’s not the player. A NPC has a still (non-animated) sprite, and holds a constant position in exactly one map. The same NPC appearing in different maps may have the same sprite, but are otherwise completely different. A NPC has a name, which is shown above the NPC’s head on mouse over; when clicked the player enters a conversation. A NPC has exactly one conversation attached to it.

The conversation data in the game is defined in a file: speech.dat. The first part of the file contains a sort of scripting language describing how the conversations flow, while the second part is a dump of all the actual String data to put for the dialogs. Each line in the String data section is assigned a number starting from 0, to be referred to in the rest of the game.

A conversation always starts with the player. From there, whoever is speaking can continue to speak (the same command), or the other person can start speaking (the chgspk command). Either that, or we can present the player with a list of choices (the choose command). When the conversation ends, we direct the next line to END_DIALOG, which is defined on line 0.

The flow of the conversation is contained in arrays or maps of the SpeechCode object. This object contains the line number of the source string, the line number of the target string, and the opcode. When drawing the message, we look up the String from a table using the source key, and when the player clicks the continue part, we look up the new SpeechCode using the target key, and adjust the speaker according to the opcode.

Hopefully this is enough high level documentation for the project. I don’t think I’ll be working on this game again.

How System.out.println() really works

A few days ago I came across an interesting article, Where the printf() Rubber Meets the Road, describing how the printf function ‘works’ on the low level.

Commonly asked by Java beginners is the question, “How does System.out.println() work?”; the above blog post inspired me to do some research into this question. In this blog post I’ll attempt to provide an explanation of what System.out.println() does behind the scenes.

Most of the relevant code can be found on OpenJDK, which is the primary implementation of Java itself. System.out.println() may be implemented completely differently on other Java platforms.

I will warn you now that this article is very long and not for the easily bored.

First steps

Our first step in figuring out how System.out.println works is by first understanding what System.out is and how it came to be.

Let’s take a look through the OpenJDK’s Mercurial online repository. Digging around a bit, we find System.java. In this file System.out is declared:

public final static PrintStream out = nullPrintStream();

But when we find the code for nullPrintStream():

private static PrintStream nullPrintStream() throws NullPointerException {
    if (currentTimeMillis() > 0) {
        return null;
    }
    throw new NullPointerException();
}

So nullPrintStream() simply returns null or throws an exception. This can’t be it. What’s going on here?

The answer can be found in the function initializeSystemClass(), also in System.java:

FileOutputStream fdOut = new FileOutputStream(FileDescriptor.out);
setOut0(new PrintStream(new BufferedOutputStream(fdOut, 128), true));

There’s a lot of stuff going on in this code. I’m going to refer back to this two lines of code later, but setOut0() is what actually initializes System.out.

The function setOut0() is a native function. We can find its implementation in System.c:

JNIEXPORT void JNICALL
Java_java_lang_System_setOut0(JNIEnv *env, jclass cla, jobject stream)
{
    jfieldID fid =
        (*env)->GetStaticFieldID(env,cla,"out","Ljava/io/PrintStream;");
    if (fid == 0)
        return;
    (*env)->SetStaticObjectField(env,cla,fid,stream);
}

This is pretty standard JNI code that sets System.out to the argument passed to it.

At first all this deal with setting System.out to nullPrintStream() and later setting it with JNI seems entirely unnecessary. But this is actually justified.

In Java, static fields are initialized first, and everything else comes after. So even before the JVM and the System class is fully initialized, the JVM tries to initialize System.out.

Unfortunately at this point the rest of the JVM isn’t properly initialized so it’s impossible to reasonably set System.out at this point. The best that could be done would be to set it to null.

The System class, along with System.out is properly initialized in initializeSystemClass() which is called by the JVM after static and thread initialization.

There is a problem, however. System.out is final, meaning we cannot simply set it to something else in initializeSystemClass(). There’s a way around that, however. Using native code, it is possible to modify a final variable.

Wait, what’s a FileDescriptor?

Notice this line of code:

FileOutputStream fdOut = new FileOutputStream(FileDescriptor.out);

A FileOutputStream object is created from something referred to as FileDescriptor.out.

The FileDescriptor class, though part of java.io, is rather elusive. It can’t be found in the java.io directory in OpenJDK.

This is because FileDescriptor is much lower level than most of the Java standard library. While most .java files are platform independent, there are actually different implementations of FileDescriptor for different platforms.

We’ll be using the Linux/Solaris version of FileDescriptor.java.

A FileDescriptor object is very simple. Essentially all it really holds is an integer. It holds some other data too, which aren’t really important. The constructor of FileDescriptor takes an integer and creates a FileDescriptor containing that integer.

The only use of a FileDescriptor object is to initialize a FileOutputStream object.

Let’s see how FileDescriptor.out is defined:

public static final FileDescriptor out = new FileDescriptor(1);

FileDescriptor.out is defined as 1, in as 0, and err as 2. The basis of these definitions are from a very low level somewhere in Unix.

We now know how System.out is initialized. For now, we’re going to leave behind the FileDescriptor; we only need to know what it does.

A tour through java.io

Now we redirect our attentions to the println() function of PrintStream.

PrintStream is a comparably higher level class, capable of writing many different kinds of data, flushing and handling errors for you without much effort.

Let’s see how println() is defined in PrintStream.java:

public void println(String x) {
    synchronized (this) {
        print(x);
        newLine();
    }
}

Following the call stack to print():

public void print(String s) {
    if (s == null) {
        s = "null";
    }
    write(s);
}

Going deeper, and looking at write():

private void write(String s) {
    try {
        synchronized (this) {
            ensureOpen();
            textOut.write(s);
            textOut.flushBuffer();
            charOut.flushBuffer();
            if (autoFlush && (s.indexOf('\n') >= 0))
                out.flush();
        }
    }
    catch (InterruptedIOException x) {
        Thread.currentThread().interrupt();
    }
    catch (IOException x) {
        trouble = true;
    }
}

Internally, the PrintStream object (System.out) contains three different objects to do its work:

  • The OutputStreamWriter object (charOut), writing character arrays into a stream
  • The BufferedWriter object (textOut), writing not only character arrays but also strings and text
  • A BufferedOutputStream object (out), passed all the way down the call stack and used much lower then at the PrintStream level

We can see that PrintStream.write() calls BufferedWriter.write() and flushes both buffers. I’m not sure why it’s necessary to flush the charOut buffer, so I’m going to ignore that.

Delving deeper, let’s find the implementation of write() in BufferedWriter.java.. wait it’s not here. The function write(String) is actually defined in the abstract class Writer.java:

public void write(String str) throws IOException {
    write(str, 0, str.length());
}

Moving back to BufferedWriter:

public void write(String s, int off, int len) throws IOException {
    synchronized (lock) {
        ensureOpen();

        int b = off, t = off + len;
        while (b < t) {             int d = min(nChars - nextChar, t - b);             s.getChars(b, b + d, cb, nextChar);             b += d;             nextChar += d;             if (nextChar >= nChars)
                flushBuffer();
        }
    }
}

As its name suggests, BufferedWriter is buffered. Data is stored in a data buffer until it’s written all at once, or flushed. Buffered IO is much faster than simply writing to the hardware one byte at a time.

The function BufferedWriter.write() doesn’t actually write anything. It only stores something in an internal buffer. The flushing is not done here, but back at PrintStream.write().

Let’s go to flushBuffer(), in the same file:

void flushBuffer() throws IOException {
    synchronized (lock) {
        ensureOpen();
        if (nextChar == 0)
            return;
        out.write(cb, 0, nextChar);
        nextChar = 0;
    }
}

We find yet another write() call, on a Writer object (out). The out object here is the charOut object of PrintStream, and has the type OutputStreamWriter. This object is also the same object as charOut in PrintStream.

Let’s look at OutputStreamWriter.write() in OutputStreamWriter.java:

public void write(char cbuf[], int off, int len) throws IOException {
    se.write(cbuf, off, len);
}

This now transfers the job to another object, se. This object is of type sun.nio.cs.StreamEncoder. We’re going to leave the java.io directory for a while.

Let’s see the implementation of StreamEncoder.write() in StreamEncoder.java:

public void write(char cbuf[], int off, int len) throws IOException {
    synchronized (lock) {
        ensureOpen();
        if ((off < 0) || (off > cbuf.length) || (len < 0) ||                 ((off + len) > cbuf.length) || ((off + len) > 0)) {
            throw new IndexOutOfBoundsException();
        } else if (len == 0) {
            return;
        }
        implWrite(cbuf, off, len);
    }
}

Moving on to StreamEncoder.implWrite():

void implWrite(char cbuf[], int off, int len)
    throws IOException
{
    CharBuffer cb = CharBuffer.wrap(cbuf, off, len);

    if (haveLeftoverChar)
        flushLeftoverChar(cb, false);

    while (cb.hasRemaining()) {
        CoderResult cr = encoder.encode(cb, bb, false);
        if (cr.isUnderflow()) {
            assert (cb.remaining() <= 1) : cb.remaining();             if (cb.remaining() == 1) {                 haveLeftoverChar = true;                 leftoverChar = cb.get();             }             break;         }         if (cr.isOverflow()) {             assert bb.position() > 0;
            writeBytes();
            continue;
        }
        cr.throwException();
    }
}

Again this calls another function, writeBytes(). Here’s the implementation:

private void writeBytes() throws IOException {
    bb.flip();
    int lim = bb.limit();
    int pos = bb.position();
    assert (pos <= lim);
    int rem = (pos <= lim ? lim - pos : 0);     if (rem > 0) {
        if (ch != null) {
            if (ch.write(bb) != rem)
                assert false : rem;
        } else {
            out.write(bb.array(), bb.arrayOffset() + pos, rem);
        }
    }
    bb.clear();
}

We’re done with StreamEncoder. This class essentially processes or encodes character streams, but ultimately delegates the task of writing the bytes back to BufferedOutputStream.

Let’s take a look at the code for write() in BufferedOutputStream.java:

public synchronized void write(byte b[], int off, int len) throws IOException {
    if (len >= buf.length) {
        /* If the request length exceeds the size of the output buffer,
           flush the output buffer and then write the data directly.
           In this way buffered streams will cascade harmlessly. */
        flushBuffer();
        out.write(b, off, len);
        return;
    }
    if (len > buf.length - count) {
        flushBuffer();
    }
    System.arraycopy(b, off, buf, count, len);
    count += len;
}

And BufferedOutputStream passes the baton again, this time to FileOutputStream. Remember when we instantiated fdOut as a FileOutputStream? Well, this is it, passed down through dozens of system calls.

Believe it or not, FileOutputStream is the final layer before JNI. We see the function write() in FileOutputStream.java:

public void write(byte b[], int off, int len) throws IOException {
    writeBytes(b, off, len);
}

And writeBytes():

private native void writeBytes(byte b[], int off, int len) throws IOException;

We’ve reached the end of the Java part. But we’re not quite finished.

A Review of the java.io call stack

This is a ‘contains’ chart:

Also here’s the entire call stack:

Stepping into the JNI

After FileOutputStream, the writing of bytes to the console is handled natively. Much of this native code is platform dependent: there are different versions of the code for Windows and Linux. We’re going to deal with the Linux versions first.

The native implementation of writeBytes() is defined in FileOutputStream_md.c.

JNIEXPORT void JNICALL
Java_java_io_FileOutputStream_writeBytes(JNIEnv *env,
    jobject this, jbyteArray bytes, jint off, jint len) {
    writeBytes(env, this, bytes, off, len, fos_fd);
}

The field fos_fd is the integer stored in the FileDescriptor object that we’ve visited so long ago. So for the out stream, fos_fd should be 1.

We’re just calling a method, writeBytes, with the additional argument of fos_id. The implementation of writeBytes() is defined in io_util.c:

void
writeBytes(JNIEnv *env, jobject this, jbyteArray bytes,
           jint off, jint len, jfieldID fid)
{
    jint n;
    char stackBuf[BUF_SIZE];
    char *buf = NULL;
    FD fd;

    if (IS_NULL(bytes)) {
        JNU_ThrowNullPointerException(env, NULL);
        return;
    }

    if (outOfBounds(env, off, len, bytes)) {
        JNU_ThrowByName(env, "java/lang/IndexOutOfBoundsException", NULL);
        return;
    }

    if (len == 0) {
        return;
    } else if (len > BUF_SIZE) {
        buf = malloc(len);
        if (buf == NULL) {
            JNU_ThrowOutOfMemoryError(env, NULL);
            return;
        }
    } else {
        buf = stackBuf;
    }

    (*env)->GetByteArrayRegion(env, bytes, off, len, (jbyte *)buf);

    if (!(*env)->ExceptionOccurred(env)) {
        off = 0;
        while (len > 0) {
            fd = GET_FD(this, fid);
            if (fd == -1) {
                JNU_ThrowIOException(env, "Stream Closed");
                break;
            }
            n = IO_Write(fd, buf+off, len);
            if (n == JVM_IO_ERR) {
                JNU_ThrowIOExceptionWithLastError(env, "Write error");
                break;
            } else if (n == JVM_IO_INTR) {
                JNU_ThrowByName(env, "java/io/InterruptedIOException", NULL);
                break;
            }
            off += n;
            len -= n;
        }
    }
    if (buf != stackBuf) {
        free(buf);
    }
}

The writing here is done by a method called IO_Write. At this point, what happens next becomes platform dependent, as IO_Write is defined differently for Windows and Linux.

The Linux Way

The linux way of handling IO uses the HPI (Hardware Platform Interface). Thus, the method is defined as JVM_Write in io_util_md.h:

#define IO_Write JVM_Write

The code form JVM_Write is defined in the JVM itself. The code is not Java, nor C, but it’s C++. The method can be found in jvm.cpp:

JVM_LEAF(jint, JVM_Write(jint fd, char *buf, jint nbytes))
  JVMWrapper2("JVM_Write (0x%x)", fd);

  //%note jvm_r6
  return (jint)os::write(fd, buf, nbytes);
JVM_END

The writing is now done by various HPI methods. Although you could go further, I’m going to stop here, since we’re now so far from where we started.

The Way of Windows

In Windows, the method IO_Write is routed away from the HPI layer. Instead, it’s redefined as handleWrite in io_util_md.h.

The implementation for handleWrite() is defined in io_util_md.c:

JNIEXPORT
size_t
handleWrite(jlong fd, const void *buf, jint len)
{
    BOOL result = 0;
    DWORD written = 0;
    HANDLE h = (HANDLE)fd;
    if (h != INVALID_HANDLE_VALUE) {
        result = WriteFile(h,           /* File handle to write */
                      buf,              /* pointers to the buffers */
                      len,              /* number of bytes to write */
                      &written,         /* receives number of bytes written */
                      NULL);            /* no overlapped struct */
    }
    if ((h == INVALID_HANDLE_VALUE) || (result == 0)) {
        return -1;
    }
    return written;
}

The WriteFile function is in the Windows API. The Windows API is not open source, so we would have to stop here.

Conclusion

We’ve taken a tour through the entire call stack of System.out.println(), from the instantiation of System.out to the path through java.io, all the way down to JNI and HPI level IO handling.

We haven’t even reached the end. No doubt there’s dozens more levels underneath the HPI layer and the WriteFile API call.

Perhaps the better answer to the question, “how does System.out.println() work” would be “it’s magic”.

Facebook: Simon Says – How to set up Thrift on Windows

I’ve been doing some of the Facebook Engineering Puzzles recently, and in a previous blog post I described how to solve the problem User Bin Crash.

The problem User Bin Crash would be considered a batch problem. Such problem requires a program that takes some input, and produces some output. All the judge does is feed your program the input and check its output.

Thrift problems are a bit different. Such a problem would be an interactive problem, where the judge program has to interact with your program.

In the facebook puzzles, Simon Says, Rush Hour, Battleship, and Dinosaur island are interactive problems. All of the rest of the problems are batch.

Interactive problems are submitted in a different way from regular problems, as well. You, the programmer, are required to make a Thrift program, and instead of sending it to run on their server, you run your program on your own computer. The program connects to the facebook servers via Thrift. A successful program will return a special code which can be used to claim credit for a problem.

Because of the nature of interactive problems, they are somewhat difficult to set up. Thrift itself is rather new and its documentation lacking. When making my first Thrift submission, I found a few difficulties. No adequate tutorial exists on this topic, so this post may be of some use to future puzzlers.

Prerequisites

Simon Says is, after all, a simple test problem to help you get set up with Thrift.

This tutorial is relevant most if you are using the Java programming language, and are using Windows with Cygwin. If you’re using a different language, or a different platform, parts of this document may not apply to you.

Cygwin is required because the thrift compiler itself does not run natively on windows. Only the base cygwin is necessary to run the thrift compiler.

Step 1: Setting up the Thrift compiler

The official Thrift package comes only with the source code, and no linux nor cygwin binaries. As building anything from source is a tricky and error-prone process, we’re not going to compile Thrift from source (even though the official documentation recommends us to do so).

I wasn’t able to compile Thrift from source, but I found someone else’s cygwin Thrift binaries. I’ll put a link to it:

thrift.zip (2.5 mb)

To run this in Cygwin, extract thrift.exe to /cygwin/bin/.

This Thrift binary is of version 0.20, which is not backwards compatible with 0.10. The Thrift wiki provides cygwin binaries to 0.10, which isn’t very useful for us since the code generated by 0.10 can’t be used to solve Facebook problems.

Anyways, this compiler will likely be obsolete soon, and 0.3x will likely break backwards compatability again.

The Thrift compiler compiles your thrift source into source code into a language of your choice. The outputted source code contains much of the code handling networking, protocols, etc.

To run the thrift compiler, navigate to the directory containing simonsays.thrift (while in cygwin), and run,

thrift --gen java simonsays.thrift

You should now have a directory called gen-java. At this point we just need the stuff in gen-java, and we don’t need the thrift compiler anymore. We can also switch back from the cygwin shell.

Part 2: Setting up the Java libraries

To build and run a Thrift Java program, we need to link a few libraries. The first library is the Java thrift library, which I’ve named thrift.jar.

Another dependency is SLF4J, a logging framework required by the Thrift libraries. I’m not sure why it really needs this library, but we need this to compile the code. I’ve named this library slf4j.jar.

Here’s a download link to the two jar files:

javathrift.zip (189 kb)

Now we’re ready to begin coding. In a new directory, place the two jar files and the gen-java folder; create your source file in this folder as well.

Part 3: Coding the problem

The problem itself is very simple. On each round, you receive a list of colors via startTurn(), and send the colors back one by one in order using chooseTurn(). When you’re done, call endTurn() (which also tells you if there’s more rounds).

In the beginning, call registerClient() with your facebook email address; at the end, call winGame() to receive the special password.

Here’s my implementation (simonsays.java):

import org.apache.thrift.*;
import org.apache.thrift.transport.*;
import org.apache.thrift.protocol.*;
import java.util.*;

public class simonsays{
    public static void main(String[] args) throws Throwable {

        // Set up the thrift connection to the Facebook servers
        TTransport transport =
            new TSocket("thriftpuzzle.facebook.com", 9030);
        TProtocol protocol = new TBinaryProtocol(transport);
        SimonSays.Client client = new SimonSays.Client(protocol);
        transport.open();

        // Register client
        client.registerClient("your.email@gmail.com");

        boolean done = false;

        while(!done){

            // Retrieve color list
            List<Color> listColors = client.startTurn();

            // Some debug information
            System.out.println(listColors.size());

            // Play back colors list
            for(Color color : listColors){
                client.chooseColor(color);
            }

            // If we're done, endTurn() will return true.
            done = client.endTurn();
        }

        String pwd = client.winGame();
        System.out.println(pwd);
    }
}

Compiling the code:

javac -cp .;./thrift.jar;./slf4j.jar;./gen-java simonsays.java

Running the code:

java -cp .;./thrift.jar;./slf4j.jar;./gen-java simonsays

If you did everything correctly, the program should output the numbers 1 to 31 and finally a line like this:

simonsays(8d96b611989c0d38b0c47703a37466c5)

Part 4: Submitting the code

Be sure to replace my email with your own email if you wish to receive credit for the problem.

From the email you provided in registerClient(), send an email to puzzles@facebook.com, with the subject as the line outputted by the program.

If you want, you can also attach your source code, but that’s not needed. We’re done!

Facebook: User Bin Crash

I’ve started doing some of the Facebook engineering puzzles, which are programming challenges that Facebook supposedly uses to recruit people.

This is a little bit similar to Project Euler and various online judges like SPOJ, but it’s somewhat different too.

Instead of submitting solutions in a web form, solutions are sent via email, in the form of an attachment. After several hours, the automated grader would send you back a response: whether it was successful or not, and if it is, how long your program ran.

The Facebook system differs from SPOJ in that results are not available immediately, and also that an incorrect submission would return a generic error message (whether it produced incorrect output, crashed, ran out of time, failed to compile, whatever).

This made it a bit annoying to write solutions as it was difficult to figure out exactly what was wrong with the submission.

The problems are grouped into four groups in order of difficulty: Hors d’oeuvre, Snack, Meal, and Buffet. So far I’ve only solved the Hors d’oeuvre problems and one snack.

User Bin Crash

The problem goes something like this:

You’re on a plane, and somehow you have to dump some cargo or else it will crash. You know how much you need to dump (in pounds), and also an inventory of the items you can dump.

Each item in the inventory has a certain weight, and a certain value. By dumping a combination of the items, you have to dump at minimum the given weight, while minimizing the loss.

You can only dump integral amounts of an item (you can’t dump three quarters of a package), but you’re allowed to dump any amount of the item.

The program you write takes the parameters and outputs the minimum loss (value of items that are dumped).

An example

Suppose that the plane needs to dump 13 pounds. To simplify things, suppose that there are only two types of items we are allowed to dump.

Item A weighs 5 pounds, and costs 14.

Item B weighs 3 pounds, and costs 10.

The optimal solution is to dump two of item A, and one of item B. The cost for this is 2 \cdot 14 + 1 \cdot 10 or 38.

Any other combination either costs more than 38, or does not weigh at least 13 pounds.

A solution using dynamic programming

This problem is a variation of the fairly well known knapsack problem. A dynamic programming solution exists for that, and can be modified to work for this problem.

Dynamic programming is just a way to speed up recursion. So in order to form a dynamic programming algorithm, we should first make a recursive algorithm.

Working backwards, suppose that we have a weight W, and a set of items S = [e_1,e_2, \cdots e_n] such that S is the optimal set for weight W.

Now remove one item from the set:

S' = S - e

This new set S' must be the optimal set for W-w_e (I’m going to use the notation w_e to denote the weight of an item e)

The converse is not necessarily true, however. Just because you have an optimal set for some subproblem, adding any arbitrary element to your set does not make your new set optimal.

But adding an element to an optimal subset may create another optimal subset. This depends on which is smaller- the cost obtained by adding the element, and the cost obtained by not adding the element.

It’s probably better to express this idea recursively:

Hosted by imgur.com

Here F() is a function taking a list of items we can use, L, and the minimum weight, W, and returning the minimum cost. e is an element of L (for convenience, e is always the first element).

Obviously when W \leq 0, we don’t have to dump any more items.

The first path, F(L, W-w_e) + v_e is the path taken when we decide to dump e.

The second path, F(L-e, W) is the path taken when we don’t dump any more of e. In order to avoid recursing indefinitely, once we decide not to dump any more of something we never go back and dump more of it.

The code doesn’t handle all the edge cases. For example if we only have one possible item to dump, we are forced to dump it until the weight is reached; we can’t just decide not to dump any more of it and end up with an empty list.

If we use this code, the program will start unfolding the recursion:

Hosted by imgur.com

Being a recursive function, we can go further:

Hosted by imgur.com

Now having reached the end of the recursion, we can fill up the tree from bottom up:

Hosted by imgur.com

Whenever we reach a node that is the parent of the two nodes, we fill it up with the smaller of the two child nodes.

Now let’s transform this recursive function into a dynamic programming routine.

Instead of a function taking two parameters, we have the intermediate results stored in a two-dimensional array:
Hosted by imgur.com

Here the first row is the optimal solutions for each weight using only A, while the second row is by using A and B.

Filling up the first row is very obvious, as we basically only have one item to choose from:

Hosted by imgur.com

The first few cells of the second row is equally easy:

Hosted by imgur.com

However we now reach a point where it’s uncertain what we should put in the cell with the question mark. If we follow our pattern, it should be 20.

But the cell above it is 14. How can the optimal solution when we’re allowed to use both A and B be 20, if the optimal solution when we’re not allowed to use B is 14?

Instead, the cell should be 14:

Hosted by imgur.com

We continue this to fill up the entire array:

Hosted by imgur.com

The bottom right corner of this array is our answer.

The computational complexity of this algorithm is the size of the array, or O(nW). This complexity is not actually polynomial, but this algorithm is considered to run in pseudo-polynomial time.

This is because as W‘s length increases, the running time increases exponentially. If, in our example, W was actually 13000000 instead of 13, and A weighed 5000000 instead of 5, and B weighed 3000000 instead of 3, this algorithm might run out of space.

There is no real way around this problem. The knapsack problem is NP-complete to solve exactly.

However there’s something we can do about it. We can divide all weights by a common factor, and the result would be the same. In the example we can simply divide 13000000, 5000000, and 3000000 all by a million.

Needless to say, this would fail badly if W had been, for instance, 13000001.

The implementation

With the algorithm, it’s pretty straightforward to implement it.

Here’s my implementation in Java (don’t cheat though):

import java.io.*;
import java.util.*;

public class usrbincrash{
    public static void main(String[] args) throws Exception{

        BufferedReader in = new BufferedReader(
            new FileReader(args[0]));

        // Minimum weight to prevent crash
        int crashw = Integer.parseInt(in.readLine());

        // List containing weights of items
        List<Integer> itemW = new ArrayList<Integer>();

        // List containing values of items
        List<Integer> itemV = new ArrayList<Integer>();

        String parse;
        while( (parse = in.readLine()) != null){
            Scanner scn = new Scanner(parse);
            scn.next();

            itemW.add(scn.nextInt());
            itemV.add(scn.nextInt());
        }

        // Take the GCD's before starting the DP
        int gcd = crashw;
        for(int i : itemW) gcd = gcd(gcd, i);

        // Divide all weights by gcd
        crashw /= gcd;
        for(int i=0; i<itemW.size(); i++)
            itemW.set(i, itemW.get(i)/gcd);

        // Calculate optimal fit using dynamic programming
        int[][] dp = new int[itemW.size()][crashw+1];

        // First row of DP array done separately
        dp[0][0] = 0;
        for(int j=1; j<=crashw; j++){

            int aW = itemW.get(0);
            int aV = itemV.get(0);

            if(aW > j) dp[0][j] = aV;
            else dp[0][j] = aV + dp[0][j-aW];
        }

        // Filling up the rest of the DP array
        for(int i=1; i<dp.length; i++){

            dp[i][0] = 0;
            for(int j=1; j<=crashw; j++){

                int iW = itemW.get(i);
                int iV = itemV.get(i);

                // Cell directly up from current
                int imUp = dp[i-1][j];

                // Cell left of it by iW
                int imLeft = 0;
                if(iW > j) imLeft = iV;
                else imLeft = iV + dp[i][j-iW];

                // Smallest of the two
                dp[i][j] = imUp<imLeft? imUp: imLeft;
            }
        }

        System.out.println(dp[itemW.size()-1][crashw]);
    }

    // GCD using the Euclid algorithm
    static int gcd(int a, int b){
        if(b == 0) return a;
        return gcd(b, a%b);
    }
}

When submitting it, it’s necessary to use the -Xmx1024m option. Otherwise the program will run out of memory and fail. According to the robot, the longest test case took 2911.623 ms to run.

My uncreative and stupid batch file scripting solution

I hate batch files.

I don’t even know why I hate batch files. Maybe because of the awkwardness of the language itself, the difficulty in adding one number to another number.

Or perhaps because everyone writes so called ‘viruses’ with batch files when they’re 12 years old. The ones that randomly open 50 windows and won’t quit.

After some time I’ve come to loathe this icon –

Hosted by imgur.com

So when deploying an application, I feel like, ‘Ant, Maven, Jar, anything. No way I’m using a batch file’.

Except you can’t really send your game to your friend and tell her, ‘So you open command prompt, navigate to my game using cd.., then type this: java -Xmx=256m -cp .;./lib/jogl-251106.jar;./lib/openal_951_c.jar game.Main…’

Nono, that doesn’t work. Instead you defeatedly write up a batch file.

Then today I had an absolutely genius (not) idea. Everyone likes .exe files. What if instead of bat files, I had exe files that did the same thing?

So while normally you would have this code:

@echo off
java -Xmx=256m -cp .;./lib/jogl-251106.jar;./lib/openal_951_c.jar game.Main
pause

I would instead have this code:

int main() {
system("java -Xmx=256m -cp .;./lib/jogl-251106.jar;./lib/openal_951_c.jar game.Main");
system("pause");
return 0;
}

..which does the exact same thing with more syntax.

A ‘solution’

But that’s really tedious and dumb, I said to myself. So instead, I wrote this java program to generate the c code and call GCC to compile it.

Therefore, instead of writing this code:

int main() {
system("java -Xmx=256m -cp .;./lib/jogl-251106.jar;./lib/openal_951_c.jar game.Main");
system("pause");
return 0;
}

.. I would only have to write this code:

java -Xmx=256m -cp .;./lib/jogl-251106.jar;./lib/openal_951_c.jar game.Main
pause

Aha, I’ve come to a full circle. Now I created a mini-language with even less functionality than a batch file, and somehow I’ve convinced myself that this 16kb exe is still better than the 97 byte batch file.

But for some reason it seemed like a good idea at the time.

In other news

It seems like I did fairly well in the Cayley contest this year. I came into group IV, between 136 and 140 points (out of 150). This is the best in my school and second best in Calgary.

I got the second last question wrong, and did not answer the last question.

The CCC results aren’t out yet, and it was around the same time as this contest so they should be out soon now.

The Euclid contest is this wednesday, and the Galois this friday.

I’ve switched from using tabs into spaces. Probably because tabs caused so much problems with Haskell layout. Vim supports soft tabs, so ‘:set ts=4 sts=4 sw=4 et’ and you’re all set to use spaces. ‘:retab’ converts the tabs to spaces, which may be useful.

Project Euler 280 (Revisited)

A while ago I wrote this blog post on this problem. The previous code was able to produce the answer in about 20 minutes, using several gigabytes of RAM.

You may want to read the previous blog post first.

There is a simpler and more efficient solution (used by inamori, zwuupeape, and many others).

The new approach

We do not need to know the exact value of the solution, only an approximate. This approximation has to be accurate only to six digits.

Any any step, there is a certain probability that the ant will reach the final state in that step.

Let’s call this function P(s): the probability that the ant will reach the final state on step s:

Hosted by imgur.com

At very small values of s, the probability is zero because it takes a certain number of steps to get to the final position. 44 is the smallest number of steps to get from the initial to the final position, and the probability increases from there.

But it only increases until a certain point. After that point, the probability decreases. After all, if we run this for thousands of steps, how likely is the ant to still not have reached the final position?

However, the graph continues forever to the right. Even after thousands of steps, there is still a chance, however small, that the final position hasn’t been reached.

Let’s define Q(s) as the weighted average of the probabilities of each value of P(s) from 0 to s:

Hosted by imgur.com

The expected value and the answer for this problem would simply be the weighted average for the entire graph.

Since s must be an integer greater than zero, we don’t have to do any integration with curves. A bit misleading because I’ve drawn P(s) and Q(s) as curves, when they are not.

But because Q(s) cannot be expressed algebraically, we cannot evaluate it as it approaches infinity. Instead, we pick a point that gives us enough precision:

Hosted by imgur.com

Either that, or we keep calculating the weighted average while increasing s until we have enough precision.

Calculating the probabilities

In order to calculate a weighted average Q(s), we need to be able to calculate P(s); while P(s) is the probability function for the final state, we’ll need to know the probabilities for the in-between states as well.

The probabilities of the states on step s depend most upon the probabilities of the previous step, s-1.

Hosted by imgur.com

So if on step s-1 there’s a 0.6 probability that we’re on state X, then on step s we should have a 0.3 probability of being on either Y or Z as there’s an equal chance of moving to either state.

And if multiple states can go to our state, we can get the probability by adding up the probabilities:

Hosted by imgur.com

Coding a solution

At first we start on the initial state, with a probability of 1 (certain chance) of being on it.

On each step we generate a new set of probabilities using rules I described above, and so on.

A lot of code is stolen from my previous work on this problem. The State class is essentially unchanged in this version.

Here’s the code:

import java.util.*;

public class Main{

	public static void main(String[] args){

		final int ITERATIONS = 2501;

		// Initialize probability map.
		// The initial step is 0, containing the initial position with a probability of 1.
		Map<State,Double> prevProbs = new LinkedHashMap<State,Double>();
		prevProbs.put(State.INIT_STATE, 1.0);

		// Distributions for the final state.
		double[] finalValues = new double[ITERATIONS+1];
		Arrays.fill(finalValues, 0);

		// Keep the time.
		long startTime = System.currentTimeMillis();

		// Loop counter is actually the step number of the next step.
		for(int step=1; step<ITERATIONS; step++){

			// Make new probabilities.
			Map<State,Double> nextProbs = new LinkedHashMap<State,Double>();

			// Loop through old probabilities and add
			Set<State> stateSet = prevProbs.keySet();

			for(State state : stateSet){

				// Probability of being on this state right now
				double stateProb = prevProbs.get(state);

				// List of next states
				List<State> nextStates = nextStates(state);

				// Probability factor for each of the next states
				double multiplier = 1.0 / nextStates.size();

				// Added value to each of the next states
				double added = stateProb * multiplier;

				// Now go and update all the state probabilities.
				for(State nextState : nextStates){

					// If we've got the final state, handle it separately.
					if(nextState.equals(State.FINAL_STATE)){
						finalValues[step] += added;
						continue;
					}

					// Could be the first time.
					if(!nextProbs.containsKey(nextState))
						nextProbs.put(nextState, added);

					// Might not be the first time.
					else {
						// Old value, we need to add to it instead of replacing it.
						double previous = nextProbs.get(nextState);
						nextProbs.put(nextState, previous + added);
					}
				}
			}

			// Our new probabilities are the old probabilities for the next loop.
			prevProbs = nextProbs;

			System.out.println(step + " " + weightedAverage(finalValues));
		}

		System.out.println((System.currentTimeMillis() - startTime) + "ms");
	}

	// Calculates a weighted average of a double array with the indices as
	// values and the values in the array as weights.
	static double weightedAverage(double[] array){

		double sumValues = 0;
		for(int i=0; i<array.length; i++)
			sumValues += i * array[i];

		return sumValues;
	}

	// Returns a list of possible continuation states from the current one.
	static List<State> nextStates(State state){

		// Current and changing position of the ant
		int antX = state.ant % 5;
		int antY = state.ant / 5;

		// Whether it can go into each of the four directions (N,S,E,W respectively).
		boolean[] possibleDirs = new boolean[4];
		Arrays.fill(possibleDirs, true);

		// Take out some directions if it's in the corner.
		if(antY == 0) possibleDirs[0] = false; // Can't go north
		if(antY == 4) possibleDirs[1] = false; // Can't go south
		if(antX == 4) possibleDirs[2] = false; // Can't go east
		if(antX == 0) possibleDirs[3] = false; // Can't go west

		// Construct a list of continuations.
		List<State> nextStates = new ArrayList<State>();

		// Loop through the four directions.
		for(int i=0; i<4; i++){

			// Cannot go this direction.
			if( !(possibleDirs[i])) continue;

			int newAntX = antX;
			int newAntY = antY;

			// Modify direction.
			switch(i){
				case 0: newAntY--; break;
				case 1: newAntY++; break;
				case 2: newAntX++; break;
				case 3: newAntX--; break;
			}

			// Start constructing new state object.
			int oldAnt = state.ant; // old ant position
			int newAnt = 5*newAntY + newAntX;
			int[] board = state.board.clone();
			boolean carrying = state.carrying;

			// Carrying a seed. Notice that a square can contain
			// two seeds at once (but not more); seeds are indistinguishable
			// so we just need to keep track of the number of seeds
			// on each square.
			if(carrying){
				board[oldAnt] --;
				board[newAnt] ++;
			}

			// Drop off the seed.
			if(newAntY == 0 && board[newAnt] == 1 && carrying)
				carrying = false;

			// Pick up a new seed.
			if(newAntY == 4 && board[newAnt] == 1 && !carrying)
				carrying = true;

			// Treat the five done positions the same.
			if(donePosition(board))
				nextStates.add(State.FINAL_STATE);

			// Add it normally.
			else nextStates.add(new State(board, newAnt, carrying));
		}

		return nextStates;
	}

	// Is the board in the done position?
	static boolean donePosition(int[] b){
		return b[0]==1 && b[1]==1 && b[2]==1 && b[3]==1 && b[4]==1;
	}
}

class State{

	static final State INIT_STATE = new State(
	new int[]{
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		1,1,1,1,1
	}, 12, false);

	// Consider all final states the same; there is
	// no ant position.
	static final State FINAL_STATE = new State(
	new int[]{
		1,1,1,1,1,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0
	}, -1, true);

	// 25 board.
	int[] board;

	int ant;
	boolean carrying;

	State(int[] board, int ant, boolean carrying){
		this.board = board;
		this.ant = ant;
		this.carrying = carrying;
	}

	State(State s){
		this(s.board, s.ant, s.carrying);
	}

	public boolean equals(Object o){
		State s = (State) o;
		return Arrays.equals(s.board, board) && s.ant == ant && s.carrying == carrying;
	}

	public int hashCode(){
		return Arrays.hashCode(board) + ant;
	}

	// For debugging mostly.
	public String toString(){
		StringBuilder ret = new StringBuilder("\n");
		for(int i=0; i<5; i++){
			for(int j=0; j<5; j++){
				int pos = 5*i + j;
				if(ant == pos) ret.append("#");
				else ret.append(board[pos] >= 1? "+" : "-");
			}
			ret.append("\n");
		}
		return ret.toString();
	}
}

As we run this program, the answer becomes more and more accurate. We only need 2300 or 2500 steps to get the six digits of accuracy we need.

Running the program:

Hosted by imgur.com

This takes just over a minute to run — not bad at all.

Project Euler 280

Project Euler 280 is an interesting problem involving probability and combinatorics:

There is a 5×5 grid. An ant starts in the center square of the grid and walks randomly. Each step, the ant moves to an adjacent square (but not off the grid).

In each of the five bottom-most squares, there is a seed. When the ant reaches such a square, he picks up the seed (if he isn’t already carrying one).

When the ant reaches a square in the top-most row while carrying a seed, he drops off the seed (if there isn’t already a seed there).

This ‘game’ ends when all five seeds are in the five squares of the top-most row.

The problem asks for the expected (average) number of turns it would take to get from the initial to the ending position. It requires six digits of precision.

The Monto Carlo Approach

Perhaps the easiest way to tackle this problem is with a Monto Carlo simulation. This uses a computer to actually run the game many times, using random number generators.

This is my straight-forward Monto Carlo implementation in Java:

import java.util.*;

public class Main{
	public static void main(String[] args){
		Random r = new Random();
		int stepsum = 0;
		int tries = 0;
		while(true){
			stepsum += new Simulation(r).simulate();
			tries ++;
			System.out.println((double) stepsum / (double) tries);
		}
	}
}

class Simulation{

	static final int[] init = {
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		1,1,1,1,1
	};
	State state;
	Random rand;
	int steps;

	Simulation(Random rand){
		state = new State(init, 12, false);
		this.rand = rand;
		steps = 0;
	}

	int simulate(){
		while(!done())
			step();
		return steps;
	}

	boolean done(){
		int[] b = state.board;
		return b[0]==1 && b[1]==1 && b[2]==1 && b[3]==1 && b[4]==1;
	}

	boolean step(){
		steps ++;

		int antX = state.ant % 5;
		int antY = state.ant / 5;
		int dir;

		while(true){
			// 0:N 1:S 2:E 3:W
			dir = rand.nextInt(4);
			if(antY==0 && dir==0) continue;
			if(antY==4 && dir==1) continue;
			if(antX==4 && dir==2) continue;
			if(antX==0 && dir==3) continue;
			break;
		}

		switch(dir){
			case 0: antY--; break;
			case 1: antY++; break;
			case 2: antX++; break;
			case 3: antX--; break;
		}

		int oldAnt = state.ant;
		state.ant = 5*antY + antX;

		if(state.carrying){
			state.board[oldAnt]--;
			state.board[state.ant]++;
		}

		if(antY == 0 && state.board[state.ant] == 1 && state.carrying){
			// drop off
			state.carrying = false;
		}

		if(antY == 4 && state.board[state.ant] == 1 && !state.carrying){
			// pick up
			state.carrying = true;
		}

		return true;
	}
}

class State{
	// 25 board.
	int[] board;

	int ant;
	boolean carrying;

	State(int[] board, int ant, boolean carrying){
		this.board = board.clone();
		this.ant = ant;
		this.carrying = carrying;
	}

	State(State s){
		this(s.board, s.ant, s.carrying);
	}

	public boolean equals(Object o){
		State s = (State) o;
		return Arrays.equals(s.board, board) && s.ant == ant;
	}

	public int hashCode(){
		return Arrays.hashCode(board) + ant;
	}
}

Running this program will produce something close to the final result. But this will not nearly be accurate enough to actually solve the problem: running this for a few hours would only produce two or three digits of precision, while six is required.

It’s not exactly impossible, as on the forums Rodinio claims to have run a similar Monto Carlo simulation on a computer cluster, giving enough precision to start making guesses for the last digits. To get so many digits on a Monto Carlo simulation requires an astronomical amount of tries.

Obviously this is not the most efficient approach.

Introducing the Markov Chain

A more efficient solution can be implemented using Markov Chains.

A Markov Chain solves the problem of discrete random processes. What is a Markov Chain, and how is it used?

Let’s say we have a finite group of states, S = \{ s_1, s_2, \cdots , s_n \}. Make a matrix M, of size n * n.

On each step (or move) of the process, the probability of going from state s_i to s_j is M_{ij}.

The process starts on an initial state. From each state there is a certain probability of going to every other state.

Notice that in a Markov Chain, what happens next does not depend on what has happened before. The only data is the current state you’re on.

I’ll explain all this with a very simple example:

On a 1×3 game board, Bob (the happy face) starts at square 1. Each step, he randomly moves to an adjacent square with equal probability. The game ends when he reaches square 3.

Of course the only time he has a ‘choice’ in which square to move to is when he’s on square 2 (half-half chance of moving to 1 and 3). If he’s already on square 1, he has a 100% chance of moving to square 2, and if he’s on square 3, well, the game is over.

We can represent this game like this:

Another way of showing the above would be something like this:

This is the matrix, of course:

\left[ \begin{array}{ccc} 0 & 1 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 1 \end{array} \right]

This type of matrix is called a Stochastic matrix. What’s special about this matrix is that each row of the matrix adds up to 1.

A state that can only return to itself is called an absorbing state. If in the matrix, M_{ii} = 1 for any value of i, then state i is an absorbing state.

Here, state 3 is an absorbing state.

The next step is very important: determining the time until absorption.

From our matrix, take out all of the absorbing rows, and all of the left columns to make it a square matrix:

It seems that by doing this we are losing information. But we’re actually not. We are treating each absorbing state as the same; and since each row originally added up to 1, the probability of going to the absorbing state is simply 1 minus the sum of the rest of the row.

This form is considered the canonical form of the stochastic matrix. Our matrix in canonical form looks like this:

\left[ \begin{array}{cc} 0 & 1 \\ \frac{1}{2} & 0 \end{array} \right]

Next we subtract it from the identity matrix.

\left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right] - \left[ \begin{array}{cc} 0 & 1 \\ \frac{1}{2} & 0 \end{array} \right] = \left[ \begin{array}{cc} 1 & -1 \\ -\frac{1}{2} & 1 \end{array} \right]

Next we invert this matrix and get:

\left[ \begin{array}{cc} 1 & -1 \\ -\frac{1}{2} & 1 \end{array} \right]^{-1} = \left[ \begin{array}{cc} 2 & 2 \\ 1 & 2 \end{array} \right]

The expected absorption time from state s_n is simply the sum of row n in the above matrix.

So because we started on state 1, the expected length of the game is 2+2 or 4.

All of this seems like magic, because I haven’t given any proof for this. If you really want to prove that this method works, you can get a textbook about Markov chains.

“Markov Chains” by J.R.Norris (Cambridge 1997) is a decent textbook if you want to know more about this. I would recommend this as a less dense introduction to Markov chains.

An attempt using Markov Chains

Now that we know some basics of Markov chains, we need to apply it to solve the problem.

If you attach a Set or something to the Monto Carlo simulation program, you would find that there are 10270 distinct states for this problem. If we count the five final states as the same state, then we have 10266 states.

This is exactly the same as what we’ve just done. Except instead of a 3*3 matrices, we’re now working with matrices with tens of thousands of rows and columns. Woo hoo.

You can probably see here that this is going to be a problem. A 10265*10265 (final state not counted) matrix contains over 100 million elements. Most of these elements will be zero. If we store all of this data in double types, that’s 800mb of memory used, just for the matrix.

It’s easy to underestimate the size of this problem. But there’s a few optimizations we can make.

We could save some time and space by subtracting from the identity matrix at the same time as filling up the matrix.

Inverting a 10265*10265 matrix is no small task either. Instead there’s a simple optimization to avoid inverting such a huge matrix:

Remember that we want to find the inverse of the matrix, and get the sum of all the elements in the first row. Let M be our matrix and M' be the inverse.

What’s important here is that finding the sum of all the rows of a matrix is the same as multiplying by a column of ones. This produces a one-columned matrix, each cell representing the sum of the corresponding row.

If C is the column of ones, and S is the sum matrix (what we want), then M' * C = S. We can also write that as M * S = C.

See, this way we don’t have to compute the inverse. We just have to solve the above equation for S.

To avoid implementing the standard matrix solve function, I’ll be using the JAMA library for matrix manipulation.

Finally, the source code for my implementation of what I just discussed:

import java.util.*;
import Jama.*;

public class Main{

	// For a state, maps to all possible states from it.
	// All next-states have the same probability.
	static Map<State,List<State>> states = new LinkedHashMap<State,List<State>>();

	public static void main(String[] args){

		// Keep the time.
		long startTime = System.currentTimeMillis();

		// Initialize the state map.
		addAllStates(State.INIT_STATE);

		// To construct the matrix, we need to map all the states to a position
		// in the matrix (an integer). Because our map is already ordered, we
		// use its position in the map as the position in the matrix. In order
		// to avoid doing a linear search through the keyset to find its position,
		// we cache its position in a map.

		Set<State> keySet = states.keySet();
		Map<State,Integer> positionMap = new HashMap<State,Integer>();

		// Set up position map.
		Iterator<State> iterator = keySet.iterator();
		int pos = 0;
		while(iterator.hasNext()){
			positionMap.put(iterator.next(), pos);
			pos++;
		}

		// Finally we can begin constructing our matrix.
		// This takes up about 900mb of memory.
		double[][] matrix = new double[states.size()][states.size()];

		// Fill up the matrix.
		Collection<List<State>> values = states.values();
		Iterator<List<State>> rowIterator = values.iterator();

		for(int row=0; row<matrix.length; row++){

			// Fill up one row.
			List<State> thisRow = rowIterator.next();

			// What to fill with?
			double fill = 1.0 / thisRow.size();

			// An optimization: why not do the subtraction step here
			// instead of subtracting from identity matrix?
			matrix[row][row] = 1;

			for(State st : thisRow){
				// The final state doesn't count.
				if(st.equals(State.FINAL_STATE)) continue;

				int col = positionMap.get(st);
				matrix[row][col] = -fill;
			}
		}

		// Finishing up.
		Matrix bigMatrix = new Matrix(matrix);
		Matrix onesColumn = new Matrix(states.size(), 1, 1);
		Matrix sums = bigMatrix.solve(onesColumn);

		System.out.println(sums.get(0,0));
		System.out.println(System.currentTimeMillis() - startTime + "ms");

	}

	// Returns a list of possible continuation states from the current one.
	static List<State> nextStates(State state){

		// Current and changing position of the ant
		int antX = state.ant % 5;
		int antY = state.ant / 5;

		// Whether it can go into each of the four directions (N,S,E,W respectively).
		boolean[] possibleDirs = new boolean[4];
		Arrays.fill(possibleDirs, true);

		// Take out some directions if it's in the corner.
		if(antY == 0) possibleDirs[0] = false; // Can't go north
		if(antY == 4) possibleDirs[1] = false; // Can't go south
		if(antX == 4) possibleDirs[2] = false; // Can't go east
		if(antX == 0) possibleDirs[3] = false; // Can't go west

		// Construct a list of continuations.
		List<State> nextStates = new ArrayList<State>();

		// Loop through the four directions.
		for(int i=0; i<4; i++){

			// Cannot go this direction.
			if( !(possibleDirs[i])) continue;

			int newAntX = antX;
			int newAntY = antY;

			// Modify direction.
			switch(i){
				case 0: newAntY--; break;
				case 1: newAntY++; break;
				case 2: newAntX++; break;
				case 3: newAntX--; break;
			}

			// Start constructing new state object.
			int oldAnt = state.ant; // old ant position
			int newAnt = 5*newAntY + newAntX;
			int[] board = state.board.clone();
			boolean carrying = state.carrying;

			// Carrying a seed. Notice that a square can contain
			// two seeds at once (but not more); seeds are indistinguishable
			// so we just need to keep track of the number of seeds
			// on each square.
			if(carrying){
				board[oldAnt] --;
				board[newAnt] ++;
			}

			// Drop off the seed.
			if(newAntY == 0 && board[newAnt] == 1 && carrying)
				carrying = false;

			// Pick up a new seed.
			if(newAntY == 4 && board[newAnt] == 1 && !carrying)
				carrying = true;

			// Treat the five done positions the same.
			if(donePosition(board))
				nextStates.add(State.FINAL_STATE);

			// Add it normally.
			else nextStates.add(new State(board, newAnt, carrying));

		}

		return nextStates;
	}

	// Recursively add all continuation states.
	static void addAllStates(State state){

		// Don't add if it's already added.
		if(states.containsKey(state)) return;

		List<State> nexts = nextStates(state);
		states.put(state, nexts);

		// Recurse (but not if we've reached the final state).
		for(State next : nexts)
			if( !(next.equals(State.FINAL_STATE)))
				addAllStates(next);

	}

	// Is the board in the done position?
	static boolean donePosition(int[] b){
		return b[0]==1 && b[1]==1 && b[2]==1 && b[3]==1 && b[4]==1;
	}
}

class State{

	static final State INIT_STATE = new State(
	new int[]{
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		1,1,1,1,1
	}, 12, false);

	// Consider all final states the same; there is
	// no ant position.
	static final State FINAL_STATE = new State(
	new int[]{
		1,1,1,1,1,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0
	}, -1, true);

	// 25 board.
	int[] board;

	int ant;
	boolean carrying;

	State(int[] board, int ant, boolean carrying){
		this.board = board;
		this.ant = ant;
		this.carrying = carrying;
	}

	State(State s){
		this(s.board, s.ant, s.carrying);
	}

	public boolean equals(Object o){
		State s = (State) o;
		return Arrays.equals(s.board, board) && s.ant == ant && s.carrying == carrying;
	}

	public int hashCode(){
		return Arrays.hashCode(board) + ant;
	}

	// For debugging mostly.
	public String toString(){
		StringBuilder ret = new StringBuilder("\n");
		for(int i=0; i<5; i++){
			for(int j=0; j<5; j++){
				int pos = 5*i + j;
				if(ant == pos) ret.append("#");
				else ret.append(board[pos] >= 1? "+" : "-");
			}
			ret.append("\n");
		}
		return ret.toString();
	}
}

Running it:

So my program takes about 19 minutes to run, using up over 2GB of ram. The construction of the matrix only takes about 2 seconds, and the rest of the time is used on solving the huge matrix.

JAMA is probably not the fastest matrix library; the running time might be cut down a bit if we use libraries designed for sparse matrices.

But to get this to run in under a minute, a completely different approach would be needed. For now, though, I’m pretty happy with getting it in 19 minutes.

An attempt at IBM’s Ponder This (Feb 2010)

Ponder this is a collection of puzzles, with a new puzzle released every month. This month’s puzzle is supposedly a famous chess problem.

The site seems to be down right now. It may or may not be back up in the future, but if it isn’t, I think Google has it cached.

The problem is something like this:

White starts a chess game with 1. e4 . On the fifth move (10th ply), black’s knight captures white’s rook and delivers checkmate. Find the missing moves.

To clarify, the game goes something like this:

1. e4 ..
2. .. ..
3. .. ..
4. .. ..
5. .. NxR#

My attempt

I thought this problem as a problem for computers instead of for humans. So the problem now is to write a computer program to generate the solution (or a list of solutions). I used Java for the programming language.

Instead of implementing all the chess rules from scratch, I used Chesspresso as the chess library. It was obviously designed with efficiency in mind. And it’s written in pure Java.

Here are some basics on how Chesspresso is structured:

  • The two most important classes are Position and Move. The Game class is also fairly important, but I’m not using it here.
  • The Position class contains data about a particular board state. This includes where all the pieces are, and whose turn is it, and a few other things.
  • The Move class describes a single move. It contains data about its starting square, its destination square, which piece is moving, and some other things, but not much else. It’s very compact, and is normally used as a short instead of a class.
  • You really can’t do that much with a Move without its associated Position. After all, it fits in a short. A short in Java is only 16 bits, by the way.
  • Position objects are mutable. Even though the ImmutablePosition class exists, methods generally change existing Position objects instead of returning new ones. This is different from say, String or BigInteger.

The biggest problem I found with this library is that its documentation is fairly lacking. Although there are some javadocs for individual classes and methods, there is no manual on how the library is supposed to work on a large scale.

Fortunately there were a few examples, in the form of programs using the library.

While it was difficult to figure out how to do simple stuff (like creating a Move from a short), there are already functions that do more advanced things, like generating all possible moves from a given position.

So after playing a bit with my code, I came up with this:

import chesspresso.Chess;
import chesspresso.position.Position;
import chesspresso.move.Move;
import chesspresso.move.IllegalMoveException;

public class Main{

	static Position position;
	static String[] game;
	
	static final int MAX_PLY = 9;

	// Don't bother handling exceptions.
	public static void main(String[] args) throws Exception{
		// The initial position.
		position = Position.createInitialPosition();

		// Array of moves.
		game = new String[MAX_PLY + 1];

		// First move: e4.
		// Boolean input (third parameter) describes whether it's a capture.
		short firstmove = Move.getRegularMove(Chess.E2, Chess.E4, false);

		// Alter the position by making this move.
		position.doMove(firstmove);

		recurse();
	}

	// All the data is mutable and therefore is stored globally.
	// Calling this method should not change the state of the position
	// since any changes are eventually undone.
	static void recurse() throws IllegalMoveException {
		int ply = position.getPlyNumber();
		Move lastMove = position.getLastMove();

		// Record move.
		game[ply-1] = lastMove.getSAN();

		if(ply > MAX_PLY){

			// Check if we've found a position where a black knight captures
			// a white rook with checkmate on the fifth move.
			if(position.isMate() && lastMove.isCapturing()
				&& lastMove.getMovingPiece() == Chess.KNIGHT
				&& position.getPiece(lastMove.getToSqi()) == Chess.ROOK){

				// We found it, now print the sequence of moves.
				for(int i=0; i<ply; i++)
					System.out.println(game[i]);
				System.out.println();
			}
			return;
		}

		// Recurse all the possible next positions.
		short[] nextMoves = position.getAllMoves();

		for(short thisMove : nextMoves){
			// Make the move, recurse, and undo the move.
			position.doMove(thisMove);
			recurse();
			position.undoMove();
		}
	}
}

If you want to run this, save the code as Main.java. You’ll need the Chesspresso jar file (can be downloaded), I’ll call it chesspresso.jar. The following commands compiles and runs it:

javac -cp .;chesspresso.jar Main.java
java -cp .;chesspresso.jar Main

The code should work.

There is, however, one small problem. I somewhat underestimated the size and computational complexity of the calculation.

The number of chess positions grows very quickly. Because there are nine unknown moves, and using an estimate of 20 possible moves from every position, we would have 20^9 \approx 512,000,000,000 games by the end of the ninth half-move.

I can evaluate about 100,000 positions every second with my average computer, so that many positions would take me about 1422 hours, or around 2 months.

Of course if I really wanted to calculate this, I could run it on a supercomputer, or distribute the task across many computers, or more likely, make the program save its state and run it over a couple of months. It’s definitely feasible, but pointless since the solution is already available on the internet.

Apparently someone has already done this (see the last response).

So even though my program wasn’t able to solve the problem, I think I still learned something in the attempt.

Today’s CCC

So today I wrote the Canadian Computing Competition today. I wrote the Junior division paper.

So this is a 3 hour programming contest, with 5 programming problems. A program reads input from the keyboard and outputs to the screen.

How this was set up was contestants were allowed to bring a USB with whatever we wanted on it. We used the school’s laptops. So I took Vim, Java, and some other stuff.

Vim really failed on me today. Randomly, my keyboard would switch to a French keyboard mapping or something (and wrong symbols appeared). Restarting Vim would correct this problem. Not knowing how to fix this, I had to restart Vim about 7-8 times. This was very frustrating under the contest situation.

I’m not going to type up the problems here, so if you haven’t written the CCC today, this blog post would make little sense. Well, until the problems are posted.

I think the problems themselves were pretty easy. This year problem 5 wasn’t particularly challenging. I finished all five questions in about an hour, and spent the next two hours doing completely unnecessary optimizations and the like. I scored 67 out of 75.

For the second problem, I had a spelling mistake (“Bryon” instead of “Byron”) and that cost me two points.

I somehow lost 6 points too for the fourth problem. I <think> it’s because I mishandled the one weird edge case where n=1, but I’m not really sure. I guess I’ll know when the test data comes out.

My solutions are available if anyone is interested.