Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.ArrayList;
- import java.util.StringTokenizer;
- import java.util.TreeSet;
- public class Alphametics {
- public static int[] swap(int data[], int left, int right) {
- int temp = data[left];
- data[left] = data[right];
- data[right] = temp;
- return data;
- }
- public static int[] reverse(int data[], int left, int right) {
- while (left < right) {
- int temp = data[left];
- data[left++] = data[right];
- data[right--] = temp;
- }
- return data;
- }
- public static boolean findNextPermutation(int data[]) {
- if (data.length <= 1)
- return false;
- int last = data.length - 2;
- while (last >= 0) {
- if (data[last] < data[last + 1]) {
- break;
- }
- last--;
- }
- if (last < 0)
- return false;
- int nextGreater = data.length - 1;
- for (int i = data.length - 1; i > last; i--) {
- if (data[i] > data[last]) {
- nextGreater = i;
- break;
- }
- }
- data = swap(data, nextGreater, last);
- data = reverse(data, last + 1, data.length - 1);
- return true;
- }
- int getNumber(char[] arr, int[] map) {
- int ans = 0;
- for (int i = 0; i < arr.length; i++) {
- ans *= 10;
- ans += map[arr[i]];
- }
- return ans;
- }
- String s;
- public Alphametics(String s) {
- this.s = s;
- }
- String solve() {
- String[] data = s.split(" ");
- ArrayList<char[]> words = new ArrayList<>();
- TreeSet<Character> letters = new TreeSet<>();
- for (int i = 0; i < data.length; i += 2) {
- words.add(data[i].toCharArray());
- for (char ch : words.get(words.size() - 1)) {
- letters.add(ch);
- }
- }
- char[] p = new char[10];
- int[] map = new int[256];
- int f = letters.size();
- for (int i = 0; letters.size() > 0; i++) {
- p[i] = letters.pollFirst();
- map[p[i]] = i;
- }
- if (f <= 5) {
- for (int a = 0; a < 10; a++) {
- for (int b = 0; b < 10; b++) {
- if (a == b) continue;
- for (int c = 0; c < 10; c++) {
- if (a == c || b == c) continue;
- for (int d = 0; d < 10; d++) {
- if (a == d || b == d || c == d) continue;
- for (int e = 0; e < 10; e++) {
- if (a == e || b == e || d == e || c == e) continue;
- int[] cur = new int[]{a, b, c, d, e};
- int m = words.size();
- for (int i = 0; i < f; i++) {
- map[p[i]] = cur[i];
- }
- long sum = 0;
- for (int i = 0; i < m - 1; i++) {
- sum += getNumber(words.get(i), map);
- }
- sum -= getNumber(words.get(m - 1), map);
- if (sum == 0) {
- boolean leadingZeros = false;
- for (char[] word : words) {
- if (word.length > 1 && map[word[0]] == 0) {
- leadingZeros = true;
- break;
- }
- }
- if (!leadingZeros) {
- StringBuilder answer = new StringBuilder();
- for (int i = 0; i < m - 1; i++) {
- answer.append(getNumber(words.get(i), map)).append(" ");
- if (i != m - 2) {
- answer.append("+ ");
- } else {
- answer.append("= ");
- }
- }
- answer.append(getNumber(words.get(m - 1), map));
- return answer.toString();
- }
- }
- }
- }
- }
- }
- }
- }
- int[] perm = new int[p.length];
- for (int i = 0; i < perm.length; i++) {
- perm[i] = i;
- }
- int m = words.size();
- for (char[] str : words) {
- int n = str.length;
- for (int j = 0; j < n / 2; j++) {
- char tmp = str[j];
- str[j] = str[n - 1 - j];
- str[n - 1 - j] = tmp;
- }
- }
- do {
- for (int i = 0; i < p.length; i++) {
- map[p[perm[i]]] = i;
- }
- boolean good = true;
- int sum = 0;
- for (int digit = 0; digit < 8; digit++) {
- for (int i = 0; i < m; i++) {
- if (i + 1 < m) {
- if (words.get(i).length > digit) {
- sum += map[words.get(i)[digit]];
- }
- } else {
- if (words.get(i).length > digit) {
- sum -= map[words.get(i)[digit]];
- }
- }
- }
- if (sum % 10 != 0) {
- good = false;
- break;
- }
- sum /= 10;
- }
- if (words.get(m - 1).length == 9) {
- sum -= map[words.get(m - 1)[8]];
- }
- if (good && sum == 0) {
- boolean leadingZeros = false;
- for (char[] word : words) {
- if (word.length > 1 && map[word[word.length - 1]] == 0) {
- leadingZeros = true;
- break;
- }
- }
- if (!leadingZeros) break;
- }
- } while (findNextPermutation(perm));
- StringBuilder answer = new StringBuilder();
- for (char[] str : words) {
- int n = str.length;
- for (int j = 0; j < n / 2; j++) {
- char tmp = str[j];
- str[j] = str[n - 1 - j];
- str[n - 1 - j] = tmp;
- }
- }
- for (int i = 0; i < m - 1; i++) {
- answer.append(getNumber(words.get(i), map)).append(" ");
- if (i != m - 2) {
- answer.append("+ ");
- } else {
- answer.append("= ");
- }
- }
- answer.append(getNumber(words.get(m - 1), map));
- return answer.toString();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement