U : Snowball league

21Dec13

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

Snowball league

When the elves are not busy making toys, they play at the snowball profi league. A match of snowball consists of up to three sets. Each set is won by the team that first reaches 17 points. The team that has first won 2 sets is the match winner.

Problem

Implement a snowball league table calculator. You program should first read an integer, the number of matches to process, followed by the match results, one per line, consisting of

team1 vs. team2 a:b c:d e:f

where a,b,c,d,e,f are the number of points in the respective sets. If there are onyl two sets in a match, only a:b c:d is given. After reading the matches, your program shall print a list of the the teams according to their position in the table. Each team name should be preceded with the rank in the league followed by a dot and space. The ranking rules of the tyble league are as follows:

  1. Teams are primarily sorted according to the number of matches won.
  2. Teams with no distinction via rule number 1 are ranked according to the quotient of won matches to lost matches.
  3. Teams with no distinction via previous rules are further sorted according to the number of sets won.
  4. Teams with no distinction via previous rules are ranked according to the quotient of won sets to lost sets.

Example

Input

3
Isotopes of the North vs. Santas 17:6 13:17 11:17
Satans vs. Isotopes of the North 17:16 17:8
Satans vs. Santas 17:15 11:17 14:17

Output

1. Santas
2. Satans
3. Isotopes of the North

Solution (U.java):

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

class Team
{
  public String m_name;
  public int m_matchesWon = 0, m_matchesLost = 0, m_setsWon = 0, m_setsLost = 0;

  public Team( String p )
  {
    m_name = p;
  }
}

class Teams
{
  private static ArrayList<Team> m_teams = new ArrayList<Team>();

  public static Team add( String p )
  {
    for( Team t : m_teams )
      if( t.m_name.equals( p ))
        return t;
    m_teams.add( new Team( p ));
    return m_teams.get( m_teams.size() - 1 );
  }

  public static void print()
  {
    for( int i = 0; i < m_teams.size(); i ++ )
      System.out.println(( i + 1 ) + ". " + m_teams.get( i ).m_name );
  }

  public static void sort()
  {
    boolean sort_occurred;
    do
    {
      sort_occurred = false;
      for( int i = 0; i < m_teams.size() - 1; i ++ )
      {
        Team a = m_teams.get( i );
        Team b = m_teams.get( i + 1 );
        if( compare( a, b ) < 0 )
        {
          sort_occurred = true;
          m_teams.set( i, b );
          m_teams.set( i + 1, a );
        }
      }
    }
    while( sort_occurred );
  }

  private static int compare( Team a, Team b )
  {
    if( a.m_matchesWon > b.m_matchesWon )
      return 1;
    if( a.m_matchesWon < b.m_matchesWon )
      return -1;
    double q_a = ( double )a.m_matchesWon / a.m_matchesLost;
    double q_b = ( double )b.m_matchesWon / b.m_matchesLost;
    if( q_a > q_b )
      return 1;
    if( q_a < q_b )
      return -1;
    if( a.m_setsWon > b.m_setsWon )
      return 1;
    if( a.m_setsWon < b.m_setsWon )
      return -1;
    q_a = ( double )a.m_setsWon / a.m_setsLost;
    q_b = ( double )b.m_setsWon / b.m_setsLost;
    if( q_a > q_b )
      return 1;
    if( q_a < q_b )
      return -1;
    return 0;
  }
}

class Set
{
  public int m_a_setsWon = 0, m_a_setsLost = 0, m_b_setsWon = 0, m_b_setsLost = 0, m_index;

  public Set( int p )
  {
    m_index = p;
  }
}

public class U
{
  public static void main( String p[] )
  {
    Scanner scanner = new Scanner( System.in );
    final int number_of_matches = Integer.parseInt( scanner.nextLine());
    for( int i = 0; i < number_of_matches; i ++ )
    {
      String l = scanner.nextLine();
      int k = l.indexOf( " vs. " );
      Team a = Teams.add( l.substring( 0, k ));
      int m = l.indexOf( ':' );
      for( m --; ; m -- )
        if( l.charAt( m ) == ' ' )
          break;
      Team b = Teams.add( l.substring( k + 5, m ));

      Set s = new Set( m + 1 );
      parseSet( l, s );
      parseSet( l, s );
      if( s.m_index < l.length())
        parseSet( l, s );
      if( s.m_a_setsWon > s.m_b_setsWon )
      {
        a.m_matchesWon ++;
        b.m_matchesLost ++;
      }
      else
      {
        b.m_matchesWon ++;
        a.m_matchesLost ++;
      }
      a.m_setsWon += s.m_a_setsWon;
      a.m_setsLost += s.m_a_setsLost;
      b.m_setsWon += s.m_b_setsWon;
      b.m_setsLost += s.m_b_setsLost;
    }
    Teams.sort();
    Teams.print();
  }

  private static void parseSet( String l, Set s )
  {
    int i = l.indexOf( ':', s.m_index );
    int a = Integer.parseInt( l.substring( s.m_index, i ));
    s.m_index = i + 1;
    i = l.indexOf( ' ', s.m_index );
    if( i == -1 )
      i = l.length();
    int b = Integer.parseInt( l.substring( s.m_index, i ));
    s.m_index = Math.min( i + 1, l.length());
    if( a > b )
    {
      s.m_a_setsWon ++;
      s.m_b_setsLost ++;
    }
    else
    {
      s.m_b_setsWon ++;
      s.m_a_setsLost ++;
    }
  }
}

Testing:

3
Isotopes of the North vs. Santas 17:6 13:17 11:17
Satans vs. Isotopes of the North 17:16 17:8
Satans vs. Santas 17:15 11:17 14:17
1. Santas
2. Satans
3. Isotopes of the North
Advertisements


No Responses Yet to “U : Snowball league”

  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: