Guest User

L'union fait la force

a guest
Jan 22nd, 2016
85
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package unionfaitlaforce;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  *
  7.  * @author alain
  8.  */
  9. public class UnionFaitLaForce {
  10.  
  11.     static final int FREE = 0, SELECTED = 1, FORBIDDEN = 2;
  12.     int[][] input = new int[][]{
  13.         {0, 2, 7, 7, 7, 8, 4, 3, 0, 9},
  14.         {0, 3, 1, 9, 6, 2, 0, 9, 4, 0},
  15.         {0, 5, 9, 2, 5, 7, 8, 1, 3, 6},
  16.         {0, 8, 0, 3, 3, 2, 3, 6, 5, 7},
  17.         {0, 8, 3, 1, 8, 4, 2, 6, 2, 8},
  18.         {1, 0, 5, 4, 9, 3, 7, 5, 3, 9},
  19.         {1, 1, 8, 2, 8, 2, 4, 0, 9, 3},
  20.         {1, 2, 5, 1, 2, 7, 6, 7, 8, 5},
  21.         {1, 4, 2, 1, 5, 3, 1, 7, 0, 4},
  22.         {2, 0, 8, 3, 4, 8, 5, 1, 5, 5},
  23.         {2, 3, 2, 7, 1, 3, 2, 1, 8, 3},
  24.         {2, 6, 5, 2, 7, 5, 3, 9, 2, 4},
  25.         {2, 9, 4, 4, 1, 1, 4, 7, 7, 6},
  26.         {3, 0, 7, 2, 2, 1, 9, 8, 6, 1},
  27.         {4, 1, 2, 8, 7, 4, 6, 5, 1, 6},
  28.         {4, 5, 0, 6, 6, 8, 2, 8, 5, 5},
  29.         {5, 6, 2, 9, 8, 7, 7, 3, 7, 8},
  30.         {7, 1, 0, 7, 1, 7, 1, 5, 2, 0},
  31.         {7, 8, 2, 9, 2, 3, 4, 1, 2, 7},
  32.         {8, 1, 9, 1, 7, 0, 7, 8, 8, 7},
  33.         {8, 3, 1, 4, 5, 1, 6, 3, 2, 3},
  34.         {8, 5, 1, 1, 1, 3, 6, 3, 9, 4},
  35.         {9, 7, 1, 0, 0, 5, 4, 6, 3, 2}
  36.     };
  37.     /*int[][] input = new int[][]{
  38.         { 0, 7, 3, 4, 4},
  39.         { 1, 4, 0, 9, 8},
  40.         { 2, 7, 3, 5, 6},
  41.         { 3, 6, 4, 2, 9},
  42.         { 4, 5, 3, 7, 4},
  43.         { 5, 2, 2, 0, 7},
  44.         { 6, 3, 8, 2, 2},
  45.         { 7, 0, 5, 5, 8},
  46.         { 8, 5, 2, 3, 7},
  47.         { 9, 7, 6, 6, 5}
  48.     };*/
  49.     int[][] occurrences, status;
  50.     int[] max;
  51.  
  52.     public static void main(String[] args) {
  53.         long startTime = System.currentTimeMillis();
  54.         for (int i = 0; i < 1000; i++) {
  55.             UnionFaitLaForce union = new UnionFaitLaForce();
  56.             union.init();
  57.             union.iterate();
  58.         }
  59.         System.out.println(System.currentTimeMillis() - startTime);
  60.     }
  61.  
  62.     private void init() {
  63.         status = new int[10][input[0].length];
  64.         computeOcurrences();
  65.     }
  66.  
  67.     private void print(int[][] input) {
  68.         for (int row = 0; row < input.length; row++) {
  69.             for (int col = 0; col < input[0].length; col++) {
  70.                 System.out.print(input[row][col] + " ");
  71.             }
  72.             System.out.println("");
  73.         }
  74.     }
  75.  
  76.     private void computeOcurrences() {
  77.         occurrences = new int[10][input[0].length];
  78.         for (int row = 0; row < input.length; row++) {
  79.             for (int col = 0; col < input[0].length; col++) {
  80.                 occurrences[input[row][col]][col]++;
  81.             }
  82.         }
  83.     }
  84.  
  85.     private void iterate() {
  86.         while (sumMaxes() >= input.length) {
  87.             int d = 0, c = 0, max = -1;
  88.             for (int digit = 0; digit < occurrences.length; digit++) {
  89.                 for (int col = 0; col < occurrences[0].length; col++) {
  90.                     if (occurrences[digit][col] > max && status[digit][col] == FREE) {
  91.                         max = occurrences[digit][col];
  92.                         d = digit;
  93.                         c = col;
  94.                     }
  95.                 }
  96.             }
  97.             if (max >= 0) {
  98.                 int[][] statusCopy = deepCopy(status);
  99.                 select(d, c);
  100.                 iterate();
  101.                 status = deepCopy(statusCopy);
  102.                 status[d][c] = FORBIDDEN;
  103.             } else {
  104.                 System.out.println("Found");
  105.                 for (int col = 0; col < status[0].length; col++) {
  106.                     for (int digit = 0; digit < status.length; digit++) {
  107.                         if (status[digit][col] == SELECTED) {
  108.                             System.out.print(digit + " ");
  109.                         }
  110.                     }
  111.                 }
  112.                 System.out.println();
  113.                 break;
  114.             }
  115.         }
  116.     }
  117.  
  118.     private int sumMaxes() {
  119.         max = new int[input[0].length];
  120.         int sum = 0;
  121.         for (int col = 0; col < occurrences[0].length; col++) {
  122.             for (int digit = 0; digit < occurrences.length; digit++) {
  123.                 if (status[digit][col] != FORBIDDEN) {
  124.                     max[col] = occurrences[digit][col] < max[col] ? max[col] : occurrences[digit][col];
  125.                 }
  126.             }
  127.             sum += max[col];
  128.         }
  129.         return sum;
  130.     }
  131.  
  132.     private void select(int d, int c) {
  133.         status[d][c] = SELECTED;
  134.         for (int digit = 0; digit < occurrences.length; digit++) {
  135.             if (d != digit) {
  136.                 status[digit][c] = FORBIDDEN;
  137.             }
  138.         }
  139.         for (int row = 0; row < input.length; row++) {
  140.             if (input[row][c] == d) {
  141.                 for (int col = 0; col < input[0].length; col++) {
  142.                     if (col != c) {
  143.                         status[input[row][col]][col] = FORBIDDEN;
  144.                     }
  145.                 }
  146.             }
  147.         }
  148.     }
  149.  
  150.     private int[][] deepCopy(int[][] original) {
  151.         final int[][] result = new int[original.length][];
  152.         for (int i = 0; i < original.length; i++) {
  153.             result[i] = Arrays.copyOf(original[i], original[i].length);
  154.         }
  155.         return result;
  156.     }
  157. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×