# TheTileGame

Jun 20th, 2011
1,487
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }