Advertisement
999ms

Untitled

Jun 29th, 2020
1,617
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.19 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.StringTokenizer;
  4. import java.util.TreeSet;
  5. public class Alphametics {
  6.    
  7.     public static int[] swap(int data[], int left, int right) {
  8.         int temp = data[left];
  9.         data[left] = data[right];
  10.         data[right] = temp;
  11.         return data;
  12.     }
  13.     public static int[] reverse(int data[], int left, int right) {
  14.         while (left < right) {
  15.             int temp = data[left];
  16.             data[left++] = data[right];
  17.             data[right--] = temp;
  18.         }
  19.         return data;
  20.     }
  21.     public static boolean findNextPermutation(int data[]) {
  22.         if (data.length <= 1)
  23.             return false;
  24.         int last = data.length - 2;
  25.         while (last >= 0) {
  26.             if (data[last] < data[last + 1]) {
  27.                 break;
  28.             }
  29.             last--;
  30.         }
  31.         if (last < 0)
  32.             return false;
  33.         int nextGreater = data.length - 1;
  34.         for (int i = data.length - 1; i > last; i--) {
  35.             if (data[i] > data[last]) {
  36.                 nextGreater = i;
  37.                 break;
  38.             }
  39.         }
  40.         data = swap(data, nextGreater, last);
  41.         data = reverse(data, last + 1, data.length - 1);
  42.         return true;
  43.     }
  44.     int getNumber(char[] arr, int[] map) {
  45.         int ans = 0;
  46.         for (int i = 0; i < arr.length; i++) {
  47.             ans *= 10;
  48.             ans += map[arr[i]];
  49.         }
  50.         return ans;
  51.     }
  52.     String s;
  53.    
  54.     public Alphametics(String s) {
  55.       this.s = s;
  56.     }
  57.    
  58.     String solve() {
  59.         String[] data = s.split(" ");
  60.         ArrayList<char[]> words = new ArrayList<>();
  61.         TreeSet<Character> letters = new TreeSet<>();
  62.         for (int i = 0; i < data.length; i += 2) {
  63.             words.add(data[i].toCharArray());
  64.             for (char ch : words.get(words.size() - 1)) {
  65.                 letters.add(ch);
  66.             }
  67.         }
  68.  
  69.         char[] p = new char[10];
  70.         int[] map = new int[256];
  71.         int f = letters.size();
  72.         for (int i = 0; letters.size() > 0; i++) {
  73.             p[i] = letters.pollFirst();
  74.             map[p[i]] = i;
  75.         }
  76.  
  77.         if (f <= 5) {
  78.             for (int a = 0; a < 10; a++) {
  79.                 for (int b = 0; b < 10; b++) {
  80.                     if (a == b) continue;
  81.                     for (int c = 0; c < 10; c++) {
  82.                         if (a == c || b == c) continue;
  83.                         for (int d = 0; d < 10; d++) {
  84.                             if (a == d || b == d || c == d) continue;
  85.                             for (int e = 0; e < 10; e++) {
  86.                                 if (a == e || b == e || d == e || c == e) continue;
  87.                                 int[] cur = new int[]{a, b, c, d, e};
  88.                                 int m = words.size();
  89.                                 for (int i = 0; i < f; i++) {
  90.                                     map[p[i]] = cur[i];
  91.                                 }
  92.  
  93.                                 long sum = 0;
  94.                                 for (int i = 0; i < m - 1; i++) {
  95.                                     sum += getNumber(words.get(i), map);
  96.                                 }
  97.                                 sum -= getNumber(words.get(m - 1), map);
  98.                                 if (sum == 0) {
  99.                                     boolean leadingZeros = false;
  100.                                     for (char[] word : words) {
  101.                                         if (word.length > 1 && map[word[0]] == 0) {
  102.                                             leadingZeros = true;
  103.                                             break;
  104.                                         }
  105.                                     }
  106.                                     if (!leadingZeros) {
  107.                                         StringBuilder answer = new StringBuilder();
  108.                                         for (int i = 0; i < m - 1; i++) {
  109.                                             answer.append(getNumber(words.get(i), map)).append(" ");
  110.                                             if (i != m - 2) {
  111.                                                 answer.append("+ ");
  112.                                             } else {
  113.                                                 answer.append("= ");
  114.                                             }
  115.                                         }
  116.                                         answer.append(getNumber(words.get(m - 1), map));
  117.                                         return answer.toString();
  118.                                     }
  119.                                 }
  120.  
  121.                             }
  122.                         }
  123.                     }
  124.                 }
  125.             }
  126.  
  127.         }
  128.  
  129.         int[] perm = new int[p.length];
  130.         for (int i = 0; i < perm.length; i++) {
  131.             perm[i] = i;
  132.         }
  133.         int m = words.size();
  134.  
  135.         for (char[] str : words) {
  136.             int n = str.length;
  137.             for (int j = 0; j < n / 2; j++) {
  138.                 char tmp = str[j];
  139.                 str[j] = str[n - 1 - j];
  140.                 str[n - 1 - j] = tmp;
  141.             }
  142.         }
  143.  
  144.        
  145.  
  146.         do {
  147.            
  148.             for (int i = 0; i < p.length; i++) {
  149.                 map[p[perm[i]]] = i;
  150.             }
  151.             boolean good = true;
  152.             int sum = 0;
  153.             for (int digit = 0; digit < 8; digit++) {
  154.                 for (int i = 0; i < m; i++) {
  155.                     if (i + 1 < m) {
  156.                         if (words.get(i).length > digit) {
  157.                             sum += map[words.get(i)[digit]];
  158.                         }
  159.                     } else {
  160.                         if (words.get(i).length > digit) {
  161.                             sum -= map[words.get(i)[digit]];
  162.                         }
  163.                     }
  164.                 }
  165.                 if (sum % 10 != 0) {
  166.                     good = false;
  167.                     break;
  168.                 }
  169.                 sum /= 10;
  170.             }
  171.             if (words.get(m - 1).length == 9) {
  172.                 sum -= map[words.get(m - 1)[8]];
  173.             }
  174.             if (good && sum == 0) {
  175.                 boolean leadingZeros = false;
  176.                 for (char[] word : words) {
  177.                     if (word.length > 1 && map[word[word.length - 1]] == 0) {
  178.                         leadingZeros = true;
  179.                         break;
  180.                     }
  181.                 }
  182.                 if (!leadingZeros) break;
  183.             }
  184.         } while (findNextPermutation(perm));
  185.         StringBuilder answer = new StringBuilder();
  186.  
  187.         for (char[] str : words) {
  188.             int n = str.length;
  189.             for (int j = 0; j < n / 2; j++) {
  190.                 char tmp = str[j];
  191.                 str[j] = str[n - 1 - j];
  192.                 str[n - 1 - j] = tmp;
  193.             }
  194.         }
  195.         for (int i = 0; i < m - 1; i++) {
  196.             answer.append(getNumber(words.get(i), map)).append(" ");
  197.             if (i != m - 2) {
  198.                 answer.append("+ ");
  199.             } else {
  200.                 answer.append("= ");
  201.             }
  202.         }
  203.         answer.append(getNumber(words.get(m - 1), map));
  204.         return answer.toString();
  205.     }
  206. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement