Quine-McCluskey algorithm

qm.d

// (a & b) + (¬a & c) → [[T,T,X],[N,X,T]]
enum Literal
{
    T, // Term
    N, // ¬Term
    X // Null
}

alias Conjunction = Literal[];
alias DNF = Conjunction[]; // Disjunctive normal form

DNF[] qm(DNF dnfin, size_t[] dontcare)
{

    import std.algorithm : sort, uniq, any, fold, equal, filter, map, sum;
    import std.range : array, iota, back, popBack, zip, empty;

    size_t size = dnfin[0].length;

    struct TaggedConjunction
    {
        bool flag;
        size_t[] mergedfrom;
        Conjunction conjunction;
    }

    TaggedConjunction[] merged;
    TaggedConjunction[] prime;

    foreach (i, c; dnfin)
        merged ~= TaggedConjunction(false, [i], c);

    do
    {
        auto table = new TaggedConjunction[][](size + 1);
        foreach (c; merged)
            table[hammingWeight(c.conjunction)] ~= c;

        merged = [];

        foreach (i; 0 .. size)
            foreach (ref c1; table[i])
                foreach (ref c2; table[i + 1])
                    if (hammingDistance(c1.conjunction, c2.conjunction) == 1)
                    {
                        auto mergedfrom = (c1.mergedfrom ~ c2.mergedfrom).sort.uniq.array();
                        auto mergedconjunction = merge(c1.conjunction, c2.conjunction);
                        merged ~= TaggedConjunction(false, mergedfrom, mergedconjunction);

                        c1.flag = true;
                        c2.flag = true;
                    }

        foreach (t; table)
            foreach (c; t)
                if (c.flag == false && !any!(x => x == c)(prime))
                    prime ~= c;
    }
    while (merged != []);

    size_t min = size_t.max;
    DNF[] result;
    bool[] stack = [false];

    while (true)
    {
        if (stack.length < prime.length)
        {
            stack ~= false;
        }
        else
        {
            bool isCovered = zip(stack, prime).map!(x => (x[0]) ? x[1].mergedfrom : [])
                .fold!((a, b) => a ~ b)
                .sort
                .uniq
                .filter!(n => !any!(d => d == n)(dontcare))
                .equal(iota(0, dnfin.length).filter!(n => !any!(d => d == n)(dontcare)));
            if (isCovered)
            {
                auto tmp = zip(stack, prime).filter!(x => x[0])
                    .map!(x => x[1].conjunction)
                    .array;
                size_t s = tmp.fold!((a, b) => a ~ b)
                    .map!(l => (l != Literal.X) ? 1 : 0)
                    .sum();
                if (s < min)
                {
                    min = s;
                    result = [tmp];
                }
                else if (s == min)
                {
                    result ~= tmp;
                }
            }

            while (!stack.empty && stack.back)
                stack.popBack();
            if (stack.empty)
                return result;
            stack.popBack();
            stack ~= true;
        }
    }
}

unittest
{
    // https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AF%E3%82%A4%E3%83%B3%E3%83%BB%E3%83%9E%E3%82%AF%E3%83%A9%E3%82%B9%E3%82%AD%E3%83%BC%E6%B3%95
    DNF input = () {
        with (Literal)
            return [// dfmt off
                [N, T, N, N],
                [T, N, N, N],
                [T, N, N, T],// Don't care
                [T, N, T, N],
                [T, T, N, N],
                [T, N, T, T],
                [T, T, T, N],// Don't care
                [T, T, T, T]
            ];
            // dfmt on
    }();
    DNF[] output = () {
        with (Literal)
            return // dfmt off
            [
                [[X, T, N, N], [T, X, X, N], [T, X, T, X]], // B¬C¬D + A¬D + AC
                [[X, T, N, N], [T, N, X, X], [T, X, T, X]] // B¬C¬D + A¬B + AC
            ];
            // dfmt on
    }();
    assert(qm(input, [2, 6]) == output);
}

size_t hammingWeight(Conjunction a)
{
    import std.algorithm : filter, map, sum;

    return a.filter!(x => x == Literal.T)
        .map!(x => 1)
        .sum;
}

unittest
{
    with (Literal)
    {
        assert(hammingWeight([N, N, N]) == 0);
        assert(hammingWeight([N, N, T]) == 1);
        assert(hammingWeight([T, T, T]) == 3);
        assert(hammingWeight([X, N, T]) == 1);
    }
}

size_t hammingDistance(Conjunction a, Conjunction b)
{
    import std.algorithm : filter, map, sum;
    import std.range : zip;

    return zip(a, b).filter!(t => t[0] != t[1])
        .map!(x => 1)
        .sum;
}

unittest
{
    with (Literal)
    {
        assert(hammingDistance([T, T, T], [T, T, T]) == 0);
        assert(hammingDistance([N, N, N], [N, N, T]) == 1);
        assert(hammingDistance([T, N, T], [N, T, N]) == 3);
        assert(hammingDistance([T, N, X], [T, X, T]) == 2);
    }
}

Conjunction merge(Conjunction a, Conjunction b)
{
    assert(hammingDistance(a, b) == 1);
    auto result = new Conjunction(a.length);
    foreach (i, ref l; result)
        if (a[i] == b[i])
        {
            l = a[i];
        }
        else
        {
            l = Literal.X;
        }
    return result;
}

unittest
{
    with (Literal)
    {
        assert(merge([T, T, T], [T, T, N]) == [T, T, X]);
        assert(merge([N, X, N], [N, X, T]) == [N, X, X]);
    }
}