API tools faq
paste
Advertisement
anas_harby

Untitled

anas_harby
Apr 30th, 2016
72
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 15.66 KB | None | 0 0
raw download clone embed print report
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.Scanner;
  5.  
  6. // TODO: Auto-generated Javadoc
  7. /**
  8.  * The Class Solver.
  9.  */
  10. public class Solver {
  11.  
  12.     /** The minterms. */
  13.     static ArrayList<Integer> minterms = new ArrayList<Integer>();
  14.    
  15.     /** The dontcares. */
  16.     static ArrayList<Integer> dontcares = new ArrayList<Integer>();
  17.    
  18.     /** The comparisons. */
  19.     static ArrayList<ArrayList<ArrayList<String>>> comparisons = new ArrayList<ArrayList<ArrayList<String>>>();
  20.    
  21.     /** The essential prime implicants. */
  22.     static ArrayList<String> essentialPrimeImplicants = new ArrayList<String>();
  23.    
  24.     /** The minterms apperancescount. */
  25.     static int[][] mintermsApperancescount;
  26.    
  27.     /** The prime implicants. */
  28.     static ArrayList<String> primeImplicants = new ArrayList<String>();
  29.  
  30.     /** The combination. */
  31.     static String[] combination = new String[26];
  32.  
  33.     /** The Maxnumber of_ vars. */
  34.     static int MaxnumberOf_Vars;
  35.    
  36.     /** The found combination. */
  37.     static boolean foundCombination = false;
  38.  
  39.     /** The in. */
  40.     static Scanner in = new Scanner(System.in);
  41.  
  42.     /**
  43.      * Fill array list.
  44.      */
  45.     private static void fillArrayList() {
  46.         for (int i = 0; i < 26; i++) {
  47.             comparisons.add(new ArrayList()); // comparisons
  48.             for (int j = 0; j <= MaxnumberOf_Vars; j++)
  49.                 comparisons.get(i).add(new ArrayList()); // groups
  50.         }
  51.     }
  52.  
  53.     /**
  54.      * Find_num ofvars.
  55.      *
  56.      * @return the int
  57.      */
  58.     private static int find_numOfvars() {
  59.         int maxMinterm = 0, maxDontCare = 0;
  60.         if (minterms.isEmpty() == false)
  61.             maxMinterm = Collections.max(minterms);
  62.         if (dontcares.isEmpty() == false)
  63.             maxDontCare = Collections.max(dontcares);
  64.  
  65.         int maxImplicant = Math.max(maxDontCare, maxMinterm);
  66.         String binary = Integer.toBinaryString(maxImplicant);
  67.         return binary.length();
  68.     }
  69.  
  70.     /**
  71.      * Differ binary.
  72.      *
  73.      * @param firstMinterm the first minterm
  74.      * @param secondMinterm the second minterm
  75.      * @return the string
  76.      */
  77.     private static String differBinary(String firstMinterm, String secondMinterm) {
  78.         String result = "";
  79.         int ones = 0;
  80.         for (int i = 0; i < firstMinterm.length(); i++) {
  81.             if (firstMinterm.charAt(i) != secondMinterm.charAt(i))
  82.                 result += "-";
  83.             else
  84.                 result += firstMinterm.charAt(i);
  85.             if (firstMinterm.charAt(i) == '1')
  86.                 ones++;
  87.         }
  88.         return result + " " + String.valueOf(ones);
  89.     }
  90.  
  91.     /**
  92.      * Decimal to binary.
  93.      */
  94.     private static void decimalToBinary() {
  95.  
  96.         for (int i = 0; i < minterms.size(); i++) {
  97.             int div = minterms.get(i), ones = 0;
  98.             String res = "";
  99.             while (div != 0) {
  100.                 if (div % 2 == 1) {
  101.                     ones++;
  102.                     res = "1" + res;
  103.                 } else
  104.                     res = "0" + res;
  105.                 div /= 2;
  106.             }
  107.             for (int j = 0, len = res.length(); j < MaxnumberOf_Vars - len; j++)
  108.                 res = "0" + res;
  109.             comparisons.get(0).get(ones).add(res + " " + Integer.parseInt(res, 2));
  110.         }
  111.         for (int i = 0; i < dontcares.size(); i++) {
  112.             int div = dontcares.get(i), ones = 0;
  113.             String res = "";
  114.             while (div != 0) {
  115.                 if (div % 2 == 1) {
  116.                     ones++;
  117.                     res = "1" + res;
  118.                 } else
  119.                     res = "0" + res;
  120.                 div /= 2;
  121.             }
  122.             for (int j = 0, len = res.length(); j < MaxnumberOf_Vars - len; j++)
  123.                 res = "0" + res;
  124.             comparisons.get(0).get(ones).add(res + " " + Integer.parseInt(res, 2));
  125.         }
  126.         for (int i = 0; i < comparisons.get(0).size(); i++)
  127.             Collections.sort(comparisons.get(0).get(i));
  128.     }
  129.  
  130.     /**
  131.      * Do comparisons.
  132.      */
  133.     private static void doComparisons() {
  134.         int k;
  135.         for (k = 0; k < comparisons.size() - 1; k++) { // comparisons
  136.             boolean[][] takenToNextComparison = new boolean[10][100];
  137.             for (int l = 0; l < comparisons.get(k).size(); l++) { // groups
  138.                 if (comparisons.get(k).get(l).isEmpty())
  139.                     continue;
  140.                 int m = l + 1;
  141.  
  142.                 while (m < comparisons.get(k).size() && comparisons.get(k).get(m).isEmpty())
  143.                     m++;
  144.                 if (m == comparisons.get(k).size()) {
  145.                     for (int i = 0; i < comparisons.get(k).get(l).size(); i++) {
  146.                         if (!takenToNextComparison[l][i]) {
  147.                             ArrayList<String> iData = new ArrayList<String>();
  148.                             for (String retval : comparisons.get(k).get(l).get(i).split(" "))
  149.                                 iData.add(retval);
  150.                             String info = iData.get(0);
  151.                             for (int x = 1; x < iData.size(); x++)
  152.                                 info += " " + iData.get(x);
  153.                             primeImplicants.add(info);
  154.                         }
  155.                     }
  156.                     break;
  157.                 }
  158.                 for (int i = 0; i < comparisons.get(k).get(l).size(); i++) {
  159.                     boolean fPrime = true;
  160.                     ArrayList<String> iData = new ArrayList<String>();
  161.                     for (String retval : comparisons.get(k).get(l).get(i).split(" "))
  162.                         iData.add(retval);
  163.                     for (int j = 0; j < comparisons.get(k).get(m).size(); j++) {
  164.                         ArrayList<String> jData = new ArrayList<String>();
  165.                         for (String retval : comparisons.get(k).get(m).get(j).split(" "))
  166.                             jData.add(retval);
  167.                         float exponent = 0;
  168.                         int difference = 0;
  169.                         boolean fAccept = true;
  170.                         for (int x = 1; x < iData.size(); x++) {
  171.                             int iDifference = Integer.parseInt(iData.get(x));
  172.                             int jDifference = Integer.parseInt(jData.get(x));
  173.                             int tempDifference = jDifference - iDifference;
  174.                             float tempExponent = (float) (Math.log(tempDifference) / Math.log(2));
  175.                             if (x == 1) {
  176.                                 difference = tempDifference;
  177.                                 exponent = tempExponent;
  178.                                 if (difference < 0 || exponent - (int) exponent != 0) {
  179.                                     fAccept = false;
  180.                                     break;
  181.                                 }
  182.                             } else {
  183.                                 if (tempDifference != difference || tempExponent != exponent) {
  184.                                     fAccept = false;
  185.                                     break;
  186.                                 }
  187.                             }
  188.                         }
  189.                         if (fAccept) {
  190.                             fPrime = false;
  191.                             String iBinary = iData.get(0);
  192.                             String jBinary = jData.get(0);
  193.                             takenToNextComparison[l][i] = true;
  194.                             takenToNextComparison[m][j] = true;
  195.                             ArrayList<String> dashesAndOnes = new ArrayList<String>();
  196.                             for (String retval : differBinary(iBinary, jBinary).split(" "))
  197.                                 dashesAndOnes.add(retval);
  198.                             String differenceBinary = dashesAndOnes.get(0);
  199.                             int ones = Integer.parseInt(dashesAndOnes.get(1));
  200.                             boolean fDuplicate = false;
  201.                             for (int x = 0; x < comparisons.get(k + 1).size(); x++) {
  202.                                 for (int y = 0; y < comparisons.get(k + 1).get(x).size(); y++) {
  203.                                     String duplicate = comparisons.get(k + 1).get(x).get(y).split(" ")[0];
  204.                                     if (duplicate.equals(differenceBinary)) {
  205.                                         fDuplicate = true;
  206.                                         break;
  207.                                     }
  208.                                 }
  209.                             }
  210.                             if (!fDuplicate) {
  211.                                 String info = differenceBinary;
  212.                                 for (int x = 1; x < iData.size(); x++) {
  213.                                     info += " " + iData.get(x);
  214.                                 }
  215.                                 for (int x = 1; x < jData.size(); x++) {
  216.                                     info += " " + jData.get(x);
  217.                                 }
  218.                                 comparisons.get(k + 1).get(ones).add(info);
  219.                             } else
  220.                                 continue;
  221.  
  222.                         }
  223.                     }
  224.                     if (fPrime && !takenToNextComparison[l][i]) {
  225.                         String info = iData.get(0);
  226.                         for (int x = 1; x < iData.size(); x++)
  227.                             info += " " + iData.get(x);
  228.                         primeImplicants.add(info);
  229.                     }
  230.  
  231.                 }
  232.             }
  233.         }
  234.         for (int i = 0; i < comparisons.get(k).size(); i++) // groups
  235.             for (int j = 0; j < comparisons.get(k).get(i).size(); j++) {
  236.                 ArrayList<String> data = new ArrayList<String>();
  237.                 for (String retval : comparisons.get(k).get(i).get(j).split(" "))
  238.                     data.add(retval);
  239.                 String info = data.get(0);
  240.                 for (int x = 1; x < data.size(); x++)
  241.                     info += " " + data.get(x);
  242.                 primeImplicants.add(info);
  243.             }
  244.     }
  245.  
  246.     /**
  247.      * Find_ expression.
  248.      *
  249.      * @param a the a
  250.      * @return the string
  251.      */
  252.     private static String find_Expression(ArrayList a) {
  253.         String expression = new String();
  254.         ;
  255.         StringBuilder Dashes_expression = null;
  256.         StringBuilder expression_Builder = new StringBuilder();
  257.         /// I want to know the maximum estimated number of variables;
  258.  
  259.         for (int i = 0; i < a.size(); i++) {
  260.             for (String retval : ((String) a.get(i)).split(" ")) {
  261.                 Dashes_expression = new StringBuilder();
  262.                 Dashes_expression.append(retval);
  263.                 break;
  264.             }
  265.  
  266.             for (int j = 0; j < Dashes_expression.length(); j++) {
  267.                 if (Dashes_expression.charAt(j) == '1') {
  268.                     char character = (char) ((int) ('A') + j);
  269.                     expression_Builder.append(character);
  270.                 } else if (Dashes_expression.charAt(j) == '0') {
  271.                     char character = (char) ((int) ('A') + j);
  272.                     String str = new String();
  273.                     str += character + "'";
  274.                     expression_Builder.append(str);
  275.  
  276.                 }
  277.  
  278.             }
  279.             if (i != (a.size() - 1))
  280.                 expression_Builder.append(" + ");
  281.         }
  282.  
  283.         expression = expression_Builder.toString();
  284.         return expression;
  285.     }
  286.  
  287.     /**
  288.      * Check combination.
  289.      *
  290.      * @param len the len
  291.      * @return true, if successful
  292.      */
  293.     private static boolean checkCombination(int len) {
  294.         ArrayList<Integer> checkedMinterms = new ArrayList<Integer>();
  295.  
  296.         for (int i = 0; i < len; i++) {
  297.             ArrayList<String> data = new ArrayList<String>();
  298.             for (String retval : combination[i].split(" "))
  299.                 data.add(retval);
  300.             for (int j = 1; j < data.size(); j++)
  301.                 checkedMinterms.add(Integer.parseInt(data.get(j)));
  302.         }
  303.         if (checkedMinterms.containsAll(minterms))
  304.             return true;
  305.         else
  306.             return false;
  307.     }
  308.  
  309.     /**
  310.      * Count_the appearnces.
  311.      */
  312.     private static void count_theAppearnces() {
  313.         StringBuilder str2;
  314.         int foundFlag = 0;
  315.         mintermsApperancescount = new int[minterms.size()][2];
  316.         for (int i = 0; i < minterms.size(); i++) {
  317.             mintermsApperancescount[i][0] = minterms.get(i);
  318.  
  319.         }
  320.         for (int i = 0; i < primeImplicants.size(); i++) {
  321.             String str = primeImplicants.get(i).split(" ", 2)[1];
  322.             str2 = new StringBuilder();
  323.             for (int j = 0; j <= str.length(); j++) {
  324.                 foundFlag = 0;
  325.                 if ((j != str.length()) && (str.charAt(j) != ' ')) {
  326.                     str2.append(str.charAt(j));
  327.  
  328.                 } else {
  329.                     int vaL = Integer.parseInt(str2.toString());
  330.                     for (int k = 0; k < mintermsApperancescount.length; k++) {
  331.                         if (vaL == mintermsApperancescount[k][0]) {
  332.                             foundFlag = 1;
  333.                             mintermsApperancescount[k][1]++;
  334.                             str2 = new StringBuilder();
  335.                             break;
  336.  
  337.                         }
  338.                     }
  339.                     if (foundFlag == 0)
  340.                         str2 = new StringBuilder();
  341.  
  342.                 }
  343.             }
  344.         }
  345.  
  346.     }
  347.  
  348.     /**
  349.      * Hunt_the rest.
  350.      *
  351.      * @return true, if successful
  352.      */
  353.     private static boolean hunt_theRest() {
  354.         int countZeros = 0;
  355.  
  356.         for (int i = 0; i < mintermsApperancescount.length; i++) {
  357.             if (mintermsApperancescount[i][1] == 0) {
  358.                 for (int j = 0; j < minterms.size(); j++) {
  359.                     if (mintermsApperancescount[i][0] == minterms.get(j)) {
  360.                         minterms.remove(j);
  361.                         break;
  362.                     }
  363.  
  364.                 }
  365.                 countZeros++;
  366.             }
  367.         }
  368.         if (countZeros == mintermsApperancescount.length) {
  369.             return true;
  370.         } else {
  371.             return false;
  372.         }
  373.     }
  374.  
  375.     /**
  376.      * Thefinal_expression.
  377.      */
  378.     private static void thefinal_expression() {
  379.         int uniqueMinterm, foundFlag = 0;
  380.         StringBuilder str2;
  381.  
  382.         for (int i = 0; i < mintermsApperancescount.length; i++) {
  383.             if (mintermsApperancescount[i][1] == 1) {
  384.                 uniqueMinterm = mintermsApperancescount[i][0];
  385.                 for (int j = 0; j < primeImplicants.size(); j++) {
  386.                     String str = primeImplicants.get(j).split(" ", 2)[1];
  387.                     str2 = new StringBuilder();
  388.                     for (int k = 0; k <= str.length(); k++) {
  389.                         if ((k != str.length()) && (str.charAt(k) != ' ')) {
  390.                             str2.append(str.charAt(k));
  391.  
  392.                         } else if (((k != str.length()) && (str.charAt(k) == ' ')) || (k == (str.length()))) {
  393.                             int value = Integer.parseInt(str2.toString());
  394.                             if (value == uniqueMinterm) {
  395.                                 essentialPrimeImplicants.add(primeImplicants.get(j));
  396.                                 primeImplicants.remove(j);
  397.                                 str2 = new StringBuilder();
  398.                                 for (int u = 0; u <= str.length(); u++) {
  399.                                     foundFlag = 0;
  400.                                     if ((u != str.length()) && (str.charAt(u) != ' ')) {
  401.                                         str2.append(str.charAt(u));
  402.  
  403.                                     } else {
  404.                                         int vaL = Integer.parseInt(str2.toString());
  405.                                         for (int m = 0; m < mintermsApperancescount.length; m++) {
  406.                                             if (vaL == mintermsApperancescount[m][0]) {
  407.                                                 foundFlag = 1;
  408.                                                 mintermsApperancescount[m][1] = 0;
  409.                                                 str2 = new StringBuilder();
  410.                                                 ;
  411.                                                 break;
  412.  
  413.                                             }
  414.                                         }
  415.                                         if (foundFlag == 0)
  416.                                             str2 = new StringBuilder();
  417.  
  418.                                     }
  419.  
  420.                                 }
  421.                             } else {
  422.                                 str2 = new StringBuilder();
  423.                             }
  424.                         }
  425.                     }
  426.                 }
  427.             }
  428.         }
  429.  
  430.     }
  431.  
  432.     /**
  433.      * Contains one.
  434.      *
  435.      * @return true, if successful
  436.      */
  437.     private static boolean containsOne() {
  438.         for (int i = 0; i < mintermsApperancescount.length; i++) {
  439.             if ((mintermsApperancescount[i][1]) == 1)
  440.                 return true;
  441.         }
  442.         return false;
  443.     }
  444.  
  445.     /**
  446.      * Generate combinations.
  447.      *
  448.      * @param element the element
  449.      * @param m the m
  450.      * @param len the len
  451.      */
  452.     private static void generateCombinations(int element, int m, int len) { // (1,0,size)
  453.         if (m == len) {
  454.             if (checkCombination(len)) {
  455.                 foundCombination = true;
  456.                 fillEssentialPrime(len);
  457.                 Arrays.fill(combination, "");
  458.             }
  459.             return;
  460.         }
  461.         if (element == primeImplicants.size() + 1)
  462.             return;
  463.         combination[m] = primeImplicants.get(element - 1);
  464.         generateCombinations(element + 1, m + 1, len);
  465.         generateCombinations(element + 1, m, len);
  466.  
  467.     }
  468.  
  469.     /**
  470.      * Fill essential prime.
  471.      *
  472.      * @param numberOfEssential the number of essential
  473.      */
  474.     private static void fillEssentialPrime(int numberOfEssential) {
  475.         ArrayList<String> essential = new ArrayList<String>();
  476.         for (int i = 0; i < numberOfEssential; i++) {
  477.             System.out.println(combination[i]);
  478.             essential.add(combination[i]);
  479.         }
  480.         for (int i = 0; i < essentialPrimeImplicants.size(); i++)
  481.             System.out.println(essentialPrimeImplicants.get(i));
  482.         System.out.println();
  483.         String expression = find_Expression(essentialPrimeImplicants) + " + " + find_Expression(essential);
  484.         System.out.println(expression);
  485.     }
  486.  
  487.     /**
  488.      * The main method.
  489.      *
  490.      * @param args the arguments
  491.      */
  492.     public static void main(String[] args) {
  493.         System.out.println("Enter the minterms in decimal <-1 to finish>:");
  494.         while (true) {
  495.             int input;
  496.             input = in.nextInt();
  497.             if (input == -1)
  498.                 break;
  499.             minterms.add(input);
  500.         }
  501.         System.out.println("Enter the dontcares in decimal <-1 to finish>:");
  502.         while (true) {
  503.             int input;
  504.             input = in.nextInt();
  505.             if (input == -1)
  506.                 break;
  507.             dontcares.add(input);
  508.         }
  509.         MaxnumberOf_Vars = find_numOfvars();
  510.         fillArrayList();
  511.         decimalToBinary();
  512.         doComparisons();
  513.         count_theAppearnces();
  514.  
  515.         for (int k = 0; k < comparisons.size(); k++) {
  516.             boolean comparisonHasElements = false;
  517.  
  518.             for (int i = 0; i < comparisons.get(k).size(); i++) {
  519.                 if (comparisons.get(k).get(i).isEmpty())
  520.                     continue;
  521.                 for (int j = 0; j < comparisons.get(k).get(i).size(); j++) {
  522.                     System.out.println(comparisons.get(k).get(i).get(j));
  523.                 }
  524.                 comparisonHasElements = true;
  525.                 System.out.println("-----------------");
  526.             }
  527.             if (comparisonHasElements) {
  528.                 System.out.println("______________________________________________________");
  529.                 System.out.println();
  530.             }
  531.         }
  532.         System.out.println("Prime Implicants:");
  533.         for (int i = 0; i < primeImplicants.size(); i++) {
  534.             System.out.println(primeImplicants.get(i));
  535.         }
  536.         System.out.println();
  537.         System.out.println(find_Expression(primeImplicants));
  538.         System.out.println();
  539.         System.out.println();
  540.         System.out.println("Essential Prime Implicants:");
  541.         count_theAppearnces();
  542.         if (containsOne()) {
  543.             thefinal_expression();
  544.             if (!hunt_theRest()) {
  545.                 for (int i = 1; i <= primeImplicants.size() && !foundCombination; i++)
  546.                     generateCombinations(1, 0, i);
  547.             }
  548.             else {
  549.                 for(int i=0; i<essentialPrimeImplicants.size(); i++)
  550.                     System.out.println(essentialPrimeImplicants.get(i));
  551.                 System.out.println(find_Expression(essentialPrimeImplicants));
  552.             }
  553.         }
  554.  
  555.     }
  556. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!