Update: The contest is over, I finished 36th out of 708. That isn’t too bad, I suppose, but it’s not great either. I guess I can be happy about finishing in the top 50, and easily in the top 10%.

The University of Waterloo (in Canada) along with Google representatives is hosting a Tron A.I. programming contest. (Finals Tournament is on Feb. 26th, 2010). Having not participated in any programming contests since high school, I have decided to compete in this just to see how well I stack up. The basis behind this challenge is to create a Tron AI which will compete with other people’s submissions, so it becomes your program vs. every body else. The current rankings can be seen here, while my own personal page can be seen here. Bots are welcome to be programmed in a variety of languages, including C++, Java, Python, C#, Haskell, Go, Javascript, Perl, and others, however it’s been noted that the JVM the contest organizers are using is extremely slow, which is devastating when your bot is allowed only 1 second to move. So don’t make the same mistake I did, and use something other than Java.

You should learn from my mistake and not keep all of your source code stored on a personal server that doesn’t have some sort of X server installed. This is the first (and hopefully only) time in my life where I program an entire project using the nano text editor, rather than something sane like JCreator, Eclipse, or Visual Studio. I’ll admit the syntax coloring looks nice at first, but in reality, I like having line numbers. I mean, I really like having line numbers. And the ability to use my mouse. And not having to ssh into my server whenever I want to edit code. So from now on, I vow to only use real IDE’s. No more of this retro 70’s GNU ASCII text editor stuff.

It looks pretty, and seemed like a good idea at the time

Mmmk, here is the source code for my Java Bot (which sucks compared to my C++ bot, but was (and still can be) a most worthwhile learning experience.

First up is the Bug class, which, as the name implies, is used for debugging. Turning it on causes the S.O.P.’s to print to the console, turning it off causes the bot to be silent. Usage is just as a static function call would be, so Bug.ol(“blah blah”);

public class Bug
{
	private Bug(){} // no instantiating
	public static final boolean on = true;
	public static void ol(String str)
	{
		if(on)
			System.err.println(str);
	}
	public static void o(String str)
	{
		if(on)
			System.err.print(str);
	}
}

Next up is the Point class, which holds some additional information other than just X and Y coordinates. It also provides the manhattan distance between itself and another Point object, as well as returns an array of Points which are adjacent to that point, as well as returns the specific point one space away from a given direction

enum DIR { NORTH, SOUTH, EAST, WEST };

public class Point
{
	private int mX;
	private int mY;

	public Point(int x, int y)
	{
		mX = x;
		mY = y;
	}

	public Point(Point p)
	{
		mX = p.mX;
		mY = p.mY;
	}
	public int X() { return mX; }
	public int Y() { return mY; }
	public void setX(int x) { mX = x; }
	public void setY(int y) { mY = y; }

	public Point[] adjPointsToMe()
	{
		Point[] adjPs = new Point[4];
		int i = 0;
		for(DIR dir : DIR.values())
		{
			adjPs[i] = getAdjPoint(dir);
			i++;
		}
		return adjPs;
	}

	public Point getAdjPoint(DIR dir)
	{
		int x = mX;
		int y = mY;
		switch(dir)
		{
			case NORTH:
				return new Point(x,y-1);
			case SOUTH:
				return new Point(x,y+1);
			case EAST:
				return new Point(x+1,y);
			case WEST:
				return new Point(x-1,y);
			default:
				return null;
		}
	}

	public int manhattanDist(Point b)
	{
		return Math.abs(mX - b.mX) + Math.abs(mY - b.mY);
	}

	public boolean isNorthOf(Point b)
	{
		return ( this.mY < b.mY);
	}

	public boolean isSouthOf(Point b)
	{
		return ( this.mY > b.mY );
	}

	public boolean isEastOf(Point b)
	{
		return ( this.mX < b.mX);
	}

	public boolean isWestOf(Point b)
	{
		return ( this.mX > b.mX);
	}

	@Override
	public int hashCode()
	{
		final int prime = 31;
		int result = 1;
		result = prime * result + mX;
		result = prime * result + mY;
		return result;
	}

	@Override
	public boolean equals(Object obj)
	{
		if(obj == null)
			return false;
		if(this == obj)
			return true;
		if(getClass() != obj.getClass())
			return false;
		Point other = (Point)obj;
		if(mX != other.mX)
			return false;
		if(mY != other.mY)
			return false;
		return true;
	}

	public String toString()
	{
		return "[" + mX + "][" + mY + "]";
	}
}

Here we have the Move class, which is basically a Point but with a value member variable. What does that value represent? Good question, actually, because I abuse this class in a number of places, using it to represent for different kinds of values. At one point I tried to implement A* and there was a whole other Node class, but, that failed when I gave up on the implementation.

import java.util.PriorityQueue;
//import java.util.Comparable;

public class Move implements Comparable<Move>
{
	private Point myPoint;
	private int myVal;

	public Move(Point p)
	{
		myPoint = p;
		myVal = 0;
	}
	public Move(Point p, int v)
	{
		myPoint = p;
		myVal = v;
	}

	public Point getPoint()
	{ return myPoint; }

	public PriorityQueue<Move> getAdjMoves()
	{
		PriorityQueue<Move> pq = new PriorityQueue<Move>();
		Point[] possPoints = myPoint.adjPointsToMe();
		Map map = new Map();
		for(int i=0; i < possPoints.length; i++)
		{
			Move temp = new Move(possPoints[i]);
			if(map.isValid(possPoints[i]))
				temp.myVal = -1000; // die
			else
			{
				// if enemy could move there, temp.myVal -= 50
				if(map.canEnemyMoveTo(temp.myPoint))
					temp.myVal = -500;
				 temp.myVal += map.openPtsFrom(new Point(possPoints[i].X(),possPoints[i].Y()));
			}
			pq.offer(temp);
		}
		return pq;
	}

	public int compareTo(Move other)
	{
		//Bug.ol("Move CompareTo called");
		if(myVal < other.myVal)
			return 1;
		else if(myVal > other.myVal)
			return -1;
		else
			return 0;
	}

	public void setValue(int i)
	{
		myVal = i;
	}

	public int getValue()
	{
		 return myVal;
	}

	@Override
	public int hashCode()
	{
		final int prime = 37;
		int result = myPoint.hashCode()*prime;
		result = myVal * prime * result;
		return result;
	}
	@Override
	public boolean equals(Object obj)
	{
		if(obj == null)
			return false;
		if(this == obj)
			return true;
		if(getClass() != obj.getClass())
			return false;
		Move other = (Move)obj;
		if(myVal != other.myVal)
			return false;
		if(! myPoint.equals(other.myPoint) )
			return false;
		return true;
	}

	@Override
	public String toString()
	{
		String t = myPoint.toString();
		t+= ": " + myVal;
		return t;
	}
}

Ah, the heart and soul of my Java Bot, the Map class. This isn't the same map class that is provided with the starter kit. I renamed that to Tron.java so I could use the name "Map". Everything here was designed and coded by yours truly, and it does a fairly good job if I may say so myself. Unfortunately, I failed at implementing A*, and so this relies somewhat on a very ghetto best - first algorithm for moving towards the opponent. That is why this is not a high ranking bot. It needs a better path finding algorithm. The flood fill algorithm on the other hand is top notch. Ish.

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.lang.StringBuilder;
import java.util.LinkedList;
import java.util.ArrayList;

public class Map
{
	private Point me;
	private Point op;
	private char[][] walls;
	private int width;
	private int height;

	public Map()
	{// init to default values
		walls = Tron.getCharMap();
		me = new Point(Tron.MyX(),Tron.MyY());
		op = new Point(Tron.OpponentX(),Tron.OpponentY());
		width = Tron.Width();
		height = Tron.Height();

	}

	public Point getMe() { return me; }
	public Point getOp() { return op; }

	public Map(char[][] w, Point m, Point o)
	{
		height = w.length;
		width = w[0].length;
		me = m;
		op = o;
		// deep copy
		walls = new char[width][height];
		for(int r = 0; r < height; r++ )
			for(int c = 0; c < width; c++)
				walls[r][c] = w[r][c];
	}

	public boolean isClosedOff()
	{
		boolean ret = !openAtoB(me,op);
		Bug.ol("me: " + me + " , op: " + op + "  isClosedOff: " + ret);
		return ret;
	}

	public boolean canEnemyMoveTo(Point p)
	{
		Point[] possEnemyMoves = op.adjPointsToMe();
		Point[] possPMoves = p.adjPointsToMe();
		for(Point a : possEnemyMoves)
		{
			for(Point b : possPMoves)
			{
				if(a.equals(b))
					return true;
			}
		}
		return false;
	}
	public boolean openAtoB(Point a, Point b)
	{
		//Bug.o("Checking open from: " + a + " to: " + b );
		Queue<Point> openQueue = new LinkedList<Point>();
		Set<Point> closedQueue = new HashSet<Point>(); // no doubles!
		openQueue.offer(a);
		while(!openQueue.isEmpty())
		{
			//Bug.ol("here");
			Point p = openQueue.remove();
			//Bug.ol("comparing: " + p + " to " + b );
			closedQueue.add(p);
			if(nextToEachOther(p,b))
			{
				//Bug.ol(":  true");
				return true;
			}
			for(Point adjPoint : adjFreePointsTo(p))
			{
				if(!(openQueue.contains(adjPoint) || closedQueue.contains(adjPoint)))
					openQueue.offer(adjPoint);
			}
		}
		//Bug.ol(":  false");
		return false;
	}

	public int openPtsFrom(Point start)
	{
		int count = 0;
		Queue<Point> openQueue = new LinkedList<Point>();
		Set<Point> closedQueue = new HashSet<Point>();
		openQueue.offer(start);
		while(!openQueue.isEmpty())
		{
			Point p = openQueue.remove();
			closedQueue.add(p);
			count++;
			for(Point adjPoint : adjFreePointsTo(p))
				if(!(openQueue.contains(adjPoint) || closedQueue.contains(adjPoint)))
					openQueue.offer(adjPoint);
		}
		return count;
	}

	public boolean nextToEachOther(Point a, Point b)
	{
		Point[] pts = a.adjPointsToMe();
		for(Point n : pts)
		{
			if(n.equals(b))
			 return true;
		}
		return false;
	}

	public ArrayList<Point> adjFreePointsTo(Point point)
	{
		ArrayList<Point> adjfree = new ArrayList<Point>();
		for(Point t : point.adjPointsToMe())
		{
			if(isValid(t))
				adjfree.add(t);
		}
		return adjfree;
	}

	public boolean isValid(Point p)
	{ // not wall and not me and not enemy
		//Bug.o("width: " + width + ", height: " + height);
		if( (p.X() >= 0) && (p.X() < width) && (p.Y() >= 0) && (p.Y() < height))
		{
			//Bug.ol("isValid IB: " + p);
			return walls[p.X()][p.Y()] == ' ';
		}
		else
		{
			//Bug.ol("isValid OOB: " + p);
			return false; // out of bounds
		}
	}

	public DIR closeCombatDecision()
	{
		Move m = new Move(me);
		PriorityQueue<Move> bestMoves = m.getAdjMoves();
		Move t = bestMoves.peek();
		Point p = t.getPoint();
		Bug.ol("ccD bestMove Point: " + t.getPoint());
		if( me.getAdjPoint(DIR.NORTH).equals(p))
			return DIR.NORTH;
		if( me.getAdjPoint(DIR.SOUTH).equals(p))
			return DIR.SOUTH;
		if( me.getAdjPoint(DIR.EAST).equals(p))
			return DIR.EAST;
		if( me.getAdjPoint(DIR.WEST).equals(p))
			return DIR.WEST;
		Bug.ol("cCD ERROR");
		return DIR.NORTH;
	}

	public int taxiDist(Point a, Point b)
	{
		return a.manhattanDist(b);
	}

	public DIR moveTo(Point end)
	{ // ghetto best first algo
		int mX = me.X();
		int mY = me.Y();
		int oX = op.X();
		int oY = op.Y();
		DIR NS_bias = null;
		DIR EW_bias = null;
		DIR Total_bias = null;
		int NSdist = Math.abs(mY - oY);
		int EWdist = Math.abs(mX - oX);
		if(mY > oY)
			NS_bias = DIR.NORTH;
		else
			NS_bias = DIR.SOUTH;

		if(mX > oX)
			EW_bias = DIR.WEST;
		else
			EW_bias = DIR.EAST;

		if(NSdist >= EWdist) // NS bias is greater, moves N or S
		{
		   if(isValid(me.getAdjPoint(NS_bias)))
				Total_bias = NS_bias;
		}else // EW bias is greater, move E or W
		{
			if(isValid(me.getAdjPoint(EW_bias)))
				Total_bias = EW_bias;
		}

		Bug.ol("moveTo: " + end + " is going: " + Total_bias);
		return Total_bias;
	}

	public DIR getBestQDir()
	{
		Point[] possPoints = me.adjPointsToMe();
		int max = 0;
		Point bestPoint = new Point(me.getAdjPoint(DIR.NORTH)); // default, die?
		PriorityQueue<Move> allMoves = new PriorityQueue<Move>();
		// calculate the numOpenSpaces*3 + numWalls next to, store that as value
		// in PQ allMoves<Move>
		for(Point p : possPoints)
		{
			Move m = new Move(p,0);
			//int t=0;
			if(!isValid(p))
				m.setValue(-1000); //t = -1000;
			else
				m.setValue(openPtsFrom(p)*3); //t = openPtsFrom(p);
			int nWalls = numWallsNextTo(p);
			m.setValue(m.getValue()+nWalls);
			allMoves.offer(m);
		}
		Bug.ol("allMoves: " + allMoves);
		//Move[] mArray = allMoves.toArray(new Move[0]);
		//Bug.ol("mArray: " + mArray);
		Move bestMove = allMoves.peek();//mArray[mArray.length-1]; //allMoves.peek();
		max = bestMove.getValue();
		bestPoint = bestMove.getPoint();
		Bug.ol("gBQD Value: " + max + " , point: " + bestPoint);
		if(me.getAdjPoint(DIR.NORTH).equals(bestPoint))
			return DIR.NORTH;
		if(me.getAdjPoint(DIR.SOUTH).equals(bestPoint))
			return DIR.SOUTH;
		if(me.getAdjPoint(DIR.EAST).equals(bestPoint))
			return DIR.EAST;
		if(me.getAdjPoint(DIR.WEST).equals(bestPoint))
			return DIR.WEST;
		Bug.ol("ERROR - gBQD");
		return DIR.NORTH;
	}

	public int numWallsNextTo(Point p)
	{
		Point[] adjPts = p.adjPointsToMe();
		int c = 0;
		for(Point m : adjPts)
			if(!isValid(m))
				c++;
		return c;
	}

	public String toString()
	{
		StringBuilder build = new StringBuilder( ) ;
		for(int r = 0 ; r< width; r++ )
		{
			build.append( walls[ r ] ) ;
		}
		return build.toString();
	}
}

Here is MyTronBot, which is what contains main and is used for getting things started, as well as running the fundamental strategy that is to be used

public class MyTronBot
{
	boolean IsClosedOff;

	public MyTronBot()
	{
		IsClosedOff = false;
	}

	public int convertMove(DIR dir)
	{
		Bug.ol("Choice: " + dir);
		switch(dir)
		{
			case NORTH: return 1;
			case SOUTH: return 3;
			case EAST: return 2;
			case WEST: return 4;
			default: return 0;
		}
	}

	public DIR makeMove()
	{
		Map map = new Map();
		DIR decision = DIR.SOUTH;
		if(!IsClosedOff)
		{ // we may need to update boolean, don't waste time
			IsClosedOff = map.isClosedOff();
		}
		if(IsClosedOff)
		{
			Bug.ol("Is closedOff, doing max fill strategy");
			decision = map.getBestQDir();
		}else
		{
			Bug.ol("Is !closedOff, doing ccombat ghetto moveTo ");
			if(map.nextToEachOther(map.getMe(), map.getOp()))
			{
				Bug.ol("Bots are next to eachother, doing close combat");
				decision = map.closeCombatDecision();
			}
			else
			{
				Bug.ol("Moving to OP (?)");
				decision = map.moveTo(map.getOp());
				if(decision == null)
				{
					Bug.ol("couln't go towards, picking flood");
				 	decision = map.getBestQDir();
				}
			}
		}
	//	while(false != true)
	//	{
		//	if(map.nextToEnemy(map.getMe(), map.getOp()))
		//	{
		//		Bug.ol("Next To Enemy, do something");
		//		decision = map.closeCombatDecision();
		//	}else if( map.getMe().manhattanDist(map.getOp()) == 2)
		//	{
		//		Bug.ol("manhattanDist == 2, prepare for combat?");
		//	}else
		//	{
				//
		//	}
			// close combat,
			// check taxi dist
			//  if far, do max fill
			//  if near, do cut - off

		//}
		return decision;
	}

	public static void main(String abc[])
	{
		MyTronBot mrBot = new MyTronBot();
		while(true)
		{
			Tron.Initialize();
			Tron.MakeMove(mrBot.convertMove(mrBot.makeMove()));
		}
	}
}

Lastly, Tron is just the Map.java file from the starter pack renamed, which can be found here.

GNU Octave doesn’t come with an easy way to set a PATH variable so as to simply calling library functions and whatnot. To add to the PATH, you need to edit the octaverc file. On windows this will be in:
C:\Octave\3.2.3_gcc-4.4.0\share\octave\3.2.3\m\startup
and on linux you will find it at:
~/.octaverc

In this file you need to add the line:

addpath(genpath("C:\\Path\\to\\your\\library"));

somewhere before the atexit(…) call. It is important to use double backward slashes in the directory path, otherwise Octave will try to parse the path name as escape characters which will not end well.

Proper, consistent indentation of source code is a crucial component to keep from going insane when staring at lines of text for hours on end. Most people adhere to a single favored style, be it K&R, ANSI, GNU, or whatever*, which for the most part is acceptable because they aren’t all that different from one another, and most modern IDE’s are capable of understanding different coding styles and adapting auto indentation settings to the wants of the programmer. However, there is also a tool included (or at least available for) *nix systems, called indent which can actually manipulate C/C++ source code to modify it’s indentation style.

Take for example this extremely lazy solution to projecteuler.net problem #3 It has many levels of indentation, comments, and is nice and short, which will help emphasize the major differences between coding styles in my examples. My personal favorite coding style follows the ANSI standard, which is good for distinguishing code blocks, but takes up a lot more vertical space than other styles.

//* Euler Three */
#include <iostream>
using std::cout;
using std::endl;

#include <cmath>
using std::sqrt;

bool isPrime(unsigned long long);

int main()
{
  unsigned long long NUM = 600851475143; // as provided by projecteuler   problem #3
  for (unsigned long long i = NUM / 2; i >= 2; i--)
    {
    // The following for-loop is going to do something relavent
    for (unsigned long long t = i; t >= 2; t--)
    {
      if ((t * i) == NUM)
      {
        if (isPrime(t))
        {
            cout << "PFF: " << t << endl;
         }
       }
     }
   }
  return 0;
}

bool isPrime(unsigned long long n)
{
  bool prime = true;
  for (unsigned long long i = 3; i <= sqrt(n); i += 2)
  {
    if (n % i == 0)
    {
      prime = false;
      break;
    }
  }
  if ((n % 2 != 0 && prime && n > 2) || n == 2)
  {
    return true;
  }
  else
  {
    return false;
   }
}

Now, let’s use indent to change to the more common K&R style:
$ indent -kr Three.cpp

The resulting source file:

/* Euler Three */

#include <iostream>
using std::cout;
using std::endl;

#include <cmath>
using std::sqrt;

bool isPrime(unsigned long long);

int main()
{

    unsigned long long NUM = 600851475143;	// as provided by projecteuler problem #3
    for (unsigned long long i = NUM / 2; i >= 2; i--) {
	// The following for-loop is going to do something relavent
	for (unsigned long long t = i; t >= 2; t--) {
	    if ((t * i) == NUM) {
		if (isPrime(t)) {
		    cout << "PFF: " << t << endl;
		}
	    }
	}
}
return 0;
}

/*
	The follwing function was copied and pasted from somewhere on the internets
	and should probably have some sort of credit to the author or something
*/
bool isPrime(unsigned long long n)
{
    bool prime = true;

    for (unsigned long long i = 3; i <= sqrt(n); i += 2) {
	if (n % i == 0) {
	    prime = false;
	    break;
	}
    }
    if ((n % 2 != 0 && prime && n > 2) || n == 2) {
	return true;
    } else {
	return false;
    }
}

The style is changed, and all I had to do was invoke a command with a single switch and the file name as the parameter. There are other switches available, of course, including:
-bad (force blank lines after declarations)
-bap (force blank lines after function bodies)
-bl (format according to the Pascal standard)
-bf (forces braces on if statements)
-bls (put braces on the line after struct declaration lines)
-kr (format to the Kernighan & Ritchie coding style)
-orig (format to Berkeley coding style)
-st (send to standard output )
-bbo (break after boolean operators)
-bc (break after commas)
… and a bazillion more options, all available in the man pages :p

* for more reading on indentation styles, check out the wiki entry

Wordpress 2.8.5 and 2.8.6 as packaged with Ubuntu are broken. Using the admin pages gives the error:
Warning: constant() [function.constant]: Couldn't find constant WP_CORE_UPDATE in /usr/share/wordpress/wp-admin/includes/update.php on line 33

A bug report addressing* this problem can be found here.

I have a simple/ghetto workaround for this issue. Open:
/usr/share/wordpress/wp-admin/includes/update.php
and comment out the two lines:
if ( !constant('WP_CORE_UPDATE') )
return false;

!! You will need to edit this file with root permissions. If you are running a full desktop, you can do:
sudo gedit /usr/share/wordpress/wp-admin/includes/update.php &

If you are running a headless server as I am, you can open the file for editing using vim, nano, emacs, etc. ie:
sudo nano /usr/share/wordpress/wp-admin/includes/update.php

The error will no longer appear, and the blog will continue to function 100%. There are absolutely better ways to deal with this issue, but that is up for the Ubuntu package maintainers to .. maintain.

The following screen-shot shows exactly where to add comment notation:

* “addressing” might be too strong of a word considering the progress being made on this issue. Two versions of wordpress to go through the package maintainers and it’s still broken? In fact, the report is still considered “New”.

UPDATE 12-24-2009
Turns out the Wordpress 2.9-1 update still has this issue…

Overview

The classic way of building RTEMS is to start by building your own tool chain for the specific target architecture for which you wish to build your RTEMS kernel for. This can be a tedious process as there are an abundance of little “gotcha’s” that lead to many failed compiles and hurt feelings.

The simplest way to build RTEMS is with the pre-built tool chains available on the rtems website. They are only available in .rpm format, and require the yum package manager for the easy – easy way of getting RTEMS compiled.

The website does have existing instructions on getting these pre-built tool chains setup, but I found them to be incomplete and confusing. So here is a guide to augment those instructions.

General vs. Example

For the sake of clarity, I’ll be showing general commands in normal code font and example commands in red code font . Since there are many different environments and build targets, the general case will be sort of “fill in the blank”, while following the examples in red will get to a working i386 RTEMS kernel.

Downloading Things

For the example build, I’ll be using i386 RTEMS 4.9.2 and the Fedora 12 32-bit O.S. If you aren’t using either Fedora, CentOS, RedHat, or Suse, these instructions are probably useless to you. You’ll need to either build the toolchain by hand or start using one of the supported operating systems.

*One important thing to note about the RTEMS naming convention is that the toolchain drops the last digit of the version number of the RTEMS version you want to build. For example, if you’re building RTEMS 4.9.2, you use the 4.9 toolchain.

Download

Go to www.rtems.org/ftp/pub/rtems/linux/ and click through the links until you’ve found the page listing rpm packages relevant to your OS and desired RTEMS version. There will be an .rpm (probably at the bottom) in the form:
rtems-BRANCH-yum-conf-VERSION-DISTRO.noarch.rpm
For example,
wget http://www.rtems.org/ftp/pub/rtems/linux/4.9/fedora/12/i386/rtems-4.9-yum-conf-0.20-1.fc12.noarch.rpm
will download the correct file into your current directory.