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

interface

uses
    SysUtils;
const
    max_ops = 10000;
type
    tvars = set of 'a'..'k';

const
    notProb: double = 0.3;
    vars = 11;
var
    ops: longint;

function generate(len, vars: longint): longint;
procedure outputRandom(root: longint);
procedure shuffleVariables();
function bEq(op1, op2: longint): longint;
function bImpl(op1, op2: longint): longint;
function bOr(op1, op2: longint): longint;
function bAnd(op1, op2: longint): longint;
function bVar(v: longint): longint;
function bNot(op: longint): longint;

implementation

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

var
    op: array [1..max_ops] of string;
    op1, op2: array [1..max_ops] of longint;
    values: array [-2..max_ops] of boolean;

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

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

function bImpl(op1, op2: longint): longint;
begin
    assert(op1 <> 0);
    assert(op2 <> 0);
    result := add('=>', op1, op2);
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 precendence(op: string): longint;
begin
	if op = '&' then begin
		result := 1;
	end else if op = '|' then begin
		result := 2;
	end else if op = '=>' then begin
		result := 3;
	end else if op = '<=>' then begin
		result := 4;
	end else begin
		result := 0;
	end;
end;

procedure outputNode(root: longint; parentOp: string);
var
    parenthesis: boolean;
begin
    if op[root] = 'v' then begin
        write(chr(ord('a') + op1[root]));
    end else if op[root] = '~' then begin
        write('~');
        outputNode(op1[root], '~');
  	end else begin
		
        parenthesis := precendence(op[root]) > precendence(parentOp);
        if (parenthesis) then write('(');
        outputNode(op1[root], op[root]);
        write(op[root]);
        outputNode(op2[root], op[root]);
        if (parenthesis) then write(')');
	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
        if (op[i] <> 'v') and (op[i] <> '~') then begin
            if (random < 0.5) then begin
                t := op1[i]; op1[i] := op2[i]; op2[i] := t;
            end;
        end;
    end;
end;

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

function expandNode(opTop, opBottom: char; a, b: longint): longint;
begin
    result := add(opBottom, add(opTop, op1[a], b), add(opTop, op2[a], b))
end;

function addFeature(opTop, opBottom: char; root: longint): longint;
var
    v: longint;
begin
    v := random(root) + 1;
    result := add(
        opTop,
        root,
        add(
            opBottom,
            v,
            add('~', v, -1)
        )
    );
end;

function generate(len, vars: longint): longint;
var
    i: longint;
begin
    for i := 0 to vars - 1 do begin
    	bVar(i);
    end;
    for i := 1 to len do begin
        if random < notProb then begin
            bNot(ops);
        end else if (random < 0.5) then begin
        	if (random < 0.5) then begin
            	bAnd(ops, random(ops) + 1);
        	end else begin
        		bOr(ops, random(ops) + 1);
        	end;
    	end else begin
        	if (random < 0.5) then begin
            	bImpl(ops, random(ops) + 1);
        	end else begin
            	bEq(ops, random(ops) + 1);
        	end;
    	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;

begin
    values[bFalse] := false;
    values[bTrue] := true;
end.
