o2SubsetSum

MODULE PowerSet;

IMPORT Out, Bit;

TYPE
    NodePtr- = POINTER TO Node;
    Node- = RECORD
        num- : INTEGER;
        prev- : NodePtr;
    END;
    ListPtr- = POINTER TO ListType;
    ListType- = RECORD
        last- : NodePtr;
    END;
    SubsetsType- = POINTER TO ARRAY OF ListPtr;

PROCEDURE AddNode(VAR l : ListPtr; nn : NodePtr);
BEGIN
    ASSERT(nn # NIL);
    IF l.last = NIL THEN l.last := nn;
    ELSE nn.prev := l.last; l.last := nn;
    END;
END AddNode;

PROCEDURE PowerSetForArray*(VAR ai : ARRAY OF INTEGER) : SubsetsType;
VAR subsetCount : INTEGER;
    subsetIndex, itemIndex : INTEGER;
    subsets : SubsetsType;
    subset : ListPtr;
    node : NodePtr;
BEGIN
    subsetCount := ASH(1, LEN(ai));
    subsetIndex := 0;
    NEW(subsets, subsetCount);
    WHILE subsetIndex < subsetCount DO
        NEW(subset);
        subset.last := NIL;
        FOR itemIndex := 0 TO LEN(ai) - 1 DO
            IF (Bit.And(ASH(subsetIndex, -itemIndex), 1) > 0) THEN
                NEW(node);
                node.num := ai[itemIndex];
                AddNode(subset, node);
            END;
        END;
        subsets[subsetIndex] := subset;
        INC(subsetIndex);
    END;
    RETURN subsets;
END PowerSetForArray;

PROCEDURE PrintSubsets*(s : SubsetsType);
VAR i, l : INTEGER;
    lp : ListPtr;
    np : NodePtr;
BEGIN
    ASSERT(s # NIL);
    l := LEN(s^);
    FOR i := 0 TO l - 1 DO
        lp := s[i];
        ASSERT(lp # NIL);
        np := lp.last;
        WHILE(np # NIL) DO
            Out.Int(np.num,0); Out.String(" ");
            np := np.prev;
        END;
        Out.Ln;
    END;
    Out.Ln;
END PrintSubsets;

BEGIN
END PowerSet.

(* ---------- CUT HERE ---------- *)

MODULE SubsetSum;

IMPORT PowerSet, Out;

PROCEDURE PrintArr(a : ARRAY OF INTEGER);
VAR i  :INTEGER;
BEGIN
  Out.String("[");
  FOR i := 0 TO LEN(a) - 1 DO
    Out.LongInt(a[i], 0);
    IF i < LEN(a) - 1 THEN Out.String(", "); END;
  END;
  Out.String("]");
END PrintArr;

PROCEDURE PrintBool(b : BOOLEAN);
BEGIN
  IF b THEN Out.String("TRUE"); ELSE Out.String("FALSE"); END;
END PrintBool;

PROCEDURE Check(a : ARRAY OF INTEGER) : BOOLEAN;
VAR i, j : INTEGER;
BEGIN
  FOR i := 0 TO LEN(a) - 2 DO
    FOR j := i + 1 TO LEN(a) - 1 DO
      IF (a[i] = 0) OR (a[j] = 0) THEN RETURN TRUE; END;
      IF (a[i] + a[j]) = 0 THEN RETURN TRUE; END;
    END;
  END;
  RETURN FALSE;
END Check;

PROCEDURE CheckAllSubsets(a : ARRAY OF INTEGER) : BOOLEAN;
VAR subsets : PowerSet.SubsetsType;
    i, l : INTEGER;
    lp : PowerSet.ListPtr;
    np : PowerSet.NodePtr;
    res : LONGINT;
    isZero : BOOLEAN;
BEGIN
  subsets := PowerSet.PowerSetForArray(a);
  ASSERT(subsets # NIL);
  l := LEN(subsets^);
  i := 0;
  isZero := FALSE;
  WHILE (i < l) & (isZero = FALSE) DO
    lp := subsets[i]; (* array of lists *)
    ASSERT(lp # NIL);
    np := lp.last; (* end node of list *)
    IF np # NIL THEN
      res := 0;
      WHILE (np # NIL)  & (isZero = FALSE) DO
        IF np.num = 0 THEN isZero := TRUE; END;
        res := res + np.num;
        np := np.prev;
      END;
      IF res = 0 THEN isZero := TRUE; END;
    END;
    INC(i);
  END;
  subsets := NIL;
  RETURN isZero;
END CheckAllSubsets;

PROCEDURE PerformSingleTest(a : ARRAY OF INTEGER; allSubs : BOOLEAN);
VAR res : BOOLEAN;
BEGIN
  res := FALSE;
  IF allSubs THEN res := CheckAllSubsets(a);
  ELSE res := Check(a);
  END;
  PrintArr(a);
  Out.String(" => ");
  PrintBool(res);
  Out.Ln;
END PerformSingleTest;

PROCEDURE Test();
VAR a0 : ARRAY 0 OF INTEGER;
    a1 : ARRAY 1 OF INTEGER;
    a2 : ARRAY 2 OF INTEGER;
    a3 : ARRAY 3 OF INTEGER;
    a6 : ARRAY 6 OF INTEGER;
    a10 : ARRAY 10 OF INTEGER;
    a18 : ARRAY 18 OF INTEGER;
BEGIN
  a3[0] := 1; a3[1] := 2; a3[2] := 3;
  PerformSingleTest(a3, FALSE);

  a6[0] := -5; a6[1] := 2; a6[2] := -1; a6[3] := 2; a6[4] := 4; a6[5] := 6;
  PerformSingleTest(a6, FALSE);

  PerformSingleTest(a0, FALSE);

  a2[0] := -1; a2[1] := 1;
  PerformSingleTest(a2, FALSE);

  a6[0] := -97364; a6[1] := -71561; a6[2] := -69336; a6[3] := 19675;
  a6[4] := 71561; a6[5] := 97863;
  PerformSingleTest(a6, FALSE);

  a6[0] := -53974; a6[1] := -39140; a6[2] := -36561; a6[3] := -23935;
  a6[4] := -15680; a6[5] := 0;
  PerformSingleTest(a6, FALSE);

  (* CheckBonus *)
  a1[0] := 0;
  PerformSingleTest(a1, TRUE);

  a3[0] := -3; a3[1] := 1; a3[2] := 2;
  PerformSingleTest(a3, TRUE);

  a10[0] := -98634; a10[1] := -86888; a10[2] := -48841; a10[3] := -40483;
  a10[4] := 2612; a10[5] := 9225; a10[6] := 17848; a10[7] := 71967;
  a10[8] := 84319; a10[9] := 88875;
  PerformSingleTest(a10, TRUE);

  (* FALSE *)
  a18[0] := -83314; a18[1] := -82838; a18[2] := -80120; a18[3] := -63468;
  a18[4] := -62478; a18[5] := -59378; a18[6] := -56958; a18[7] := -50061;
  a18[8] := -34791; a18[9] := -32264; a18[10] := -21928; a18[11] := -14988;
  a18[12] := 23767; a18[13] := 24417; a18[14] := 26403; a18[15] := 26511;
  a18[16] := 36399; a18[17] := 78055;
  PerformSingleTest(a18, TRUE);

  a18[0] := -92953; a18[1] := -91613; a18[2] := -89733; a18[3] := -50673;
  a18[4] := -16067; a18[5] := -9172; a18[6] := 8852; a18[7] := 30883;
  a18[8] := 46690; a18[9] := 46968; a18[10] := 56772; a18[11] := 58703;
  a18[12] := 59150; a18[13] := 78476; a18[14] := 84413; a18[15] := 90106;
  a18[16] := 94777; a18[17] := 95148;
  PerformSingleTest(a18, TRUE);

  (* TRUE *)
  a18[0] := -97162; a18[1] := -95761; a18[2] := -94672; a18[3] := -87254;
  a18[4] := -57207; a18[5] := -22163; a18[6] := -20207; a18[7] := -1753;
  a18[8] := 11646; a18[9] := 13652; a18[10] := 14572; a18[11] := 30580;
  a18[12] := 52502; a18[13] := 64282; a18[14] := 74896; a18[15] := 83730;
  a18[16] := 89889; a18[17] := 92200;
  PerformSingleTest(a18, TRUE);

  (* TRUE *)
  a18[0] := -93976; a18[1] := -93807; a18[2] := -64604; a18[3] := -59939;
  a18[4] := -44394; a18[5] := -36454; a18[6] := -34635; a18[7] := -16483;
  a18[8] := 267; a18[9] := 3245; a18[10] := 8031; a18[11] := 10622;
  a18[12] := 44815; a18[13] := 46829; a18[14] := 61689; a18[15] := 65756;
  a18[16] := 69220; a18[17] := 70121;
  PerformSingleTest(a18, TRUE);
END Test;

BEGIN
  Test;
END SubsetSum.