SHARE
TWEET

XorPuzzle

a guest Mar 29th, 2016 128 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class XorPuzzle {
  4.   static int[] noAns = {-1};
  5.  
  6.   boolean order(int x, int y, int z) {
  7.     return x <= y && y <= z;
  8.   }
  9.  
  10.   public String checkData(int n, int[] a) {
  11.     if (!order(1, a.length, 1 << n))
  12.       return "a must containt between 1 and (2 ^ k) integers, inclusive.";
  13.  
  14.     for (int x : a)
  15.       if (!order(0, 1, (1 << n) - 1))
  16.         return "Each element of a must be between 0 and (2 ^ k) - 1, inclusive.";
  17.  
  18.     return "";
  19.   }
  20.  
  21.   boolean unique(int[] a, int l, int r) {
  22.     for (int i = l; i < r; ++i)
  23.       for (int j = i + 1; j < r; ++j)
  24.         if (a[i] == a[j])
  25.           return false;
  26.     return true;
  27.   }
  28.  
  29.   public String checkAnswer(int n, int[] a, int[] ans, int[] refAns) {
  30.     if (ans.length != refAns.length)
  31.       return "The length of answer must exactly match the expected one.";
  32.  
  33.     if (refAns.length == 1)
  34.       if (ans[0] == -1)
  35.         return "";
  36.       else
  37.         return "Must be {-1}.";
  38.  
  39.     for (int x : ans)
  40.       if (!order(0, x, (1 << n) - 1))
  41.         return "Each element of ans must be between 0 and (2 ^ k) - 1, inclusive.";
  42.  
  43.     if (!unique(ans, 0, a.length) || !unique(ans, a.length, 2 * a.length))
  44.       return "Elements in b and c must be unique.";
  45.  
  46.     for (int i = 0; i < a.length; ++i)
  47.       if (a[i] != (ans[i] ^ ans[i + a.length]))
  48.         return "xor of b[" + i + "] and c[" + i + "] is not equal to a[" + i + "]";
  49.  
  50.     return "";
  51.   }
  52.  
  53.   int[] a, b, pa, c;
  54.  
  55.   void swp(int v, int u) {
  56.       //amazing swap
  57.       a[u] ^= a[v];
  58.       a[v] ^= a[u];
  59.       a[u] ^= a[v];
  60.  
  61.       int x = a[u], y = a[v];
  62.       pa[x] ^= pa[y];
  63.       pa[y] ^= pa[x];
  64.       pa[x] ^= pa[y];
  65.   }
  66.  
  67.  
  68.   public int[] find(int n, int[] input) {
  69.     assert(checkData(n, input) == "");
  70.  
  71.     int xor = 0;
  72.     for (int x : input)
  73.       xor = xor ^ x;
  74.    
  75.     if (input.length == (1 << n) && xor != 0)
  76.       return noAns;
  77.  
  78.     a = new int[1 << n];
  79.     pa = new int[1 << n];
  80.     b = new int[1 << n];
  81.     c = new int[1 << n];
  82.  
  83.     for (int i = 0; i < (1 << n); ++i)
  84.       a[i] = b[i] = pa[i] = i;
  85.  
  86.     for (int i = 0; i < input.length; ++i)
  87.       c[i] = input[i];
  88.     if (xor != 0)
  89.       c[input.length] = xor;
  90.  
  91.     //solution always exist at this point
  92.  
  93.     for (int i = 0; i < (1 << n); ++i) {
  94.       int u = i;
  95.       while ((a[u] ^ b[u]) != c[u]) {
  96.  
  97.         int v = -1;
  98.         /*
  99.         for (int j = 0; j < (1 << n); ++j)
  100.           if ((a[j] ^ b[u]) == c[u])
  101.             v = j;
  102.         */
  103.  
  104.         v = pa[b[u] ^ c[u]];
  105.  
  106.         assert(v != pa[b[u] ^ c[u]]);
  107.  
  108.         swp(u, v);
  109.  
  110.         if (v > i)
  111.           break;
  112.         else {
  113.           //here it goes again
  114.           b[v] ^= b[i + 1];
  115.           b[i + 1] ^= b[v];
  116.           b[v] ^= b[i + 1];
  117.           u = v;
  118.         }
  119.       }
  120.     }
  121.    
  122.     int[] ans = new int[2 * input.length];
  123.     for (int i = 0; i < input.length; ++i) {
  124.       ans[i] = a[i];
  125.       ans[i + input.length] = b[i];
  126.     }
  127.    
  128.     /*
  129.     for (int i = 0; i < input.length; ++i) {
  130.       System.out.print(a[i]);
  131.       System.out.print(" ");
  132.       System.out.print(b[i]);
  133.       System.out.print(" ");
  134.       System.out.println(c[i]);
  135.     }
  136.     */
  137.  
  138.     return ans;
  139.   }
  140.  
  141.   public static void main(String[] args) {
  142.     XorPuzzle solver = new XorPuzzle();
  143.     int n = 2;
  144.     int[] a = {2, 2, 0, 0};
  145.     solver.find(n, a);
  146.   }
  147. };
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