Project: Optimal Circuit Synthesis with SAT · Searching Small Circuits

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

In this step you are asked not only to find the minimum circuit size, but also to output the circuit itself.

Programming problem. Construct a minimum-size circuit for a Boolean function of at most three variables.

Input format. The first line contains \(n\) (\(1\le n\le3\)). The second line contains a binary string of length \(2^{n}\), the target truth table.

Output format. First print the number of gates \(m\). Then print \(m\) gate lines, each containing predecessor indices \(a_{i},b_{i}\) and a four-bit operation string. Gate \(i\) has source index \(n+i\), so both predecessors must be smaller than \(n+i\). Finally, print one source index: the circuit output.

This problem can only be submitted at Cogniterra.
Public samples
Public sample 1
Input
1
01
Example output
0
0
Public sample 2
Input
2
0110
Example output
1
0 1 0110
2
Public sample 3
Input
3
00010111
Example output
4
0 1 0001
0 1 0111
2 4 0001
3 5 0111
6