Advertisement
alefhidalgo

TheTileGame

Jun 20th, 2011
1,259
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.92 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement