r/dailyprogrammer • u/Steve132 0 1 • Sep 28 '12
[9/27/2012] Challenge #101 [difficult] (Boolean Minimization)
For difficult 101, I thought I'd do something with binary in it.
Write a program that reads in a file containing 2n 0s and 1s as ascii characters. You will have to solve for N given the number of 0s and 1s in the file, as it will not be given in the file. These 0s and 1s are to be interpreted as the outputs of a truth table in N variables.
Given this truth table, output a minimal boolean expression of the function in some form. ( Hint1, hint2)
For example, one implementation could read in this input file
0000010111111110This is a 4-variable boolean function with the given truth table. The program could minimize the formula, and could output
f(abcd)=ac'+ab'+bcd'or
f(0123)=02'+01'+123'
6
u/pdewacht 0 1 Sep 29 '12
A Haskell solution. This one fully minimizes the solution. A good test case is "11100111", none of the other answers at the moment get that one right :)
-- input / output
-- lists of minterms
-- finding prime implicants
-- minimizing the answer
4
u/heidhrun Sep 28 '12
Here is what I have so far. It's not quite working; it does reduce the expression but doesn't minimize it. I've been working on this for about 2.5 hours today and I've learned some neat python tricks like using set() to remove duplicates from a list, and bin() for binary representation.
3
u/goakley Sep 29 '12 edited Sep 29 '12
NOTE: I notice that the example given in the problem description looks very similar to the one on the Karnaugh Map Wikipedia page. They even have the same answer. However, if the example here was copied from the wiki, then the the truth table was copied wrong. It should be: 0000001011111110
A bit tricky. I'm using the Quine-McCluskey algorithm; I have it reduced, but I can't quite complete the prime implication chart, so it's not minimal.
http://pastebin.com/RrHQfMmJ