daily pastebin goal
68%
SHARE
TWEET

TheTileGame

alefhidalgo Jun 20th, 2011 700 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.InputStreamReader;
  2. import java.io.UnsupportedEncodingException;
  3. import java.util.Scanner;
  4.  
  5. /**
  6.  * Tuenti Programming Contest
  7.  * Challenge 7: The Tile Game
  8.  * @author alefhidalgo [at] gmail [dot] com
  9.  */
  10. public class TheTileGame {
  11.        
  12.         public int levenshtein(char[] string1, char[] string2, int costSub, int costIn, int costDel) {
  13.                 int len1 = string1.length;
  14.                 int len2 = string2.length;
  15.                 int[] row0 = new int[len2 + 1];
  16.                 int[] row1 = new int[len2 + 1];
  17.                 int[] row2 = new int[len2 + 1];
  18.                 int i, j;
  19.  
  20.                 for (j = 0; j <= len2; j++)
  21.                         row1[j] = j * costIn;
  22.                 for (i = 0; i < len1; i++) {
  23.                         int[] dummy;
  24.  
  25.                         row2[0] = (i + 1) * costDel;
  26.                         for (j = 0; j < len2; j++) {
  27.                                 /* substitution */
  28.                                 row2[j + 1] = row1[j] + costSub
  29.                                                 * ((string1[i] != string2[j]) ? 1 : 0);
  30.                                 /* deletion */
  31.                                 if (row2[j + 1] > row1[j + 1] + costDel)
  32.                                         row2[j + 1] = row1[j + 1] + costDel;
  33.                                 /* insertion */
  34.                                 if (row2[j + 1] > row2[j] + costIn)
  35.                                         row2[j + 1] = row2[j] + costIn;
  36.                         }
  37.  
  38.                         dummy = row0;
  39.                         row0 = row1;
  40.                         row1 = row2;
  41.                         row2 = dummy;
  42.                 }
  43.  
  44.                 i = row1[len2];
  45.  
  46.                 return i;
  47.         }
  48.  
  49.  
  50.         public static void main(String args[]) throws UnsupportedEncodingException {           
  51.                 TheTileGame theTileGame = new TheTileGame();
  52.                 Scanner in = new Scanner(new InputStreamReader(System.in, "UTF-8"));   
  53.                 Scanner lineScanner = null;
  54.                 Scanner intScanner = null;
  55.                 String tileA = null;
  56.                 String tileB = null;
  57.                 int costIn, costDel, costSub;
  58.                 while (in.hasNextLine()) {
  59.                         lineScanner = new Scanner(in.nextLine());
  60.                         tileA = ""+lineScanner.next();
  61.                         tileB= ""+lineScanner.next();
  62.                         intScanner = new Scanner(lineScanner.next());
  63.                         intScanner.useDelimiter(",");
  64.                         costIn = intScanner.nextInt();
  65.                         costDel = intScanner.nextInt();
  66.                         costSub = intScanner.nextInt();        
  67.                         System.out.println(theTileGame.levenshtein(tileA.toCharArray(), tileB.toCharArray(), costSub, costIn, costDel));                       
  68.                 }
  69.                
  70.         }
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top