K : Elf simulation

11Dec13

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 (K; medium difficulty):

Elf simulation

At Santa’s place there are elves cutting wood and elves crafting nice carvings out of the wood, then putting it onto Santa’s sleigh. Implement a one-dimensional simulation with the following elements:

T Tree
w Woodcutter elf, empty-handed
W Woodcutter elf, carrying wood
c Crafter elf, empty-handed
k Crafter elf, carrying wood
C Crafter elf, carrying carving
S Santa’s sleigh
. Empty spot
Implement a time-discrete simulation where each action takes one simulation step.

Simulation rules

  1. Elves can do one action (move one field, chop, craft, exchange, or load) per simulation step
  2. Elves can never occupy the same place, moving is only possible if the space in that direction is free at the beginning of the move
  3. An empty-handed woodcutter elf is always moving left if there is space, only to stop at a tree or at the “end of the world”
  4. If an empty-handed woodcutter elf arrives near a tree, he chops it down the tree and carries wood in the next step.
  5. A wood-carrying woodcutter elf moves right if there is space
  6. If a wood-carrying woodcutter meets an empty-handed woodcutter, the wood is exchanged (passed on from the left to the right)
  7. Empty-handed crafter elves are always moving left if there is space
  8. If a wood-carrying woodcutter meets an empty-handed crafter, the wood is exchanged (passed on from the left to the right)
  9. A crafter receiving a wood piece crafts a carving out of it in one step
  10. A crafter with a carving moves right if there is space
  11. An empty-handed crafter moves left if there is space
  12. If a crafter with a carving meets an empty-handed crafter, the carving is exchanged (passed on from the left to the right)
  13. If a crafter with a carving arrives at Santa’s Sleigh, she loads the carving onto the sleigh.
  14. All elves move at the same time, in case of a conflict, the elf coming from the right side has to yield

Problem

Implement a program that reads a line with the world layout followed by a colon and the number of simulation steps. Print the state of the world after the given number of simulation steps as answer. You can assume that all elves are empty-handed at the beginning of the simulation. The world will always be constructed of trees, woodcutters, crafters and Santa’s Sleigh from left to right. Empty space can appear anywhere. Upon reading an empty line the program shall terminate.

Example

Input

.T.TTTT...ww.c.c.....................................S:1
.T.TTTT...ww.c.c.....................................S:10
.T.TTTT...ww.c.c.....................................S:100
(empty line)

Output

.T.TTTT..w.wc.c......................................S
.T.T.W..wk..C........................................S
.T..w...w..c.....c...................................S

Solution (K.java):

import java.util.Scanner;

public class K
{
  public static void main( String p[] )
  {
    Scanner s = new Scanner( System.in );
    String l = s.nextLine();
    while( l.length() > 0 )
    {
      int i = l.indexOf( ':' );
      final int iterations = Integer.parseInt( l.substring( i + 1, l.length()));
      l = l.substring( 0, i );
      for( i = 0; i < iterations; i ++ )
        l = simulate( l );
      System.out.println( l );
      l = s.nextLine();
    }
  }

  private static String simulate( String p )
  {
    final char o[] = p.toCharArray();
    char n[] = new char[ p.length() ];
    for( int i = 0; i < o.length; i ++ )
      switch( o[ i ] )
      {
        case 'T':
          n[ i ] = 'T';
          break;
        case 'w':
          n[ i ] = 'w';
          if( i > 0 )
            if( o[ i - 1 ] == '.' )
            {
              n[ i - 1 ] = 'w';
              n[ i ] = '.';
            }
            else
              if( o[ i - 1 ] == 'T' )
              {
                n[ i - 1 ] = '.';
                n[ i ] = 'W';
              }
              else
                if( o[ i - 1 ] == 'W' )
                {
                  n[ i - 1 ] = 'w';
                  n[ i ] = 'W';
                }
          break;
        case 'W':
          n[ i ] = 'W';
          if( i + 1 < n.length && o[ i + 1 ] == '.' )
          {
            n[ i ] = '.';
            n[ i + 1 ] = 'W';
            i ++;
          }
          break;
        case 'c':
          n[ i ] = 'c';
          if( i > 0 )
            if( o[ i - 1 ] == '.' && n[ i - 1 ] == '.' )
            {
              n[ i ] = '.';
              n[ i - 1 ] = 'c';
            }
            else
              if( o[ i - 1 ] == 'W' )
              {
                n[ i ] = 'k';
                n[ i - 1 ] = 'w';
              }
              else
                if( o[ i - 1 ] == 'C' )
                {
                  n[ i ] = 'C';
                  n[ i - 1 ] = 'c';
                }
          break;
        case 'k':
          n[ i ] = 'C';
          break;
        case 'C':
          n[ i ] = 'C';
          if( i + 1 < n.length )
            if( o[ i + 1 ] == '.' )
            {
              n[ i ] = '.';
              n[ i + 1 ] = 'C';
              i ++;
            }
            else
              if( o[ i + 1 ] == 'S' )
                n[ i ] = 'c';
          break;
        case 'S':
          n[ i ] = 'S';
          break;
        case '.':
          n[ i ] = '.';
          break;
      }
    return new String( n );
  }
}

Testing:

.T.TTTT...ww.c.c.....................................S:1
.T.TTTT..w.wc.c......................................S
.T.TTTT...ww.c.c.....................................S:10
.T.T.W..wk..C........................................S
.T.TTTT...ww.c.c.....................................S:100
.T..w...w..c.....c...................................S
Advertisements


No Responses Yet to “K : Elf simulation”

  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: