{$q+,r+,o-}
unit tools;

interface

uses
    SysUtils;
const
    max_ops = 10000;

const
    notProb: double = 0.3;
    andProb: double = 0.5;
    expandProb: double = 0.4;
    vars = 26 * 2;

function generateFree(l, r: longint): longint;
function generateSymmFree(l, r: longint): longint; overload;
function generate(len, vars: longint): longint;
procedure output(root: longint);
procedure outputRandom(root: longint);
function expand(root: longint; prob: double): longint;
function addFeatures(root: longint; prob: double): longint;
procedure shuffleVariables();
function buildNF(root: longint): longint; overload;
function bOr(op1, op2: longint): longint;
function bAnd(op1, op2: longint): longint;
function bVar(v: longint): longint;
function bNot(op: longint): longint;
function generateChooser(choose, vars: longint): longint;

implementation

const
    bTrue: longint = -1;
    bFalse: longint = -2;

var
    op: array [1..max_ops] of char;
    op1, op2: array [1..max_ops] of longint;
    ops: longint;

function add(_op: char; _op1, _op2: longint): longint;
begin
    inc(ops);
    op[ops] := _op;
    op1[ops] := _op1;
    op2[ops] := _op2;
    add := ops;
end;

function bOr(op1, op2: longint): longint;
begin
    assert(op1 <> 0);
    assert(op2 <> 0);
    result := add('|', op1, op2);
end;

function bAnd(op1, op2: longint): longint;
begin
    assert(op1 <> 0);
    assert(op2 <> 0);
    result := add('&', op1, op2);
end;

function bVar(v: longint): longint;
begin
    result := add('v', v, 0);
end;

function bNot(op: longint): longint;
begin
    result := add('~', op, 0);
end;

function generateFree(l, r: longint): longint;
var
    m: longint;
begin
    if (random < notProb) then begin
        result := bNot(generateFree(l, r));
    end else if (l = r - 1) then begin
        result := bVar(l);
    end else if (random < andProb) then begin
        m := l + 1 + random(r - l - 2);
        result := bAnd(generateFree(l, m), generateFree(m, r));
    end else begin
        m := l + 1 + random(r - l - 2);
        result := bOr(generateFree(l, m), generateFree(m, r));
    end;
end;

function generateSymmFree(l, r: longint; op: char): longint; overload;
var
    m: longint;
begin
    if (random < notProb) then begin
        if op = '|' then begin
            result := bNot(generateSymmFree(l, r, '&'));
        end else begin
            result := bNot(generateSymmFree(l, r, '|'));
        end;
    end else if (l = r - 1) then begin
        result := bVar(l);
    end else if (op = '|') then begin
        m := (l + r + 1) div 2;
        result := bAnd(generateSymmFree(l, m, '&'), generateSymmFree(m, r, '&'));
    end else begin
        m := (l + r + 1) div 2;
        result := bOr(generateSymmFree(l, m, '|'), generateSymmFree(m, r, '|'));
    end;
end;

function generateSymmFree(l, r: longint): longint;
begin
    if (random < andProb) then begin
        result := generateSymmFree(l, r, '&');
    end else begin
        result := generateSymmFree(l, r, '|');
    end;
end;

procedure outputNode(root: longint; parentOp: char);
var
    parenthesis: boolean;
begin
    if (root = bTrue) then begin
        write('1');
        exit;
    end;
    if (root = bFalse) then begin
        write('0');
        exit;
    end;
    case op[root] of
        '&', '|':
            begin
                parenthesis :=
                    (op[root] = '|') and not (parentOp = '|') or
                    (op[root] = '&') and not (parentOp in ['|', '&']);
                if (parenthesis) then write('(');
                outputNode(op1[root], op[root]);
                write(op[root]);
                outputNode(op2[root], op[root]);
                if (parenthesis) then write(')');
            end;
        '~':
            begin
                write('~');
                outputNode(op1[root], '~');
            end;
        'v': begin
                if op1[root] < 26 then begin
                    write(chr(ord('a') + op1[root]));
                end else begin
                    write(chr(ord('A') + op1[root] - 26));
                end;
            end
        else
            writeln('Unknown op');
    end;
end;

procedure output(root: longint);
begin
    outputNode(root, '|');
    writeln;
end;

procedure shuffleVariables();
var
    i: longint;
    t: longint;
    nvars: array [0..vars - 1] of longint;
begin
    for i := 0 to vars - 1 do begin
        t := random(i + 1);
        nvars[i] := nvars[t];
        nvars[t] := i;
    end;
    for i := 1 to ops do begin
        if op[i] = 'v' then begin
          op1[i] := nvars[op1[i]];
        end;
    end;
end;

procedure shuffleTree();
var
    i: longint;
    t: longint;
begin
    for i := 1 to ops do begin
        case op[i] of
            '&', '|':
                begin
                    if (random < 0.5) then begin
                        t := op1[i]; op1[i] := op2[i]; op2[i] := t;
                    end;
                end;
        end;
    end;
end;

procedure outputRandom(root: longint);
begin
    shuffleVariables();
    shuffleTree();
    output(root);
end;

function addFeatures(root: longint; prob: double): longint;
begin
    addFeatures := root;
end;

function expand(root: longint; prob: double): longint;
begin
    expand := root;
end;

function generate(len, vars: longint): longint;
var
    i: longint;
begin
    for i := 0 to vars - 1 do begin
        if (random < andProb) then begin
            bAnd(ops, bVar(i));
        end else begin
            bOr(ops, bVar(i));
        end;
    end;
    for i := 1 to len do begin
        if random < notProb then begin
            bNot(ops);
        end else if random < andProb then begin
            bAnd(ops, random(ops) + 1);
        end else begin
            bOr(ops, random(ops) + 1);
        end;
    end;
    result := ops;
end;
                 
function generateChooser(choose, vars: longint): longint;
var
    i, c, j: longint;
    z: longint;
begin
    result := bFalse;
    for i := 0 to (1 shl vars) - 1 do begin
        c := 0;
        for j := 0 to vars - 1 do begin
            if ((i shr j) and 1) <> 0 then inc(c);
        end;
        if (c = choose) then begin
            z := bTrue;
            for j := 0 to vars - 1 do begin
                if ((i shr j) and 1) <> 0 then begin
                    z := bAnd(z, bVar(j));
                end;
            end;
            result := bOr(result, z);
        end;
    end;
end;

function buildNF(root: longint): longint; overload;
begin
    buildNF := root;
end;

end.
