I : Secret Santa

09Dec13

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

Secret Santa

Santa’s appearance should be a surprise for the kids, so Santa felt a need for encrypting his communication about the flight route with his reindeers. They agree to use the Caesar cipher, which is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. The alphabet is thought to wrap around, so A follows after Z. The encryption key defines the shift that is used for the cipher. For example, with a shift of 5, A would be replaced by F, K would become P, Z would become E, etc. The method is named after Julius Caesar, who used it in his private correspondence. Santa and reindeers further agreed on the following rules:

  • Only alphabetical characters are to be encrypted, all other characters stay the same.
  • The upper/lowercase of a character is preserved

If the encryption key (an integer between 0 and 25) is known, a text can be encrypted and decrypted. Santa used a different key for each communication partner. Unfortunately Santa lost the notes with the keys, so he is now in deep trouble. Luckily, he has still a number of encrypted messages in his inbox. He also remembers that all messages had at least one of his reindeers named in the text.

Problem

Write a program that helps Santa recovering the keys. If you are missing information research it from other sources. Your program should read one encrypted message per line, determine the encryption key and print the key followed by a newline. If the program reads an unencrypted message, the program should terminate.

Example

Input

Fgct Fcujgt! Vjg hnkijv tqwvg yknn fghkpkvgna iq qxgt ktgncpf.
Qbi wulym qbcwb Clyfuhx? Nby cmfuhx, Xuhwyl.
Hi Vixen! All future messages will be encrypted!

Output

2
20

Solution (I.java):

import java.util.Scanner;

class WordsFromString
{
  private int m_beginAtIndex = 0;
  private String m_string;

  public WordsFromString( String p )
  {
    m_string = p;
  }

  public String getWordFromString()
  {
    if( m_beginAtIndex >= m_string.length())
      return null;
    boolean word_begun = false;
    String s = "";
    for( int i = m_beginAtIndex; i < m_string.length(); i ++ )
    {
      final char c = m_string.charAt( i );
      if( !word_begun )
      {
        if(( c >= 'a' && c <= 'z' ) || ( c >= 'A' && c <= 'Z' ))
        {
          word_begun = true;
          s += c;
        }
      }
      else
        if(( c >= 'a' && c <= 'z' ) || ( c >= 'A' && c <= 'Z' ))
          s += c;
        else
        {
          m_beginAtIndex = i + 1;
          return s;
        }
    }
    return s;
  }
}

public class I
{
  private static final String REINDEER_NAME[] = { "Dasher", "Dancer", "Prancer", "Vixen", "Comet", "Cupid", "Donner", "Blitzen", "Rudolph" };

  public static void main( String p[] )
  {
    Scanner s = new Scanner( System.in );
    int key = 0 /* Stops the compiler from complaining... */ ;
    do
    {
      String l = s.nextLine();
      WordsFromString wordsFromString = new WordsFromString( l );
      String w;
      while(( w = wordsFromString.getWordFromString()) != null )
      {
        boolean key_found = false;
        for( key = 0; key < 26; key ++ )
        {
          if( isReindeerName( w ))
          {
            if( key != 0 )
              System.out.println( 26 - key );
            key_found = true;
            break;
          }
          w = shiftCharacters( w, 1 );
        }
        if( key_found )
          break;
      }
    }
    while( key != 0 );
  }

  static String shiftCharacters( String p_string, int p_shiftCharactersBy )
  {
    while( p_shiftCharactersBy >= 26 )
      p_shiftCharactersBy -= 26;
    while( p_shiftCharactersBy < 0 )
      p_shiftCharactersBy += 26;
    String s = "";
    for( int i = 0; i < p_string.length(); i ++ )
    {
      char c = p_string.charAt( i );
      if(( c >= 'a' && c <= 'z' ) || ( c >= 'A' && c <= 'Z' ))
      {
        final boolean uppercase = c >= 'A' && c <= 'Z';
        if( uppercase )
          c = ( "" + c ).toLowerCase().charAt( 0 );
        c -= 'a';
        c += p_shiftCharactersBy;
        if( c >= 26 )
          c -= 26;
        if( c < 0 )
          c += 26;
        c += 'a';
        if( uppercase )
          c = ( "" + c ).toUpperCase().charAt( 0 );
      }
      s += c;
    }
    return s;
  }

  private static boolean isReindeerName( String p )
  {
    for( String s : REINDEER_NAME )
      if( s.equals( p ))
        return true;
    return false;
  }
}

Testing:

Fgct Fcujgt! Vjg hnkijv tqwvg yknn fghkpkvgna iq qxgt ktgncpf.
2
Qbi wulym qbcwb Clyfuhx? Nby cmfuhx, Xuhwyl.
20
Hi Vixen! All future messages will be encrypted!
Advertisements


No Responses Yet to “I : Secret Santa”

  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: