nand-nor-minimizer

nand-nor-minimizer.cc

/**
 * nand-nor-minimizer by Mygod.
 *
 * Test samples:
 * 1000000000000000 NOR(A, B, C, D)
 * 1111111111111110 NAND(A, B, C, D)
 * 0000000000001110
 * 1110111011101111
 * 0110011011100000 My stupid assignment
 * 0010011101110100 A random test sample
 * 0010110000100001 Another random test sample (sloooow)
 * 0110100101101001 4-variable XOR (super slooooow)
 */

#include <bitset>
#include <iostream>
#define MAX 28

using namespace std;

int use[MAX];
bool nand[MAX];
int top;
bool correct[16];

bool go(int n, int start, int mask) {
  int diff = top - n;
  int upper = 1 << 4 + n;
  if (diff == 1 && start < 1 << 3 + n) start = 1 << 3 + n;
  for (use[n] = start; use[n] < upper; ++use[n]) {
    int newMask = mask & ~use[n];
    if (diff > 1) {
      if (diff > 4) cerr << n << ": " << use[n] << '/' << upper << endl;  // for showing progress
      nand[n] = false;
      if (go(n + 1, use[n] + 1, newMask)) return true;
      if (use[n] & use[n] - 1) {
        nand[n] = true;
        if (go(n + 1, use[n] + 1, newMask)) return true;
      }
    } else if (!newMask) {
      for (int state = 0; state < 16; ++state) {
        int j = state;
        for (int i = 0; i < top; ++i) if (nand[i] ? (use[i] & j) != use[i] : !(use[i] & j)) j |= 1 << 4 + i;
        if (correct[state] == !(j & 1 << 3 + top)) return false;
      }
      cerr << "Solution found!" << endl;
      for (int i = 0; i < top; ++i) cout << (nand[i] ? "NAND" : "NOR ") << static_cast<bitset<32>>(use[i]) << endl;
      return true;
    }
  }
  return false;
}

int main(int argc, char **argv) {
  int i = 1;
  while (i < argc) {
    int j = 0;
    char *c = argv[i];
    while (j < 16) {
      if (*c == '0') correct[j] = false; else if (*c == '1') correct[j] = true; else break;
      ++j;
      ++c;
    }
    if (j >= 16) break;
    ++i;
  }
  if (i >= argc) cout << "Usage: nand-nor-minimizer [16-bit boolean truth table]" << endl << endl
        << "Example:" << endl << "  nand-nor-minimizer 0110100101101001" << endl;
  else for (top = 1; top <= MAX; ++top) {
    cerr << "Testing " << top << " NAND/NOR gates..." << endl;
    if (go(0, 1, (1 << 3 + top) - 1)) break;
    if (top == 1) {
      nand[0] = true;
      if (go(0, 1, 15)) break;
    }
  }
  return 0;
}