Langton’s Ant

26Jan14

In the twelve months from March 2013 to March 2014, I programmed solutions to the problems posted on the Contest Coding blog run by Lewis Cornwall, solving 33 problems (out of 47) and achieving a position of 4th on the leaderboard (out of 23).

As that blog has now been discontinued, I’m posting here the solutions I programmed to those problems.

Langton’s Ant

Langton’s Ant moves on a grid of squares that can be either black or white. The grid begins as fully white and the ant can only face left, right, down or up. It then moves in accordance to the following two rules:

  • If the ant is on a black square, it changes the colour of the square to white, rotates 90 degrees anticlockwise and moves forward one square.
  • If the ant is on a white square, it changed the colour of the square to black, rotates 90 degrees clockwise and move forward one square.

Find the total number of black squares on the grid after the ant moves 1000 times.

Solution and answer (Langtons_Ant.java):

import java.util.Date;

/*
Solution and answer for problem "Langton's Ant" (26th January 2014) of http://ContestCoding.WordPress.com/

Sun Jan 26 09:00:00 GMT+00:00 2014

There are 118 black squares on the grid after the ant has moved 1,000 times.

Sun Jan 26 09:00:00 GMT+00:00 2014

Solution programmed in Java using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition); solution took ~1s to run on a 80MHz PowerPC 601.
*/

public class Langtons_Ant
{
  private static final byte UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3;

  public static void main( String p[] )
  {
    System.out.println( new Date());

    byte direction = UP;
    short x = 0, y = 0;
    Squares squares = new Squares();
    for( short i = 1; i <= 1000; i ++ )
    {
      Square square = squares.getSquare( x, y );
      if( square.m_colour == SquareColour.WHITE )
      {
        square.m_colour = SquareColour.BLACK;
        if( ++ direction > LEFT )
          direction = UP;
      }
      else
      {
        square.m_colour = SquareColour.WHITE;
        if( -- direction < UP )
          direction = LEFT;
      }
      x += xComponentOfDirection( direction );
      y += yComponentOfDirection( direction );
    }
    System.out.println( "\nThere are " + squares.getNumberOfSquaresOfColour( SquareColour.BLACK ) + " black squares on the grid after the ant has moved 1,000 times.\n" );

    System.out.println( new Date());
  }

  private static short xComponentOfDirection( byte p )
  {
    if( p == LEFT )
      return -1;
    if( p == RIGHT )
      return 1;
    return 0;
  }

  private static short yComponentOfDirection( byte p )
  {
    if( p == UP )
      return 1;
    if( p == DOWN )
      return -1;
    return 0;
  }
}

class SquareColour
{
  public static final byte WHITE = 0, BLACK = 1;
}

class Square
{
  public Square m_next = null;
  public byte m_colour = SquareColour.WHITE;
  public short m_x, m_y;

  public Square( short p_x, short p_y )
  {
    m_x = p_x;
    m_y = p_y;
  }
}

class Squares
{
  private Square m_first = null, m_last;

  public Square getSquare( short p_x, short p_y )
  {
    Square s = m_first;
    while( s != null )
    {
      if( s.m_x == p_x && s.m_y == p_y )
        return s;
      s = s.m_next;
    }
    s = new Square( p_x, p_y );
    if( m_first == null )
      m_first = s;
    else
      m_last.m_next = s;
    m_last = s;
    return s;
  }

  public int getNumberOfSquaresOfColour( byte p )
  {
    Square s = m_first;
    int i = 0;
    while( s != null )
    {
      if( s.m_colour == p )
        i ++;
      s = s.m_next;
    }
    return i;
  }
}
Advertisements


No Responses Yet to “Langton’s Ant”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: