S : Word search

19Dec13

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 (S; easy difficulty):

Word search

Advent Programming Contest 2013 - S

Help Santa to solve the word search riddle in the Daily North Pole paper. Words can appear horizontally, vertically, diagonal; in all directions forward or backward.

Problem

Your program shall read one line with two integers seperated by space, those are width and height of the raster. Then you program should read the characters of the raster, no spacing, one line for each row. In the last line the program gets a comma-seperated list of word to search for. All text are uppercase characters. You program should output the set of all the words that have been found at least once, in alphabetical order seperated by commas.

Example

Input

6 7
YSQNER
RAAALU
RENNAD
EERYTI
MDEERA
BLIXEN
NORTHP
SANTA,BLIXEN,RUDOLPH,NORTHPOLE

Output

BLIXEN,SANTA

Solution (S.java):

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

public class S
{
  private static char c[][];

  public static void main( String p[] )
  {
    Scanner s = new Scanner( System.in );
    String l = s.nextLine();
    int i = l.indexOf( ' ' );
    final int W = Integer.parseInt( l.substring( 0, i ));
    final int H = Integer.parseInt( l.substring( i + 1, l.length()));
    c = new char[ H ][ W ];
    for( int y = 0; y < H; y ++ )
    {
      l = s.nextLine();
      for( int x = 0; x < W; x ++ )
        c[ y ][ x ] = l.charAt( x );
    }
    l = s.nextLine();
    int k = 0;
    ArrayList<String> words_to_find = new ArrayList<String>();
    do
    {
      i = l.indexOf( ',', k );
      if( i == -1 )
        i = l.length();
      words_to_find.add( l.substring( k, i ));
      k = i + 1;
    }
    while( i < l.length());

    ArrayList<Integer> words_found = new ArrayList<Integer>();
    for( i = 0; i < words_to_find.size(); i ++ )
    {
      boolean found = false;
      final String word = words_to_find.get( i );
      final String word_reversed = reverse( word );

      for( int y = 0; y < H && !found; y ++ )
        for( int x = 0; x < W - ( word.length() - 1 ) && !found; x ++ )
          found = isWordInArray( x, y, 1, 0, word, word_reversed );

      for( int x = 0; x < W && !found; x ++ )
        for( int y = 0; y < H - ( word.length() - 1 ) && !found; y ++ )
          found = isWordInArray( x, y, 0, 1, word, word_reversed );

      for( int y = 0; y < H - ( word.length() - 1 ) && !found; y ++ )
        for( int x = 0; x < W - ( word.length() - 1 ) && !found; x ++ )
          found = isWordInArray( x, y, 1, 1, word, word_reversed );

      for( int y = 0; y < H - ( word.length() - 1 ) && !found; y ++ )
        for( int x = W - 1; x >= ( word.length() - 1 ) && !found; x -- )
          found = isWordInArray( x, y, -1, 1, word, word_reversed );

      if( found && !intIsAlreadyInArrayList( i, words_found ))
        words_found.add( new Integer( i ));
    }
    String words_found_sorted[] = new String[ words_found.size() ];
    for( i = 0; i < words_found.size(); i ++ )
      words_found_sorted[ i ] = words_to_find.get( words_found.get( i ).intValue());
    boolean sort_occurred;
    do
    {
      sort_occurred = false;
      for( i = 0; i < words_found_sorted.length - 1; i ++ )
        if( words_found_sorted[ i ].compareTo( words_found_sorted[ i + 1 ] ) > 0 )
        {
          sort_occurred = true;
          final String w = words_found_sorted[ i ];
          words_found_sorted[ i ] = words_found_sorted[ i + 1 ];
          words_found_sorted[ i + 1 ] = w;
        }
    }
    while( sort_occurred );
    for( i = 0; i < words_found_sorted.length; i ++ )
    {
      System.out.print( words_found_sorted[ i ] );
      if( i + 1 < words_found_sorted.length )
        System.out.print( "," );
    }
    System.out.println();
  }

  private static String reverse( String p )
  {
    String s = "";
    for( int i = p.length() - 1; i >= 0; i -- )
      s += p.charAt( i );
    return s;
  }

  private static boolean isWordInArray( int x, int y, int x_step, int y_step, String word, String word_reversed )
  {
    String s = "";
    for( ; s.length() < word.length(); x += x_step, y += y_step )
      s += c[ y ][ x ];
    return word.equals( s ) || word_reversed.equals( s );
  }

  private static boolean intIsAlreadyInArrayList( int p_int, ArrayList<Integer> p_arrayList )
  {
    for( Integer i : p_arrayList )
      if( p_int == i.intValue())
        return true;
    return false;
  }
}

Testing:

6 7
YSQNER
RAAALU
RENNAD
EERYTI
MDEERA
BLIXEN
NORTHP
SANTA,BLIXEN,RUDOLPH,NORTHPOLE
BLIXEN,SANTA
Advertisements


No Responses Yet to “S : Word search”

  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: