T : Santa’s Cube Adventure

20Dec13

I recently participated in the Advent Programming Contest 2013 organised by the IEEE Student Branch Klagenfurt (with support from Alpen-Adria-Universität Klagenfurt), wherein – as I’d recently received from Udacity a certificate for Introduction to Programming : Problem Solving with Java (CS046) – I challenged myself to program my solutions to the problems posed by the contest using only Java (I’d used C and C++ when I’d participated in the contest in 2012); I solved eighteen of the problems posed by the contest, achieving a rank of 10th (out of 155 participants).

As submissions of solutions to the contest are now closed, I’m posting here the solutions I submitted to the contest.

Problem (T; hardest difficulty):

Santa’s Cube Adventure

Advent Programming Contest 2013 - T

Santa made it safely home from the cube (see Problem O).

To recap:

Santa got drunk at the tavern the other day. As he awakes he finds himself inside an empty cubic room. After a moment of surprise, Santa notices that at the centre of each wall, roof, and floor there is a gate that seems to give access to another similar empty cubic room. At each gate Santa notices numbers which identify the current room and the room the gate is leading to.

After looking at the numbers, Santa also finds out that the numbers to the next rooms always have a regular offset depending on the moving direction:

  • west and east are +1 and -1, respectively
  • north and south are +29 and -29, respectively
  • up and down is +727 and -727, respectively

By throwing his boots into some of the neighboring rooms, Santa also finds out that all rooms with a number with less than three different prime factors are trapped and cannot be passed safely. So, for example room 10000 and 100001 would be trapped, while room 10002 would be not.

Santa was part of a cruel experiment, where he started in the middle cube of a building consisting of 15 x 15 x 15 cubes. The building has a bridge attached at the cube that lies east of the corner that is the most eastern, southern and lowest.

Problem

Santa decides that his adventure should become a computer game. Write a program that let’s you control Santa in the cube. Each line, you can enter one of the following commands:

go north or n if possible, Santa switches to the room north of him. Otherwise, the answer is “There is no way!”
go south or s if possible, Santa switches to the room south of him. Otherwise, the answer is “There is no way!”
go east or e if possible, Santa switches to the room east of him. Otherwise, the answer is “There is no way!”
go west or w if possible, Santa switches to the room west of him. Otherwise, the answer is “There is no way!”
go up or u if possible, Santa switches to the room up of him. Otherwise, the answer is “There is no way!”
go down or d if possible, Santa switches to the room down of him. Otherwise, the answer is “There is no way!”
look repeats the room’s description, lists the items in the room and the possible exits
take object takes the object if it is present in this room (“You took object.”), otherwise the answer is “There is no object here!”
inventory or i lists Santa’s inventory in the form “You have object1, object2, object3.
use object If the object is the calculator, answer is “Safe directions are ” followed by an alphabetical list of all adjacent safe rooms. Directions are separated by a comma and space and there should be a period after the last direction. Once the calculator has been used successfully, the list of safe exits appears with every room. For other present objects than the calculator the answer is “Nothing happens.”. If the object is neither in the room nor in inventory, answer is “You don’t have object!”.

Room descriptions are listed upon entering a room or as response to the look command. Possible descriptions are

You are in a cubic room. for all cube rooms which are safe.
This room is trapped! You die a horrible death! for all cube rooms which are trapped. There is no list of items or exits following this description. Your program shall terminate right after printing the death message.
You are on the bridge. if you are on the bridge. The bridge has exits to the west (where you came from) and east (where you get out)
You made it out! You are free! Congratulations! There is no list of items or exits following this description. Your program shall terminate after printing this message.

If there are objects in the room, the description is followed by a line “You see: ” and a list of objects in this room (not those in the inventory). The last line consist of “Exits are: ” listing an alphabetical list of possible exits. If you are in a cube with an outside wall, this direction is not available except for the room near the bridge. If the calculator is activated and in possession of the player or in the current room, a further output “Safe directions are ” followed by a (comma plus space)-separated alphabetical list of all adjacent safe rooms is added in the next line of the room description.

Items are

calculator Initially in room north of the starting room.
boots Initially in Santa’s inventory.
santa hat Initially in Santa’s inventory.

If a command cannot be decoded, your program should answer “What?”.

Starting situation: Santa is in the central room, which has the number 9085. The program shall start with displaying the room description and then wait for the players input.

Some clarifications: The “You see ” line should be only printed if there is an object inside this room, otherwise this line is omitted. The “Safe directions ” line is always printed with the room description if the calculator is with us (in the room or in the inventory) and has been previously activated (“use calculator”). The “Safe directions ” function should also work on the bridge. Hope that helps.

Example

You are in a cubic room.
Exits are: down, east, north, south, up, west.
n
You are in a cubic room.
You see: calculator.
Exits are: down, east, north, south, up, west.
take calculator
You took calculator.
use calculator
Safe directions are south.
s
You are in a cubic room.
Exits are: down, east, north, south, up, west.
Safe directions are down, east, north, up, west.
inventory
You have boots, calculator, santa hat.
s
This room is trapped! You die a horrible death!

Solution:

PrimeDecomposition.java:

import java.util.ArrayList;

class PrimeDecomposition
{
  private int m_primes[];

  public PrimeDecomposition( int p )
  {
    // Determine the prime numbers in the range of numbers 0..p
    boolean b[] = new boolean[ p + 1 ];
    for( int i = 3; i < b.length; i += 2 )
      b[ i ] = true;
    int number_of_primes = 1; /* 2 */
    for( int i = 3; i < b.length; i += 2 )
      if( b[ i ] )
      {
        number_of_primes ++;
        for( int k = i + i; k < b.length; k += i )
          b[ k ] = false;
      }

    // Make an array of the prime numbers in the range of numbers 0..p
    m_primes = new int[ number_of_primes ];
    int k = 0;
    m_primes[ k ++ ] = 2;
    for( int i = 3; i < b.length; i += 2 )
      if( b[ i ] )
        m_primes[ k ++ ] = i;
  }

  public ArrayList<Integer> primeFactors( int p )
  {
    ArrayList<Integer> prime_factors = new ArrayList<Integer>();
    for( int i = m_primes.length - 1; i >= 0; i -- )
      if( m_primes[ i ] == p )
      {
        prime_factors.add( new Integer( m_primes[ i ] ));
        return prime_factors;
      }
      else
        if( primeFactors( p, i, m_primes[ i ], prime_factors ))
        {
          prime_factors.add( new Integer( m_primes[ i ] ));
          return prime_factors;
        }
    return null;
  }

  private boolean primeFactors( int p_targetProduct, int p_index, int p_product, ArrayList<Integer> p_primeFactors )
  {
    for( int i = p_index; i >= 0; i -- )
    {
      final int p = p_product * m_primes[ i ];
      if( p == p_targetProduct )
      {
        p_primeFactors.add( new Integer( m_primes[ i ] ));
        return true;
      }
      else
        if( p < p_targetProduct )
          if( primeFactors( p_targetProduct, p_index, p, p_primeFactors ))
          {
            p_primeFactors.add( new Integer( m_primes[ i ] ));
            return true;
          }
    }
    return false;
  }
}

T.java:

import java.util.Scanner;
import java.util.ArrayList;

public class T
{
  private static final int BRIDGE = -1, OUTSIDE = -2, INVENTORY = -2;

  private static final PrimeDecomposition m_primeDecomposition = new PrimeDecomposition( 14384 );

  private static int m_roomNumber = 9085, m_calculatorRoomNumber = 9085 + 29, m_roomNumberBeforeBridge;
  private static byte m_southNorthCoordinate = 8, m_westEastCoordinate = 8, m_downUpCoordinate = 8;
  private static boolean m_usedCalculator = false, m_gameover = false;

  public static void main( String p[] )
  {
    Scanner s = new Scanner( System.in );
    printDescriptionOfRoom();
    do
    {
      final String l = s.nextLine();
      boolean instruction_understood = false;
      if( l.equals( "go south" ) || l.equals( "s" ))
      {
        instruction_understood = true;
        if( m_roomNumber == BRIDGE || m_southNorthCoordinate == 1 )
          System.out.println( "There is no way!" );
        else
        {
          m_southNorthCoordinate --;
          m_roomNumber -= 29;
          printDescriptionOfRoom();
        }
      }
      if( l.equals( "go north" ) || l.equals( "n" ))
      {
        instruction_understood = true;
        if( m_roomNumber == BRIDGE || m_southNorthCoordinate == 15 )
          System.out.println( "There is no way!" );
        else
        {
          m_southNorthCoordinate ++;
          m_roomNumber += 29;
          printDescriptionOfRoom();
        }
      }
      if( l.equals( "go west" ) || l.equals( "w" ))
      {
        instruction_understood = true;
        if( m_roomNumber == BRIDGE )
        {
          m_roomNumber = m_roomNumberBeforeBridge;
          printDescriptionOfRoom();
        }
        else
          if( m_westEastCoordinate == 1 )
            System.out.println( "There is no way!" );
          else
          {
            m_westEastCoordinate --;
            m_roomNumber ++;
            printDescriptionOfRoom();
          }
      }
      if( l.equals( "go east" ) || l.equals( "e" ))
      {
        instruction_understood = true;
        if( m_roomNumber == BRIDGE )
        {
          m_roomNumber = OUTSIDE;
          printDescriptionOfRoom();
        }
        else
          if( m_westEastCoordinate == 15 && m_southNorthCoordinate == 1 && m_downUpCoordinate == 1 )
          {
            m_roomNumberBeforeBridge = m_roomNumber;
            m_roomNumber = BRIDGE;
            printDescriptionOfRoom();
          }
          else
            if( m_westEastCoordinate == 15 )
              System.out.println( "There is no way!" );
            else
            {
              m_westEastCoordinate ++;
              m_roomNumber --;
              printDescriptionOfRoom();
            }
      }
      if( l.equals( "go down" ) || l.equals( "d" ))
      {
        instruction_understood = true;
        if( m_roomNumber == BRIDGE || m_downUpCoordinate == 1 )
          System.out.println( "There is no way!" );
        else
        {
          m_downUpCoordinate --;
          m_roomNumber -= 727;
          printDescriptionOfRoom();
        }
      }
      if( l.equals( "go up" ) || l.equals( "u" ))
      {
        instruction_understood = true;
        if( m_roomNumber == BRIDGE || m_downUpCoordinate == 15 )
          System.out.println( "There is no way!" );
        else
        {
          m_downUpCoordinate ++;
          m_roomNumber += 727;
          printDescriptionOfRoom();
        }
      }
      if( l.equals( "look" ))
      {
        instruction_understood = true;
        printDescriptionOfRoom();
      }
      if( l.equals( "inventory" ) || l.equals( "i" ))
      {
        instruction_understood = true;
        System.out.println( "You have boots, " + (( m_calculatorRoomNumber == INVENTORY )?"calculator, ":"" ) + "santa hat." );
      }
      if( !instruction_understood )
      {
        final int i = l.indexOf( ' ' );
        if( i > -1 )
        {
          final String verb = l.substring( 0, i ), noun = l.substring( i + 1, l.length());
          if( verb.equals( "take" ))
          {
            instruction_understood = true;
            if( noun.equals( "calculator" ) && m_roomNumber == m_calculatorRoomNumber )
            {
              m_calculatorRoomNumber = INVENTORY;
              System.out.println( "You took calculator." );
            }
            else
              System.out.println( "There is no " + noun + " here!" );
          }
          if( verb.equals( "use" ))
          {
            instruction_understood = true;
            if( noun.equals( "boots" ) || noun.equals( "santa hat" ))
              System.out.println( "Nothing happens." );
            else
              if( noun.equals( "calculator" ) && ( m_calculatorRoomNumber == INVENTORY || m_calculatorRoomNumber == m_roomNumber ))
              {
                m_usedCalculator = true;
                printSafeDirections();
              }
              else
                System.out.println( "You don't have " + noun + "!" );
          }
        }
      }
      if( !instruction_understood )
        System.out.println( "What?" );
    }
    while( !m_gameover );
  }

  private static boolean safeRoomNumber( int p )
  {
    ArrayList<Integer> prime_factors = m_primeDecomposition.primeFactors( p );
    Integer prime_factor = prime_factors.remove( 0 );
    int number_of_prime_factors = 1;
    for( Integer i : prime_factors )
      if( !i.equals( prime_factor ))
      {
        if( ++ number_of_prime_factors >= 3 )
          return true;
        prime_factor = i;
      }
    return false;
  }

  private static void printDescriptionOfRoom()
  {
    if( m_roomNumber == OUTSIDE )
    {
      m_gameover = true;
      System.out.println( "You made it out! You are free! Congratulations!" );
    }
    else
      if( m_roomNumber == BRIDGE )
      {
        System.out.println( "You are on the bridge." );
        System.out.println( "Exits are: east, west." );
        if(( m_calculatorRoomNumber == INVENTORY || m_roomNumber == m_calculatorRoomNumber ) && m_usedCalculator )
          printSafeDirections();
      }
      else
        if( !safeRoomNumber( m_roomNumber ))
        {
          m_gameover = true;
          System.out.println( "This room is trapped! You die a horrible death!" );
        }
        else
        {
          System.out.println( "You are in a cubic room." );
          if( m_roomNumber == m_calculatorRoomNumber )
            System.out.println( "You see: calculator." );
          String doors[] = new String[ 6 ];
          int number_of_doors = 0;
          if( m_downUpCoordinate > 1 )
            doors[ number_of_doors ++ ] = "down";
          if( m_westEastCoordinate < 15 || ( m_westEastCoordinate == 15 && m_southNorthCoordinate == 1 && m_downUpCoordinate == 1 ))
            doors[ number_of_doors ++ ] = "east";
          if( m_southNorthCoordinate < 15 )
            doors[ number_of_doors ++ ] = "north";
          if( m_southNorthCoordinate > 1 )
            doors[ number_of_doors ++ ] = "south";
          if( m_downUpCoordinate < 15 )
            doors[ number_of_doors ++ ] = "up";
          if( m_westEastCoordinate > 1 )
            doors[ number_of_doors ++ ] = "west";
          System.out.print( "Exits are: " );
          for( int i = 0; i < number_of_doors; i ++ )
            System.out.print( doors[ i ] + (( i + 1 < number_of_doors )?", ":"" ));
          System.out.println( "." );
          if(( m_calculatorRoomNumber == INVENTORY || m_roomNumber == m_calculatorRoomNumber ) && m_usedCalculator )
            printSafeDirections();
        }
  }

  private static void printSafeDirections()
  {
    System.out.print( "Safe directions are " );
    if( m_roomNumber == BRIDGE )
      System.out.print( "east, west" );
    else
    {
      String safe_directions[] = new String[ 6 ];
      int number_of_safe_directions = 0;
      if( m_downUpCoordinate > 1 && safeRoomNumber( m_roomNumber - 727 ))
        safe_directions[ number_of_safe_directions ++ ] = "down";
      if(( m_westEastCoordinate < 15 && safeRoomNumber( m_roomNumber - 1 )) || ( m_westEastCoordinate == 15 && m_southNorthCoordinate == 1 && m_downUpCoordinate == 1 ))
        safe_directions[ number_of_safe_directions ++ ] = "east";
      if( m_southNorthCoordinate < 15 && safeRoomNumber( m_roomNumber + 29 ))
        safe_directions[ number_of_safe_directions ++ ] = "north";
      if( m_southNorthCoordinate > 1 && safeRoomNumber( m_roomNumber - 29 ))
        safe_directions[ number_of_safe_directions ++ ] = "south";
      if( m_downUpCoordinate < 15 && safeRoomNumber( m_roomNumber + 727 ))
        safe_directions[ number_of_safe_directions ++ ] = "up";
      if( m_westEastCoordinate > 1 && safeRoomNumber( m_roomNumber + 1 ))
        safe_directions[ number_of_safe_directions ++ ] = "west";
      for( int i = 0; i < number_of_safe_directions; i ++ )
        System.out.print( safe_directions[ i ] + (( i + 1 < number_of_safe_directions )?", ":"" ));
    }
    System.out.println( "." );
  }
}

Testing:

You are in a cubic room.
Exits are: down, east, north, south, up, west.
n
You are in a cubic room.
You see: calculator.
Exits are: down, east, north, south, up, west.
take calculator
You took calculator.
use calculator
Safe directions are south.
s
You are in a cubic room.
Exits are: down, east, north, south, up, west.
Safe directions are down, east, north, up, west.
inventory
You have boots, calculator, santa hat.
s
This room is trapped! You die a horrible death!
Advertisements


No Responses Yet to “T : Santa’s Cube Adventure”

  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: